EXAPUNKS

byCarbon dioxide

Part 5: TRASH WORLD NEWS - Tutorial 4

Part 5 - TRASH WORLD NEWS - Tutorial 4

The last of the tutorial assignments! Let's jump right into it.

How do you feel about it now?
You're closer to the goal.
Any change?

The votes were more divided this time. One for Not really and two each for the other two options. I did a pseudorandom toin coss to settle the tie.

I feel like I'm in a study.

Sure, think of it like that.
Everything's an opportunity to learn.
Anyway, there's just one more tutorial to go.
You're almost there.

Meanwhile in the chat:

Yeah. "Don't touch the poop", as they say.

Sounds like a useful thing to learn.

Yes. You can do it!
This is positive encouragement.
It is designed to increase activity in your prefrontal cortex.

Three votes for Don't count on it and one each for the other options.

Don't count on it.

But you're doing great!
There, a little more for you.
I'm sure it will help.

Well, whatever. Let's see the assignment.

OST: Getting Started

The Zine page for this assignment goes into loops and conditionals. These are a necessary component to make any programming language "Turing-complete", which basically means it can be used to write any arbitrary program.

We learn four new instructions. The first is TEST. It tests whether some comparison is true or not. What this page doesn't mention is that it can do checks with =, <, and > (is number A equal to, less than, greater than number B). If the comparison is true, it places 1 in the T register. If not, it places 0 there.

TJMP and FJMP go together: TJMP (jump if true) makes the EXA start executing elsewhere in the program, if T equals 1. Otherwise it just continues with the next instruction down the line. FJMP (jump if false) does the opposite: it causes the EXA to start executing elsewhere if T is set to 0.

It is not required to set T with the TEST command, you can just COPY or ADDI or whatever to T as well.

How does it decide where to jump execution to? Well, you need to add a label, and you can mark the location to jump to with MARK label. The example code in the Zine shows how it's done.

I think things will get more clear as I try to solve the assignment.

But I think this is a good time to bring up Compiler errors.

A compiler is a special program that translates human readable code (such as the EXA language we've been learning) into machine instructions that can actually be fed into a CPU. But it can only translate code that follows the syntax rules. Otherwise, it will give an error and you can't even run or test your program. That might seem like a bad thing but it's actually very helpful - it prevents a lot of bugs from making it into the final program.

In the case of EXODUS, any compiler errors are underlined in red and you can just hover over them to see the error message. The run buttons at the bottom are disabled until you fix all compiler errors.

Here, I hover over the 'instruction' MAGIC. Sadly, EXAs have no MAGIC instruction, and the compiler immediately tells me so. This is quite helpful when coming from another language, such as the one used to program chips by that automation company in Shenzhen you might've heard of.

In a similar vein, you can't jump to a label that isn't defined anywhere by a MARK instruction.

Anyway, back to the assignment itself.

Since this tutorial ramps up the complexity I'll try to take you step by step through my thinking process instead of just giving the solution all at once.

I first built the 'skeleton' of the code. I decided to go with two EXAs where one reads the file and sends data to the other who writes it.
XA grabs the file, copies the value into X, and then, as an example, forwards it to the communication register M and subtracts one for the next round.

Why use X as an intermediate? Because doing arithmetic such as SUBI directly on a file is very annoying. The file cursor keeps moving forward and is never where you want it to be.

Anyway, for now XB goes to the OUTBOX host and puts the value it gets from M into a newly created file.

Now, just copy-paste that subtraction-and-copy code 9 times and we're done, right? Not quite. Since the starting number is different for each test, that would never work. It would also make the program size huge. Let's write a loop!

I have two loops in place now. XA does the same it did before, but after subtracting 1 from X it checks if X is less than 0. If that is NOT the case, it jumps back to LOOPSTART. If it is, we know it's done (because it just sent 0 to the other EXA, then subtracted 1, so it's sitting at -1 now). It WIPEs the file and self destructs as it runs out of instructions.

Note that both the MARK instruction and the empty lines never use up any cycles. The empty lines help with code readability and the MARK is exactly that, just a bookmark. It doesn't "do" anything. The FJMP instruction does use a cycle, though.

XB has a loop too, and as you can see I named the mark LOOPSTART as well. That's fine - an EXA only knows about its own code, it won't suddenly start running another EXA's code. Anyway, this loop is very simple. It copies the value it gets from M into the file, and will do so repeatedly. Since there's no TEST, T is always zero, and FJMP will always make it jump back.

The resulting file is exactly what I need! However, XB gets stuck in this case. Once XA is done, the next COPY M F instruction in XB will wait forever for a message and never get one. So I need to do a bit more.

This should solve it. The loop in XB is now conditional as well. It only jumps back if X does not equal 0, otherwise it tries to run the next instruction, doesn't find one, and self-destructs.
Again I decided to use X as an intermediate because I run into the same annoyance of the file cursor being in the wrong place if I do a TEST on F directly.

Let's test the program.

Both EXAs are set up where they need to be, XA is about to send and XB is about to receive.

The EXAs are at their first TEST. Since for neither of them the test is true, they jump back to the start of the loop.

XA is ready to send the next number, which is one less than the last one: 8.

The loops repeat a whole bunch of times, writing a new number to the file every round, until only the 0 is left to write.

That's done now, and in the last loop, both EXAs' tests are now true, so the FJMP does not jump back to the loop, but causes the EXAs to finish.

And I'm left with nothing but the correct file.

As you can see we can do (much) better on every count. That's not surprising - there are many ways to optimize loops like this.

This is the test run data screen at the end. For every test run, it shows the number of cycles and the activity. You can see the cycles differs quite a bit. That's because the EXAs have to go through more loops if the starting number is higher. The value shown on the leaderboard is the worst value of all 100 test runs.

So, how can we improve this?

Let's start with the most straightforward improvement: We can drop the activity from 3 to 2 by switching to a one-EXA solution. Maybe that improves other stats too.

This EXA GRABs the file in the INBOX, copies the one value to its X register, then WIPEs the file and continues on to the OUTBOX. There it MAKEs an empty file, copies X into the file, subtracts 1 from X, copies that into the file, and repeats until X is less than 0.

This change improves all stats significantly.

And this was another idea I had. We keep two EXAs, however the first EXA only sends the individual value from the file to M, and the second handles lowering the value and writing it to the file repeatedly. Since the communication through M took a lot of cycles this is a huge improvement compared to the other two-EXA solution.

This solution uses 406 cycles, has size 13 and the activity is of course 3 again.

That's one cycle lower than the one-EXA solution but worse, size and activity-wise.

Luckily, the game keeps track of each leaderboard separately. So currently it says my best solutions have 406 cycles, size 11 and activity 2. You don't need to optimize all 3 in the same solution!

Anyway, apparently better solutions are possible. Some people solved it with size 12 and they got the cycle count under 200.

I'm not sure what they are. For the cycle count I suspect they did something like hardcode a bunch of COPY 5 F; COPY 4 F; COPY 3 F; etc. and then using a whole bunch of conditional jumps to decide where to start, avoiding the looping code altogether and requiring less TESTs overall.

Since we're out of tutorial mode now, I will make a follow-up post containing the full instruction sheet of the EXAs. We've seen most of them already anyway. Feel free to use that to suggest further improvements. Also, with that instruction sheet, perhaps you can figure out how to reduce the activity number in the previous tutorial.
If you're not that familiar with programming and don't get happy from reading instruction sheets, feel free to skip that post. You'll see the instructions in use before too long.

But before that, let's go check on Ember.

Nice work.
I knew you could do it.

And the intro to the next assignment.

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.

Next time... pizza, apparently. Please vote for both questions.