Human Resource Machine/Year 19

Instructions

Countdown

For each number in the INBOX, send that number to the OUTBOX, followed by all numbers down to (or up to) zero. It's a countdown!

You got new commands! They add ONE or subtract ONE from an item on the floor. The result is given back to you, and for your convenience, also written back to the floor. BUMP!

Strategy

The time has come for you to receive your final two commands: BUMP+ and BUMP- (listed as BUMPUP and BUMPDN respectively in the program listings.)

BUMP+

This instruction is always accompanied by a number. It commands the worker to walk over to whatever box is indicated by the number, and add one to the value it contains. Then the resulting value replaces whatever you're holding in your hand. Note that you cannot instruct the worker to attempt to bump a box that contains no value.

BUMP-

Almost exactly the same as BUMP+, except that it subtracts one from the value in the box, instead of adding one.

For this task, both commands will obviously come in handy. You'll grab a number from the INBOX and copy it to a box (as well as the OUTBOX.) Then if the number is positive, you'll continue to BUMP- that number and copy the result to the OUTBOX until you reach zero. If the number is negative, you'll continue to BUMP+ instead.

For this particular problem, there are a number of ways to write the solution, but there does not seem to be one solution that meets both the size requirement (10 instructions and under) and the speed requirement (82 steps per average.) Two solutions will be presented based on which challenge you are trying to accomplish. They are not the only solutions, or even the best, but they are easy to explain.

Size Challenge

To get a program small enough that will meet the size challenge, you need to generalize the instructions and keep them very contained. The approach this program will take is as follows:

First, we will get a number from the INBOX and copy it to box 0. We're always going to OUTBOX that value as well. Then we'll return to box 0 and copy the value. From there, if the number is zero, we're done and we can go back and get a another number. If it's not zero, we'll check if it's negative. If it is, we'll bump the number up by one and jump back to the OUTBOX instruction. If it's not, we'll bump the number down by one and jump back.

This program can be written in 10 instructions, but it executes in an average of 122 steps. This is largely due to the fact that we're jumping around so often, especially since we're constantly asking if a number is negative or positive in order to direct the program to the correct bump, despite the fact that the number's sign never changes.

a:
   INBOX   
   COPYTO   0
b:
   OUTBOX  
   COPYFROM 0
   JUMPZ    a
   JUMPN    c
   BUMPDN   0
   JUMP     b
c:
   BUMPUP   0
   JUMP     b

Size Challenge(revised on speed)

111 steps.

a:
   INBOX   
   COPYTO   0
   JUMP     c
b:
   BUMPUP   0
c:
d:
   OUTBOX  
   COPYFROM 0
   JUMPZ    a
   JUMPN    b
   BUMPDN   0
   JUMP     d

Speed Challenge

The following code corrects the mistake explained with the program above by asking if a number is positive or negative only once and then writing two separate loops, one if the number is positive and one if the number is negative. Obviously this will add to the number of lines the code contains, but it will dramatically cut down on the number of steps needed to complete the problem because we won't continuously ask if the number is positive and negative.

We start by setting up an OUTBOX instruction that we will jump over the first time, and always jump back to when we reach a zero value, followed by the INBOX instruction. We will copy the value to a box, and then ask if it's zero. If it is, we will jump back up to the OUTBOX instruction and continue. If it's not, we'll ask if it's negative. If it is, we'll send it to a loop that sends the value to the OUTBOX and then bumps the number up until it reaches zero. If it's positive, we'll send it to a similar loop that bumps the number down until it reaches zero.

   JUMP     d
a:
b:
c:
   OUTBOX  
d:
   INBOX   
   COPYTO   0
   JUMPN    f
   JUMPZ    a
e:
   OUTBOX  
   BUMPDN   0
   JUMPZ    b
   JUMP     e
f:
g:
   OUTBOX  
   BUMPUP   0
   JUMPZ    c
   JUMP     g

Speed challenge revisited

The above solution is certainly fast (79 cycles), but it can be faster. The following will finish in 74 cycles:

    JUMP     d
 a:
 b:
 c:
    OUTBOX
 d:
    INBOX
    COPYTO   0
    JUMPN    f
    JUMPZ    a
 e:
    OUTBOX
    BUMPDN   0
    JUMPZ    b
    JUMP     e
 f:
 g:
    OUTBOX
    BUMPUP   0
    JUMPN    g
    JUMP     c