Part 6: Euclid's Pizza

Part 6 - Euclid's Pizza

Thanks for all the posts about optimizations! What I'll do is discuss them in the first part of new updates. If you like to nerd out about that and get a deeper comprehension of the code, read on.

I will try to explain all the submissions as clearly as I can. Even if you're not that familiar with programming, give it a try! Perhaps my explanations help.

In this part, I need to go into quite some detail as your ideas introduced a lot of new concepts.

If you want to skip past all that because you're here mostly for the plot and new puzzles, search for the next occurrence of the word "pizza" in this post.


=== Trash World Inbox ===

Alright, before we dive into your suggestions, let's jump back for a moment to Tutorial 3.



In my original solution we got it down to 9 cycles, with size 12 and activity 4. Now that we have the full language reference, we can get the activity further down.



The solution is the REPL command. It replicates the EXA, and the replicated one starts processing from the given label (in this case WRITER).
By doing this after the first LINK, the total number of LINK operations is reduced to 3.





Here is the simulation just after the REPL instruction. You see the new EXA has the same name as the old but with a number appended. And it starts executing below the WRITER mark, while the original EXA just continues below the REPL instruction.

I realize now I named the mark wrong - the 'writer' actually does the reading. Oh well.



We got the activity down to three, but the cycles and size increased a bit. If you're wondering why that says "Unchanged", it's because I tend to run the simulation multiple times trying small tweaks and it only compares your new score to the last run.

I could've put a HALT instruction just before the WRITER mark. It's not really necessary. After its last copy to F instruction, the original XA will skip the MARK (which doesn't take a cycle), try to execute LINK 799, find there's no 799 link id from its current position, throw an error and explode.

Errors that destroy an EXA can be surprisingly useful, the Zine even has a page on it. I'll show it below when we get to the new assignment.

Using a HALT here has some limited use - destroying an EXA through an error takes two cycles (one to show the error and one to explode), while a HALT does it in one. So adding a HALT would save one cycle but also increase the size by 1.

Either way, we don't need to do this because since each score is tracked separately, with the original solution and the REPL solution combined, we got the best score in each of the histograms now.



And with that, let's go to Tutorial 4 and the optimizations y'all sent in.

Looks like I'll have to go into a lot of detail this time because you chose some strategies we haven't seen at all yet.

Yes, so what you need to know for this is that TJMP activates for any non-zero value of T, not just 1 (while FJMP only activates on 0). That is: any non-zero value is considered "True".

Changing this solution from the last update...



... to this solution.



This drops the cycle count from 406 to 304.

Basically what this is doing is, it subtracts 1 from the value in T every loop, then if T is still greater than 0, it jumps back to LOOPSTART. The final COPY is necessary to get the required zero at the end of the file.

Doing the same with the one-EXA solution gives us a count of 305 by the way.

This one starts by storing a value that's one higher than what we need. Since that can be done in a single ADDI instruction that replaces the COPY, it doesn't change the size. silentsnack reordered the loop so the SUBI happens before the COPY. That way we still write the correct values to the file - but we're still inside the loop when T becomes zero, so we write the zero to the file as well. That extra copy operation is no longer necessary and the size drops to 10.

We've now minimized both the size and activity - all that's left is the cycles and since we don't care about size or activity anymore we can use every ugly trick you can think of.

I think silentsnack explains this one quite well. In my own words: it writes two values to the file every loop. E.g, if the value in T is 10, it writes 9, 8 and then updates T to 8. However, because you're only testing every 2 values, you'd run into trouble handling odd numbers. You'd check T at 1 (which is True), then next loop, T contains -1 (which is also True), and the loop would never end.

This is handled by splitting the code into two and using a MODI operation to find if the number is even. MODI X 2 equals 0 for even numbers, 1 for odd numbers. Since the MODI operation is done on the original value + 1 (there's an ADDI on the fourth line), it becomes the opposite so we have to jump to EVEN if the value is 1 (= True). In that case one more is added to the value to make sure the loops exits correctly, then SEEK -9999, VOID F is used to delete the first value of the file, which was one too high.

So, for each test run it runs EITHER the even, or the odd code. Never both in the same run.

Meanwhile, Quackles was working on a slightly different solution.



Here is Quackles' actual program. It looks different from the code example in their post and I'll get into why that is in a bit.

The lines starting with a ; (semicolon) are just notes, like the NOTE "instruction". They help us understand the program but the EXAs ignore them entirely, their size is 0 and they don't take up any cycles.

First, let's dig into how it actually works.

It uses two tricks:
- The first is "loop unrolling". Instead of doing jump instructions we just repeat the code of the loop a bunch of times. Since each jump instruction takes a cycle, this can save a lot of cycles in a simple, but ugly way. In fact, silentsnack's solution did this as well by putting 2 steps in every loop.

Loop unrolling is actually a common optimization technique in real programs, although usually the programmer doesn't have to think about it, because the compiler is programmed to make an informed decision when this is worth it and changes the compiled program on the fly.

You see both of the loops (The loops starting with the TIMER and TIMER2 marks) are repeated 8 times and then use a jump. It would work just as well, and save even more cycles, to repeat them more times before the jump, as long as you have a way to stop looping once the file is written. But, doing so would push the size over this assignment's limit of 50. Submitting a solution like that counts as finishing the assignment - but is not eligible for the leaderboards at all. So we have to stop at 8. Still, that means you save seven out of each eight jump cycles, a huge improvement.

- The second improvement is using two EXAs, made through a REPL instruction. REPL copies all code, the state of the X and T registers, but, importantly, NOT the file the original is holding.

The first EXA loops through TIMER and checks every step if T is zero (in which case it jumps to BAIL). The second EXA loops through TIMER2, copying a new value to the file every step. It has an unconditional JUMP so it would loop forever.

This takes less cycles than the previous solutions because each 'loop' is only two cycles (SUBI / FJMP for the first EXA and COPY / SUBI for the second, as compared to the three-cycle SUBI / SUBI / TJMP originally.)

It does mean you have to stop the infinite loop somehow, and that's what the first EXA is for. As soon as T hits zero, it jumps to BAIL.
It then has to wait for a bit to allow the second EXA to write the last zero. Since it has to wait anyway, it can use this free cycle to WIPE the original file it was still holding, and then it uses KILL to kill the other, infinitely looping EXA, after which it HALTs itself.

The NOOP instruction turns out to be necessary in case the starting number is divisible by 8 - then the second EXA needs one more cycle before it writes the 0 because it's jumping back to TIMER2. It does no harm in other cases because the second EXA spends the additional cycle doing a harmless SUBI to T.

The final result is 219 cycles, 48 size (but who cares) and 3 activity (since KILL counts for activity).

Now, to go back to Quackles' actual code example.



We haven't seen the @REP 8 and @END instructions before, they aren't explained until the second edition of the Zine. They are macro instructions. In short, that means they tell the compiler to rewrite the code in some way before the program even starts. @REP 8 means that the lines of code following that instruction until the @END instruction, should be repeated 8 times. That is, it does the loop unroll for you.

REP macro instructions take up no cycles (since they are done before the program even starts), but they cannot make use of any registers or other variables (since they are done before the program even starts), only hardcoded numbers.

You also can't use REP to cheat the size limit - it counts the size after unrolling. In fact, as soon as you press run on this code, EXODUS will show the code after the REP instructions are processed, which is the screenshot I used to explain the solution above.

So, REP can't win you any cycles or size - the only thing it really does is save you from copy-pasting a bunch of code, making the result a bit easier to read.

Let's go to the next improvement silentsnack came up with:

The SUBI T @{1,1} F line is a special syntax you can use together with REP. The @{1,1} is substituted by a number at runtime. The initial value will be the left number (1 in this case), then every next value will be the previous one increased by the right number.
In other words, this unrolls into
And so on.

Anyway, this is a very neat solution. It starts the same as their last solution but then it does a MODI X 8 T. T now contains the remainder of dividing the original value (plus 1) by 8. Then it deletes the remainder from X, meaning X will now contain a value that can be divided by 8.

If the remainder was already 0 it skips a step and jumps directly to EVEN. Else, it gets into LOOPA, where it writes the sum of the remainder and X (so the original value) to the file, reduces the remainder by 1, and repeat. In this loop you write all the values above the current value of X.

After that, whether working through a reminder was necessary or not, the program goes to MARK EVEN and writes 8 values to the file per LOOPB cycle. We know for sure the test will trigger at the right time because we made sure to not go to this loop before the value is divisible by 8.

Finally, Quackles submitted this solution:

It is indeed quite similar to the previous one, just handling the remainder at the end instead of at the start. And perhaps the TEST X > 7 is a bit easier to read than a test based on MODI.

As silentsnack said, you can easily change the size of the loop by changing the 8s. That works in either of the solutions. I played around a bit with that and it looks like 8 is optimal. For both solutions you can't go too high because the code can't handle an initial number smaller than the loop size. And other loop sizes speed up some tests but makes the slowest test run (which is used for cycle count) slower.

Theoretically you could start with another split in the code path, to use a larger loop for larger initial numbers only. But that means you need at least two unrolled loops, probably pushing the size past the limit. And no matter what you choose, you always run into cases where you need to handle the biggest remainder possible, which will take longer for larger batch sizes, so I don't think it's possible. And the community seems to agree with me on that, since silentsnack's 143 cycles solution is the best anyone's gotten.




=== Euclid's pizza - Order System ===

Nice work.
I knew you could do it.



Looks like everyone was so busy optimizing code that they forgot to vote. No worries, I'll use my trusty three-sided dice again.

Stop that.

But you're awesome!
This is more talk designed to further excite your prefrontal cortex.
Now it's time to do some real hacking.

Finally.





I could use some pizza. How're we gonna do that?

So you want to know who I am.
I will reveal this information.
Let us discuss it over a pizza...
A free pizza.
I want to see you use your regained skills first.



Okay.

Great.
I am looking forward to this.


New OST: Code and Registers

This actual business system already looks a lot more complicated than the tutorial assignments.

Our assignment is:
- Append your order (file 300) to the end of the order list (file 200)
- Note that all orders, including yours, will consist of exactly five keywords.



While we're here, let's poke around in their files a bit.

I'm not entirely convinced those are actually the Pythagorean Theorem and Zeno's Paradox but what do I know...



Anyway, I have to copy the data from our file 300 and add it to the end of their file 200. Doesn't sound too complicated, let's get started.



The first EXA grabs the file with our order, and sends the data one by one over the M register.

The second EXA goes into the order system, grabs the file with their orders list, uses SEEK 9999 to jump to the end of the file and writes the data from M to the file.

I don't even need to bother destroying our file 300, since it's sitting in my home host, it doesn't count as leaving a trace.

Of course, I could use a loop and loop 5 times over a single copy command. But that would involve:
- Keeping a counter that is increased every round, then checked every round, and then a conditional jump, and a mark for the jump to go somewhere.
- Or a check in XA if it's at the end of the file, in which case it tells XB to die, which is also a bunch extra logic.

If you read through the Trash World Inbox section of this update you've seen that sometimes, repeating code is the simplest solution, and it's the case here too.



As it turns out, this is actually the best solution possible for this assignment. The loop solutions require so much setup that they require as much lines of code, while costing more cycles. I'll take it!

Before we continue, what's that on the right side of the simulation?

You might've seen on page 7 of the Zine, those things such as #POWR are hardware registers. They're a way for EXAs to communicate with external hardware directly. In this assignment I don't need them, but we can certainly mess around with them.

Those #TEMP ones have widely different initial values. I guess one is just the room thermostat, one is for the freezer, and one is for the oven? The first #POWR register is for the lights, I don't know what the second one is for.

No, I can't put the place on fire, apparently there's limits on the #TEMP registers. But there is a Steam achievement associated with this assignment.



Flipping the lights on and off like this nets me the achievement PIZZA_PARTY: Throw a rave at the pizza parlor.

Time to enjoy pizza!
For you at least.
I'm not going to have any.
Guess why.



Uhhh.. you're far away?

I am an AI construct.
You know. Artificial intelligence.
Surprised?



Where's the option "I saw that coming a mile away"?

A little.

A little.
Okay.
I'll have to remember that.



Yeah, the zine is kinda nice, isn't it?

Speaking of, there's an interesting page about runtime errors.



So, a runtime error is completely different from a compile error, which we've seen before. An EXA with a compile error won't even run until you fix it. Compile errors often come from incorrect syntax. But a runtime error is using correct syntax in the wrong place. For instance, trying to GRAB file 200 while that file doesn't exist, or LINKing to a host that doesn't exist. If you do so, the EXA that tried to run that instruction is immediately destroyed, but at least you know that that file or host isn't there.

If you want some homework, consider how we could make use of this. We'll see it soon enough in future assignments though.

Anyway, looks like my pizza is here.



Pizza delivery...

It's Nivas again, except this time they're wearing a Euclid's Pizza uniform.
"Euclid's- a better pie, and we can prove it!"
The reference seems kind of obscure for a pizza joint.

Don't look too surprised.
I'm an independent operator. I handle a wide range of businesses.
Economy like this, you gotta hustle.
So here's your pizza... and here's your "other" package. I hope it helps.

Nivas hands me an unlabeled prescription bottle. It's clearly a knock-off.

Good work getting that money together.
If there's anything else you need, you know who to call.

Nice! Free pizza, and the first batch of the medicine. Exactly what I need.

Let's see what Ember has to say about that.

So about that left arm of yours.
The medicine stops your condition from spreading, but it can't fix things like that.
You'll need to take care of that yourself.



This choice seems a good place to end this update. Feel free to vote.