Human Resource Machine/Year 14

Instructions

Maximization Room

Grab TWO things from the INBOX, and put only the BIGGER of the two in the OUTBOX. If they are equal, just pick either one. Repeat!

You got a new command! Jumps only if the thing you're holding is negative. (Less than zero.) Otherwise continues to the next line.

Strategy

This time around, you get a new jump command: JUMP _{IF NEGATIVE} (abbreviated JUMPN in the program listings).

JUMP _{IF NEGATIVE}

This jump command works similarly to the JUMP _{IF ZERO} command. However, this command only jumps to a different instruction if, and only if, the value held in the worker's hands is negative. If it is, the program will follow the jump. If it's zero or any positive value, the program will ignore the jump command, and continue on to the next command.

This new jump command will expand your options a little bit. Your task now is to determine which of two numbers is bigger. You can figure this out by subtracting them. If you subtract a first number from a second and the answer is negative, then you can conclude that the first number was bigger. If the answer is positive, then the second number was bigger.

To write this program correctly, you will have to evaluate the difference between two numbers, and write two sections of code, one for when the first number is bigger and the other for when the second number is bigger. Since you don't know which number you'll be bringing to the OUTBOX, you might want to store both numbers in boxes first.

Your first attempt may look like the following program, although it will fail both the size test and the speed test:

a:
   INBOX   
   COPYTO   0
   INBOX   
   COPYTO   1
   SUB      0
   JUMPN    b
   COPYFROM 1
   JUMP     c
b:
   COPYFROM 0
c:
   OUTBOX  
   JUMP     a

Optimizing

You may think by now that the trick to optimizing this program is to move the OUTBOX instruction, and you'd be partially correct, but that won't reduce the size of the program. The above program is 11 instructions, and the challenge is to be 10 instructions or less. So you need to find one instruction to remove.

One area to focus on is the need to copy the second value into a box before subtracting the first from the second. You do this because if you decide that you want to bring the second number to the OUTBOX, you don't want to lose it. However, subtracting the first number from the second number can be reversed. In order to get the second number back, you can simply add the first number to the difference, and you'll be holding the second number again. So we can eliminate the need to copy the number to a box first, reducing the program from 11 instructions to 10.

a:
   INBOX   
   COPYTO   0
   INBOX   
   SUB      0
   JUMPN    b
   ADD      0
   JUMP     c
b:
   COPYFROM 0
c:
   OUTBOX  
   JUMP     a

The above program will meet both optimization conditions. However, you can still further optimize the program by doing what was mentioned earlier, and moving the OUTBOX command to the top of the program. To get a little more speed out of it, you can also move the COPYFROM command up, and only jump to it if the difference is negative. Otherwise, you can add the first number back and jump straight to the OUTBOX command.

   JUMP     c
a:
   COPYFROM 0
b:
   OUTBOX  
c:
   INBOX   
   COPYTO   0
   INBOX   
   SUB      0
   JUMPN    a
   ADD      0
   JUMP     b