Counting Sequence Length in TIS-100 I picked up a programming game, TIS-100. Programming manual can be found on Steam as well, but I have described the relevant syntax in my question.



Basically, you're dealing with some old machine that uses its own variant of assembly. It's a gamification of learning assembly, almost.

The machine consists of nodes. Each node has pipes (UP LEFT DOWN RIGHT) that it can write and read from. When a pipe is read from, the value in the pipe disappears. It also has two registers, ACC and BAK. BAK can only be accessed with the SAV and SWP opcodes. Each node has its own code that it executes. This code is limited to 15 lines of 18 characters per node.

I've already solved this level. The goal is counting sequences:

- SEQUENCE COUNTER -
&gt; SEQUENCES ARE ZERO-TERMINATED
&gt; READ A SEQUENCE FROM IN
&gt; WRITE THE SUM TO OUT.S
&gt; WRITE THE LENGTH TO OUT.L


Short syntax run down (based on commands I used):

MOV &lt;src&gt; &lt;dest&gt; //moves from source to destination. Blocks if source is a pipe and doesn't have a value available. Blocks if dest is a pipe and already has a value.
ADD value //adds to ACC
&lt;label&gt;: //defines a label (for jumps)
JMP &lt;label&gt; //jumps execution to label
JEZ &lt;label&gt; //jumps to label if ACC = 0. JumpifEqualsZero
//there's also JumpifNotZero (JNZ), JumpifGreaterZero (JGZ), JumpifLesserZero (JLZ).
SAV //MOV ACC BAK
SWP //switches values of ACC and BAK


The game describes it like this:



My program is a bit unwieldy to post in full, so I'll limit it to the three main nodes.

This is the node responsible for counting the sequence length:

S: MOV LEFT ACC
JEZ E
SWP
ADD 1
SAV
JMP S
E: SWP
MOV ACC DOWN
MOV 0 ACC
SAV


This is the node responsible for summing sequences:

S: MOV UP ACC
JEZ E
MOV ACC LEFT
SWP
ADD LEFT
SAV
JMP S
E: SWP
MOV ACC DOWN
MOV 0 ACC


And this is the node I abuse as temporary storage:

MOV RIGHT ACC
MOV ACC RIGHT


What I don't like about my code is that it doesn't read very well.

The sequence counter goes like so:

START
read value to ACC
if ACC is 0, then GOTO END
swap ACC and BAK
add 1 to ACC
write ACC to BAK
GOTO START
END
swap ACC and BAK
write ACC as output
set ACC to 0
write ACC to BAK


There's duplication in here, where no matter if you are in the then or the (implicit) else case of the JEZ, you first swap ACC and BAK. Additionally, I'm abusing "swap set write" for altering BAK, but maybe that's the shortest way there is.

For the sequence summer, I don't like how I'm abusing a separate node just for temporary storage.

It works without errors.



For reference, these are histograms showing the scores of people on levels, with mine highlighted via arrow:
Unfortunately my hard drive containing my savegames crashed yesterday, so I cannot look up my solution, but I can say that the things you consider ugly are because of the limitations of that old computer system. I am abusing nodes as temporary storage all the time and my solution pretty much looked the same (if I remember correctly). As the histograms show you are not that bad (especially on cycles).

We can optimize your solution in terms of # of instructions and maybe cycles as well, though. I am focussing on optimizing the existing algorithms, instead of creating a new program. I could not test my optimized solution, because I don't have Steam on this box, but they should work none-the-less:


Your temporary storage node can be simplified to:

MOV RIGHT RIGHT


This is a valid instruction and saves you one instruction.
I only save my ACC just before it would get overridden. This removes some duplicate code (namely at least one SAV in your counter) and simplifies control flow. My rewritten algorithm is one instruction less than yours:

L:
SAV          # Save counter
MOV LEFT ACC # Next item
JEZ EZ       # End of sequence
SWP          # Restore counter
ADD 1        # Increment
JMP L        # Loop
EZ:          # End of sequence
SWP          # Restore counter
MOV ACC DOWN # Output
SUB ACC      # Clear ACC 

BAK is not needed in your summing node. You only need the value from your temporary storage node and the new value. Some reordering of instructions allows you to directly add the saved sum to the new value. I again saved the ACC in the very last moment:

L:
MOV ACC LEFT  # Save sum 
MOV UP ACC    # Next item
JEZ EZ        # End of sequence
ADD LEFT      # Add sum 
JMP L         # Loop
EZ:           # End of sequence
MOV LEFT DOWN # Output sum 
SUB ACC       # Clear ACC


Getting rid of BAK saved us 3 instructions on this one!




Conclusion: Absolutely abuse the instruction set (e.g. my first bullet point) and possibilities of the game (storing values in the pipes) to achieve good scores in the different metrics. Don't try to optimize for everything, you have got three saves per level!