Manufactoria - a game about Turing machines

http://jayisgames.com/games/manufactoria/

by Zarkonnen • 16 years ago

111 42 16 years ago

jayisgames.com

philh• 16 years ago

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.)

Zarkonnen2• 16 years ago

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

onewland• 16 years ago

Let's play regular expressions!

Natsu3• 16 years ago

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).

johnswamps4• 16 years ago

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)

endtime2• 16 years ago

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?

johnswamps4• 16 years ago

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.

Artifex• 16 years ago

What is the song in this game?

tumland• 16 years ago

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.

naturalethic• 16 years ago

That concept is introduced in later levels.

RabidChihuahua• 16 years ago

All I can say is...COOL!

hamilton• 16 years ago

The game music is a Shostakovich piece. Awesome.

rauljara• 16 years ago

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...

frederickcook• 16 years ago

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.)

jtbarrett• 16 years ago

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.

bluemetal• 16 years ago

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)

Natsu3• 16 years ago

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.)

barrkel• 16 years ago

Seems rather unusable with a Dvorak keyboard, unfortunately.

jganetsk3• 16 years ago

Just turn off Dvorak while playing the game.

dkersten3• 16 years ago

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

Prolorn• 16 years ago

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

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

zemaj• 16 years ago

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?"

Natsu3• 16 years ago

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.

scotty793• 16 years ago

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.

jganetsk3• 16 years ago

I wish I could save the game!

jganetsk3• 16 years ago

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

boredguy8• 16 years ago

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

joshu• 16 years ago

That helps a lot.

ericlevine• 16 years ago

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.

branden2• 16 years ago

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?

johnswamps4• 16 years ago

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

branden2• 16 years ago

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

scotty793• 16 years ago

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;

Zarkonnen2• 16 years ago

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

phreeza2• 16 years ago

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.

dkersten3• 16 years ago

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

phreeza2• 16 years ago

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°

scotty793• 16 years ago

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.

Manufactoria - a game about Turing machines

Related Stories