# 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 -
> SEQUENCES ARE ZERO-TERMINATED
> READ A SEQUENCE FROM IN
> WRITE THE SUM TO OUT.S
> WRITE THE LENGTH TO OUT.L


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

MOV <src> <dest> //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.
<label>: //defines a label (for jumps)
JMP <label> //jumps execution to label
JEZ <label> //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
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
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
if ACC is 0, then GOTO END
swap ACC and BAK
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:

1. Your temporary storage node can be simplified to:

MOV RIGHT RIGHT


This is a valid instruction and saves you one instruction.

2. 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
JMP L        # Loop
EZ:          # End of sequence
SWP          # Restore counter
MOV ACC DOWN # Output
SUB ACC      # Clear ACC

3. 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
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!

• Did not know that MOV RIGHT RIGHT is valid, I thought it would be writing to a pipe that still contains an incoming value. I spotted #2 myself after a few minutes (I say few but it's more like 15)... and as for #3, that's brilliantly spotted. The new solution runs in 253/6/22 and I could probably cut a node by making the summer MOV ACC RIGHT as well. – Pimgd Jun 7 '15 at 18:38
• Are blank lines free (Like L:\nMOV...)? – Pimgd Jun 7 '15 at 18:46
• @Pimgd I'm pretty sure they are, but feel free to move the lines following a label into the line with the label. – TimWolla Jun 7 '15 at 18:47
• It’s also possible to reduce the solution to only 4 nodes (my first solution), wasn’t the fastest though. I somehow tend to use as few nodes as possible, same in SpaceChem ^^ – max-m Jun 7 '15 at 19:07
• @Pimgd Empty lines and labels don't add you your instruction count, but they do consume precious space (i.e. the 15 lines of text you can have per node) – Grant Peters Jul 3 '15 at 4:36

In line with the above statement about optimizing for different methods, increasing node count to decrease cycle counts is a valid approach to lower your metrics.

I have to confirm it, but I believe instructions and cycle counts are separately tabulated for just this reason. In fact, I think that in 1 cycle, you can run many instructions so long as they are distributed and run in parallel. Thus, you can try to bring one or the other lower in any of your three approaches for cycles, instructions and node count.