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 Author
01 Robotoast!CommentaryScreenshotSaved game3Nayuki
02 Robocoffee!CommentaryScreenshotSaved game3Nayuki
03 Robolamp!CommentaryScreenshotSaved game8Nayuki
04 Robofish!CommentaryScreenshotSaved game4Nayuki
05 Robobugs!CommentaryScreenshotSaved game11Liam Miller-Cushon
06 Robocats!CommentaryScreenshotSaved game11Nayuki
07 Robobears!CommentaryScreenshotSaved game15Liam Miller-Cushon
08 RC Cars!CommentaryScreenshotSaved game7Nayuki
09 Robocars!CommentaryScreenshotSaved game7Nayuki
10 Robostilts!CommentaryScreenshotSaved game9Nayuki
11 Milidogs!CommentaryScreenshotSaved game8Nayuki
12 Soldiers!CommentaryScreenshotSaved game7Nayuki
13 Officers!CommentaryScreenshotSaved game23Trinetra
14 Generals!CommentaryScreenshotSaved game30Nayuki
15 Robotanks!CommentaryScreenshotSaved game25Nayuki
16 Robospies!CommentaryScreenshotSaved game8Nayuki
17 Androids!CommentaryScreenshotSaved game12Nayuki
18 Robo-children!CommentaryScreenshotSaved game25Nayuki
19 Police!CommentaryScreenshotSaved game51Simon & Nayuki
20 Judiciary!CommentaryScreenshotSaved game99Nayuki
21 Teachers!CommentaryScreenshotSaved game23Nayuki
22 Politicians!CommentaryScreenshotSaved game30Liam Miller-Cushon
23 Academics!CommentaryScreenshotSaved game34Nayuki
24 Engineers!CommentaryScreenshotSaved game31Wang & Nayuki
25 Roborockets!CommentaryScreenshotSaved game7Nayuki
26 Roboplanes!CommentaryScreenshotSaved game7Nayuki
27 Rocket Planes!CommentaryScreenshotSaved game21Selmar
28 Robomecha!CommentaryScreenshotSaved game19Erik & Nayuki
29 SeraphimCommentaryScreenshotSaved game23Liam Miller-Cushon
30 OphanimCommentaryScreenshotSaved game54Trinetra
31 MetatronCommentaryScreenshotSaved game70Trinetra

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. This solution was generously contributed by a reader Trinetra. My own best solution used 25 parts.

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 Wang, a visitor to the site, and further optimized by me.

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

30 Ophanim
Screenshot: Ophanim

Use a green as teminator for the second part of the string, then add a red and copy all the first part then another green terminator for the status region. Loop by removing the last character of the second part and then add a red to the first part and remove its last character. If the two removed characters were of the same type then re-add the status flags unchanged; otherwise add a red, reject, or a blue, accept, as top-level status depending on whether the character from the second part was greater than the other. After the end of the second part, check if the first part still has some blue: if so then accept, otherwise look for the top status flag to decide.

This solution and explanation was generously contributed by a reader Trinetra. I didn’t have the patience to solve this level on my own.

31 Metatron
Screenshot: Metatron

Use a green symbol as the terminator of the second part of the string. Add a red to the first part of the string and copy it, then put two yellow cursors before the green terminator. Loop by removing the last character of the second part, and depending on its type use one of two sub-algorithms. If last character was red, then add a red at the start of the first part and then look for the last character before the two yellow cursors and put it after the two yellows, then copy the rest of the string. The other algorithm is a sub-loop that puts a red as the last character of the second part replacing the blue just read, then removes the last character before the first yellow cursor. If this was a red then append a blue and copy the string until the second yellow; then append both yellow cursors, copy the remainder of the first part and return to the main loop. If instead the last removed character was a blue, then append a yellow and red, then copy all until the next green, copy the second part as well, and loop again in the sub-loop until a red is found. At the end of the main loop, remove a green, then copy the entire string until it can remove the next green; in the meantime also drop the two yellows.

This solution and explanation was generously contributed by a reader Trinetra. I didn’t have the patience to solve this level on my own.

Notes

The game mechanics and artwork are not made by Nayuki. Most of the solution machines are designed by Nayuki (unless otherwise indicated and credited).

Another player, Viktoras Bezaras, has posted a good set of solutions. The harder levels have smaller solutions than the solutions on my page here.