Instructions[edit]
Strategy[edit]
Like comments, labels are purely for your own benefit. If you want to mark a box with a particular purpose, you can click on the box and draw your own label for it. If you do, the program that you write will reflect the labels that you've designated rather than the number of the box.
As you can tell from the instructions, you must now write a multiplication program. But you clearly don't have a multiplication instruction. Fortunately, multiplication can be performed purely with addition. Multiplying m by n is the same as adding m to itself n times.
So to solve this problem, you will copy two values into two boxes. From there, you will proceed to add one of the values to itself, while you bump the other value down by one, and repeat this process until the value you're bumping down reaches zero. Then you'll send the result to the OUTBOX.
You don't have to worry about negative numbers, but there is another concern that you still have: multiplying by zero. This is what's known as an "edge case," a situation that runs outside the normal circumstance that you have to write extra code to specifically handle. Naturally when either number is a zero, you want to simply put a zero in the OUTBOX and move on to the next two numbers. If the second number you pick up is the zero, put it on the OUTBOX. But if the zero is the first number, you still need to grab the next number off the IN conveyor or your answer will be wrong.
Since this is another case where you can't complete the size challenge and the speed challenge with one single program, the solutions will be split out again.
Size Challenge[edit]
15 instructions can be a tough number to hit on this challenge, but it can be done with enough proper setup. We'll start by assuming that three boxes are going to used for the following tasks: Box 2 will be where we hold onto the sum of the number we're adding to itself. Box 1 will be where we cache that number so that we know how much to add each time. Box 0 will be where we store the other number that we're multiplying by, and it will be the number we bump down while we count how many times we add.
Since the summed up number will be stored in box 2, the top of our program can be fetching the number from box 2, and bringing it to the OUTBOX. We'll skip over those lines the first time we run. When we're ready to hit the INBOX, we're going to do what's known as initialization. We're going to initialize Box 2 with the starting value of zero, which we can copy from box 9. Then we'll grab the first two numbers off the IN conveyor and cache them in boxes 1 and 0 respectively.
The number in box 0 will get bumped down, and if it's negative, that's how we know we're done. We'll grab whatever is in box 2 and put it in the OUTBOX and continue. If it's not, we have some addition to do. So we'll grab the current sum from box 2, add the contents of box 1, and store the answer back in box 2. Then we jump back to bumping box 0 down and test if we're finished again.
This works well for the obvious cases, albeit inefficiently, but it does handle the two edge cases when either number might be zero. If the first number is zero, then we just end up adding zero to itself over and over again until the second number becomes negative. If the second number is zero, it will become negative before anything ever gets added to the initial value of zero in box 2, which is what we'll send to the OUTBOX.
JUMP b a: COPYFROM 2 OUTBOX b: COPYFROM 9 COPYTO 2 INBOX COPYTO 1 INBOX COPYTO 0 c: BUMPDN 0 JUMPN a COPYFROM 2 ADD 1 COPYTO 2 JUMP c
Speed challenge[edit]
Reaching the desired speed of an average of 109 steps is a challenge indeed. In order to do this, we're going to need to write special case code to handle certain situations, but we need to do it with as few jumps or decisions as possible. We'll be using the same boxes for the same purpose as above, only we won't be initializing anything. Instead, we're going to try to set up the problem so that the initialization won't be necessary.
Again, we're always going to assume that the answer will be coming from box 2, and we're going to leverage that fact early on. Right away, we're going to ask if the first number we pull of the conveyor is zero. If it is, we're going to write that zero into box 2, grab the next value off the IN conveyor and throw it away, and then proceed with the normal finishing condition of grabbing whatever is in box 2 (a zero in this case) and putting it in the OUTBOX.
If that's not the case, we'll take whatever the value is, and write it to both box 1 and box 2. In this way, we've already handled what the sum is if we're multiplying the number by one. Then we'll grab the second number from the INBOX. If this number is a zero, we're pretty much done. We can simply walk with that zero over to the OUTBOX and put it down and continue on.
If by this time we've concluded that neither number is zero, we will proceed like normal. We'll place the second number in box 0, and bump it down. If after bumping it turns out to be zero (so the second number must have been a one), we'll take the contents out of box 2 (which was a copy of the first number), and put it in the OUTBOX.
If, after bumping, the number is not zero, we'll go ahead and pick up the sum value in box 2, and add the number in box 1 to it before storing it back in box 2. Then we'll bump the number in box 0 down again and repeat the process of checking whether it's zero.
The following code is presented below, but there are two points worth noting that affect its performance:
- You'll notice that we copy the first number twice before checking if the second number is zero, and then copying the second number once. At first glance, it may appear to be faster to copy the first number once, and the second number twice, in case the first number is zero, and you don't have to copy the second number at all. However, one aspect of this game that is very tricky to perceive, is the cost of fetching a value before operating on it. When we copy the second number to box 0, we immediately bump it down. In doing so, we pay no extra cost to fetch the value in box 0 because we already have it (we just copied it in there.) If you reversed this order and copied the first number to box 0, you would make the program less efficient because after copying the second number in two boxes, you'd have to back to box 0 and fetch the number before you bumped it down. Try reversing those steps and see what the impact is on the performance.
- You can actually improve upon the speed of this program even further! If you take the last five lines before the final jump and repeat them, you'll make the program longer, but you'll actually improve its average speed. This is due to the fact that by repeating the code, you're reducing the number of times you jump back to do it over again almost in half. The more you repeat the code, the faster your code can become, but at diminishing rates of return (The more you repeat it, the less boost in speed you will see.)
JUMP e a: INBOX b: c: COPYFROM 2 d: OUTBOX e: INBOX COPYTO 2 JUMPZ a COPYTO 1 INBOX JUMPZ d COPYTO 0 BUMPDN 0 JUMPZ c f: COPYFROM 2 ADD 1 COPYTO 2 BUMPDN 0 JUMPZ b JUMP f
Alternative solution[edit]
This solution uses 103 moves.
JUMP g a: OUTBOX INBOX JUMP f b: c: d: COPYFROM 1 e: OUTBOX f: g: INBOX JUMPZ a COPYTO 0 COPYTO 1 COPYTO 2 INBOX JUMPZ e SUB 1 JUMPN h ADD 1 COPYTO 1 COPYTO 2 BUMPDN 0 JUMPZ b JUMP i h: ADD 1 COPYTO 0 BUMPDN 0 JUMPZ c i: j: COPYFROM 1 ADD 2 COPYTO 1 BUMPDN 0 JUMPZ d JUMP j