Academics! (Level 23)
Algorithm and Part Optimization Walkthrough
The task: take an input string of only red and blue symbols and reverse it.
Unlike for our Robomecha solution, there isn't a clear correct basic algorithm to start with. Our obvious starting points are:
[Algorithm v1.0a]
Loop
1. Read the last symbol.
2. Move it to the front.
End Loop
[Algorithm v1.0b]
Loop
1. Read the first symbol.
2. Move it to the back.
End Loop
v1.0a may be particularly attractive to us because it looks an awful lot like Robomecha, which we've already solved. Let's examine the basic apparatus required for the first step of each algorithm, though. Non destructively read the last symbol:
Non destructively read the first symbol:
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.
[Algorithm v2.0]
Loop
1. Read the first symbol.
2. Transcribe the rest of the string.
3. Write the first symbol at the end.
End Loop
In Manufactoria this becomes:
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:
[Algorithm v3.0]
1. Place a G marker. (End of the unprocessed portion.)
2. Place a Y marker. (End of the entire string.)
Loop
3. Read the first symbol.
4. Transcribe until you hit G.
5. Write G.
6. Write the first symbol.
7. Transcribe until you hit Y.
8. Write Y.
End Loop
In Manufactoria:
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:
And if you wanted to use this entire device as a component in another device, you could trivially mash all the parts together to fit inside a 5x6 box.
Enjoy!
This thread is very hard to read because the long strings with no spaces extend the page to the right for all text including paragraphs that people write, forcing one to scroll to the right on each line.
Would it be possible to fix this (either client or server side?). Or maybe to convert all level codes to urls which have shorter text? (This would be easier for viewers too since they could just be clicked.)
for example
edit: firefox doesn't have this problem, chrome does
Would it be possible to fix this (either client or server side?). Or maybe to convert all level codes to urls which have shorter text? (This would be easier for viewers too since they could just be clicked.)
Sorry, I didn't realize the URLs people were posting actually worked, as I use Chrome and didn't think the browser could affect whether or not passing a variable in the URL works. (I still don't understand how this is broken in Chrome.)
Anyway, the best solution is probably to insert newlines in the level codes. I just tested it in Manufactoria and the codes work fine with newlines. Unfortunately, for this solution to work, everyone has to adhere to it, so most likely a moderator will need to edit everyone's posts.
My more interesting (0:30 with 23 parts, faster and smaller, but neither the fastest nor the smallest) solution for Robo-children:
?lvl=18&code=y12:3f3;p12:5f3;c10:6f1;r14:5f1;b10:5f1;c10:4f2;c12:4f3;c14:4f0;p13:7f3;p12:7f3;c12:11f3;q12:6f2;p11:7f3;c14:6f1;y14:7f1;y10:7f1;c12:10f3;p11:5f3;p13:5f3;c11:4f2;c13:4f0;c12:8f3;c12:9f3;
I think the smallest solutions usually end up being the most interesting in this game. This one I posted earlier, for example, is so small and simple and yet so far from what one would typically arrive at:
And yet I still wonder if it's possible to go smaller than that on robo-children (EDIT: doubtful), or at least more vertical so as to use fewer conveyor belts at the bottom (EDIT: it can!). I don't really like that aspect of the game, though... I wish I could put "accept" positions anywhere I want, similarly to how the game allows for "reject" positions anywhere.
[img_right]http://bisqwit.iki.fi/kala/snap/manufactoria-officers-machine2.png[/img_right]Sleeping over the night, I thought of an optimization to Officers! that allows me to reduce the number of functional components in the scene. However, as it turned out, the change was over-compensated by the explosion in the number of conveyer belts needed. You need tons of conveyer belts if you want two ends of the branch to go in same target. Bleh. I hate this game. Result shown on the right.
?lvl=13&code=c12:11f3;c12:12f3;g12:2f3;c12:3f3;c13:2f0;q14:2f1;b14:3f0;q14:4f1;p15:2f0;r15:3f1;y15:4f1;r10:4f2;c11:4f2;c11:5f3;c12:4f3;p12:5f7;c14:5f1;i13:3f2;y13:4f1;c13:5f2;c10:5f1;c12:10f3;c10:6f1;c10:7f1;c10:8f1;c11:6f2;b11:7f3;i11:8f1;c11:9f2;c12:6f3;q12:7f7;c12:8f0;q12:9f7;b13:7f3;r13:8f3;p13:9f4;
Here is the description of the algorithm used above. This is all spoilers, of course.
It is described as a substring replacing engine resembling regular expressions.
1 is blue
0 is red
$ means end, indicated by green symbol
Y means 2 ("carry", indicated by yellow symbol).
x means red or blue (not Y or $)
vertical line indicates a point of entry (top: label; bottom: actions)
begin
|
$ loop
| _
0x --> 0 <loop> \_ transcribe until $/Y
1x --> 1 <loop> _/
0$ --> 1 <end> --trivial +1 and done.
1$ --> Y <begin> --make carry
0Y --> 10 <red-only transcriber> <eat $> <end> --carry mixed safely
1Y --> Y0 <red-only transcriber> <eat $> <begin> --propagate carry
$ --> 1 <end> --string is empty
Y --> 10 <red-only transcriber> <eat $> <end> --string begins with Y; add 1 decimal
The previous version of this parsed "x" by using the red-blue branch (which eats the symbol), necessiting complicated jumps directly to the second part of the loop. In this version, the "x" condition is detected as the default branch of the yellow-green branch.
[img_right]http://bisqwit.iki.fi/kala/snap/manufactoria-officers-machine3.png[/img_right]Now as I think of it (again, teaching is the best way to learn), I think it can be rewritten by doing the parsing in two parts. This allows to discard checking for green value in loop2, because now the main loop is all about getting rid of carry. We can assume that as long as the loop runs, carry exists:
begin
|
$0 loop
| _
0$ --> 1 <end> \
0x --> 0 <loop> \_ if string ends in red, trivial +1 and done.
1x --> 1 <loop> / if it ends in blue, propagate carry as below.
1$ --> Y begin2 _/
|
$ loop2
| _
0x --> 0 <loop2> \_ transcribe until $/Y
1x --> 1 <loop2> _/
0Y --> 10 <red-only transcriber> <eat $> <end> --carry mixed safely
1Y --> Y0 <red-only transcriber> <eat $> <begin2> --propagate carry
// Y --> 10 <red-only transcriber> <eat $> <end> --string begins with Y; add 1 decimal (this rule is not needed because of explicitly added leading zero in the beginning)
Result shown on the right.
?lvl=13&code=g12:2f3;p7:5f6;r7:6f1;y7:7f1;q8:5f5;b8:6f2;q8:7f5;y9:4f3;g9:5f3;c9:6f3;p9:7f3;b10:3f2;q10:4f1;r10:6f0;q10:7f1;c11:3f3;p11:4f5;r12:3f0;q12:4f5;c12:9f3;c12:10f3;c12:11f3;c13:5f3;c13:6f3;c13:7f3;q12:12f3;r11:6f2;p12:6f7;c12:8f3;c13:8f0;b13:4f3;q12:7f6;b11:7f1;
It is better than the second version (above), but still not as good as the attempt in my previous post. Hmpf.
Next I consider this change in order to merge all the red-only transcribers together, taking advantage of the fact that the main loop is all about carry removal; as long as a carry is found, the loop is not complete. If EOF marker (green) is found, it is to be terminated. But reintroducing the green checks actually makes everything worse, again:
[img_right]http://bisqwit.iki.fi/kala/snap/manufactoria-officers-machine4.png[/img_right]
begin
|
$ loop
| _
0$ --> 1 <end> \
0x --> 0 <loop> \_ if string ends in red, trivial +1 and done.
1x --> 1 <loop> / if it ends in blue, propagate carry as below.
1$ --> Y begin2 _/
|
$ loop2
| _
0x --> 0 <loop2> \_ transcribe until $/Y
1x --> 1 <loop2> _/
0Y --> 10 <red-only transcriber> <eat $> <begin2> --carry mixed safely
1Y --> Y0 <red-only transcriber> <eat $> <begin2> --propagate carry
Y --> 10 <red-only transcriber> <eat $> <begin2> --string begins with Y
0$ --> 0 <end>
1$ --> 1 <end>
?lvl=13&code=q11:9f0;g12:5f3;i12:6f7;c12:8f3;p12:9f3;q13:9f6;y11:7f1;b13:7f1;i11:8f4;i13:8f0;q12:7f7;c11:10f2;b12:10f3;c12:11f3;i13:10f6;r13:11f0;c14:10f0;c12:12f3;c15:4f3;c15:5f3;c15:6f3;c15:7f3;c15:8f3;c15:9f3;c15:10f0;b10:8f2;r14:8f0;c10:9f1;c14:9f1;y11:4f3;b12:3f2;q12:4f1;g13:2f3;c13:3f3;p13:4f5;r14:3f0;q14:4f5;c12:2f2;c11:5f2;c11:6f2;q13:5f1;p14:5f0;r14:6f1;c13:6f2;
[img_right]http://bisqwit.iki.fi/kala/snap/manufactoria-officers-machine3b.png[/img_right]EDIT: Thanks for the Academics! guide Pointless Boy. I could not figure out the merging those two types of repeaters.
But at least I know you can remove the green-eater before the last repeater in the bottom of your final solution. Seeing as how the yellow-eater that follows it does the very same thing. It does not reduce the number of parts, though. Annoying conveyer belts.
EDIT 2: Conveyer belts can sometimes be substituted with other items. Here's Officers! in 32 parts. Not something to be proud of, though! It is a variant of version 3.
?lvl=13&code=g12:2f3;p7:5f6;r7:6f1;y7:7f1;q8:5f5;b8:6f2;q8:7f5;y9:4f3;g9:5f3;c9:6f3;p9:7f3;b10:3f2;q10:4f1;r10:6f0;q10:7f1;c11:3f3;r12:3f0;q12:4f5;r11:6f2;p12:6f7;b13:4f3;b11:7f1;q12:8f3;p11:4f3;q12:9f3;q12:12f3;q12:11f3;q12:10f3;q13:5f3;q13:6f3;q12:7f3;q13:7f0;
Rocket Planes! in 2:23 using only 14 parts:
?lvl=27&code=r12:6f3;y12:7f3;p12:8f7;q12:9f4;b13:8f0;q12:5f4;r11:9f1;r11:4f3;p11:5f2;b11:6f1;y12:4f3;c11:7f1;p11:8f6;c12:10f3;
Could it be smaller?
<klmz> it reminds me of that people used to keep quoting adelikat's IRC statements in the old good days
<adelikat> no doubt
<adelikat> klmz, they still do
Rocket Planes! in 2:23 using only 14 parts:
?lvl=27&code=r12:6f3;y12:7f3;p12:8f7;q12:9f4;b13:8f0;q12:5f4;r11:9f1;r11:4f3;p11:5f2;b11:6f1;y12:4f3;c11:7f1;p11:8f6;c12:10f3;
Could it be smaller?
Exceptional, and I doubt it.
Bisqwit wrote:
... Officers ...
I'll probably make a walkthrough for Officers today or tomorrow, but until I do, a hint for simplifying your algorithm: which is easier, propagating a carry flag, or merely indicating at the end of a string that one or more carries has occurred? Consider adding 1 to something like 10111:
A hard way: 10111 -> 1011c0 -> 101c00 -> 10c000 -> 11000
An easier way? 10111 -> 1011c -> 101cc -> 10ccc -> 11ccc -> 11000
merely indicating at the end of a string that one or more carries has occurred? Consider adding 1 to something like 10111:
A hard way: 10111 -> 1011c0 -> 101c00 -> 10c000 -> 11000
An easier way? 10111 -> 1011c -> 101cc -> 10ccc -> 11ccc -> 11000
begin
|
$0 loop
| _
0$ --> 1 <end> \
0x --> 0 <loop> \_ if string ends in red, trivial +1 and done.
1x --> 1 <loop> / if it ends in blue, handle carry as below.
1$ --> Y begin2 _/
|
$ loop2
| _
0x --> 0 <loop2> \_ transcribe until Y
1x --> 1 <loop2> _/
0Y --> 10 <Y-to-0 transcriber> <eat $> <end>
1Y --> YY <Y-to-Y transcriber> <eat $> <begin2> --advance carry
Hmm. That's not as much a change as I imagined. In fact, pretty much nothing was changed compared to before (on the far right). It's now 31 parts.
Here's the version without first loop:
[img_right]http://bisqwit.iki.fi/kala/snap/manufactoria-officers-machine6.png[/img_right]
?lvl=13&code=q12:12f7;q12:11f7;q12:10f7;y9:4f2;c9:5f1;y9:6f1;q10:4f5;b10:5f2;q10:6f5;c10:7f1;g11:4f2;i11:5f3;y11:6f1;c11:7f0;c12:4f3;c12:5f3;c12:6f3;p12:7f3;c13:5f0;c13:6f2;q13:7f6;b13:8f3;r14:5f0;i14:6f3;c14:7f1;q14:9f7;b15:6f3;c15:7f3;c15:8f3;r15:9f0;r12:3f3;g12:2f3;c13:9f0;q12:9f7;
So thanks for the hint, but I'm still missing something obvious :)
This is by the way the language in which I've designed the puzzle solutions I used C++ for. I used C++ for testing and debugging, but design was done in lists like this.
[img_right]http://bisqwit.iki.fi/kala/snap/manufactoria-officers-machine3b.png[/img_right][img_right]http://bisqwit.iki.fi/kala/snap/manufactoria-officers-machine5.png[/img_right][img_right]http://bisqwit.iki.fi/kala/snap/manufactoria-officers-machine7.png[/img_right]EDIT: Hmm, with the carry-stream idea you gave, the $ delimiter in the carry loop becomes unnecessary.
begin
|
$0 loop
| _
0$ --> 1 <end> \
0x --> 0 <loop> \_ if string ends in red, trivial +1 and done.
1x --> 1 <loop> / if it ends in blue, propagate carry as below.
1$ --> Y loop2 _/
|
0x --> 0 <loop2> \_ transcribe until Y
1x --> 1 <loop2> _/
0Y --> 10 <Y-to-0 transcriber> <end>
1Y --> YY <Y-to-Y transcriber> <loop2> --propagate carry
Not that this changed anything. The space is still taken by those nasty conveyer belts. Still 31 parts. The same idea cannot be used in the one-loop version because there's no carry necessarily there.
Alt. layout for the above: ?lvl=13&code=c12:9f3;c12:11f3;c12:10f3;c12:12f3;c12:8f3;c9:1f2;q9:2f6;p9:3f0;q9:4f2;c10:1f2;b10:2f3;c10:3f0;r10:4f1;y11:1f3;y11:2f3;q11:3f0;g12:2f2;y12:3f0;q12:4f4;p12:5f6;c13:3f3;c13:4f3;c9:5f3;r13:5f0;c13:2f3;b11:5f2;c11:4f3;q12:6f6;c13:6f1;b12:7f3;c11:8f2;b9:7f2;r10:7f3;q10:8f6;c9:6f3;
Here's my first try at Officers!, potentially interesting because there is no concept of carry bits:
?lvl=13&code=g12:2f3;g9:4f2;r9:5f2;q10:4f7;p10:5f1;y10:6f1;q11:4f0;b11:5f0;y11:6f0;r11:9f2;b11:11f2;p12:6f7;q12:7f6;g12:8f3;p12:11f7;q12:12f6;b13:6f0;b13:9f0;r13:11f0;y12:3f3;r12:4f3;c12:5f3;c11:3f2;p12:9f7;q12:10f4;
It's 25 parts. I suspect smaller solutions are possible, but not with the same algorithm.
I have been working on Officers today too, got it down to 18 parts.
On the levels like androids or teachers, where it ask for some number of red then some number of blue, it does not specify if there can then be something extra after that or if it has to be the end. Has anyone seen a test case that tests this? Or know which way it should be?
I have been working on Officers today too, got it down to 18 parts.
Wow! This doesn't work when given an empty string though, which the game recognizes as zero, but I guess it doesn't specify whether handling that is required...
I understand Flagitious's program. Instead of two symbols for eof and carry, it uses one for both, and assumes that all instances of that symbol aside from one mean carry. But not Nitsuja's :)
Basically it's sequence of these regexps:
s/^/0/ <once>
s/$/G/ <once>
s/1G/GG/ <repeat while matches>
s/G// <once, delete one G>
s/0G/10/ <once>
s/G/0/g <once, automatically repeats>
I understand Flagitious's program. ... But not Nitsuja's :)
My algorithm was simply: Starting with the last 0 in the string, invert all the bits. (I prepend a 0 first so that there is always a last 0 to be found.)
I have been working on Officers today too, got it down to 18 parts.
Wow! This doesn't work when given an empty string though, which the game recognizes as zero, but I guess it doesn't specify whether handling that is required...
It can be modified to handle empty string correctly, although I'm going to side that this is not required.
Bisqwit I am certainly not out of your league, there are just many many levels
My Officers! algorithm worked almost as-is to solve Generals! too. I basically just had to swap a few colors around so that it would search for the last 1 instead of the last 0. It's still not a very optimal way of solving the problem (27 parts).
?lvl=14&code=g9:4f2;r9:5f2;q10:4f7;p10:5f1;y10:6f1;q11:4f0;b11:5f0;y11:6f0;r11:9f2;b11:11f2;c12:5f3;q12:7f6;g12:8f3;p12:9f7;q12:10f4;p12:11f7;q12:12f6;b13:9f0;r13:11f0;r13:6f0;p12:6f3;c12:4f3;c13:4f0;y11:3f2;g12:2f3;i12:3f7;b13:3f3;
Bisqwit, if it makes you feel any better, I barely understand what flagitous did and I'm still completely stuck on Police!, that's definitely not "out of your league"...
EDIT: Okay, I'm not stuck on Police! anymore, but my first solution looks pretty bad (46 parts):
?lvl=19&code=g12:2f3;b11:4f3;c11:5f2;p12:4f3;y12:5f3;r13:4f3;c13:5f0;y12:3f3;p12:6f3;r13:6f0;b11:6f2;q12:7f1;g11:7f2;c13:7f3;b12:8f3;r14:8f3;c14:9f0;c13:9f0;p11:9f4;y12:9f0;r11:8f3;b11:10f1;q10:9f5;p9:9f4;r9:8f0;b9:10f0;c8:8f3;c8:9f3;c8:10f3;p8:11f7;b9:11f3;r7:11f3;c9:13f2;c10:13f2;c11:13f2;c10:5f2;p13:8f3;q9:12f6;c10:12f1;c10:11f1;c10:10f1;c10:8f1;c10:7f1;c10:6f1;c7:12f2;c8:12f2;
I converted my solution to Generals as well, it turned out to be simpler in the edge cases: 17. I can barely understand mine as well btw. Also my attempt at police was 46 too.
Edit: interesting side challenge, no conveyors
rocket planesacademics
I got Police! in 38 with a slightly tidier attempt at the same algorithm: (Edit: and there's a better solution on page 2)
?lvl=19&code=r11:3f2;y12:2f3;b13:3f0;y12:4f3;p12:3f7;q12:12f6;p13:12f0;r13:13f1;b13:11f3;c9:7f2;y9:8f1;c10:7f2;q10:8f3;r10:9f2;g11:6f2;r11:7f2;p11:8f1;c11:9f1;y11:10f1;q12:6f7;p12:7f1;q12:8f7;b12:9f0;q12:10f4;c13:6f2;b13:7f0;y13:8f1;r13:9f3;c13:10f0;c14:6f3;c14:7f3;c14:8f3;p14:9f7;c14:10f0;b15:9f3;c15:10f0;y12:11f3;g12:5f3;
Has anyone found an efficient solution to Ophanim? Everything I've found has 20+ conveyors and the algorithm seems far too basic to be close to optimal.
?lvl=30&code=y12:2f2;c13:2f3;p13:3f2;c13:4f2;g14:2f0;q14:3f2;i14:4f7;r15:2f3;p15:3f4;b15:4f1;c11:6f2;c11:7f1;c11:8f1;b12:5f3;p12:6f6;r12:7f1;c12:8f0;r12:10f2;c13:5f2;q13:6f0;i13:8f6;c13:9f2;p13:10f1;c13:11f1;c13:12f1;q13:13f3;y14:5f3;p14:6f7;c14:8f0;p14:9f2;r14:10f2;y14:11f3;p14:12f3;q14:13f7;c15:5f0;q15:6f6;g15:7f3;p15:8f3;c15:9f3;p15:10f7;q15:11f5;c15:12f1;c15:13f1;r16:5f3;p16:6f4;b16:7f1;c16:8f3;c16:9f0;r16:10f0;g16:11f3;p16:12f7;c16:13f0;g13:7f3;
Nice list, I'd missed a few of those.
Robotanks can be done in 25 in a few different ways. Nothing interesting but it seems no-one's posted one.
?lvl=15&code=p12:4f4;p12:5f7;c12:11f3;p13:11f3;c12:3f3;c13:5f3;c11:5f3;c11:6f2;p13:7f3;c12:6f2;c13:6f3;c12:7f3;c14:7f3;c14:11f3;c14:12f0;i13:12f6;c14:8f0;c13:8f3;c12:8f2;p13:9f3;c12:9f3;c14:9f3;c14:10f0;c13:10f3;c12:10f2;
Politicians 26:
?lvl=22&code=c12:12f3;g12:6f3;q12:10f0;p12:11f7;c12:3f3;c13:6f2;p13:4f4;r13:3f3;b13:5f1;c12:5f3;q12:4f6;g12:2f3;r11:8f2;p12:8f7;c12:9f3;p13:8f6;r13:9f1;c13:7f1;c12:7f3;c14:4f0;c14:5f1;p14:6f2;b14:7f1;q15:4f6;p15:5f1;g15:6f1;
I have two more solutions optimized for least number of parts:
Engineers in 1:47, 23 parts:
?lvl=24&code=c12:5f3;c12:6f3;c12:7f3;c12:8f3;c12:9f3;c12:10f3;c12:11f3;c12:12f3;p12:4f7;g12:2f3;c12:3f3;c14:4f1;q11:4f4;c10:4f1;i11:3f4;p11:2f5;r11:1f3;r10:3f2;p13:2f5;b13:1f3;b14:3f0;i13:3f0;q13:4f2;
Seraphim in 0:36, 21 parts:
?lvl=29&code=p12:6f7;c12:5f3;c12:4f3;c12:7f3;c12:8f3;c12:9f3;c12:10f3;c12:11f3;g12:3f3;p10:6f6;p14:6f0;r14:7f1;b10:5f3;b14:5f3;r10:7f1;p11:4f5;p13:4f5;g11:5f1;g13:5f1;q13:6f2;q11:6f4;
EDIT: Also Police! with a (silly) minor optimization:
Police! in 2:43, 34 parts:
?lvl=19&code=g12:3f3;y12:2f3;y12:6f3;c12:4f3;c12:5f3;b11:8f2;r13:8f0;c12:8f3;p12:9f3;q11:9f5;q13:9f1;c14:5f0;c15:9f1;r15:8f1;p15:7f0;c14:6f1;b15:6f3;b13:6f0;r13:4f0;p13:5f4;y10:9f1;b10:8f1;c10:7f2;c11:7f2;i12:7f7;c13:7f2;q14:7f6;g14:8f1;y14:9f2;q12:10f2;p12:11f3;b11:11f2;r13:11f0;q12:12f0;
Non destructively read the first symbol:
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:
And yet I still wonder if it's possible to go smaller than that on robo-children (EDIT: doubtful), or at least more vertical so as to use fewer conveyor belts at the bottom (EDIT: it can!). I don't really like that aspect of the game, though... I wish I could put "accept" positions anywhere I want, similarly to how the game allows for "reject" positions anywhere.
Bisqwit I am certainly not out of your league, there are just many many levels
