Prev: Richard Heathfield's lie
Next: Richard Heathfield: liar
From: Lie Ryan on 24 Dec 2009 17:53
On 12/25/2009 9:06 AM, bartc wrote:
>>> I want to find an
>>> algorithm that mutates on [nums] instead by swapping things around and
>>> only do one pass on the array.
>
> It sounds to me like maintaining two separate indices (one of the next 4,
> the other of the next 5) and stepping them separately would be two distinct
> passes. (For example, if you first stepped through all the 4's, and then
> stepped through all the 5's...)

Actually I didn't think about one-pass in that respect, I consider two
separate indices as still one-pass. When I said one-pass I mean 1)
indices can only go forward; 2) indices cannot reset to 0; and 3) each
indices is used only to find one "thing". Where a "thing" may be
"fours", "fives", or "others". So I'd still consider a solution with 3
indices as elegant enough.

btw, these approaches are what I've tried (codes missing since I didn't
keep them around):
- (does not pass) make an index of "fours", "fives", and "others" and
swap them around based on this index. problem: subtleties arises when
swapping two fives
- (cheat) find the value of "others" (i.e. the number that isn't fours
and fives), and simply overwrite every values not preceeded by 4 with
this value. problem: makes an assumption that all "others" have the same
value
- (irrelevant) separate the `nums` into two stacks of items and pop them
accordingly. problem: can't find a way to ensure the 4s does not move
From: Patricia Shanahan on 24 Dec 2009 18:23
Lie Ryan wrote:
> On 12/25/2009 7:31 AM, Richard Harter wrote:
>> On Fri, 25 Dec 2009 07:02:39 +1100, Lie Ryan<lie.1296(a)gmail.com>
>> wrote:
>>
>>> The problem description:
>>>
>>> """
>>> Return an array that contains exactly the same numbers as the given
>>> array, but rearranged so that every 4 is immediately followed by a 5. Do
>>> not move the 4's, but every other number may move. The array contains
>>> the same number of 4's and 5's, and every 4 has a number after it that
>>> is not a 4. In this version, 5's may appear anywhere in the original
>>> array.
>>> http://www.javabat.com/prob/p125819
>>> """
>>
>>
>> Big Juicy Hint: Use two pointers, one for 4's and one for 5's.
>>
>> Try to work it out for yourself.
>>
>> Solution: (rot 13)
>>
>> Fgneg ol svaqvat gur svefg 4 naq gura svaq gur svefg 5. Fjnc gur
>> svefg 5. Gurernsgre frnepu sbe gur arkg 4 nsgre fjnccvat n 5.
>> Jura lbh svaq n 4, frnepu sbe gur arkg 5 naq fjnc vg. Jura lbh
>> eha bhg bs 4'f lbh ner qbar.
>>
>> It's a cute puzzle. There is a general programming trick of the
>> trade here. When scanning data it can pay to use multiple
>> pointers.
>
> Sorry mate, it's not that easy (you didn't think I haven't tried that
> approach before, did you?). That only solves the slightly easier version
> fix34 but not this fix45:
>
> public int[] fix45(int[] nums) {
> int five = 0;
> int four = 0;
> for (; four < nums.length; four++) {
> if (nums[four] == 4) {
> for (; five < nums.length && nums[five] != 5; five++);
> swap(nums, four + 1, five);
> }
> }
> return nums;
> }
>
> public void swap(int[] nums, int a, int b) {
> int tmp = nums[a];
> nums[a] = nums[b];
> nums[b] = tmp;
> }
....

I thought of a two-index solution, but did not post because Richard
Harter had already suggested the general idea.

The key invariant I see here is that each swap should exchange the first
five that does not immediately follow a four with the first non-five
that does immediately follow a four. If you have a four-five pair,
either because it appeared in the original data or created by a previous
swap, the five is not eligible for swapping.

You appear to be swapping the next four-follower with the next five,
regardless of whether either of them is part of a four-five pair.

Patricia
From: Lie Ryan on 24 Dec 2009 18:33
On 12/25/2009 7:27 AM, Mike Sieweke wrote:
> Yes, it is possible. Here is a hint: Do you know how a one-pass
> assembler resolves forward branches?

Actually I don't. Look-ahead? Marking it unfinished?
From: Lie Ryan on 24 Dec 2009 19:07
On 12/25/2009 10:23 AM, Patricia Shanahan wrote:
> I thought of a two-index solution, but did not post because Richard
> Harter had already suggested the general idea.
>
> The key invariant I see here is that each swap should exchange the first
> five that does not immediately follow a four with the first non-five
> that does immediately follow a four. If you have a four-five pair,
> either because it appeared in the original data or created by a previous
> swap, the five is not eligible for swapping.

That doesn't work either:

public int[] fix45(int[] nums) {
int five = 0;
int four = 0;
for (; four < nums.length; four++) {
if (nums[four] == 4) {
for (; five < nums.length
&& nums[five] != 5
|| 1 < five && five < nums.length - 2
&& nums[five - 1] == 4; five++);
swap(nums, four + 1, five);
}
}
return nums;
}

can't find an easy way to pass this test:
* unittest * * result from above *
fix45({4, 5, 4, 1, 5}) → {4, 5, 4, 5, 1} {4, 1, 4, 5, 5}

without doing another pass

> You appear to be swapping the next four-follower with the next five,
> regardless of whether either of them is part of a four-five pair.

when I posted the code, I mean I've tried various variations on that
general approach, not just that exact code.
From: Patricia Shanahan on 24 Dec 2009 19:18
Lie Ryan wrote:
> On 12/25/2009 10:23 AM, Patricia Shanahan wrote:
>> I thought of a two-index solution, but did not post because Richard
>> Harter had already suggested the general idea.
>>
>> The key invariant I see here is that each swap should exchange the first
>> five that does not immediately follow a four with the first non-five
>> that does immediately follow a four. If you have a four-five pair,
>> either because it appeared in the original data or created by a previous
>> swap, the five is not eligible for swapping.
>
> That doesn't work either:
>
> public int[] fix45(int[] nums) {
> int five = 0;
> int four = 0;
> for (; four < nums.length; four++) {
> if (nums[four] == 4) {

You need to check whether this four is part of an existing four-five
pair, in which case the five must not be swapped.

> for (; five < nums.length
> && nums[five] != 5
> || 1 < five && five < nums.length - 2
> && nums[five - 1] == 4; five++);
> swap(nums, four + 1, five);
> }
> }
> return nums;
> }

Patricia
First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: Richard Heathfield's lie
Next: Richard Heathfield: liar