Prev: Richard Heathfield's lie
Next: Richard Heathfield: liar
From: Patricia Shanahan on 24 Dec 2009 20:36
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) {
> 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

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
From: Lie Ryan on 24 Dec 2009 22:34
On 12/25/2009 11:18 AM, Patricia Shanahan wrote:
> 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.
From: Mike Sieweke on 24 Dec 2009 23:48
In article <4b33fa57$1(a)dnews.tpgi.com.au>,
Lie Ryan <lie.1296(a)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.


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
From: Moi on 25 Dec 2009 14:48
On Thu, 24 Dec 2009 23:48:43 -0500, Mike Sieweke wrote:

> In article <4b33fa57$1(a)dnews.tpgi.com.au>,
> Lie Ryan <lie.1296(a)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
First  |  Prev  | 
Pages: 1 2 3
Prev: Richard Heathfield's lie
Next: Richard Heathfield: liar