From StrategyWiki, the video game walkthrough and strategy guide wiki
Jump to navigation Jump to search

Instructions[edit]

Duplicate Removal
Send everything from the INBOX to the OUTBOX, unless you've seen the same value before. Discard any duplicates.

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