Human Resource Machine/Year 21

Instructions

Zero Terminated Sum

The INBOX is filled with zero terminated strings! What's that? Ask me. Your Boss.

Add together all the numbers in each string. When you reach the end of a string (marked by a ZERO), put your sum in the OUTBOX. Reset and repeat for each string.

Strategy

As your boss explains when you arrive on this level, zero-terminated strings are indeed very old. They are the most common way for a program to signify the end of a line of text, and this is done so that programmers don't need to know exactly how long each line of text is. They simply print out the lines one character at a time until they reach the zero, signifying that the text is finished.

That's pretty much exactly what you're going to do; consider each number on the IN conveyor belt, and perform some action with them until you encounter a zero. (The action in this particular exercise is sometimes referred to as a checksum. Checksums can be used as a way to tell if you've received some data correctly or not.)

Once again, we're going to start off with an initialization. We'll take the zero provided for us in box 5 and use it to start the sum of the non-zero numbers that we'll keep track of in box 0. After we do that, we'll grab a number from the INBOX. The key to this exercise is to keep our eye out for zeros, so we'll ask every time if the number we just grabbed is a zero, indicating that the string of numbers has ended.

If it is a zero, we'll take whatever number we have summed up in box 0 and take it to the OUTBOX. If it's not a zero, then we'll take this new number, and add it to the total in box 0, and put the new total back in there. Then we'll jump back to grabbing another number from the INBOX and start the whole check back over. This program will look like so:

a:
   COPYFROM 5
   COPYTO   0
b:
   INBOX   
   JUMPZ    c
   ADD      0
   COPYTO   0
   JUMP     b
c:
   COPYFROM 0
   OUTBOX  
   JUMP     a

Optimizing

Conveniently, this program above meets the Size Challenge, but it's apparently not efficient enough to meet the Speed Challenge. In fact, it's possible to meet both challenges with one program, but we'll have to restructure the instructions fairly significantly.

First we'll start with the usual "Move the OUTBOX command above the INBOX command so you don't have to jump to it" optimization that we've done many times before. Second, we're not going to rely on any initialization. So box 5 will be useless to us here.

Instead, we're going to get better at handling the special case when the very first number in the sequence is a zero, meaning the sequence has no sum. If we happen to encounter a zero before any other number, we don't have to do anything else; we can just take it over to the OUTBOX and move on to the next number.

Provided the first number is not a zero, we'll copy it to box 0 and grab another number. If that number happens to be zero, then we won't do any math, we'll just take the first number put in box 0 and bring it to the OUTBOX. Otherwise, we'll start adding the numbers up until we actually find a zero. Below is the program which satisfies both the Size and Speed challenges.

   JUMP     c
a:
   COPYFROM 0
b:
   OUTBOX  
c:
   INBOX   
   JUMPZ    b
d:
   COPYTO   0
   INBOX   
   JUMPZ    a
   ADD      0
   JUMP     d

There is an alternative solution to the Size challenge, in which instead of 10 instructions the solution contains 9 instructions. However, it is not optimal because the average number of steps is as high as 88. Thus, this solution is correct only for the Size challenge.

   JUMP     b
a:
   COPYFROM 0
   OUTBOX  
b:
   COPYFROM 5
c:
   COPYTO   0
   INBOX   
   JUMPZ    a
   ADD      0
   JUMP     c