Manufactoria - a game about Turing machines | Hacker News Reader

Manufactoria - a game about Turing machines

jayisgames.com

111 pointsZarkonnen42 comments

I spent most of yesterday playing this game. It's one of the most engaging games I've ever played. It's a lot of fun trying to come up with neat, elegant solutions. You need to use a lot of concepts that are used in programming, such as loops and recursions.

Some of the later levels are pretty brutal, especially the bonus levels, but in a good way.

(They're more like Turing machines by the way)

I'm not very far through the game yet, but as far as I can tell they are exactly DFAs. Maybe it changes later, with new components?

They're definitely not Turing machines, but they are Turing complete, they use tapes, and you can write to the tape. Some of the later puzzles ask you to solve problems that are impossible for a DFA (such as accept X blues followed by X reds (though a PDA could also do this)). Once you do the bottom branch you get the ability to read/write green and yellow, which largely increases what you can do.

Ah...I was doing the puzzles depth first, and did the top branch first. Just got my first writing one.

Very cool, but like all games, some flaws. The biggest one I saw was that some of the test inputs are less rigorous than they should be. The level that says your robots have to end with double blues, I could design a conveyor system that would pass all of the given tests, but would fail if it ended with triple blues.

The only reason I'm slightly annoyed: I designed a neat way to avoid failing on triple blues, but then the game never sent a triple blue my way...

I noticed the same thing regarding how rigorous the tests are. But, just like real life, you can write a program that passes every single fringe case every time, or that meets the specific use cases. (In this case, the specific use cases are the robots from the factory, which you don't necessarily know ahead of time.)

A tape that ends with three blues still ends with two blues. But fair enough, if there were a test case then there wouldn't be this ambiguity. Anyway, fun little game. I wonder how non-programmers receive it.

it seems to have a pool of test cases for each one, if you test it a few times you can try your luck against some different ones (including your 3 blues)

Were you supposed to reject a bot with .* BBB$ then? I never got that test case. I read the requirements as asking me to match .* BB$ and so I never tried to make it handle ^BB$|.* RBB$

(Edit: Added spaces so that the site doesn't turn my regexes into formatting.)

Stuff like this, especially if posted on here should carry a warning. "Caution: nerd sniping"!!

This cost me half a day yesterday, and I am preparing for an important exam. Not good.

Great game, though. The only issue I had was that it seamed like conceptually many of the problems were quite easy to solve, the hard part was fitting it all on the board without the conveyors overlapping. Being able to mirror the gates would be nice, for that purpose.

Space bar mirrors the gates. Also, the conveyors are allowed to overlap in a + shape and they will do what you expect.

oh that's awesome... wish i had known that earlier. Probably should read the instructions. Read about the spacebar in the previous comment but assumed what it meant by flip was rotate 180°

This game was a royal pain until I realized you could hit "space" to flip, rather than rotate, a piece.

That helps a lot.

This is amazing. You're forced to do some really complicated stuff. Here's my solution to Rocket Planes that uses all 4 colors, 4 subfunctions, and recursion: http://dl.dropbox.com/u/6625091/rocketplanes.png

Is there a simpler solution to that one?

Here's mine: http://imgur.com/9xbU3

Wow, that's way more elegant. Mine looks obfuscated by comparison :)

My first attempt was probably worse than yours, but after I was mostly done with all the levels, I went back and applied what I had learned to all the earlier levels. I was able to reduce giant, sprawling messes of mostly conveyors to much more compact machines. Of course, the more important part is finding the optimal algorithm.

Up until the last column or two, there's neat solutions to all of them, but some of the later ones really do require a huge part of the level and a nearly unreadable tangle of paths.

My solution to this was bubble sort.

?lvl=27&code=g12:4f0;p11:4f0;y11:3f3;r11:5f1;q10:4f2;c8:3f3;c8:4f3;c9:3f0;c8:8f2;c8:9f1;c8:10f1;c8:11f1;q9:8f2;b9:9f1; b9:10f3;r9:11f0;p10:8f0;c10:9f3;q10:10f3;c10:11f0;c8:5f3;c8:6f3;c10:3f0;g8:7f3;c9:7f2;c10:7f2;r11:10f1;q13:11f1;p15:5f1;b16:5f0;r14:5f2;q15:4f1;c14:4f0;c13:4f0;c16:6f1;p12:9f2; b12:10f1;r12:7f2;g11:9f2;c11:7f3;c11:8f3;c12:8f1;p13:7f1;c16:7f1;i14:7f7;c15:7f2;c13:6f2;c14:6f3;c14:8f3;c14:9f3;c14:10f3;c14:11f0;c13:9f2;

Interesting thing is that machine you build is painfully stateless. Each test you perform which result you want to keep in mind has to branch your machine into two separate nearly identical branches.

It was very refreshing for me to think about whole state traveling around your program as a single container with very limited access.

I think it might have taught me about programming Turing machine and how different it is from every day programming.

Thank you HN for tip that I can flip element with space bar. Without this information I got stuck at Ophanim level. Maybe I'll be able to finally beat it now.

I'm so trying this out on the next person I interview. "You've got 30 mins, see how far you get".

...after 30 mins... "How would you have improved this game?" "Can you make a problem that cannot be solved in this game?"

Seeing this comment made me try to answer that, just for fun. For improvements, I know that I would have included a more obvious manual somewhere (I didn't know that you could flip the pieces, rather than rotating them with a space bar, until I read that in a YC comment).

The second question is more interesting to me, because I know regexes better than Turing machine variants. I think I could give them the problem of accepting only balanced, nested "parentheses" with arbitrarily deep nesting or something similar (treating blue as open parentheses and red as close). Though they asked something close to that with the nasty "accept only bots with equal numbers of red and blue symbols" so maybe I'm wrong and I should look for some angle with incomputable functions, like the Busy Beaver.

Or you can just cheat and give the play a board that's too small (or limit them to too few pieces) for the problem to make it unsolvable.

The ability to use yellow and green makes me wonder if there's some way to solve the balanced parentheses problem, though. I quit to do something else before solving the "accept only equal numbers of red and blue" problem (alas, I wished it would let me write to balance the tape, then you could just loop until empty, write red blue and accept).

This would sure be a lot more fun than most programming tests. I had a lot of fun designing things like a "red eater" which took care of the .* in the problem asking you to match .*BB$ and trying to shave parts. I know I could get rid of several more if I had known how to flip them. I just hate seeing something and knowing there ought to be a way to simplify it further.

I found this game few days ago. I had few approaches to accept only equal number red/blue. First I attached binary yellow/green counter starting at 1111 to the end of the tape and with each pass of the tape I removed one symbol and incremented the counter if the symbol I removed was blue and decrementing it if it was red. At the end I checked if counter is still 1111

Worked perfectly until robot with only one empty space at the end of his tape was encountered.

Then I came up with much simpler solution.

Awesome game. My theory of computation professor is noted in the credits of the game. Great professor, and a very interesting application of everything he taught us.

I might end up supervising students for Regular Languages & Finite Automata next year, in which case I must encourage them to play this game. :)

Let's play regular expressions!

That outlook actually helped me solve some of these.

Once I respecified the problem as "accept .*BB$" it became a lot easier to visualize. In particular, it showed me that I needed a junction at the end which passes only an empty tape. You can, in fact, code it up by creating a piece that accepts anything (except end of tape!), two pieces that accept blue, followed by one that accepts only the end of tape and wiring them together properly (which I leave as an exercise for the reader; I'd hate to spoil any of the problems too much).

Seems rather unusable with a Dvorak keyboard, unfortunately.

Just turn off Dvorak while playing the game.

Who says that dvorak was "turned on" to begin with? Maybe the solution is turn on qwerty while playing the game.

Because the standard is QWERTY.

Yet a lot of people use dvorak. Or QWERTZ or AZERTY.

Actually, the arrow keys can substitute for the WASD keys.

WASD is just easier to use one-handed with the spacebar.

Given breakpoints and the ability to test arbitrary inputs, this game would be a lot less frustrating.

(Unless those have been added since I last played.)

Ability to test arbitrary inputs exists, I think. Press the wrench button.

The game music is a Shostakovich piece. Awesome.

Maybe it's just me, but it seems like I would do better if 1's and 0's were used instead of red and blue.

That concept is introduced in later levels.

Amazing fusion of visual-spatial reasoning and programming! A++

What is the song in this game?

I wish I could save the game!

All I can say is...COOL!

Reply on news.ycombinator.com