Counting Sequence Length in TIS-100

Question

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.
ADD value //adds to ACC
<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
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:

Answer 1

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
   ADD 1        # Increment
   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
   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!

Answer 2

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.