Robomecha! (Level 28)
Algorithm and Part Optimization Walkthrough
The task: take an input string of only red and blue symbols and output an otherwise identical string with the last symbol moved to the front.
Generally I find Manufactoria levels to be easier if you try to come up with a basic algorithm on paper, which you bit by bit translate into Manufactoria-compatible components.
[Algorithm v1.0]
1. Read the last symbol
2. Move it to the front
Since we've all played the game a bit, we realize we can't just up and read the last symbol. Our tape is a LIFO stack. The only element on the tape we can read is the first one, by popping it off the stack. (It's also important to note the very act of positively identifying a symbol is destructive, which comes into play when we need to preserve some or all of the input.) The only way we can write an element to the tape is by pushing it onto the stack -- we can only append. This necessitates some modifications to our algorithm.
[Algorithm v2.0]
1. Transcribe symbols until the last one is reached.
2. Write the last symbol.
3. Transcribe the remainder of the string from the beginning again.
Though still very rough, we are starting to reach a point where we can translate our algorithm in to Manufactoria components. For example, we have a basic transcriber:
Of course, a R/B-only string will never leave such a device, so we use the trick of first marking the end of the input string with a different color:
That's almost useful, but how do we know when we've reached the last symbol? Just a little ingenuity allows us to modify the transcriber to "record" the last symbol for us by having a separate branch for each option:
If the last symbol is blue, we head off to the left. If the last symbol is red, we head off to the right.
Now that we've modified the transcriber into something useful for our task, let's get back to the paper algorithm and refine it further.
[Algorithm v3.0]
1. Write Y to mark the end of the string.
Loop
2. Read R/B
3. Attempt to read Y
3a. Y: Exit loop and follow appropriate branch.
3b. Not Y: Write R/B and continue loop.
End Loop
Blue Branch
4. Write blue.
5. Transcribe the rest of the string.
Red Branch
4. Write red.
5. Transcribe the rest of the string.
Let's try to translate those branches back into Manufactoria:
We run into a familiar problem with this naive attempt, namely we've forgotten we always need a way to exit a transcriber. We solved this problem last time by using a Y marker, let's try that again:
We're almost there! We've made all the needed modifications to the string, we'll just have a leftover yellow marker whenever the last transcription is done, or if the string is blank. Let's get rid of it:
And that's it. This device will accept any R/B string, move the last symbol to the front, and have the string ready to be sent to the exit whenever the robot passes through any of the three downward pointing G/Y branches. For a task this simple it's pretty clear we probably can't do any better from an algorithmic standpoint. Can we reduce the number of parts we are using in Manufactoria, though?
One of the first things to look for when trying to reduce part usage is
duplicated components. Do we have any of those here? Well, we have three transcribers in our device. One of them is a special transcriber that recognizes the last component in a string, so we probably can't get rid of that one. The other two are just normal transcribers though. Do we really need both of them? Though we don't realize any immediate gains, let's use conveyors to get rid of one of the transcribers:
Another thing to look for when trying to reduce part usage is branches that allow for what I call "redundant passthrough." In the above picture we had to do some pretty ugly gymnastics with conveyors to allow for a blank string (which is actually one of the tests!) But let's think about what really happens when we get a blank string. It just goes straight down, failing to be redirected by any R/B branch. If that's the case, a blank string could pass through as many R/B branches as we wanted without issue. Why not send it through the second transcriber to get rid of some conveyors?
Now we're talking! That's starting to look really slick. Can we do
even better? Here's where we really need to start thinking outside the box. So far we've been stuck thinking about a transcriber as a device we enter through a R/B branch. But in truth you can enter any single part from any direction, and any multi-part component through any of its external pieces. What happens if we enter a transcriber through one of the writing parts? We end up writing an extra symbol of a particular color.
But wait ... isn't that what our algorithm is doing just before we go to the last transcription step? We write an extra symbol of a particular color, then transcribe the rest of the string. What if instead of explicitly writing the extra symbol, we let the transcriber do it by entering it from a different direction?
Wow! Add in to- and from-conveyors and we get the final, fully optimized solution:
Or if you prefer the level code:
?lvl=28&code=c10:7f2;b11:5f2;b11:7f2;c12:5f3;p12:6f3;p12:7f3;r13:5f0;r13:7f0;c14:7f0;y12:4f3;y10:6f3;y14:6f3;q11:6f5;q13:6f1;q12:8f2;c12:3f3;c12:9f3;c12:10f3;c12:11f3;
I hope you folks found this informative. If you'd like me to make walkthroughs for any other levels, just ask. Most of my solutions are very well optimized, and I remember the steps I went through to get there.
Familiarity notwithstanding, it looks like v1.0b might be the simpler approach, both from an algorithmic standpoint and a parts-used standpoint. Let's flesh out the starting point we chose, then.
Actually running this, we note a few problems. One, our robot has no way to exit the device, and two, our naive algorithm doesn't actually do what we thought it would do. Successively moving each first symbol to the back of the entire string doesn't reorder the string. We need to move each first symbol to the back of the portion that hasn't been moved yet. (Or, alternatively, move each first symbol to the front of the portion that has already been moved.) So we need a marker for both the end of the entire string, and the end of the unprocessed portion of the string. Luckily, Manufactoria gives us another color. Back to the algorithm:
There are more conveyors there than necessary, but hopefully they help to delineate each part of the device as they correspond to steps in our algorithm. Anyway, we're getting quite close now to a device that actually works. Do we have an exit strategy? It turns out we don't need any modifications to exit the device. Once the entire string has been reversed, the G marker indicating the start of the reversed string will in fact be the start of the entire string. That is, the string will be of the form G...Y where the ... in the middle is any sequence of reds and blues. The initial R/B branch in our device that determines the first element of the string will naturally and correctly direct the robot down instead of to either of the colored branches. At that point all we need to do is remove the leading G and terminal Y and be done. Our fully functional device:
Now let's start optimizing! As always our first step is to look for duplicated components. The main portion of our device has four transcribers, two for each branch. Moreover, each transcriber has a different exit condition. The first transcription exits on G. The second transcription exits on Y, and never the twain shall meet. We can almost assuredly use both the same transcriber and the same G/Y branch for both steps! Let's try it:
If you've read the Robomecha walkthrough, you should quickly recognize another optimization. We have a situation where we are writing a color, then transcribing the rest of the string. We can do this with fewer parts by simply entering the transcriber through the correct writer. Combine that with the straightforward removal of extraneous conveyors and we are left with a very compact device indeed:
Or if you prefer the level code: