Instructions[edit]
Strategy[edit]
This exercise is a lot like the previous one, except that now you start with an empty floor. Rather than having the values you need to skip made available for you, you'll need to generate them on your own as you encounter new letters.
For this stage, we will rely on not just one, but two different indirect counters. One will indicate how many unique letters we've found so far, and therefore which box to place new letters from the INBOX for testing. The other will indicate which of the previous letters we are testing against. Every time we fetch a new letter, we will reset the value of the second number to the value of the first, minus one. In other words, if we're placing the next letter in box 4, we want to start by comparing it against box 3.
It is important to note that we will work our way down the boxes, instead of up. This is because the particular tools you have available, namely JUMP IF ZERO and JUMP IF NEGATIVE, make it easier to tell when you're done counting down than when you're done counting up.
To start this all off, we will initially take the first letter, drop it in box 0, and carry it straight to the OUTBOX. Since it's the first letter, it will obviously be unique, and there's nothing else to test it against. Then we'll bump up the zero in box 14. The real work will begin with the second letter. We'll copy the value of box 14 to box 13 and bump it down one. Then we'll pick up a letter from the INBOX and place it in the box indicated by box 14. We'll subtract that value from the box indicated by box 13. If the answer is zero, we found a duplicate, and we'll start over with the next letter. If not, we'll bump down box 13. If that turns out to be negative it means we checked all the existing letters and didn't find a match, so we can copy the letter to the OUTBOX. Otherwise, we're not done testing, so we'll check the next letter.
The resulting code looks as follows:
INBOX COPYTO [14] a: COPYFROM [14] OUTBOX BUMPUP 14 b: COPYFROM 14 COPYTO 13 BUMPDN 13 INBOX COPYTO [14] c: SUB [13] JUMPZ b BUMPDN 13 JUMPN a COPYFROM [14] JUMP c
Optimizing Speed[edit]
The above code already exceeds both the speed and size requirements set for you. However, it's possible to tweak just a little more speed out of it, and stay below the size requirements by altering the logic a bit. Instead of using the first counter to keep track of where the new letter should go, we'll simply use box 12 as a container while we test, and then copy it to a new box before taking it to the OUTBOX if we decide it's unique. This allows us to be a bit more efficient and get more speed.
INBOX JUMP b a: BUMPUP 14 COPYFROM 12 b: COPYTO [14] OUTBOX c: COPYFROM 14 COPYTO 13 INBOX COPYTO 12 d: SUB [13] JUMPZ c BUMPDN 13 JUMPN a COPYFROM 12 JUMP d
Optimizing Size[edit]
Alternatively, we can optimize size by removing one INBOX instruction and one COPYTO instruction. However, it decreases the speed.
JUMP c a: COPYFROM [14] OUTBOX BUMPUP 14 b: c: INBOX COPYTO [14] COPYFROM 14 COPYTO 13 d: BUMPDN 13 JUMPN a COPYFROM [13] SUB [14] JUMPZ b JUMP d
Further speed optimization[edit]
Assuming, that there will be at most 5 distinct letters, we can write a long, but very fast program.
-- commands 65 -- steps 79 -- HUMAN RESOURCE MACHINE PROGRAM -- INBOX COPYTO 0 OUTBOX a: INBOX COPYTO 1 SUB 0 JUMPZ a COPYFROM 1 OUTBOX b: c: INBOX COPYTO 2 SUB 0 JUMPZ b COPYFROM 2 SUB 1 JUMPZ c COPYFROM 2 OUTBOX d: e: f: INBOX COPYTO 3 SUB 0 JUMPZ d COPYFROM 3 SUB 1 JUMPZ f COPYFROM 3 SUB 2 JUMPZ e COPYFROM 3 OUTBOX g: h: i: j: INBOX COPYTO 4 SUB 0 JUMPZ g COPYFROM 4 SUB 1 JUMPZ j COPYFROM 4 SUB 2 JUMPZ i COPYFROM 4 SUB 3 JUMPZ h COPYFROM 4 OUTBOX k: l: m: n: o: INBOX COPYTO 5 SUB 0 JUMPZ k COPYFROM 5 SUB 1 JUMPZ o COPYFROM 5 SUB 2 JUMPZ n COPYFROM 5 SUB 3 JUMPZ m COPYFROM 5 SUB 4 JUMPZ l COPYFROM 5 OUTBOX p: INBOX JUMP p