Finding a constant-space algorithm
Lie Ryan
"""
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...
Mike Sieweke
> 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
Richard Harter
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, c...@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.
bartc
"Richard Harter" <c...@tiac.net> wrote in message
news:4b33cd3f....@text.giganews.com...
> On Fri, 25 Dec 2009 07:02:39 +1100, Lie Ryan <lie....@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
Lie Ryan
> On Fri, 25 Dec 2009 07:02:39 +1100, Lie Ryan<lie....@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
Lie Ryan
>>> 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
Patricia Shanahan
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
Lie Ryan
> 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?
Lie Ryan
> 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.
Patricia Shanahan
> 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
Patricia Shanahan
Here's a working version of the two index idea:
public int[] fix45(int[] nums) {
int five = 0;
for (int four = 0; four < nums.length; four++) {
if (nums[four] == 4 && nums[four+1] != 5) {
/* Swap needed, find the first suitable 5 */
boolean found = false;
while (!found){
if (five >= nums.length){
/* Swap is needed, but no free 5 remaining.*/
throw new IllegalArgumentException
("Incorrectly formed array");
}
if(nums[five] == 5){
/* Got a possible. Check it out.*/
if(five == 0 || nums[five-1] != 4){
/* It's a good five, not preceded by a 4.*/
found = true;
}
}
if(!found){
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;
}
Obviously, we have very different Java coding styles. I find it easier
to get a complicated multi-faceted condition right if I split it up
into a series of simple questions that I can deal with one at a time.
Patricia
Lie Ryan
> 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.
That's it. I can't believe I stumped on that because I thought I should
not need to check the fours as well. Thanks.
Mike Sieweke
Lie Ryan <lie....@gmail.com> wrote:
Make a linked list of the forward references. Since RAM
was limited in early days, the linked list was constructed
inside the generated code. (*)
After a forward definition is found, the linked list of
references is traversed so each instruction can be fixed
up with the final destination.
(*) Usually the object code for each function was kept in
RAM until the function's end is found, although it would
be possible to fix up the output file. References between
functions are resolved by the linker.
Here's how it would look in my language. It tests each
array element once in the forward pass. It reads and
writes each 4 and 5 location again when it puts the
numbers in place.
shuffle : function( a : in out array [1..max_a] of integer ) is
last4 : integer := 0
last5 : integer := 0
temp : integer
i : integer
-- Pass through the array, making linked lists where
-- 4s and 5s were.
for i := 1 to max_a do
if a[i] = 4 then
-- Ignore numbers that are already in place,
-- because they complicate the fixup loop.
if a[i+1] <> 5 then
a[i] := last4
last4 := i
end if
-- Skip the following element, since we already
-- know if it's a 5.
i := i + 1
iterate i
elsif a[i] = 5 then
a[i] := last5
last5 := i
end if
end for
-- Replace the linked list pointers with the appropriate
-- values.
while last5 <> 0 do
-- Move the value following the current 4 to the
-- location of the current 5.
temp := last5
last5 := a[temp]
a[temp] := a[last4+1]
-- Put a 4 and a 5 in the current spot.
temp := last4
last4 := a[temp]
a[temp] := 4
a[temp+1] := 5
end while
end shuffle
--
Mike Sieweke
Moi
> In article <4b33fa57$1...@dnews.tpgi.com.au>,
> Lie Ryan <lie....@gmail.com> wrote:
>
>> 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?
>
> Make a linked list of the forward references. Since RAM was limited in
> early days, the linked list was constructed inside the generated code.
> (*)
>
> After a forward definition is found, the linked list of references is
> traversed so each instruction can be fixed up with the final
> destination.
>
>
> (*) Usually the object code for each function was kept in RAM until the
> function's end is found, although it would be possible to fix up the
> output file. References between functions are resolved by the linker.
>
>
> Here's how it would look in my language. It tests each array element
> once in the forward pass. It reads and writes each 4 and 5 location
> again when it puts the numbers in place.
It can be done with one linked list, since it is impossible that *both*
unmatched 4s and unmatched 5s exist at the same time.
****/
#include <stdio.h>
unsigned array1[] = {5, 4, 9, 4, 9, 5} ;
unsigned array2[] = {4, 1, 4, 1, 1, 5, 5};
unsigned array[] = {5, 5, 1, 1, 4, 1, 4, 6};
#define COUNTOF(a) (sizeof(a) / sizeof (a)[0])
int flip45( unsigned *arr, unsigned count);
int main()
{
unsigned idx;
int ret;
for (idx=0; idx < COUNTOF(array); idx++) {
fprintf( stdout, " %u", array[idx] );
}
fprintf( stdout, ".\n" );
ret = flip45(array, COUNTOF(array) );
for (idx=0; idx < COUNTOF(array); idx++) {
fprintf( stdout, " %u", array[idx] );
}
fprintf( stdout, " = %d\n", ret );
return 0;
}
/* 'debt' is the number of unpaired 4's we still have to satisfy.
* or (when negative), the number of unpaired 5s.
* We need only one linked list, which is either for fours, or for fives,
* depending on the sign of 'debt'.
* The linked list is put in the array itself, which is possible
* since we already know what the value there should be (4 or 5).
*/
int flip45( unsigned *arr, unsigned count)
{
unsigned idx;
unsigned head, tail;
int debt=0;
for (idx=head=tail=0; idx < count; idx++) {
fprintf(stderr, "[%u/%u] {%u %u} debt=%d this=%u\n", idx, count, head, tail, debt, arr[idx] );
if (!debt) head = tail = idx;
switch( arr[idx] ) {
case 4:
if (debt++ >= 0) { /* add to the linked list of waiting 4s */
fprintf(stderr, "remember 4@%u\n", idx );
arr[head] = idx; head = idx;
}
else { /* pair with oldest waiting 5 */
unsigned target = tail;
if (idx >= count-1) { fprintf(stderr, "No space %u\n", idx); }
if (arr[idx+1] == 4) { fprintf(stderr, "No4! %u\n", idx); }
fprintf(stderr, "Consume 5@%u\n", target );
tail = arr[tail];
arr[target] = arr[idx+1] ; /* swap */
arr [++idx] = 5;
}
break;
case 5:
if (debt-- <= 0) { /* add to the linked list of waiting 5s */
fprintf(stderr, "remember 5@%u\n", idx );
arr[head] = idx; head = idx;
}
else { /* pair with oldest waiting 4 */
unsigned target = tail;
fprintf(stderr, "Consume 4@%u\n", target );
tail = arr[tail] ;
arr[target] = 4;
arr[idx] = arr[target+1] ; /*swap*/
arr[target+1] = 5;
}
default: continue;
}
}
return debt;
}
/***************
HTH,
AvK