Prev: Richard Heathfield's lie
Next: Richard Heathfield: liar
From: Lie Ryan on 24 Dec 2009 15:02
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
"""

What I wrote works fine:

in pseudocode:

create an empty array [result]
for each number in [nums] loop-counter: `index`
if number is 4
set result[`index`] <- nums[`index`] // always == 4
advance `first unused 5` to the next 5
`index` += 1
set result[`index`] <- nums[`first unused 5`] // always == 5
else
advance `other items` to something not 4 or 5
set result[`index`] <- nums[`other items`]
return the [result]

or in Java:

public int[] fix45(int[] nums) {
int five = 0, others = 0;
int[] result = new int[nums.length];

for (int i = 0; i < nums.length; i++) {
if (nums[i] == 4) {
result[i] = nums[i];
while (five < nums.length && nums[five] != 5) { five++; }
result[++i] = nums[five];
} else {
while (others < nums.length
&& (nums[others] == 5
|| nums[others] == 4
)
) { others++; }
result[i] = nums[others];
}
}
return result;
}

but this algorithm creates a second array [results]. I want to find an
algorithm that mutates on [nums] instead by swapping things around and
only do one pass on the array. You may notice that my algorithm
unnecessarily gets value from the array when it is known that the value
is a 5 or 4; but I want to make the algorithm as general as possible and
not assume that it's working on an int (i.e. I can't create a new "5"s
or "4"s) and I don't want to assume that the "other uninteresting
numbers" are all the same.

Is it possible to do so? If it's impossible, do you know of a way to
"prove" it is impossible?

PS: I'm rather misusing the term "constant-space" here, I think since
doubling the space is actually "constant-space"; but you get the point...
From: Mike Sieweke on 24 Dec 2009 15:27
Lie Ryan 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
> """

8< snipped 8<

> but this algorithm creates a second array [results]. I want to find an
> algorithm that mutates on [nums] instead by swapping things around and
> only do one pass on the array. You may notice that my algorithm
> unnecessarily gets value from the array when it is known that the value
> is a 5 or 4; but I want to make the algorithm as general as possible and
> not assume that it's working on an int (i.e. I can't create a new "5"s
> or "4"s) and I don't want to assume that the "other uninteresting
> numbers" are all the same.
>
> Is it possible to do so? If it's impossible, do you know of a way to
> "prove" it is impossible?
>
> PS: I'm rather misusing the term "constant-space" here, I think since
> doubling the space is actually "constant-space"; but you get the point...

Yes, it is possible. Here is a hint: Do you know how a one-pass
assembler resolves forward branches?

--
Mike Sieweke
From: Richard Harter on 24 Dec 2009 15:31
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.



Richard Harter, cri(a)tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Infinity is one of those things that keep philosophers busy when they
could be more profitably spending their time weeding their garden.
From: bartc on 24 Dec 2009 17:06

"Richard Harter" <cri(a)tiac.net> wrote in message
news:4b33cd3f.236163500(a)text.giganews.com...
> 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.

>Start by finding the first 4 and then find the first 5. Swap the
>first 5. Thereafter search for the next 4 after swapping a 5.
>When you find a 4, search for the next 5 and swap it. When you
>run out of 4's you are done.

The OP said he wanted to do it in one pass (as well as in constant-space):

>> 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...)

--
Bartc

From: Lie Ryan on 24 Dec 2009 17:34
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;
}

specifically the naive attempt doesn't pass these:

* unittest * * result *
fix45({5, 4, 9, 4, 9, 5}) → {9, 4, 5, 4, 5, 9} {9, 4, 9, 4, 5, 5}
fix45({4, 5, 4, 1, 5}) → {4, 5, 4, 5, 1} {4, 1, 4, 5, 5}


Adding the "in-place restriction" is what makes it extremely difficult;
in the website I mentioned the online unittest uncovers many subtleties
that you won't think of until you tried it yourself. I already have
quite a few versions that either doesn't pass all the tests or
"cheats"[1] or doesn't work in-place.

[1] by making assumptions that aren't specified in the problem description
 |  Next  |  Last
Pages: 1 2 3
Prev: Richard Heathfield's lie
Next: Richard Heathfield: liar