I played and finished TIS-100. I picked it up at the $1 tier in a recent bundle.
I’m not sure I’d describe the experience as fun, not the way Infinifactory is. It’s more that once I opened a problem, I couldn’t stop thinking about how to solve it until I’d actually finished the puzzle. It was more like scratching a series of itches than playing a game. Sure, there was some satisfaction once I finished a puzzle, but it was more like relief from irritation than actual pleasure.
After bouncing off Shenzehn I/O, I didn’t think I’d finish TIS-100. The two are fairly similar, in that they’re largely about parallel processing, but the TIS-100 processors are much more limited, which makes the nature of the solutions different. The TIS-100 instructions don’t include non-destructive comparisons. You can’t test X<Y, you have to code X=X-Y and test for negative, which means you’ve got to store X somewhere else first if you will need that value again.
The net effect was that for any sufficiently complicated problem, I was constantly looking for ways to store my variables. Generally 1 variable per processor, so if I needed X, Y, Length, Color, that was 4 processors each storing one value, and passing it out as needed. The “BAK” register can theoretically be used for this, but since it can’t interact with the main ACC register except to replace the value, it’s of limited use. You can’t, for example, compare ACC and BAK.
The one advantage the TIS-100 processors have is the Jump Relative Offset (JRO) instruction. That single ACC register is a severe limitation, so JRO <input port> means you’re passing information without having to load and overwrite the ACC register. It’s very common to have one processor directing the instruction path of another by sending one or more offsets for JRO’s.
It also results in what’s essentially very dirty code. If we think of individual TIS-100 processors as modules / functions / subroutines, they’re routinely messing with the internal workings of other functions. A minor change to a code snippet may require several offset corrections in adjacent modules. If this were a serious, commercial processor setup, this would be a maintenance nightmare.
By far the hairiest problem was the list sort problem. Given that sorting is an extremely basic task in most computing, even if you’re working with assembler as you do with TIS-100, it says a lot about the platform that implementing a sort is difficult. More, since random access is impossible, the best you can achieve is a bad sort - one that’s ord(n^2), rather than the usual target of ord( n log n ).
I did manage a “reasonably fast” solution, twice as fast as Matt’s, anyway. It’s an insertion sort. At any given time, the bottom stack module contains the top half of the sorted list, pushed in low-to-high order, and the upper module has the lower half, pushed in high-to-low order. Both stacks start with guard values (-1 and 999).
When I process a list entry, I look for an insertion point. If it’s smaller than the largest value in the bottom half of the sorted list, I move entries from the bottom stack to the top stack until I find a value that’s smaller. I then do the same with the top stack, if it’s larger than the topmost (smallest) value, I move entries from top stack to bottom stack. Either way, I can then push the new value as the new, smallest value in the top half stack.
When I get the terminating zero, I find the insertion point for zero, which of course always moves all the values into the “top half” stack. Then I copy that stack to the output point.
