Zachtronics made another programming game - this time about distributed parallel assembly programming, which is basically programming but without all the tools that you use to make programming not super hard.
Your compute units are these little robot things which can navigate a network, but each one only has two registers + an array pointer, and they only have two buses to communicate - one local to a node, and one global. Also, reading from the bus always clears it. So most of the challenge of the game is figuring out how to get your ‘EXAs’ to talk to each other in the right order, without grabbing a message intended for a different EXA. The rest is trying to juggle more information than you have space for!
As it turns out, that’s really fun. And I enjoyed the whole hackers theme a lot; the story was tropey but neat.
This game isn’t nearly as amenable to cool-looking GIFs as Infinifactory was, but I thought this one - my solution to the final level - was neat! And I wanted to talk about it, not because it’s a particularly unique solution to the level but just to illustrate how this game is to play.
What it’s like to solve an EXApunks level
In this level you have to get the hostnames and values of the ‘hardware registers’ (the #NERVs) and sort them. The problem is that you have no foreknowledge of the layout of the network (it’s different in each run), and in each node, the only way to discover outgoing links is to try them and see if your EXA dies.
So the first problem is to get the register values back to your local host, then you need to sort them. Each host in the tree can be linked to up to four other hosts, with the connection values 3, 1, -1 or -3. The only thing I know is that if you go to a host with a link X, then the link back is always -X.
My first approach was to send out exas to just spread through the network and report the hostnames and register values to the global bus. The algorithm would go:
an EXA would arrive in a node with the link to the previous node in its X register
for each of the sequence of 3, 1, -1, -3 it would test if that value is equal to X; if it’s not, it would copy that value to its T register and spawn a duplicate EXA
each spawned EXA would link the value in its T register, then multiply it by minus one and copy it to its X register, then jump to the previous step
And it was cool! The EXAs would spread out in a wave and soon I’d have one EXA on every node. The EXAs could check if there’s a #NERV hardware register; if there wasn’t, trying to copy from it would kill the EXA. Then they’d copy the hostname and #NERV value to the global bus.
The problem was that if two exas happened to take the same time to reach a host - for example if one EXA went down a path 3, 1, and another went down a path 1, 3 - they’d be reporting back at the same time, and their results would get unpredictably mixed up. So instead of writing down
I’d end up getting something like
or worse have them mixed up further, with no reliable way to tell what I got.
So I resorted to a new plan: now I’d send out the EXAs in a wave to map out the network, and then walk back up the tree. I spent a lot of time trying to work out a way to make each EXA take a unique amount of time to report back, but couldn’t think of anything that would work.
So then I settled on the solution above. Now, each EXA when it arrives at a new host creates a file and writes three of 3, 1, -1, -3, skipping over the one in its X register.
Then, for each value in its file, it would spawn an EXA which would try linking that number, then if it survived, immediately link back and report to the local bus. The first EXA would test if anything is reporting on the local bus; if nothing does, it would delete that entry from its file. The spawned EXA would then go forward again, and start exploring its node.
The result was that I ended up with an EXA in each host with a list of links to the next hosts in its file - essentially a distributed map of the network.
The question then was, how could I get this information back to my own host?
At first I thought about having each ‘leaf’ host - hosts with no further outgoing links - copy down its values and then go back up a level of the tree and copy its values to the local bus. The waiting EXA on the next level up would wait for all its ‘children’ to report back, then append its own host data and go back up to the previous level. I’d ‘contract’ in a way that followed my earlier ‘expansion’.
The problem was that the logic for counting down all the returning ‘children’ got very complicated, and there was a danger that another child would return while in the middle of copying down one child’s data, which would mess everything up. Also, all the data would have to get copied several times over.
Then I considered having each non-leaf EXA, after spawning its children, go to each child’s node and copy down the information there. The logic once again got very complicated - I can’t remember at what point I abandoned that method.
Finally I hit on the idea of having a second EXA at the start wait a certain amount of time to allow the other EXAs to map out the tree, then follow the map around to visit each host.
Each EXA would copy down the hostname and #NERV value if it existed, then seek back to the beginning of their file, and start copying it to the local bus. It didn’t have to have any logic except to copy its X value (containing the link back to the previous node) after it reached the end of its file! The ‘followup’ EXA would arrive at a host, and if it was given a number, it would follow that link; if it received a string token, it would copy down the two values and then link the node it was given.
Before this ‘followup’ EXA sets out, it spawns a second EXA which puts the value -1000 on the local bus. When the ‘followup’ EXA arrives home, it knows that because it received the value -1000 that it’s home, and can move on to sorting.
So first the map nodes spread out into the tree, then the followup EXA uses the map to visit every node, then returns to the host... it turned out to be surprisingly simple!
Then the followup EXA sorts the list of hostnames and #NERV values by bubble sort (since I figured it would be easiest to implement in fewest lines of code, and speed wasn’t that important). Bubble sort was slightly fiddly because I had to use another EXA as a temporary variable store, but that was the easy part all the same.
It’s certainly not the optimal solution to this level - someone apparently managed it in about 30 lines of code, which is astonishing - but eh, I’m proud of it.
I need to program more often!
