A friend of mine just pointed me to a most excellent puzzle game, Manufactoria, wherein you build little machines to test robots. For now I won’t give away the secret of what real math/computer science topic the game teaches you, but I’ll write more about it later. For now, just have fun playing the game! =)

- algorithm algorithms approximation arithmetic art Babylonian beauty binary binomial coefficients book review bracelets carnival Carnival of Mathematics change chess chess board combinatorics consecutive cookies counting decadic decimal derivatives diagrams divisibility divisors education expansion factorization fibonacci floor foundations fractal fractions game games GIMPS graph graphs Haskell history humor hyperbinary idempotent integers integral interactive intuition irrational irrationality Ivan Niven latex logic Mersenne metric multiplication negative notation number numbers pi prime primes programming proof puzzle P vs NP rectangles repunit review sequence squares triangular video visualization
### Blogroll

### Fun

### Reference

### Categories

- algebra (14)
- arithmetic (35)
- books (25)
- calculus (6)
- challenges (46)
- combinatorics (6)
- complex numbers (3)
- computation (30)
- convergence (9)
- counting (28)
- famous numbers (38)
- fibonacci (14)
- fractals (12)
- games (17)
- geometry (27)
- golden ratio (8)
- group theory (3)
- humor (6)
- induction (7)
- infinity (17)
- iteration (15)
- links (70)
- logic (6)
- meta (37)
- modular arithmetic (10)
- number theory (47)
- open problems (11)
- paradox (1)
- pascal's triangle (8)
- pattern (54)
- people (19)
- pictures (28)
- posts without words (3)
- primes (23)
- probability (3)
- programming (15)
- proof (42)
- puzzles (10)
- recursion (8)
- review (17)
- sequences (26)
- solutions (24)
- teaching (9)
- trig (3)
- video (18)

### Archives

- December 2013 (1)
- October 2013 (1)
- July 2013 (1)
- June 2013 (1)
- May 2013 (1)
- April 2013 (3)
- March 2013 (3)
- February 2013 (2)
- January 2013 (5)
- December 2012 (3)
- November 2012 (4)
- October 2012 (5)
- September 2012 (1)
- August 2012 (4)
- July 2012 (1)
- June 2012 (6)
- May 2012 (2)
- April 2012 (3)
- March 2012 (1)
- February 2012 (4)
- January 2012 (5)
- December 2011 (1)
- November 2011 (7)
- October 2011 (4)
- September 2011 (6)
- July 2011 (2)
- June 2011 (4)
- May 2011 (5)
- April 2011 (2)
- March 2011 (4)
- February 2011 (1)
- January 2011 (1)
- December 2010 (1)
- November 2010 (4)
- October 2010 (2)
- September 2010 (1)
- August 2010 (1)
- July 2010 (1)
- June 2010 (2)
- May 2010 (3)
- April 2010 (1)
- February 2010 (6)
- January 2010 (3)
- December 2009 (8)
- November 2009 (7)
- October 2009 (3)
- September 2009 (3)
- August 2009 (1)
- June 2009 (4)
- May 2009 (5)
- April 2009 (4)
- March 2009 (2)
- February 2009 (1)
- January 2009 (7)
- December 2008 (1)
- October 2008 (2)
- September 2008 (7)
- August 2008 (1)
- July 2008 (1)
- June 2008 (1)
- April 2008 (5)
- February 2008 (4)
- January 2008 (4)
- December 2007 (3)
- November 2007 (12)
- October 2007 (2)
- September 2007 (4)
- August 2007 (3)
- July 2007 (1)
- June 2007 (3)
- May 2007 (1)
- April 2007 (4)
- March 2007 (3)
- February 2007 (7)
- January 2007 (1)
- December 2006 (2)
- October 2006 (2)
- September 2006 (6)
- July 2006 (4)
- June 2006 (2)
- May 2006 (6)
- April 2006 (3)
- March 2006 (6)

### Meta

Yeah that game is awesome. In a few weeks I’ve got an exam about computation so this is perfect procrastination.

Mmm…first to comment.

I reckon we can propose a relationship between the addictiveness of the links in a post and the rate at which comments come in. I know for one I intended to say how cool this little game was last night, but I couldn’t resist solving a few more levels, and, well, I never quite got to commenting :)

Personally I’m stuck on one of the earlier levels, the “number of blue and then same number of reds” one. It’s blocking the whole field :(

Anyway, thanks for the fun, and this is a very cool blog.

A flat line of b/r gates, solves that. I just started “put a yellow dot in the middle of a string”… Tough stuff.

haha, didn’t realise guys can enter gates from the sides!

I do feel a bit cheap solving it that way though (with the horizontal line of b/r gates), cause it won’t work for any length of blues/reds, just for as long as you sideways chain goes…I wonder if there’s a way to loop it so that it could theoretically run a million blues then back a million reds…

Rocket: I guess that happens to work on the test cases the game uses, but wouldn’t it fail on something like BBBRBRRR? (That is, it would accept that string when in fact it should not?) It also doesn’t work for the reason Tom says. Looping it wouldn’t work since if your loop is

nunits long then you can’t tell the difference between any two numbers that have the same remainder when divided by n.I wonder if you could solve it by re-writing the whole code, but leaving off the first blue and the first red you meet, and then running that process again, so the code loses a blue and a red each cycle…that way the whole code would continually reduce itself so that (if it’s legitimate) there’ll be just one blue and one red at the end…and you might somehow be able to tell that it has been reduced as such.

Tom: that’s exactly how I solved it!

Hahahaha, the sheer elegance to the simplest solution for ‘with blue as 1 and red as 0, multiply by 8′ almost knocked me over just now :)

Tom: hehe, nice, you have just discovered the “bit shift” operation. =) Almost all modern CPUs can do this as a special case so that multiplying by powers of two is much faster than multiplication in general.

This is a really interesting game. I’ve never done any programming, and I haven’t taken any computer science courses yet, but I find this game very enjoyable. Thanks for the link!

Nice game! I just have a few levels left. The only concern I have about it is that they should have put more thought into their test cases (or problem descriptions). Cause there are very simple test cases that break some of my accepted machines.

Yes, I agree with you re: test cases!

Have you tried playing manufactoria now? There is now a ‘Malevolence Engine’ which works out if the machine is flawless and if it isnt it shows you the simplest R/B combo which is wrongly accepted or rejected :)

Ah, very nice!

you have to play on specific sites for that though; i use kongregate.com :)

> a ‘Malevolence Engine’ which works out if the machine is flawless

That would be equivalent to solving the halting problem – I guess that it uses some scripted heuristics, such as to check if loops are used, probes the complexity behaviour or simply tries strings which are too long to accommodate with a feed-forward network.

> you have to play on specific sites for that though

You can also download the Manufactoria.swf and play with the standalone flashplayer.

> I just have a few levels left.

If you’ve finished, you might check out one of those (playtested, but cannot check the links here):

Robojournalists!

Our robotic investigators bring you today the news of tomorrow – and for all other days, too.

Roboeditors!

ROX News, the Robotic Objective eXaminer. fair & balanced [tm] and 100% cognitive consonant.

Robolawyers!

RAG, the robotic advocate corps, for child molesters, bankers and YOU. Now with 100% less ethics!

@Ignatius: Nah, the Malevolence Engine doesn’t do anything so complicated. It just does total-coverage testing for all tapes up to 6-12 dots long (the amount of total-coverage depends on the expected running-time of the machine – early ones do all tapes up to 12 dots, the last ones only go up to 6). It then tests several randomly-generated longer tapes. I think that Robochildren also specifically tests a maximum-length tape filled with half one color then half the other, to break naive machines just using chained branches.

Also, as part of the XKCD message board’s obsession with the game, I wrote a Manufactoria emulator in js at http://www.xanthir.com/manufactoria. Check it out – it’s good for testing out the really slow machines at the end, because it can execute long strings enormously faster than the flash version does with its animations.