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 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.
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.
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.
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 OPS
0001 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 intgers
0: 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