If you ever thought back with longing to beautiful summer days spent filling out code sheets with a worn-down pencil and a well-thumbed processor instruction code book your only companions, well, Zachtronics' TIS-100 might just be your worst nightmare.
The thin plot has your Aunt Doris sending you a bunch of your recently-deceased uncle's belongings, including the TIS-100 and its manual, the last thing on which he was working. Because of some cryptic hints in the manual, and because you have more curiosity than sense, you decide to recreate his work and discover the hidden purpose of this mysterious device.
All this is merely a wrapper to the meat of the game, which is to write programs in assembly language to solve little problems. The TIS-100 is comprised of up to twelve processing nodes which run independently, connected to adjacent nodes via ports. There is no RAM, and the instruction set is 70s-era microprocessor simple.
Like its predecessor, SpaceChem, TIS-100 is a puzzle game where solving the challenge is usually only the start of the fun. The number of nodes you used, the execution time, and the number of instructions used is compared to everyone else who has solved the puzzle. Your solution too slow? Back to the drawing board.
TIS-100 is in Steam early access, but I'm not seeing anything terribly unfinished about it. The user interface is fairly functional, and that's part of its charm. You can even go full screen for the complete old-school experience.
I just can't imagine anyone but programmers, especially those of us who actually had to do this kind of stuff back in the day, really enjoying this. The manual is minimal (but hilarious in a geeky way). The TIS-100 doesn't do a fantastic job of introducing people to parallel programming or even the sort of assembly language likely to be used by anyone — this is a really stripped down set.
That said, you may just have found the hardcore programming game you never knew you were missing. SpaceChem with all that distracting space and chemistry stuff removed…. I'm having a heck of a great time with it.
I’m wondering if you still answer question for neopets game Shapeshifter. I read your blog shewhoshapes.wordpress.com twice but because I saw no one coment there in 7 years decide write you here.
I finally understand the Flips concept and the other optimization for one line changes. There is a great advantage in solving what I call the “virtual puzzle” without put a piece on the board.
But just for the example in level 97 with 1 flip. The horizontal line 3×1 have 3 changes so in the virtual puzzle that piece can solve the first line and you can found a solution for the virtual puzzle but that isn’t the solution and take lot of time to find.
So how you discard that piece on first row be a solution without put that piece on the board and realize that move doesn’t solve the row?
My strategy is try to solve the first line, each puzzle object have first line and rest of the piece array, only altering the virtual board. Then pass the remaining pieces to try to solve the second line and so on.
To solve first line in 97 level there is 2^28 possibilites (268 million)
But using flips restriction my algorithm found 20k solution for the virtual puzzle on the first row in about 5 min. Very far from the 3 sec you need to solve the whole puzzle.
I know still haven’t apply the multithread/distribuited setup. But know in the first minute I found 50% of those 20k so still a chance of I found the right answer early.My next step is just start trying to put the pieces on the board for the 20k solutions and see how much work time is need it.
I’m just in love with the puzzle, not playing neopets from long time ago when I reach level 35 using brute force algorythm. Recently I went to a constrain program course and learn a few things that bring old memories back so I want give a second try to the puzzle.
Also was wondering if you ever tought in something like genetic algorithm aproach to solve this?
I should put all the “She Who Shapes” posts into this blog, actually.
Fact is, I lost that code in a computer crash a long time ago. I saved the hard drive, but I don’t know if I’ll be able to read it. I remember I was so into solving the puzzle that it was almost all I could think about, all the time. After I got to 100 and got my #1 place on the leader board, I started another run from level 1, but it just didn’t seem worth it. I got to the difficult puzzles in the 40s and didn’t feel like refining the solver any more.
Not all puzzles were solved that quickly; some took hours. Luck of the draw, really. Sometimes the pieces you get eliminate most of the possible positions really quickly. Since you can place the pieces in any order to find a solution, most of what I did was place the largest pieces first to cut the tree down as quickly as possible. I’d try to place them everywhere, not just the first row. I have a feeling that working from the first row won’t prune the decision tree quickly enough.
Genetic algorithms require you to be able to generate a fitness score. With Shapeshifter, there is no getting closer — it’s solved or not.
Good luck with your solver 🙂 If I still had the code, I’d release it. Unless I did and just forgot, in which case, maybe I have it on the server somewhere…
So you do something like 8 queen problem? With constrain programing?
I try to understand your code here
https://shewhoshapes.wordpress.com/2008/03/04/current-algorithm/
Here you say never put a piece on the board. But as I mention then how you know a 3×1 horizontal line doesnt solve first line of level 97 where need 3 changes?
Also in the code doesn’t show how you create the pieces array. So I don’t know what have P = pieces[level] and P.moves
My guess is Level isn’t really depth search level instead is just piece_id? but what about P.moves maybe all possible position on the board for that piece?
I had two programs, Scraper and Shifter. Scraper scraped the Shapeshifter web page and created the pieces array and the board from the page. Pieces were stored as a linear array of offsets, sorted by length descending.
Every starting board is some distance away from a finished board. The number of squares among all the given pieces are probably more than would be needed to complete the puzzle, therefore, some squares in the puzzle will need to be flipped, at a minimum, the depth of the board. Each complete transition is counted as a flip — the total number of squares among all shaped – the distance of the starting board from the finished board, all divided by the depth of the board. If placing a square in a spot would change that spot from a finished state to an unfinished state, then you need another flip to pay for it. If no flips are available, the piece can’t possibly be placed.
Level is both the depth and the piece ID.
P.moves is indeed all possible positions the piece can be placed on the board; I pre-calc that to save time.
I think you might understand the algorithm better than I do at this point 🙂
If you had a puzzle where the single piece you have would solve the puzzle, then there would be no flips left, and you would already know you had won. No searching necessary.
If you had a puzzle where you have two pieces with which to solve the puzzle, and the number of squares left to solve exactly match the number of squares in the two pieces, then you have zero flips left (again) and just need to go through all the possible positions for the first piece, and then all the possible positions for the second piece, where you just have to be sure you don’t overlap, which would cost you a flip you don’t have.
And so on. All you ever have to do is count flips.
I understand the flips concept, but i dont see how you operate with the pieces.
Please can you show me a litle sample of how you save a piece and the board.
I still dont understand the properties
P.parr, board.brdarr[i] and board.waxon[v]
Or how you work when board have more than two state for cell.
P is a class containing play information; parr is the piece array. Board.brdarr is the actual current state of the board. Waxon, I believe, stores the breadcrumbs so we know where the piece would go to solve the puzzle.
I’ve been looking around to see if I stashed the source code somewhere, but I haven’t found it… so probably, only the bits I posted on the blog survived.