TIS-100 | Programming puzzle game from SpaceChem dev & GAF's 77th Best GOTY 2015

I couldn't figure out an algorithm for OUT.E on the hidden puzzle so I tried hard-coding the values. I thought perhaps that might be the challenge for that puzzle or something. Just barely passed test 3 after about six hours of cobbling together a truly grotesque, bloated program, almost every node full...

Forgot about the random test at the end. lolol
 
Any tips on speeding up the sequence counter? It seems to do a quite common thing - keep a rolling total of a bunch of numbers (which you could do with just ADD UP or something) but needing to check for a terminator means I'm swapping things back and forth either to BAK or throwing it out to another node temporarily which slows things down a lot.

Also, bit of a shame you can't MOV ACC,LEFT and then later on MOV LEFT,ACC. Was hoping to use the directions as temp registers but you have to actually process it in another node first? Not too bad if you have space and time but a bit frustrating.
 
I just went back and optimized my Image Test Pattern 1 to 1187 cycles, which seems to be what those on my friends list are ending up at. If anyone has a lower cycle count, please post it, because it doesn't appear to be able to get any lower.

The image segments are a lot of fun.
 
I can't solve the Signal Pattern Detector and I don't see what I'm missing in my program... It should work but I'm always too early with outputting an 1 or 0 when the output changes.
Any hints are appreciated.

http://abload.de/img/untitledcxr2p.png

edit: and right after posting I found the issue. Now I don't have any room left in the node. lol
edit2: also not working. I think I just forgot to a 0 down after the JEZ jump.
edit3: got it. Whoop! 180 cycles.
 
mrklaw said:
Any tips on speeding up the sequence counter? It seems to do a quite common thing - keep a rolling total of a bunch of numbers (which you could do with just ADD UP or something) but needing to check for a terminator means I'm swapping things back and forth either to BAK or throwing it out to another node temporarily which slows things down a lot.

Also, bit of a shame you can't MOV ACC,LEFT and then later on MOV LEFT,ACC. Was hoping to use the directions as temp registers but you have to actually process it in another node first? Not too bad if you have space and time but a bit frustrating.
Click to expand...

Here is my second (very slow) solution which works without using BAK (which gave also an Achievement, yay). Now I need a way to parallelize this.

http://abload.de/img/untitledjcqu6.png
 
I decided to see what I could do to optimize things a little bit and I really got into the idea of working on bringing my node counts down to match the top of the leaderboards on a couple. I'm really pleased that I was able to figure out how to get Signal Comparator down to 278/6/20 (which seems to be the standard for most people before finding other ways to improve it), Signal Multiplexer down from whatever I had before (forgot to check but I know I improved it), and then spent far too much time getting Sequence Counter done in four nodes which was a real challenge for me. I'm curious how it compares to the others that did it in four nodes. If anyone wants to take a look and compare to how they did it or whatever you can see my silly program that worked: http://i.imgur.com/KPDFgkg.png
 
ekim said:
Here is my second (very slow) solution which works without using BAK (which gave also an Achievement, yay).
Click to expand...
Heh, I actually got that achievement for my first sequence counter. The thought of using sav/swp didn't even cross my mind. (I still only use them very rarely, basically only if nodes are at a premium)

I hate how some challenges give you a useless (well, let's call it unnecessary) stack, or even multiple ones, taking away valuable node space :P
 
Just noticed that
sending something like 38 to JRO ends up executing the last line. You can build some cool nested loops with that but it feels cheap somehow.

@Durante: just for comparison. How many nodes/instructions did you use for your 202 cycle Sequence Counter?
 
Durante said:
I completed "Stored Image Decoder".
(story spoiler)
The sequence that happens was extremely well done. Love it.
Click to expand...

Is there any way you can re-trigger this? I didn't quite follow when it happened, (hadn't been reading all the "debug" notes), and can't find a way to bring it up again.

mrklaw said:
Also, bit of a shame you can't MOV ACC,LEFT and then later on MOV LEFT,ACC. Was hoping to use the directions as temp registers but you have to actually process it in another node first? Not too bad if you have space and time but a bit frustrating.
Click to expand...

You don't really need to "process" it in the node to the left, just put MOV ANY, LAST in there and you can use it as a temporary storage space for any of the adjacent nodes.

Arulan said:
I just went back and optimized my Image Test Pattern 1 to 1187 cycles, which seems to be what those on my friends list are ending up at. If anyone has a lower cycle count, please post it, because it doesn't appear to be able to get any lower.

The image segments are a lot of fun.
Click to expand...

mercviper got to 1186, which is the theoretical minimum, although I'm not quite sure how he managed it.

Durante said:
I hate how some challenges give you a useless (well, let's call it unnecessary) stack, or even multiple ones, taking away valuable node space :P
Click to expand...

You can use them to pass variables through (basically an equivalent to MOV ANY, ANY), which I think came in useful for me maybe once. Ever so slightly more useful than a broken node, anyway.
 
Arulan said:
LEFT/RIGHT/UP/DOWN
in order of priority.
Click to expand...
Yeah, one of the first things I did in the sandbox was test this.

But do note that if your program depends on this it's not guaranteed by the manufacturer to work on all models of the TIS-100 system :P
 
ekim said:
Sequence Counter:

My 19 instructions program. Looks pretty tidy, but the
add 1
feels a bit cheap.
http://abload.de/img/untitledmqrx6.png

Here I tried to outsource the sum calculation but it even got a bit slower.
http://abload.de/img/untitled25apxo.png

This is the fastest version yet with 278 cycles.
http://abload.de/img/untitled380sil.png

As always, I'm eager to get some hints and tips on how to improve further.
Click to expand...

Hints:
Look at the values You need to add, they are all positive. Exploit that with ADD and JLZ.
Use solution without swaps
Getting value from more than one node in one logic loop is a huge bottleneck most of the time.
The key to parallelization is to use multiple streams from different nodes into one node like this:
http://i.imgur.com/2XZTswy.png
Remember about synchronization.

Ps. I parallelized my solution even more just to get 1 cycle less, so 203. Still 1 cycle behind Durante ;/

---edit---
New score :)
grAXvmD.png
 
That's pretty neat!
I haven't looked at Sequence Counter too much yet, I'm still obsessive about Signal Pattern Detector.

I just did a 3 node Sequence Reverser since I saw that Cyan had one. I wonder if his is as silly as mine is.
Also made an 11 instruction one for good measure.

Optimizing node/instruction counts is a good relaxation method in between optimizing for speed IMHO -- it's clear far more quickly whether an approach will work out or not.
 
KKRT00 said:
Hints:
Look at the values You need to add, they are all positive. Exploit that with ADD and JLZ.
Use solution without swaps
Getting value from more than one node in one logic loop is a huge bottleneck most of the time.
The key to parallelization is to use multiple streams from different nodes into one node like this:
http://i.imgur.com/2XZTswy.png
Remember about synchronization.

Ps. I parallelized my solution even more just to get 1 cycle less, so 203. Still 1 cycle behind Durante ;/

---edit---
New score :)
grAXvmD.png
Click to expand...

From your spoiler. I don't understand the first line.
how does JLZ help here?

If you mean JRO, I did that in the first screen I linked.
 
I have trouble even attempting to visualize problems in this game. Like, other logic puzzle games I could at least write something or draw something to try and work things out on paper. Here, it has to happen in code; I haven't found any good way to depict the machine graphically to imagine how input flows through it and gets stored/modified. I'm actually considering refreshing my memory on finite state automata diagrams to make some more progress but inevitably I go do something else instead. It's too much work!
 
ekim said:
From your spoiler. I don't understand the first line.
how does JLZ help here?
Click to expand...

Because all values that You need to add are greater than zero, You can use JLZ to separate 0 and >0 values while adding. You can pass 0 as for example -500 to the node with ADD <node>.
 
KKRT00 said:
Because all values that You need to add are greater than zero, You can use JLZ to separate 0 and >0 values while adding. You can pass 0 as for example -500 to the node with ADD <node>.
Click to expand...

I still don't get it :(
if I add -500 I would ruin my sum on that node (if you are talking about the sum output node)

Edit: oh wait - you mean I should add 500 back again after checking for JLZ. Right that makes sense. But isn't this basically another version of my first solution? There I added one so I can JRO my way out of the loop once an 1 arrives.
 
ekim said:
I still don't get it :(
if I add -500 I would ruin my sum on that node (if you are talking about the sum output node)
Click to expand...

Yes, thats why You add 500 at the last node to the score :)
You pass 0 as -500, add it to the final score like for example 280, so You get -220 and then before passing to the output, You add 500 to return the correct sum 280 value :)
At least i do it this way.
+20 -> check JLZ ->+50 -> check JLZ -> +38 -> check JLZ ->-500 -> check JLZ move to ADD 500 + mov acc, down
 
Durante said:
I just did a 3 node Sequence Reverser since I saw that Cyan had one. I wonder if his is as silly as mine is.
Also made an 11 instruction one for good measure.
Click to expand...

Since I saw you made one, I gave it a shot and got 3 nodes, 8 instructions! Seems I might have gotten the same solution as the unofficial leaderboard at 314 cycles.
 
ekim said:
Edit: oh wait - you mean I should add 500 back again after checking for JLZ. Right that makes sense. But isn't this basically another version of my first solution? There I added one so I can JRO my way out of the loop once an 1 arrives.
Click to expand...
Yes, but my is faster. In Yours You need additional value mov from the left/up to make it work, so You add another cycles.
In my solution, You have just ADD UP, in Yours You have both JRO UP and ADD LEFT, so You are passing the value twice and passing value to the node is the most expensive operation, so its slowing You down.
Your right node for counting is ok though, because its not passing value from another node, but just ADD 1 to acc.
 
I solved the hidden puzzle. I actually expected it to be harder, took me about 20 minutes.
Too bad there are no leaderboards for it!
 
I figured out a solution for the first image program fairly quickly and I recall people saying it takes one small change to then do the second one. My first program feels like I'm brute forcing it but I thought I spotted the easy solution to the next one. I put my quick edit in place and it just makes black and white stripes. Oops! I'll have to give that one a bit more thought.

I did get the Sequence Reverser into three nodes after some effort. I was stumped for a bit but with some VERY sloppy code
I used a ton of NOP commands to prevent the build up in the stack memory. I think I just realized how I could fix this by moving some code around, hmm.
I was able to finally knock that one out as well. As I get into tougher ones it's fun just working on stuff like node counts since I know I don't have the knowledge to really work on the cycle count stuff everyone else tries really hard on.

Edit: That quick fix on Sequence Reverser I thought of while typing that spoiler above brought me from 519/3/24 to 382/3/13. That's actually fairly respectable on the leaderboards with most of you others. I'll accept that. Only took about 15 seconds to implement that change, too.

Edit #2: And had an unnecessary jump at the end that I forgot to remove. Down to 373/3/12. I think I'm done screwing around with that one.
 
I finally figured out how to save that one instruction in the image pattern test. It was bugging me. In retrospect, it shouldn't have taken that long to figure out, there aren't that many options once you define the parameters of what needs to be done.

Here's a (pretty huge!) hint:
The order of conflict resolution on ANY is not the only unspecified but deterministic behaviour of the system.
 
KKRT00 said:
Yes, but my is faster. In Yours You need additional value mov from the left/up to make it work, so You add another cycles.
In my solution, You have just ADD UP, in Yours You have both JRO UP and ADD LEFT, so You are passing the value twice and passing value to the node is the most expensive operation, so its slowing You down.
Your right node for counting is ok though, because its not passing value from another node, but just ADD 1 to acc.
Click to expand...

Hah. That clever. Thanks! :)
But I will stick to my solution. Copying yours would be like cheating.
 
Cyan said:
Oh hell yeah, my planned solution for Image 3 finally worked. Man, that was way harder than Image 4 for some reason. Mine is like 5x faster than Gotchaye's, but I imagine he hasn't bothered to optimize since he's had no competition. :P
Click to expand...

If I'm thinking of the right one I do it in basically the slowest way possible:
I draw progressively smaller rectangles.
 
Oh man. The later levels really make my brain hurt. I'm sitting in front of the sequence peak detector for an hour now and after trying many things, I'm already thinking about reading up some basic algorithms.

edit: I should start with obvious solutions instead of trying to already have low-cycle version in the first try.
 
ekim said:
edit: I should start with obvious solutions instead of trying to already have low-cycle version in the first try.
Click to expand...
I actually think it makes sense to do solutions which just "work" for lots of levels first before optimizing, since you learn a lot of stuff just by completing the levels -- which you can then apply when optimizing. (Personally, I usually have at least one "straightforward", one "fast" and one "small" solution for each level)

Sometimes you have a nice surprise, like in the rectangle drawing program, where my first "straightforward" solution was already faster than any on my friend list :P
(I still managed to speed it up by almost a factor of 2)
 
I have to admit I'm struggling a bit, despite having experience with assembly.

My solution for the interrupt handler is very inelegant, and I'm not quite there since I have synchronization issues. Part of the problem is that in this type of parralel architecture, I'm used to being able to flush individual processing units. I can't do that here so I tend to run into synchronization issues.
 
IMHO, this was harder (to solve, never mind optimize, not going there) than the entire rest of the TIS-100 Segment Map combined.

sortt6scx.png
 
^

I need to stop trying to go back to optimize and actually finish the last few on the map I haven't completed. I have to say, I've never really been one for leaderboards, but seeing someone with a lower cycle count on my friends list and therefore knowing it can be done better really encourages me. Great use of leaderboards.

Sequence Sorter sounds fun.
 
Cyan said:
Damn it! Yep, I've been poking at this one on and off for a while. Still haven't cracked it, though I think I'm on the right track.
Click to expand...
I was surprised at how (comparatively) small many of the solutions are. I must be missing some simpler way to do it. Mine is a monster.

Oh, by the way, I finally managed to match your 133 in Differential Converter just now.
 
Durante said:
IMHO, this was harder (to solve, never mind optimize, not going there) than the entire rest of the TIS-100 Segment Map combined.

sortt6scx.png
Click to expand...

I've just sort of left this one for now. I put together a solution that I was pretty happy with, and then it failed at the zero-length sequence. There's no space to code it in as a special case, and I can't see any way of changing my code to accommodate the zero-length sequences "naturally". I'm going to come back to it later, hoping that I'll be able to see a way to fix it, but I'm worried I'm going to have to start from scratch, which would be, to put it mildly, incredibly frustrating.

Out of interest, though, which sort algorithm did you use? I used
bubblesort, as it just seemed instinctively the best choice to try to fit in the code limit
, but I'd be interested to see what other people have done.
 
I considered
bubblesort
, but my first instinct was
selection sort
and it's also what I ended up implementing.

And yeah, I ran into a very similar code size limitation w.r.t. 0-sized lists, and had to re-engineer it substantially.
 
TheExodu5 said:
I have to admit I'm struggling a bit, despite having experience with assembly.

My solution for the interrupt handler is very inelegant, and I'm not quite there since I have synchronization issues. Part of the problem is that in this type of parralel architecture, I'm used to being able to flush individual processing units. I can't do that here so I tend to run into synchronization issues.
Click to expand...

I did it in 205/7/31 : http://imgur.com/vuvJYH9

the thing that did the trick is to use the top 4 cpus from left to right as a brigade .. the second one takes the value from the first, but if zero, inspects its own input to see if a value is necessary, then passes to the right. Then the next does the same thing, etc. Then you get a stream that is synchronised and only 4 blocks are doing anything. The other 3 are just routing the output to the bottom.
 
How are you going with Image Test Pattern 2?

It does my head in how you can do it in faster than 1350 cycles.
I can't do better than writing the cursor position by pulling x,y coordinates from nextdoor blocks, then writing 303030 five times. The block is nearly all writes to the frame buffer plus one jump, one sub and one ACC init.

Doing so takes about 1380 cycles to fill the grid of 30x18, and this key block is then 0% idle. Apparently the record is 1180.
I must be missing something.
 
I still haven't tried this game (I should be working instead of playing it), but I own it, and I like that it exists!

Personal anecdote: Reading the thread brings back memories of an undergraduate class that involved assembly and computer architecture. The professor recommended me for graduate school, both of his classes were cool, and I recommended him for a teaching award. Sadly, he was sick teaching the second class, and ended up dying within a few years.

I still remember the first class though. A special program was given to the class, kind of like the TIS-100 or something, that allowed us to run assembly with some extra functions. Then we would be given challenges like solving a maze, or changing some bit of information, and we would be graded on how well we performed. He might have considered using the top student results as a curve, but I think in the end he used his own solutions or similar. If we matched his performance (say, 20 instructions), we would get 100% credit. If we beat it, we might get over 100% credit.

The funny (not funny to us) part was, he had lots of experience. So he would tell us something like, "I just did the obvious solution, didn't spend long, so it should be easy to match." Then we would start on the problem and wonder HOW ON EARTH he even got that efficient. =P
 
Cyan said:
Curse you, Durante! I'm one cycle behind on Image 1 and 2. Really not seeing where you're picking up this extra cycle...
Click to expand...

Oh? did Durante get 1150 on image 2?

Edit: Got it! I'll admit I brute forced some combinations but I just get a blank stare on my face when I try to think about the timings.

9H9ccqm.png
 
jellies_two said:
It does my head in how you can do it in faster than 1350 cycles.
Click to expand...
Here's thought process that helps(at least it did for me):
Writting to image processor has a peak rate of 2cycles per write. If you count the exact number of writes necessary to fill the screen with each pattern and multiply them by 2 - there's your result:
For Pattern 2:
( 29 color writes per line + 2 coordinates + 1 terminator ) * 18 - 1 (don't need the last terminator) = 575 writes = 1150 cycles

The trickier part is getting the instructions count down once you have the optimal speed solution (it can be done in surprisingly small amount of code actually, but larger programs will work as well).
 
IMHO, the trickiest part is writing something on the first cycle (going from 1151 to 1150). It took me a long process of elimination to figure that out.

I agree that it can be done in very little code (my 1150 solution is 19 instructions).
 
You must log in or register to reply here.

Similar threads

Fans Are Tired of 100 Hour Long Games, Says Former Starfield Dev
Opinion News Game Dev  2 3 4
193
8K
Rhazer Fusion replied
The Duskbloods (From Software, Miyazaki) official screens
Analysis Game Dev Hype  2
56
3K
blacktout replied
Sony Interactive Entertainment announces the Hero Project Vendor Program
News Business Game Dev 
5
575
HRK69 replied
New Starcraft game in-talks from Korean companies with Blizzard (NCSoft, Nexon, Netmarble, and Krafton)
Rumor Game Dev 
27
1K
ChuckeRearmed replied
Moon Studios 'Fully Independent' After Purchasing Publishing Rights from Take-Two
Game Dev 
41
3K
Hollowpoint5557 replied
Top Bottom