revisiting EXAPUNKS part 1 (for real): tutorial

ok now (probably) im ready to get started, i think in this post ill try and just blow through the tutorial levels and give an idea of how this all kinda works. also im not gonna give a full story overview but ill have sparknotes on how we get where we get

opening cutscene: A person named Nivas shows at your door, says you look really sick and they can get you the medicine you need, but it costs $700 a dose (yes, this is also HRT). You then go to your "job" (manually copying receipts into a computer for a pitiful pay (you make $0.10), and then someone named Ember appears in a dialog box on your screen and remarks on how you will never survive at this rate. She offers you a deal: if you start hacking again, she can get you 1 dose per hack you do for her. Then, Ghast (my fucking goat love this guy) appears at your door and gives you a copy of TRASH WORLD NEWS, a zine he makes on hacking to keep the knowledge alive (yes, this is the manual for the game). Then, task 1 opens.

LEVEL 1: TRASH WORLD NEWS (1)

this is as easy as the levels get, requiring you to simply take your EXA, grab file 200, and move it to OUTBOX. As long as you grasp the basics of moving the EXAs, there isn't much to the optimal solution. For movement, the way it works it that each "host" (the little squares) has links between its neighbors with numbered labels (usually 800 to go forward, and -1 to go back). So long as you use LINK N where N is a valid link, the EXA will move without issue. Additionally, EXAs self-destruct when they reach the end of their programming, so you dont need to worry about cleaning up after.

The solution I am going with here is:

LINK 800

GRAB 200

LINK 800

Once again, little room for optimization, just learning the basics

LEVEL 2: TRASH WORLD NEWS (2)

Another level for learning the basics, this one making sure you understand the math operations using EXAs. It asks you to add the first 2 values of file 200, multiply it by the third, and then subtract the fourth, and write the output to the end of file 200 and moving it to the outbox. None of this is too difficult, but one thing to remember for optimizing this is that you dont need to use temporary values much, and many of these operations can be combined to save on both cycles and size. An easy first solution to come to might be:

LINK 800

GRAB 200

COPY F X # write the first value of F to X 

ADDI F X X # add the next value of F to X and write it to X

MULI F X X # multiply the next value of F with X and write it to X

SUBI X F X # subtract the next value of F from X

COPY X F # copy the final value from X back to F

LINK 800

And while this works, an important thing to remember is that every time you read from the F register, if moves forward, so you can save a lot of time by doing this:

LINK 800

GRAB 200

ADDI F F X # add first two values of F and write it to X

MULI F X X # multiply the next value of F with X and write it to X

SUBI X F F # subtract the next value of F from X and write it to F

LINK 800

With this, both the ADDI and SUBI lines take advantage of this interaction to cut out the COPY instructions, and reach the optimal solution.

LEVEL 3: TRASH WORLD NEWS (3)

This one is not as straightforward, but still not crazy. It asks you to navigate to file 199 and pick it up, and then create a new file in the outbox that contains the same 2 values as 199, but with the order flipped, and then delete file 199. Also, this level does require a couple of strategies to cut down on just 1 cycle or two. The basic solution is as follows:

EXA 1

Navigate to file 199

Write both values in to the M register

Delete file 199

EXA 2

Navigate to outbox

Make a file

Read both values from the M register, and flip the order before writing them (store the first in X, and write it later)

However, 1 important note about writing to the M register is that it takes 2 cycles at minimum, while most instructions only take 1 (1 to prepare the register, and one to actually send), and thats if it doesnt need to wait for an EXA to read it. Because of this, whenever using the M register, we should be careful to make sure the EXAs are synced well so it does not slow down the rest of the program. With this in mind, we actually have EXA 2 make the file as its first instruction, that way it is synced properly and does not need to wait for EXA 1. The final code looks like this:

EXA 1

LINK 800

LINK 799

GRAB 199

COPY F M

COPY F M

WIPE

EXA 2

MAKE

LINK 800

LINK 800

COPY M X

COPY M F

COPY X F

And this optimizes for cycles and size, but wait! Activity is 4, but the top percentile got 3? How is that possible! The main source of activity in a program is moving between hosts, which adds 1 activity each time, and since we have 2 EXAs, each of which LINK twice, we have 4 activity. How can we fix this? It's gonna need a different solution, but the REPL command is what saves us here. The REPL command makes a copy of the EXA in the current host, which means if we set the code up right we can have our 1 EXA move into the first host, clone itself, and then the 2 EXAs will split up, leaving us with only 3 activity! By simply restructuing our code a little bit and adding a MARK command to create a label and a HALT command so our EXA stops before it enters the code for the clone, this is our solution to optimize activity:

LINK 800

REPL READ_DATA # Clone after linking into the first host

LINK 799

GRAB 199

COPY F M

COPY F M

WIPE

HALT # Halt the program, otherwise it will continue into READ_DATA

MARK READ_DATA

MAKE

LINK 800

COPY M X

COPY M F

COPY X F

Due to taking an extra cycle to perform the REPL and the extra lines, cycles and size are slightly larger, but now activity is a 3, meaning each metric has been solved for.

LEVEL 4: TRASH WORLD NEWS (4)

The last tutorial level, this one asks you to do a simple loop. Given a number N (read from file 200), create a new file in the outbox containing the integers from N to 0 and delete file 200. This is a fairly easy level, but optimizing it utilizes a handful of techniques that are very important later on for shaving off cycles. The simple solution is as follows:

LINK 800

GRAB 200

COPY F X

WIPE

MAKE

MARK LOOP # Start of loop

COPY X F

SUBI X 1 X # Write to F, and decrement X

TEST X > -1

TJMP LOOP # If X > -1, jump back up to LOOP

LINK 800 # Move to outbox and end the program

This works, but puts me smack dab in the middle of the pack, with a ton of room to go for reaching the top percentile (In cycles at least, which is the important one)

So lets try out the first method: Counting using T!

Yes, T is used for testing values and getting a true/false from that, but you can still add and subtract from it the same way as X, and TJMP/FJMP work solely based on whether or not T = 0, not whether TEST has been used. Therefore, if we use T as the value to decrement, then we can keep the TJMP logic, except we can cut out the TEST statement entirely!

LINK 800

GRAB 200

COPY F T

WIPE

MAKE

MARK LOOP

COPY T F

SUBI T 1 T # hehe tit

TJMP LOOP # If T != 0, jump back up to LOOP

COPY T F # Need to add this because the loop ends before writing a 0

LINK 800

This brings us down to 305 cycles, which is an improvement, but the top percentile is less than half that! So, whats this secret strategy to cut off 170 cycles? Its called "unrolling the loop". You see, doing JUMP commands aren't free, and they take a whole cycle to execute. Therefore, our loop is only writing 1 number ever 3 cycles, and we can do way better than that. Using the @REP command, we can easily copy code to drastically increase how much we write during each loop. For example:

MARK LOOP

COPY T F
SUBI T 1 T

TJMP LOOP # Writes once every 3 cycles

MARK LOOP

@REP 10

SUBI T @{0, 1} F

@END

SUBI T 10 T

TJMP LOOP # Writes 10 times every 12 cycles

The problem this runs into, though, is that we dont check T every cycle, so we would go over if T is not a multiple of 10. This is solved with multiple loops of descending size, but now we go back to using the X register

MARK LOOP10 # Named for size

TEST X < 10

TJMP LOOP1 # Not shown, just a regular loop

@REP 10

SUBI X @{0, 1} F

@END

SUBI X 10 X

JUMP LOOP10

Using this technique, we can write way faster, decreasing our cycles hugely. Now it simply becomes a problem of choosing the correct amounts for each loop, as we have a limited amount of space in each level (50 for this one), and these unraveled loops take far more space. With some trial and error, however, and a couple of extra optimizations to snag an extra cycle or two, we come to this for our solution:

LINK 800

GRAB 200

COPY F X

WIPE

LINK 800

MAKE # Simple start, nothing of note here

MARK LOOP23 #Trial and error show 23 is the optimal amount for loop 1

TEST X < 24

TJMP LOOP5

@REP 23

SUBI X @{0,1} F

@END

SUBI X 23 X

JUMP LOOP23

MARK LOOP5 #Combining the 23 with a 5 ends up getting minimum cycles

TEST X < 6

COPY X F # Sneaking an extra copy in here where we know X > 0

TJMP CONTINUE

@REP 4

SUBI X @{1,1} F

@END

SUBI X 5 X

JUMP LOOP5

MARK CONTINUE #Simple loop, move X into T for faster loop time

COPY X T

MARK LOOP1

SUBI T 1 T

COPY T F

TJMP LOOP

With this crazy solution, we use all 50 available lines and get a cycle count of 136, slightly lower than the top percentile of 138! One extra note is that this is not a good solution, and a much better and more scalable solution would be using more EXAs and the M register to write more/cycle, but this works just as well if not better at our scale, and trying out the M register is a problem for another day. 

One last quick additional optimization because I saw the light: the second solution (Using the T register) was 11 lines, but there is a solution in 10. The reason I think this isn't too bad is because there is a kind of useless line in there, because of issues with logic.

LINK 800

GRAB 200

COPY F T

WIPE

MAKE

MARK LOOP

COPY T F

SUBI T 1 T 

TJMP LOOP 

COPY T F # The TJMP exits before writing 0, so this is the fix

LINK 800

If I switch the order of the lines within the loop, then the opposite problem occurs where it subtracts before writing, meaning it writes the 0 but it starts at N-1 instead of N. However, if I read from F and increment it by 1, then that counteracts this affect and the solution works. This modified method is slightly slower (due to needing another loop to complete each run), but we are optimizing for size here, not cycles. With these changes implemented, this is what we get (bolded lines are altered):

LINK 800

GRAB 200

ADDI F 1 T

WIPE

MAKE

MARK LOOP

SUBI T 1 T 

COPY T F

TJMP LOOP

LINK 800

And with that, all 3 metrics have been optimized to the top percentile! But I will be back for that M register solution...

END TUTORIAL

This is where I'll call it for now, I spend a lot longer on this (really just level 4) than I anticipated, but I love optimization so much I can't wait to take this to the real levels and destroy any semblance of confidence I have in myself :3

previous entry here