Instructions[edit]
Strategy[edit]
For this floor, there are two 0-terminated words sitting in the INBOX. To start, you'll want to grab both words off the conveyor and store them on the floor. You are given two numbers to start with. One is a 0, but the other is a 10. Seeing as how no word will everbe more than 9 letters long, the 10 makes a good index into where you should begin storing the second word, and makes it easy for you to remember where to start retrieving from.
This problem needs to be solved in several steps. Start by copying the 0 to another box, and use it as an index to where each letter should be stored. Drop each letter, and increment the index by one. When you grab the zero, you want to copy that to the floor as well, so that we know how long each word is when we go to compare them.
Next, you'll copy the 10 to another box, and use that as an index for each letter of the second word. Again, we'll copy the 0 to the floor as well before moving on.
Next, we'll copy both the 10 and and 0 to other boxes. Then we'll use them as indirect indexes into each word and compare them to each other, one letter at a time. By subtracting each pairs of letters from each other, we can tell when one word is "less" than another, or comes first alphabetically. If the letters are the same (the difference is zero), then we'll bump our indices, and check the next pair of letters.
Once we determine that one pair of letters are different, then we have to choose which index to start from, 0 for the first word, or 10 for the second word, and copy only the letters of that word to the OUTBOX. There's an edge case that you have to watch out for, however. Take for example the words UN and UNIX. Both of the first two letters are equal, so you must determine that UN comes before UNIX because you reached the end of the first word before you reached the end of the second. Though it's a bit confusing, the resulting program should look as follows:
COPYFROM 23 COPYTO 22 a: INBOX COPYTO [22] JUMPZ b BUMPUP 22 JUMP a b: COPYFROM 24 COPYTO 22 c: INBOX COPYTO [22] JUMPZ d BUMPUP 22 JUMP c d: COPYFROM 24 COPYTO 22 COPYFROM 23 COPYTO 21 JUMP f e: BUMPUP 22 BUMPUP 21 f: COPYFROM [21] JUMPZ j COPYFROM [22] JUMPZ g SUB [21] JUMPZ e JUMPN h JUMP i g: h: COPYFROM 24 JUMP k i: j: COPYFROM 23 k: l: COPYTO 22 COPYFROM [22] JUMPZ m OUTBOX BUMPUP 22 JUMP l m:
Optimizing[edit]
The above program satisfies both the size challenge and speed challenge.
However, to truly make this program shorter and more efficient, we can change our strategy quite a bit. In the beginning, we will grab the first word off the conveyor and place it down like before. Except that we won't copy the 0 over, we just bump box 23 until we reach the end, and then use the 0 at the end of the first word to help us count the second word.
Next, when we start pulling letters for the second word, we won't automatically copy the entire word before we start to compare them. Instead, we'll test each letter as we pull them off. If they're the same, we'll go ahead and copy that letter to the OUTBOX right then and there, because that letter will definitely end up on there. The only change to this behavior comes when we find out that one word is different than the other. If the first word turns out to be the right answer, then we'll stop plucking letters off the INBOX and simply copy the letters on the floor to the OUTBOX. If the second word is the right one, we'll stop comparing the letters on the floor, and just grab the rest of the letters from the INBOX.
The only thing we must be careful about is knowing when one word is smaller than the other. For that, we'll keep comparing the counter that we have going to the final tally of the number we reached when copying the first word. If we reach the end of the first word before we finish the second, or vise versa, we're automatically finished. This program clocks in well under both requirements.
a: INBOX COPYTO [23] JUMPZ b BUMPUP 23 JUMP a b: COPYTO 22 c: INBOX JUMPZ h COPYTO 20 SUB [22] JUMPZ g JUMPN e d: COPYFROM [22] JUMPZ i OUTBOX BUMPUP 22 JUMP d e: COPYFROM 20 f: OUTBOX INBOX JUMPZ j JUMP f g: COPYFROM 20 OUTBOX BUMPUP 22 SUB 23 JUMPN c h: i: j:
There is also another solution, the execution of which allows you to pass both the Speed challenge and the Size challenge, and it is as follows:
-- Copy every character to memory until 0 a: INBOX -- Found 0, end of word JUMPZ b COPYTO [23] BUMPUP 23 JUMP a -- Copy length of first word (counter value) and clear counter b: COPYFROM 23 COPYTO 22 SUB 23 COPYTO 23 -- Copy letter to cell 20 c: INBOX JUMPZ m COPYTO 20 -- Check current letter from input is equal to the character in memory SUB [23] -- If result is 0 than first letter is this same and jump to d JUMPZ d -- If value was not 0, there are differences in word JUMP e -- Because letters are this same copy last letter and put to the output d: COPYFROM [23] OUTBOX -- Check current word is not longer than word in memory BUMPUP 23 SUB 22 -- If current word is longer jump to l JUMPZ l -- Jump to c and get next letter from input JUMP c -- There is need to recheck last check. If result is negative jump to G e: JUMPN g -- Last result was positive so the word in memory is first in order and need to copy values from memory to output f: COPYFROM [23] JUMPZ k OUTBOX BUMPUP 23 SUB 22 JUMPZ j JUMP f -- Because last check was negative it is known word from input is first in order so copy value from input to output g: COPYFROM 20 h: OUTBOX i: INBOX JUMPZ i JUMP h j: k: l: m: