Back in the 1980s I went to Oxford University and studied Mathematics and Computation (this was almost the entire Mathematics course plus Computer Science added on; the degrees offered today are a little different). Having sat the mathematics entrance exam and gone through all the mathematics interviews I had interviews in the Programming Research Group (now the Department of Computer Science). During those interviews two specific programming/algorithm design questions were posed. Here they are (I made up names for them).

The computer's CPU only has three instructions Z, I and J as follows:

For example, here's a loop that keeps adding one to memory location 4 until it equals memory location 20.

On the ground along Keble Road there are a line of n buckets, in each bucket is a single ball. The balls are red, green and blue. A robot is to be programming to sort the balls so that there's one ball in each bucket still but the colours are now in the order red, green, blue. So, working from left to right an observer will see all the red balls in buckets, then all the green balls in buckets, and finally all the blue balls.

The robot is only allowed to examine one ball at a time by peering into its bucket and is only allowed to examine each ball once. When it looks at a ball it must decide what to do with it. The robot has two arms and the only ball manipulation it can do is swap the balls in two buckets.

1. Program the robot to sort the balls.

2. Write out a proof that the proposed algorithm works.

Of course, a whole load of other questions were asked about program running time, correctness and what I later realized was the lambda calculus. But these were the two main 'programming' tasks.

**The Z Machine****A computer is constructed with a simple memory layout. It has an unlimited amount of memory and each memory location is numbered so that a program can refer to it. Each memory location can store a single number or be uninitialized. In the following diagram memory locations that are blank are uninitialized some other memory locations have numbers in them.**

The computer's CPU only has three instructions Z, I and J as follows:

**Z.**This instruction zeroes a memory location. For example, Z2 sets memory location 2 to 0, Z42 sets memory location 42 to 0.**I.**This instruction adds one to the contents of a memory location. For example, I3 adds 1 to whatever is currently stored in location 3.**J.**This instruction examines the contents of two memory locations and branches if the contents are different. For example J18,19 would compare the contents of memory locations 18 and 19, if they are the same the program continues with the next instruction, if different it branches. The branch destination is just specified by drawing an arrow to the instruction you want to go to.**When there are no more instructions the program stops.**

For example, here's a loop that keeps adding one to memory location 4 until it equals memory location 20.

1. The operator of the machine places two numbers (one each) in memory locations 0 and 1. Here, for example, the operator has put 3 in location 0 and 4 in location 1. Write a program using the Z, I and J instructions to add those (arbitrary) numbers together and put the result in memory location 2.

2. Under what circumstances does this program fail?

**The One-eyed Robot****(If you've studied computer science you may recognize this problem)**

On the ground along Keble Road there are a line of n buckets, in each bucket is a single ball. The balls are red, green and blue. A robot is to be programming to sort the balls so that there's one ball in each bucket still but the colours are now in the order red, green, blue. So, working from left to right an observer will see all the red balls in buckets, then all the green balls in buckets, and finally all the blue balls.

The robot is only allowed to examine one ball at a time by peering into its bucket and is only allowed to examine each ball once. When it looks at a ball it must decide what to do with it. The robot has two arms and the only ball manipulation it can do is swap the balls in two buckets.

1. Program the robot to sort the balls.

2. Write out a proof that the proposed algorithm works.

**Note**Of course, a whole load of other questions were asked about program running time, correctness and what I later realized was the lambda calculus. But these were the two main 'programming' tasks.

## 23 comments:

1 z3

2 z2

3 i2

4 i3

5 j3-0 ->3

6 z3

7 i3

8 i2

9 j3-1 ->7

It fails when either [0] or [1] contain 0

1 z3

2 z2

3 i2

4 i3

5 j3-0 ->3

6 z3

7 i3

8 i2

9 j3-1 ->7

It fails when either [0] or [1] contain 0

1 z3

2 j3-0 ->8·

3 z2

4 i2

5 i3

6 j3-0 ->4

7 z3

8 j3-1 ->12

9 i3

10 i2

11 j3-1 ->9

12 z3

Solution with managing zero case !

Damn in the last solution i forgot to initialise [2]

So insert Z2 command at second line, and add +1 to all memory address for jmp ! :)

@CoachDom: the first solution is good, but the one handling the zero case is not.

This ought to work if the two numbers are non-negative integers (and not too large, obviously):

0001: Z2

0002: Z3

0003: I3

0004: J0,2 0006

0005: J2,3 0008

0006: I2

0007: J0,2 0006

0008: Z4

0009: J1,4 0011

0010: J3,4 0014

0011: I2

0012: I4

0013: J1,4 0011

0014: Z3

The second problem's impossible, isn't it? Perhaps I'm mis-reading it.

Suppose there are 3 red balls, 1 green and 2 blue. If the first ball you come across is green, it needs to go into the third bucket from the right. But you don't know that until you've examined all the other balls. That would break the rule about deciding what to do with a ball immediately after examining it.

@Unknown: the second problem is not impossible.

Oh, I think I got it now.

left = -1;

right = num_buckets;

loc = 0;

while (loc<right) {

switch (buckets[loc]) {

case RED:

left++;

swap(buckets[loc], buckets[left]);

loc++;

break;

case BLUE:

right--;

swap(buckets[loc], buckets[right]);

break;

case GREEN:

loc++;

}

}

Here's my online implementation of the ball sorting algorithm:

http://oranchak.com/one-eyed-robot/

1 z2

2 z3

3 i2

4 j0,2 --> 3

5 i3

6 i2

7 j1,3 --> 5

Will enter an infinite loop if either [0] or [1] = zero

b = ["g", "b", "r", "b", "b", "g", "b", "r", "g", "r", "b", "r", "b", "b", "r", "g", "g", "b", "r", "r"]

pos = 0

for c in ["r", "g", "b"]:

for i in range(pos, len(b), 1):

if b[i] == c:

b[i], b[pos] = b[pos], b[i] # python swap

pos += 1

print b

I think this should work:

0 Z2

1 Z3

2 I4 //holds 1, use to force jump to exit

3 J0,3 -> 6 // r0 != 0, r1 == ?

4 J1,3 -> 12 // r0 == 0, r1 != 0

5 J3,4 -> 16

6 I2 // add r0

7 I3

8 J0,2 -> 9

9 Z3

10 J1,3 -> 11 // r0 != 0, r1 != 0

11 J3,4 -> 16 // r0 != 0, r1 == 0

12 Z3 // add r1

13 I2

14 I3

15 J1,2 -> 12

16 exit

EDIT: made a couple of typos in the summation loops.

I think this should work:

0 Z2

1 Z3

2 I4 //holds 1, use to force jump to exit

3 J0,3 -> 6 // r0 != 0, r1 == ?

4 J1,3 -> 12 // r0 == 0, r1 != 0

5 J3,4 -> 16

6 I2 // add r0

7 I3

8 J0,2 -> 6

9 Z3

10 J1,3 -> 11 // r0 != 0, r1 != 0

11 J3,4 -> 16 // r0 != 0, r1 == 0

12 Z3 // add r1

13 I2

14 I3

15 J1,2 -> 13

16 exit

Blergh typos and some shrinkage, try three.

0 Z2

1 Z3

2 I4

3 J0,3 -> 6 // r0 != 0

4 J1,3 -> 10 // r0 == 0

5 I2 // add r0

6 I3

7 J0,3 -> 5

8 Z3

9 J1,3 -> 11 // r1 != 0

10 J3,4 -> exit // r1 == 0

11 I2 // add r1

12 I3

13 J1,3 -> 11

14 exit

0000: Z 2

0001: I 2

0002: J 2, 0 (0001)

0003: I 2

0004: J 2, 1 (0003)

@Pascal.

I got the exact same answer as you for the first question.

However, for your solution to the second problem, i don't think it satisfies the condition that the robot is only allowed to examine each ball once. Phil's solution looks like it should work and meets this criteria.

01 z2 -- additive accumulator

02 z3 -- reference 0

03 z4 -- reference 1

04 i4 -- reference 1

05 z5 -- accumulator

06 j3,4 => 08 -- if false

07 i2

08 j2,0 => 07 -- add 1 until true

09 j3,4 => 12 -- if false

10 i5

11 i2

12 j5,1 => 10 -- using #5

This program will enter an infinite loop if any location has a negative number (as per the example).

It's a little tricky to take care of the case when both numbers are 0.

I managed with 17 instructions, I think this works provided 0 and 1 are integers >=0. I first check explicitly for the "both 0" case. Register 10 stays zero throughout (except in that first check).

Z2

Z10

J0, 10 -> first

J1, 10 -> first

I10

J0, 10 -> end

first:

J2, 0 -> first_loop

Z3

second:

J3, 1 -> second_loop

J3, 10 -> end

first_loop:

I2

J2, 10 -> first

second_loop:

I2

I3

J3, 10 -> second

end: Z10

2 i1

3 i2

4 j0,2 --> 2

5 i2

6 j1,2 --> 2

1 z2

2 j0,2 --> 6

3 i1

4 i2

5 j0,2 --> 3

6 j1,2 --> 9

7 i2

8 j1,2 --> 7

9 z1

First listing works for non-zero values (it may work for 0 depending upon what occurs when i command is run on max-int values).

Second listing works for values including 0.

Both may work on negative values depending again upon what occurs when i command is run on max-int values.

Both require only memory locations 0,1,and 2. Preservation of inputs was not a requirement.

Your 'Z-machine' is a Turing machine I believe from memory.

I made a couple of python 2.7.8 programs to implement my solutions.

1. Could account for zero but didn't because it makes the program not as nice looking. Negative numbers would only work if you have two of them and you interpret a positive output as negative.

s = [

('z',2),

('z',3),

('i',2),

('j',2,0,2),

('i',2),

('i',3),

('j',3,1,4)

]

l = [9,5,'','']

x = 0

while True:

if s[x][0] == 'z':

l[s[x][1]] = 0

elif s[x][0] == 'i':

l[s[x][1]] += 1

else:

if l[s[x][1]] != l[s[x][2]]:

x = s[x][3] - 1

x += 1

if x >= len(s):

break

print(l)

2.

b = [2,3,1,3,3,2,3,1,2,1,3,1,3,3,1,2,2,3,1,1]

c1 = 0

c3 = 0

x = 0

while x < len(b):

if b[x] == 1:

b[x] = b[c1]

b[c1] = 1

c1 += 1

if b[x] ==1 or b[x] ==2:

x += 1

if x >= len(b)-c3:

break

if b[x] == 3:

b[x] = b[len(b)-c3 -1]

b[len(b)-c3 -1] = 3

c3 += 1

print(b)

In short it works because balls of type 1 or 3 are put to their respective sides and 2 has no place to be except the middle. I wonder if I broke the rules.

For problem 1:

01. Z 2

02. Z 4

03. I 4

04. Z 3

05. J 3 0 07

06. J 4 0 09

07. I 2

08. J 0 2 07

09. J 3 1 11

10. J 4 1 13

11. I 3

12. I 2

13. J 3 1 11

Just 13 line. It doesn't consider Any number less than 0. Seems like no one noted down there is a floating point number mentioned in the system example. So I can say my code considers only positive integers and zeros.

Has anyone solved this in under

13 OPS0001 Z2

0002 Z3

0003 Z4

0004 I4

0005 J0,2 0007

0006 J3,4 0009

0007 I2

0008 J0,2 0007

0009 J1,3 0011

0010 J3,4 #END

0011 I2

0012 I3

0013 J1,3 0011

#END NULL

This only works for positive intgers0: z2

1: j0,2 -> 5

2: j0,3 -> 8

3: i2

4: j0,3 -> 8

5: i1

6: i2

7: j0,2 -> 5

8: j1,2 -> 3

# END

Handles the 0 case and doesn't use any additional memory.

Assumes that uninitialized memory will never equal 0, thus `j0,3 -> x` acts as an unconditional jump to `x`

Post a Comment