Project Nayuki


Manufactoria solutions

Manufactoria is a Flash game about designing a machine to make decisions about accepting or editing a set of strings. (For readers with a computer science background, it’s like constructing a finite-state automaton or a tag system.)

On this page are my solutions for almost all the levels in this game. I seek to minimize the number of filled tiles (which are called “parts” in the game) – but not necessarily the number of execution steps or the clarity of the machine. Each solution comes with a short explanation of the algorithm I implemented to solve the problem.

I will not try to explain the mechanics of this game or the basic techniques. I assume you can play the game to understand how it works, and find tutorials and strategy guides elsewhere online.

Overview

Level Commentary Screenshot Saved game Parts
01 Robotoast!CommentaryScreenshotSaved game3
02 Robocoffee!CommentaryScreenshotSaved game3
03 Robolamp!CommentaryScreenshotSaved game8
04 Robofish!CommentaryScreenshotSaved game4
05 Robobugs!CommentaryScreenshotSaved game11
06 Robocats!CommentaryScreenshotSaved game11
07 Robobears!CommentaryScreenshotSaved game15
08 RC Cars!CommentaryScreenshotSaved game7
09 Robocars!CommentaryScreenshotSaved game7
10 Robostilts!CommentaryScreenshotSaved game9
11 Milidogs!CommentaryScreenshotSaved game8
12 Soldiers!CommentaryScreenshotSaved game7
13 Officers!CommentaryScreenshotSaved game25
14 Generals!CommentaryScreenshotSaved game30
15 Robotanks!CommentaryScreenshotSaved game25
16 Robospies!CommentaryScreenshotSaved game8
17 Androids!CommentaryScreenshotSaved game12
18 Robo-children!CommentaryScreenshotSaved game25
19 Police!CommentaryScreenshotSaved game51
20 Judiciary!CommentaryScreenshotSaved game99
21 Teachers!CommentaryScreenshotSaved game23
22 Politicians!CommentaryScreenshotSaved game30
23 Academics!CommentaryScreenshotSaved game34
24 Engineers!CommentaryScreenshotSaved game51
25 Roborockets!CommentaryScreenshotSaved game7
26 Roboplanes!CommentaryScreenshotSaved game7
27 Rocket Planes!CommentaryScreenshotSaved game21
28 Robomecha!CommentaryScreenshotSaved game19
29 SeraphimCommentaryScreenshotSaved game23
30 OphanimUnsolved by Nayuki
31 MetatronUnsolved by Nayuki

Commentaries

01 Robotoast!
Screenshot: Robotoast!

Self-explanatory.

02 Robocoffee!
Screenshot: Robocoffee!

Self-explanatory.

03 Robolamp!
Screenshot: Robolamp!

Self-explanatory, but achieving a compact layout requires some thinking and editing.

04 Robofish!
Screenshot: Robofish!

Self-explanatory.

05 Robobugs!
Screenshot: Robobugs!

Self-explanatory, but achieving a compact layout requires some thinking and editing. This solution is borrowed from Liam Miller-Cushon.

06 Robocats!
Screenshot: Robocats!

Self-explanatory, but achieving a compact layout requires some thinking and editing.

07 Robobears!
Screenshot: Robobears!

The left side remembers that the first symbol was red, and the right side remembers that the first symbol was blue. This solution is borrowed from Liam Miller-Cushon.

08 RC Cars!
Screenshot: RC Cars!

Self-explanatory.

09 Robocars!
Screenshot: Robocars!

Self-explanatory.

10 Robostilts!
Screenshot: Robostilts!

The three-piece red-blue gadget copies red and blue symbols to the end of the string until either a green symbol, yellow symbol, or the end of tape is reached. This gadget will be used a lot in the advanced levels.

11 Milidogs!
Screenshot: Milidogs!

In other words, accept strings that end with blue. Achieving a compact layout requires some thinking and editing.

12 Soldiers!
Screenshot: Soldiers!

In other words, add three 0s to the end, which means adding three red symbols.

13 Officers!
Screenshot: Officers!

Write a yellow symbol at the end of the string. A yellow symbol indicates that the preceding symbol needs to be incremented. Use a green symbol to mark the end of the logical string. When we see red yellow, replace it with blue. When we see blue yellow, replace it with yellow red. When we see yellow at the beginning of the logical string, replace it with blue.

14 Generals!
Screenshot: Generals!

The idea is quite similar to level 13. Write a yellow symbol at the end of the string. A yellow symbol indicates that the preceding symbol needs to be decremented. Use a green symbol to mark the end of the logical string. When we see blue yellow, replace it with red. When we see red yellow, replace it with yellow blue. Unlike the addition case, yellow cannot occur at the beginning of the logical string.

15 Robotanks!
Screenshot: Robotanks!

Check that the string has a blue followed by at least 4 symbols, so that it is at least 100002 (i.e. 16). Achieving a compact layout requires some thinking and editing.

16 Robospies!
Screenshot: Robospies!

Check that the string begins with any number of 0s, followed by a 1, followed by an even number of 0s.

17 Androids!
Screenshot: Androids!

Mark the end of the logical string with green. Copy over blues until we encounter blue red, which we eliminate, then copy over reds. Repeat until the logical string is empty, in which case we accept. Otherwise if the string begins with red or ends with blue, then reject.

18 Robo-children!
Screenshot: Robo-children!

If we see a red, then try to find a later blue and eliminate both. If we see a blue, then try to find a later red and eliminate both. Accept if the logical string is empty, or reject if any search fails.

19 Police!
Screenshot: Police!

First write yellow at the beginning and end of the logical string. Mark the end of the logical string with green. Move the first yellow backward and the second yellow forward until they meet. Then covert double yellow into single yellow.

My first published solution used 76 parts. Years later, a reader Simon generously contributed a 58-part solution. I examined it and optimized it down to 51 parts.

20 Judiciary!
Screenshot: Judiciary!

Combine #19 and #29. In my solution, the verify-green-separated-string mechanism is in the lower left, and the put-yellow-in-middle mechanism is in the upper right. The mechanism from #19 has been reshaped to be more right-leaning, and the mechanism from #29 has merely been rotated clockwise by 90°.

21 Teachers!
Screenshot: Teachers!

If the string starts with a blue, then eliminate it, eliminate the earliest red that follows, then eliminate the earliest blue that follows. Accept if the logical string is empty, or reject if any search fails.

22 Politicians!
Screenshot: Politicians!

The solution starts by echoing the blues and consuming the first red. Next it echos the rest of the string, tries to consume two blues, and echos the rest of the string. This solution is logically correct but takes a long time. The game says “the malevolence engine is out of patience” but the level completes successfully. This solution is borrowed from Liam Miller-Cushon and tweaked.

An alternate 33-part solution is more time-efficient and succeeds with no warnings. If the string starts with red, then find two blues to eliminate. If the string starts with blue, then find a blue and red (in either order) to eliminate. Accept if the logical string is empty, or reject if any search fails. This solution is made by me.

23 Academics!
Screenshot: Academics!

Write yellow at the end of the string. Mark the end of the logical string with green. The substring from yellow to green is the already-reversed original symbols. On each scan through the string, move the first symbol to immediately after the yellow. Repeat until yellow is at the beginning of the string, then eliminate yellow at the beginning and green at the end.

24 Engineers!
Screenshot: Engineers!

Iteratively check that the first color in the string matches the last color, then delete them. This solution was generously contributed by Pegasus Assistant, a visitor to the site.

25 Roborockets!
Screenshot: Roborockets!

Self-explanatory.

26 Roboplanes!
Screenshot: Roboplanes!

Self-explanatory.

27 Rocket Planes!
Screenshot: Rocket Planes!

On each scan through the string, if there is a red followed by blue then move that one red to the end of the string. Otherwise exit because there is nothing to do. This solution was generously contributed by Selmar, a visitor to the site.

28 Robomecha!
Screenshot: Robomecha!

Write a green at the end of the logical string. The left side remembers that the most recent symbol was blue; the right side remembers that the most recent symbol was red. After consuming the last red/blue symbol, write green and the last symbol. Now copy over the prefix of the original string, and finally eliminate the green symbol. A generous visitor to the site contributed a small simplification to my solution.

My first published solution used 33 parts. Years later, a reader Erik generously contributed a 27-part solution. I examined it and optimized it down to 21 parts.

29 Seraphim
Screenshot: Seraphim

Repeat until no more red/blue: Add a green, consume and remember the first color, echo the remaining reds/blues until a green, then consume and check the next color. Note that the first and second substrings swap places in each iteration. This solution is borrowed from Liam Miller-Cushon.

Notes

The game mechanics and artwork are not made by Nayuki. The solution machines, however, are almost all designed by Nayuki (unless otherwise indicated and credited).