35
\$\begingroup\$

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.

A cool programming game

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:

quick reference

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.

It's running

For reference, these are histograms showing the scores of people on levels, with mine highlighted via arrow:

stats

\$\endgroup\$
19
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Pimgd Jun 7 '15 at 18:38
  • \$\begingroup\$ Are blank lines free (Like L:\nMOV...)? \$\endgroup\$ – Pimgd Jun 7 '15 at 18:46
  • \$\begingroup\$ @Pimgd I'm pretty sure they are, but feel free to move the lines following a label into the line with the label. \$\endgroup\$ – TimWolla Jun 7 '15 at 18:47
  • \$\begingroup\$ 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 ^^ \$\endgroup\$ – max-m Jun 7 '15 at 19:07
  • \$\begingroup\$ @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) \$\endgroup\$ – Grant Peters Jul 3 '15 at 4:36
2
\$\begingroup\$

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.

\$\endgroup\$

protected by Jamal Aug 20 '15 at 19:20

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.