Manufactoria - Make Turing Machines with Conveyor Belts

[Nix]

The record score table was here, now moved to the new page. I'm leaving the edit history behind.


Updates since moving to this page:

J.P. broke a set of size records. In Generals he reduced his own 19 parts to 18, in Judiciary he erased jareds's 44 parter with a cool 39, and in Engineers my record 25 suffered a loss to J.P.'s 24, although the new one takes almost 70% more steps.

I found a little bit more speed on the simple Robobears and Milidogs.


2010-06-13

Metatron finally gets a really good speed record, as jestingrabbit almost doubles the speed going from his previous 4M to 2.07M steps in the solution posted below.

Jani found another 152 steps to eliminate from Robocats.


2010-06-14

I improved Robocats speed even more, 462 steps off Jani's record. I'm quite sure it's still not optimal. I also found a faster 20 part Officers, replacing J.P.'s 180k with 139k. The speed record is still 81k with 103 parts.


2010-06-15

J.P. took back the fastest 20 part Officers with 135k, and went down to 40 parts in Ophanim, erasing my record of 44. He's really selling speed for size, spending 3.8M instead of 1.4M steps.

(edit 1) I made a faster Teachers much like my speed Androids. It's not pretty but lightning fast at 8872 steps, down from jareds's decent 17214. I used a load of 70 parts while jareds had just 38, although I was already a tad faster with 35 parts.


2010-06-16

Added Xanthir's 23-part Engineers from the thread, displacing J.P.'s 24-part one.

(edit 1) J.P. got back with an unbelievable 21 parts in Engineers.


2010-06-18

Great new head-scratchers from tehtmi in the thread: Robo-children in 17 replaces my 18, and Seraphim in 19 beats jareds's 21.

(edit 1) Added the faster 23-part Politicians posted by Steve496, to replace my slower same-sized one.

(edit 2) I made Engineers in 20 parts with the same new trick that's obviously been behind many of the recent improvements. Gone is J.P.'s 21-part record, which was a lot slower too.

(edit 3) I found a refreshing new Politicians in only 20 parts. It's even slower than my old 23-part one that Steve496 outpaced, but beats them nicely in size.

(edit 4) I wasn't expecting the same new approach to shrink Robo-children to 16 parts, but that way I erased tehtmi's 17-parter from the list, and was slightly faster too.

(edit 5) In the thread tehtmi showed a 64-part Metatron, nicely smaller than J.P.'s 72.


2010-06-20

A long-standing record by Berengal was broken when Nabb posted a 32k to 28k speed improvement for Robo-children. (edit 2010-06-25: disqualified for errors with certain long inputs)


2010-06-21 Moved the updated table and scores.txt to the new page. Edit history continues there.

[Nix]

I really like Roboparrots too. It would really fit in the game. It feels like there should be a simpler solution, but here's mine of 37 parts:
?lvl=32&code=c12:9f3;c12:12f3;q12:5f4;c12:6f3;c12:7f3;c12:8f3;y12:2f3;g12:3f3;c12:4f3;p11:5f2;p12:10f3;b11:10f2;r13:10f0;q12:11f6;g8:7f1;g8:3f3;r9:4f3;p9:5f2;b9:6f1;y11:3f0;q10:3f1;b11:2f0;p10:2f7;r9:2f2;r9:3f0;c8:4f3;c8:5f2;c8:6f1;q10:7f7;y11:7f0;b9:8f2;p10:8f5;r11:8f0;b9:7f0;b11:6f3;r11:4f1;q10:5f7;&ctm=Roboparrots!;OUTPUT:_the_input,_repeated_twice!;b:bb|brbb:brbbbrbb|:|rrb:rrbrrb|bbrbrr:bbrbrrbbrbrr;13;3;0;

[J.P.]

I couldn't think of any particularly clever approach for Roboparrots, but here's a 35-part solution:

?lvl=32&code=r9:7f3;p9:8f2;b9:9f1;c10:6f2;b10:7f1;q10:8f4;y10:9f1;c11:6f2;r11:7f2;g12:6f3;p12:7f7;p12:9f3;c13:6f0;b13:7f0;c14:6f0;r14:7f1;q14:8f2;y14:9f1;r15:7f3;p15:8f4;b15:9f1;c12:5f3;q12:10f2;p12:11f7;b13:11f0;r11:11f2;q12:12f6;r11:3f2;p12:3f7;b13:3f0;y12:4f3;y12:2f3;q12:8f2;r13:9f2;b11:9f0;&ctm=Roboparrots!;OUTPUT:_the_input,_repeated_twice!;b:bb|brbb:brbbbrbb|:|rrb:rrbrrb|bbrbrr:bbrbrrbbrbrr;13;3;0;

[jestingrabbit]

Another metatron. This one should be a significant increase in efficiency.

Spoiler:

It contains a couple of biggish innovations. The first is the way that I work the "read through to the end of a string of blues and reds, and remember how it ends", there's a small number of strings where it will be a touch less efficient (a string of only blues), but those are few and far between. Given that these blocks are used O(n²) times, the small decrease in time gives a speed up that would be worth it all by itself. But they are also a lot smaller, and that is what has allowed the me to wedge another loop into the frame. This extra loop deals with the case where the bits of one of the numbers have exhausted, so that you're left with less to worry about, but you need to design to take advantage of this. In previous solutions I had something that worked well for about 3/8ths of the circumstances where this happened, but given the test data, it makes sense to work to try to get this final loop in there. The only thing that bugs me about this particular solution is that this additional loop is two steps longer than it could be, but I just can't manage to shoehorn it into the corner if I didn't give it that extra bit of length. This basically means that I might well have gotten away with a change in syntax and reused a block to get the same speedup, which is irritating.

?lvl=31&code=c6:1f3;c6:2f3;c6:3f2;y6:4f3;b6:5f3;c6:6f2;r6:7f1;y6:8f1;c6:9f2;c6:10f1;c6:11f1;c7:1f0;r7:2f2;c7:3f3;q7:4f3;c7:6f2;q7:8f5;c7:9f1;r7:10f2;c7:11f0;c8:1f0;p8:2f1;b8:3f1;g8:4f3;r8:5f3;c8:6f2;b8:7f1;y8:8f1;b8:9f3;p8:10f7;c8:11f0;r9:2f3;p9:3f7;q9:4f3;c9:6f2;q9:8f5;p9:9f1;r9:10f1;g10:2f0;b10:3f0;g10:4f3;b10:5f3;p10:6f6;r10:7f1;g10:8f1;b10:9f0;i12:2f6;y12:3f3;c13:2f0;b13:3f2;g13:4f2;q14:2f1;p14:3f5;r14:4f1;b15:3f3;p15:4f3;r16:4f0;p11:2f3;q11:13f3;r10:12f2;p11:12f7;b12:12f0;q11:11f3;c10:11f3;c12:11f3;p11:10f3;i12:10f6;c13:6f1;p13:5f6;c12:4f3;c12:5f2;q12:6f3;i11:6f7;c11:3f3;c11:4f3;c11:5f3;g10:10f0;c12:9f3;c11:7f3;q12:8f2;g12:7f2;r13:7f3;b13:9f1;p13:8f2;c13:10f0;c14:10f0;i15:9f5;c15:10f0;c14:5f3;c15:5f3;c11:8f2;q15:8f0;c14:6f3;c15:6f3;b18:11f3;r15:11f3;p14:11f1;r13:11f2;p18:12f0;b16:12f0;p15:12f7;b14:12f1;c13:12f0;r18:13f1;g16:13f2;q15:13f3;c14:13f0;c13:13f1;r17:13f1;p16:10f4;c17:11f1;c15:7f3;c14:7f3;q14:9f5;c16:11f0;c16:9f3;g14:8f3;g17:10f0;q17:12f2;

[Arancaytar]

I just finished the robot engineers (palindrome tester) one.

The operating concept is unsurprisingly simple (recursive palindrome algorithms are easy, after all) but the actual mechanics and workflow is tricky.

Spoiler:

The idea is to match the current first to the current last and delete both, until 0 or 1 element is left. Deleting the first is easy - but recognizing the last and deleting it takes a sort of "look-ahead".

Spoiler:

While inside one of the two scanning branches (for red or blue, depending on the first element), after each R/B branch, it first looks for the terminator (green) and only copies the R/B back if it is not yet reached. Other than that, each branch is a simple two-state machine that accepts if the terminator follows the color of the first element, and otherwise rejects. If the terminator is found after a matching R/B, the R/B is not copied back (thus stripping it off the end), and we move back to the beginning.

If the tape is empty or contains only a single element, it is accepted as symmetrical.

Spoiler:

?lvl=24&code=c12:2f3;c12:3f3;p12:6f7;c12:4f3;g12:5f3;c14:6f2;c13:6f2;p15:6f2;b14:7f1;p15:3f5;r15:4f1;q15:5f1;q16:3f2;q14:3f4;b13:3f3;q15:7f0;q9:5f1;p9:6f0;q9:7f6;c10:6f0;r10:7f1;i11:6f2;b9:4f1;q8:3f4;q10:3f2;p9:3f5;r11:3f3;c11:4f0;c10:4f3;c10:5f3;r17:3f1;c15:2f3;b7:3f1;c9:2f3;c16:6f3;c16:7f3;c16:8f3;c16:9f0;c15:9f0;c14:9f0;c13:9f0;c12:9f3;c8:6f3;c8:7f3;c8:8f3;c8:9f2;c9:9f2;c10:9f2;c11:9f2;c12:10f3;c12:11f3;c12:12f3;c9:8f2;c10:8f2;c14:8f0;c13:8f0;c12:7f3;i12:8f1;c11:8f1;c11:7f1;c11:5f2;c13:4f3;c13:5f3;c7:2f1;c7:1f2;c8:1f2;c9:1f3;c15:1f3;c16:1f0;c17:1f0;c17:2f1;c14:2f0;c13:2f0;c10:2f2;c11:2f2;c15:8f0;

Unfortunately, the Policeman (finding the string's center) and the binary adder elude me. Little-endian would be easy, but I can't figure out how to process the carry starting from the left element. I suppose I'll have to make one pass per digit...

Edit:

I did solve the Seraphim test though, using a similar concept as for the palindrome.

Spoiler:

?lvl=29&code=c12:10f3;c12:11f3;c15:5f1;c9:5f1;p9:4f5;b8:4f2;r10:4f0;q9:3f7;g8:3f2;c10:3f2;c11:3f2;c12:3f3;c12:4f3;p15:4f5;p10:6f5;g10:7f1;q10:8f4;r11:7f3;p11:8f4;b11:9f1;y12:6f3;c12:7f3;p12:8f3;c12:9f3;r13:7f3;p13:8f2;b13:9f1;p14:6f5;g14:7f1;q14:8f2;c12:5f3;c9:6f1;c15:6f1;r16:4f0;b14:4f2;q15:3f3;g16:3f0;c14:3f0;c13:3f0;

Edit:

Adder (Officer) solved. My earlier error was not adding a terminator and rotating the tape to its correct alignment after every operation.

Spoiler:

The carry can be tracked with a yellow bead after the digit. Just append a yellow bead at the start, and then do the following:

Copy everything until you reach [BY] (1 - carry) or [RY] (0 - carry). On the first case, write [YR] (carry - 0), roll the tape to its starting position (copy until you reach the green terminator and reappend the terminator) and repeat, and on the second, write [B] (1), roll the tape to its right alignment and accept.
It goes like this:

BBRBBB - 55
BBRBBBYG
BBRBBYRG
BBRBYRRG
BBRYRRRG
BBBRRRG
BBBRRR - 56

?lvl=13&code=c12:6f3;p12:7f3;y12:2f3;g12:3f3;c12:4f3;r9:4f2;p10:4f1;b11:4f0;q10:3f3;y9:3f2;c11:3f2;q11:7f5;b11:6f2;q13:7f1;r13:6f0;y10:7f1;r10:6f1;c10:5f1;c12:5f3;c14:7f3;c14:8f0;c13:8f0;b12:8f3;p12:9f3;r13:9f0;b11:9f2;q12:10f0;c12:11f3;c12:12f3;

[Tirian]

Unfortunately, the Policeman (finding the string's center) and the binary adder elude me. Little-endian would be easy, but I can't figure out how to process the carry starting from the left element. I suppose I'll have to make one pass per digit...

That's about the size of it. To me, they were similarly motivated designs.

Also, my designs made a quantum leap forward when I saw how other people (maybe just Nix, I suppose) wrote the "code" to pop a dot off the back of a string. It's something that can be freakishly space-efficient if done properly, and I was far from it which made half of the later designs far more tangled and snow than they needed to be. If you can improve that design for yourself, then you'll find it paying off well.

[Xanthir]

Policemen got me for quite a while too. It requires a significantly new thought to solve, though once you've figured out how to find the middle the rest of it is easy. Hint:

Spoiler:

Put a dot at each end, and move them inward.

[Tirian]

Just for lulz, here is my Ophanim solution drawn as how I sort of imagined a queue machine would be drawn if anyone ever did. (Yes, it doesn't strip the leading reds out first, and it should.)

Spoiler:

I suppose the game would have less replay value if it were like this instead of having to twist the branches and conveyor belts ideally, but it kind of makes me feel closer to the science.

[squareroot]

Wow! I'm surprised so many people play this game too, this is cool. For me, there are currently 3 I'm trying to solve - Officer (add 1), Police (yellow in the middle), and Academic (reverse the input string). I know how to do Police for sure, and I've got two ideas for Officer that I haven't tried yet:

Spoiler:

First idea is to reverse the string (once I figure out Academic) and then go through pretty simply and replace one red with a blue, or a blue with red and then add the next one, keep on carrying... until you can stop. Then reverse it again.

The second idea is to go through to the end and replace a red with a blue, and a blue with a green. Then go through the string again, and if you reach a green you increment the previous one and change the green to a red. If no greens are encountered, return the robot.

I haven't really tried much in the way of efficiency yet, I probably should though...

[Nix]

I did solve the Seraphim test though, using a similar concept as for the palindrome.

Spoiler:

?lvl=29&code=c12:10f3;c12:11f3;c15:5f1;c9:5f1;p9:4f5;b8:4f2;r10:4f0;q9:3f7;g8:3f2;c10:3f2;c11:3f2;c12:3f3;c12:4f3;p15:4f5;p10:6f5;g10:7f1;q10:8f4;r11:7f3;p11:8f4;b11:9f1;y12:6f3;c12:7f3;p12:8f3;c12:9f3;r13:7f3;p13:8f2;b13:9f1;p14:6f5;g14:7f1;q14:8f2;c12:5f3;c9:6f1;c15:6f1;r16:4f0;b14:4f2;q15:3f3;g16:3f0;c14:3f0;c13:3f0;

This has problems with some inputs. The ones the game gives tend to be too easy. Your machine accepts anything that matches while the first string lasts, even if the second one continues after that. The simplest input to break it is [GR]. It's easy to fix though, without increasing the part count even. There are also two unused green writers.

Your Officers has two unused blue writers and one yellow one. Otherwise, all solutions are good.

[Arancaytar]

I did solve the Seraphim test though, using a similar concept as for the palindrome.

Spoiler:

?lvl=29&code=c12:10f3;c12:11f3;c15:5f1;c9:5f1;p9:4f5;b8:4f2;r10:4f0;q9:3f7;g8:3f2;c10:3f2;c11:3f2;c12:3f3;c12:4f3;p15:4f5;p10:6f5;g10:7f1;q10:8f4;r11:7f3;p11:8f4;b11:9f1;y12:6f3;c12:7f3;p12:8f3;c12:9f3;r13:7f3;p13:8f2;b13:9f1;p14:6f5;g14:7f1;q14:8f2;c12:5f3;c9:6f1;c15:6f1;r16:4f0;b14:4f2;q15:3f3;g16:3f0;c14:3f0;c13:3f0;

This has problems with some inputs. The ones the game gives tend to be too easy. Your machine accepts anything that matches while the first string lasts, even if the second one continues after that. The simplest input to break it is [GR]. It's easy to fix though, without increasing the part count even. There are also two unused green writers.

Your Officers has two unused blue writers and one yellow one. Otherwise, all solutions are good.

Yeah, I noticed that problem. I used the idea I had for the Judge (which I didn't actually implement until today), which

Spoiler:

first used the Policeman to split the string and then this for checking the equality of the two halves. The problem, of course, is that the implicit assumption that the two strings are going to have equal length only works for the Judge, not the Seraphim that gets two arbitrary strings.

Anyway, I've finally implemented the Metatron, so I now have a game-passing (though not free of errors in some cases) solution for all of them.

Judge:

?lvl=20&code=p11:3f0;r11:4f1;b11:2f3;q10:3f4;q10:4f4;y10:5f3;p9:4f0;b9:3f0;r9:5f0;c8:4f3;c11:6f2;c8:6f3;q15:6f6;g15:7f3;c15:9f2;b16:5f3;p16:6f0;r16:7f1;r16:8f2;c16:9f2;p17:6f1;p17:8f1;p17:9f2;b18:8f0;p17:10f3;r18:10f0;b16:10f2;p17:12f3;p16:12f0;b16:11f3;r16:13f1;q15:12f4;g15:11f1;q17:7f7;y18:7f1;c18:6f0;y18:11f3;c18:12f0;c14:8f3;i14:9f7;c14:10f3;c14:11f0;c13:11f0;c12:11f3;c12:12f3;p8:7f3;q7:7f5;b7:6f2;q9:7f1;c10:6f2;i12:6f3;c13:9f2;c13:8f3;y6:7f3;b6:8f2;y10:7f2;r11:7f3;b11:9f1;p11:8f2;q12:8f4;c12:7f1;c13:4f1;c7:8f2;c8:8f2;c9:8f2;c10:8f2;y14:1f2;b14:2f2;c15:1f3;p15:2f3;y15:3f0;r16:2f0;g12:3f0;c14:3f0;c13:3f0;c12:2f2;c13:2f1;c13:1f2;r9:6f0;y8:5f3;c8:3f3;c12:5f1;q13:6f6;g13:7f3;y13:5f3;p14:6f0;r14:7f1;b14:5f3;c12:4f2;q17:11f1;q15:10f5;q15:8f3;

Metatron:

Spoiler:

Since we already have an incrementer and a decrementer (the officer and general, respectively), we just have to decrement one and increment the other string until one reaches 0. This is less easy than it sounds, since the machine has to scroll the tape around to toggle between numbers quite a bit (twice in a row, to get to the beginning of the same number, after each pass that shifts the carry). The field won't have much room left - although it is possible to save a lot of space through careful reuse and overlap of elements. For example, each scroller (an R/B copier that terminates by reading and rewriting a green delimiter) can be aligned to begin by writing a red, yellow or green before entering the loop. This solution takes exponential time, since the binary number is decremented one step at a time.

Spoiler:

?lvl=31&code=c18:4f3;c18:7f3;c18:8f3;c18:5f3;c18:6f3;c18:9f3;c18:10f3;c18:11f3;c18:12f3;c18:13f0;c17:13f0;c16:13f0;c15:13f0;c14:13f0;c13:13f0;p13:2f2;c13:1f3;b13:3f2;p14:3f3;r15:3f0;y14:4f2;q15:4f5;r15:5f2;g16:4f3;p16:5f7;b17:5f0;y16:6f2;q17:6f0;r15:6f0;q15:7f6;p15:8f0;q15:9f2;y15:10f0;b16:7f3;c16:8f0;r16:9f1;c17:7f3;g17:8f0;c17:9f1;c17:10f1;q17:11f4;y17:12f1;r16:10f3;b16:12f1;p16:11f2;q14:11f3;p14:12f1;b15:12f0;r13:12f2;g15:11f2;b14:10f3;y13:11f2;r11:2f3;p11:3f2;b11:4f1;q12:3f4;g12:2f2;b13:6f2;g13:7f0;p14:6f3;q14:7f1;q11:6f6;p11:7f4;q11:8f2;r12:6f3;c12:7f0;b12:8f1;c11:5f1;c13:8f1;c14:2f2;c18:3f3;p15:1f3;b14:1f2;r16:1f0;q15:2f5;c16:2f2;r17:1f3;b17:3f1;p17:2f2;q18:2f0;p12:10f2;q13:10f4;c13:9f1;r12:9f3;b12:11f1;y11:9f0;q10:10f3;p10:11f1;b11:11f0;r9:11f2;r10:9f3;g11:10f2;c10:6f1;c10:5f2;q10:7f0;

[Arancaytar]

Wow! I'm surprised so many people play this game too, this is cool. For me, there are currently 3 I'm trying to solve - Officer (add 1), Police (yellow in the middle), and Academic (reverse the input string). I know how to do Police for sure, and I've got two ideas for Officer that I haven't tried yet:

Spoiler:

First idea is to reverse the string (once I figure out Academic) and then go through pretty simply and replace one red with a blue, or a blue with red and then add the next one, keep on carrying... until you can stop. Then reverse it again.

The second idea is to go through to the end and replace a red with a blue, and a blue with a green. Then go through the string again, and if you reach a green you increment the previous one and change the green to a red. If no greens are encountered, return the robot.

I haven't really tried much in the way of efficiency yet, I probably should though...

I started out with something close to the second idea, but then realized it could be even simpler:

Spoiler:

Just append your green to the end first, and then repeat: Scroll through till you find your green, and replace a "BLUE-GREEN" with "GREEN-RED" (1 +1 = 0, carry the 1 forward) or a "RED-GREEN" with a "BLUE" (0 +1 = 1, no carry) and go through again from the start. Since there is only the one green carry counter, once you reach a Red-Green or a Green at the start of the string (both to be replaced by a Blue), you can finish.

[walkerm930]

Here's my solution for engineers. The machine is surprisingly simpler than i thought one of the last levels was going to be.

what i did:

Spoiler:

Instead of checking if the first was the same as the last, I checked if the last was the same as the first, deleting them from the tape as i checked. If I hadn't done it the first way, I'm pretty sure it would it would have been larger and more complicated.

code:
?lvl=24&code=g12:2f3;c12:8f3;c12:9f3;c12:10f3;c12:11f3;c12:12f3;c12:3f3;c10:4f2;c10:6f1;g10:7f1;c11:5f2;r11:6f2;q11:7f1;c12:4f3;c12:5f3;c12:6f3;p12:7f7;c13:5f0;b13:6f0;q13:7f5;c14:4f0;c14:6f1;g14:7f1;p13:4f4;c14:5f1;p11:4f6;c10:5f1;

[Xanthir]

Oh, wow, that's a brilliant solution.

Spoiler:

Massively smaller than checking the first against the last, because you only have to create a guarded read once, rather than once for each side. Your particular arrangement is smaller, but slightly slower, than my first try with this strategy.

I've reduced your construction to be both smaller and faster, and also produced an even smaller variant (slightly slower). The following illustrates both (just remove the one you don't want to look at):
?lvl=24&code=g12:3f3;c10:4f1;c11:3f2;b11:4f2;q11:5f1;p12:5f3;c13:3f0;r13:4f0;q13:5f5;c14:4f1;c12:4f3;c12:6f3;c12:7f3;c12:9f3;c12:11f3;c12:12f3;p10:5f0;b9:5f2;c10:3f2;c14:3f0;p14:5f2;r15:5f0;c10:9f2;b10:10f1;c11:7f2;p11:8f1;i11:9f3;q11:10f4;q13:10f2;r14:10f1;p13:8f5;c14:9f0;i13:9f2;c13:7f0;g12:8f3;p12:10f3;c12:2f3;

[Xanthir]

Nix: I have a new record smallest Engineers, at 23 parts:

Code: Select all

?lvl=24&code=c12:6f3;c12:11f3;c12:12f3;c10:4f2;b10:5f1;c11:2f2;p11:3f1;i11:4f3;q11:5f4;c12:2f3;g12:3f3;c12:4f3;p12:5f3;c13:2f0;i13:4f2;q13:5f2;c14:4f0;r14:5f1;c12:7f3;c12:8f3;c12:9f3;c12:10f3;p13:3f1;


Edit: Fixed a flipped gate that I didn't test. >_<

[Notch]

It fails the first test?

[Tirian]

True, but you only need to flip the branch to the right of the green marker to make it work.

[Xanthir]

Argh, I can't believe I did that. After I established that the left side worked correctly, I just mirrored it to the right without testing. I hate it when I do that and get my gates backwards. >_<

Anyway, corrected the solution in the previous post.

[phlip]

Slowest level 1?
?lvl=1&code=c12:6f2;c13:6f1;c13:5f2;c14:5f3;c14:6f3;c14:7f0;c13:7f0;c12:7f0;c11:7f1;c11:6f1;c11:5f0;c10:5f3;c10:6f3;c10:7f3;c10:8f3;c10:9f2;c11:9f1;c11:8f2;c12:8f2;c13:8f2;c14:8f3;c14:9f0;c13:9f0;

How about this:
?lvl=1&code=i12:6f1;i13:6f0;c13:5f2;c14:5f3;c14:6f0;i11:6f6;c10:6f1;c10:5f2;c11:5f3;c10:9f2;c10:8f3;c12:7f2;i13:7f3;c14:7f3;c14:8f3;c14:9f0;c13:9f1;c13:8f1;c12:8f3;c11:7f0;c10:7f3;c11:9f1;c11:8f2;

I got one better:
?lvl=1&code=c10:5f3;c11:5f0;c13:5f3;c14:5f0;c10:6f2;i11:6f4;i12:6f5;i13:6f5;c14:6f1;c10:7f3;i11:7f0;i12:7f1;i13:7f1;c14:7f0;c10:8f3;c11:8f1;c12:8f0;c13:8f3;c14:8f1;c10:9f2;c11:9f2;c13:9f2;c14:9f1;
I think that's the worst possible:

Spoiler:

By parity, any path is going to take an even number of steps (ie, counting both the start and end, it will visit an odd number of squares, counting duplicates). This actually applies to every puzzle - which is why it can move two spaces per second, and always take a whole number of seconds, regardless of the shape of the level. If you imagine colouring the squares as a checkerboard, then every step is moving from black to white or vice-versa, and (since the height of the grid is always odd) the start and end are on the same colour.

So that path visits every space and has 6 bridges. A longer path would have to visit every space and have at least 8 bridges (as if there were 7 bridges it would have to miss a space, meaning it would take the same amount of time as the 6-bridge version). There are only 9 places a bridge can be placed and used - the 9 spaces in the middle of the grid. If all 9 are bridges, then a robot will come in the entrance, go straight down to the exit, and finish, so that's not an option. Similarly, if there are 8 bridges, the one of those middle 9 that isn't a bridge must be on the middle column, or the same will apply.
However, since it's a FSM with no input, it can only visit each state once without infinite-looping (and every square has one state except a bridge which has two). So whatever is in that spot that isn't a bridge, it'll only have one entrance direction and one exit direction. But it's neighbouring three or four bridges (depending on which spot on the column it is), and bridges must have an entrance or exit in each of the 4 directions (otherwise the bridge won't be used twice, and may as well be a normal conveyor). So nothing will fit. The corners of the middle 9 only neighbour 2 bridges, but if the only non-bridge is one of those, then there'll be an unbroken vertical conveyor down the middle column. Thus, no 8-bridge solution exists, and the 6-bridge is the longest: 25 spaces + 6 double-visited - 1 for fencepost-counting = 32 steps, 16 seconds.

[squareroot]

I really like the "worst case" problem - the slowest possible. I agree that the solution for #1 posted above is the best - er, worst - and I managed to get 1:17 for level 2:

Code: Select all

?lvl=2&code=i13:6f0;i12:6f1;i12:7f5;c12:8f2;c13:8f1;i13:7f4;c13:5f2;c14:5f3;c14:6f0;i11:6f6;c10:6f1;c10:5f2;c11:5f3;i11:7f5;c10:8f1;c10:7f2;c11:8f3;c11:9f0;c10:9f1;c14:7f3;c14:8f3;p14:9f3;c13:9f0;

P.S. - Could people please put level codes inside code tags, it makes it much easier to copy.

[Xanthir]

Heads up - I couldn't be arsed to find a c++ compiler to run Nix's code, so I translated it into javascript for running in the browser. It works and can run levels to completion now, I just need to put together a slightly prettier interface (right now you just edit a string in the <script> tag of the html page to change your level code).

[Xanthir]

And here we are:
Manufactoria Emulator

Next priorities:
1. Prettier board display (ascii isn't great, and it's very information-low too).
2. In-page level editor.

Edit: Nix, what do you actually do to obtain your numbers? I don't want to spend the time deciphering your actual runner code.

[Nix]

Great! But predictably not too fast, so getting comparable numbers for speed may be inconvenient.

In counting steps, it seems your counts are low by one, as if you don't count the last move (to ground or exit) or the first one (down from the entrance tile). Once that is corrected, you should get equal step counts just by summing over all inputs from 0 to 10 in length for the red/blue input levels, regardless of the result being rejection or accept/return. Some inputs are skipped if not applicable to a level, those are no-blue (zero) inputs for Generals, and odd length inputs for Police. For the last three levels, I'm counting all legal inputs (those with exactly one green) with length from 1 to 11, which is certainly too slow for JavaScript.

Edit: It seems that your switches read a color off the tape even if it's not one of the tested colors. At least they do something wrong in that case. Breaks lots of solutions in the later levels.

[Xanthir]

Yeah, I'm probably off-by-one. I don't count the first move - I just treat the entrance square as an empty tile (which it is, after the first step), and start the pointer one square below that with the "input direction" set appropriately.

My switches shouldn't be popping wrong colors off of the tape. I've run several of the later levels, and they work correctly. For example, right now I'm looking at my Engineers solution, which involves both types of switches and 3 colors.

Do you have a particular level code that demonstrates it failing?

[Nix]

I do the same with the entrance, but I count steps when entering a tile, so entering the first tile below entrance is the first step.

Here's an example, if not a real solution: ?lvl=10&code=y12:4f3;p12:5f3;c12:7f3;c12:8f3;c12:9f3;c12:10f3;q12:6f2;

Your emulator shows it rejecting the empty string, while clearly it should not.

Edit: It might not be eating wrong colors after all, since even this does the same confuses me: ?lvl=10&code=y12:4f3;c12:7f3;c12:8f3;c12:9f3;c12:10f3;q12:5f2;c12:6f3;

[Xanthir]

What browser are you trying to run this in? I *know* this won't work correctly in IE, because of the way it handles inheritance of the Array builtin. (I can fix that, I just didn't bother with it.)

I ask because my emulator accepts the empty string just fine when I run it in Chrome. ^_^

(I suspect that my checker for robostilts is broken, though...)
Edit: Scratch that, all of my checkers for "OUTPUT" levels are broken. Output levels should *never* dump a robot on the floor, but right now my checker logic counts it as a success if you dump it on the floor while the tape is in a state that the level wouldn't accept.
Edit2: Err, it appears that I have a further bug regarding YG reader orientation. I assumed that the YG readers would be the same as the BR readers with a color swap, but apparently that's not true. I must have gotten lucky so far for my levels with a YG reader to work.

[Nix]

My mistake. The second code does work as expected, I was confusing the feedback related to Robostilts with what's really supposed to happen. But the first one shows rejects both in Opera and Firefox.

Edit: But Y/G and B/R are the same, aren't they? I'd think it's something else. Especially since my two codes do work differently in your emulator. Or did I make mistakes with copying around the codes and such, since now they seem to work the same (wrong) again. Maybe you changed the code.

[jestingrabbit]

I thought this was an interesting idea for a level, but its actually pretty dull. Basically, divide the input by three and return the quotient and remainder. Unfortunately, the way that binary is parsed makes it a bit too touchy.

Code: Select all

?ctm=Tribots;Input_is_n_in_binary._Output_is_q_-_green_-_r_where_3q_+_r_=_n_and_0<=_r_<3;bb:bgr|bbb:brgb|bbrbr:brrrgbr|r:rgr;13;3;1;

[tehtmi]

Smaller solutions for

Robo-children! (17 parts)

Code: Select all

?lvl=18&code=c12:7f3;b11:3f3;p11:4f2;r11:5f1;c11:6f1;q12:4f0;g12:5f3;p12:6f3;c13:4f0;c13:5f1;p13:6f6;b13:7f1;g12:3f3;c12:8f3;c12:9f3;c12:10f3;c12:11f3;

Seraphim (19 parts)

Code: Select all

?lvl=29&code=b10:5f3;p10:6f2;r10:7f1;p12:6f3;c12:9f3;c12:10f3;c12:11f3;r13:3f3;p13:4f0;b13:5f1;c13:6f1;q12:7f4;q12:8f0;q11:6f0;y11:5f1;q12:4f6;y12:3f3;g12:5f3;p11:4f5;

[phlip]

Hmm, that [edit](by which I mean jr's post)[/edit] gives me an idea:

Code: Select all

?ctm=Collatz!;OUTPUT:_If_the_input_is_even,_divide_it_by_2!_If_it's_odd,_triple_it_and_add_1!;br:b|b:brr|brrbr:brrb|brb:brrrr|brbb:brrrbr;13;3;1;

Note: I just made this rule now, I have no idea if it's even possible to solve in the space. Good luck!

[andy11235]

Collatz wasn't all that hard in the end. Dividing by 2 is trivial, and multiplying by 3 can be done recursively using a 2 bit carry. Here's my (very un-optimised) solution.

Code: Select all

?lvl=32&code=c12:2f3;g12:3f2;c13:3f2;p14:3f2;q14:4f0;q14:2f4;r13:2f3;b13:4f1;c15:2f1;c14:1f2;c15:1f2;q15:3f4;c16:1f2;c17:1f2;c18:1f3;c18:2f3;c18:3f3;c18:4f3;c18:8f3;c18:7f3;c18:6f3;c18:5f3;c18:9f3;c18:10f3;c18:11f3;c18:12f3;c18:13f0;c17:13f0;c16:13f0;c15:13f0;c14:13f0;c13:13f0;g14:5f2;b15:5f2;r16:5f2;r17:5f3;c17:6f3;c17:7f3;c17:8f3;c17:9f0;g16:9f0;c15:9f0;p14:9f0;q14:10f6;q14:8f2;b15:8f3;r15:10f1;g14:11f2;r15:11f2;p16:11f1;b17:11f0;q16:10f2;g14:7f0;c13:7f0;c11:7f0;c10:7f0;p9:7f0;p9:6f1;p9:8f3;b10:6f1;b8:8f0;r7:8f1;r7:7f1;b8:6f1;r8:5f1;b8:4f2;c7:6f1;c7:5f1;c7:4f1;c7:3f2;c8:3f2;b10:5f0;r9:5f1;c9:4f2;c10:4f2;p11:4f2;r11:3f3;b11:5f1;c12:7f0;r10:8f3;b10:9f0;b9:9f0;c8:9f0;c7:9f0;c6:9f1;c6:8f1;c6:7f1;c6:6f2;c9:3f3;c12:4f3;c12:5f3;q12:6f3;c13:6f2;c14:6f2;c15:6f2;c16:6f2;q13:9f1;c12:9f3;c12:12f3;p12:10f3;r13:10f0;b11:10f2;q12:11f0;&ctm=Collatz!;OUTPUT:_If_the_input_is_even,_divide_it_by_2!_If_it's_odd,_triple_it_and_add_1!;br:b|b:brr|brrbr:brrb|brb:brrrr|brbb:brrrbr;13;3;1;

[squareroot]

What about a recursive collatz? If it's an integer, return 1. But you have to do it sloooooooowly!

[jestingrabbit]

What about a recursive collatz? If it's an integer, return 1. But you have to do it sloooooooowly!

You could maybe ask for a unary/binary representation of the number of iterations it takes to reach 1.

[squareroot]

That would be pretty good... I suppose one you have a basic Collatz function, it's extremely simple to turn it into one that iterates it and increments it. The only two things would be space, and how to increment in a way that doesn't interfere with the calculation. Maybe some sort of "blockade" of one color that couldn't occur otherwise? I'm not sure though.

[Steve496]

tehtml's Robo-children solution allows a faster 23-part Politicians to be constructed:

Code: Select all

?lvl=22&code=p12:4f3;r13:4f0;c12:3f3;p11:4f0;r11:5f1;b11:3f2;g12:2f3;b13:5f3;p13:6f4;r13:7f1;c13:8f1;q12:6f6;g12:7f3;p12:8f7;c12:9f3;c11:6f2;c11:7f1;p11:8f0;b11:9f1;c12:10f3;c12:11f3;c12:12f3;c12:5f3;

[Xanthir]

Smaller solutions for

Robo-children! (17 parts)

Code: Select all

?lvl=18&code=c12:7f3;b11:3f3;p11:4f2;r11:5f1;c11:6f1;q12:4f0;g12:5f3;p12:6f3;c13:4f0;c13:5f1;p13:6f6;b13:7f1;g12:3f3;c12:8f3;c12:9f3;c12:10f3;c12:11f3;

Could you explain this one, tehtmi? I don't understand how it works, or why you're constantly swapping the colors.

Edit: Well, now that scores.txt has been updated and I see J.P.'s Engineers, I think I understand it a bit better. Clever!

[Nix]

@Xanthir: Thanks for spoiling all over the place! To be honest, I'm happy you gave the hint for Robo-children, it was subtle enough to still make it fun to solve myself, and I was definitely getting frustrated.

[tehtmi]

I'll attempt to explain Robo-children!:

Spoiler:

First, realize that swapping reds with blues (as happens a whole bunch) does not change whether or not the condition is true.

The first thing that happens is a color swapping. This swapping serves no real purpose, but allows for a more efficient layout of the machine.

Then we get to the red-blue selector in the middle column. The red path is roughly what you would expect: you try to find and consume the next blue while preserving all the rest of the input. Except we actually color swap the remaining input -- this is so we can reuse the reversing circuit used below instead of constructing a separate copying circuit.

The blue path of the selector doesn't consume anything, it just color swaps the input -- which means that the next time we get to the red-blue selector in the middle column the first token will be red.

That's pretty much it.

[edit]

Here's a smaller Metatron (64 parts):

Code: Select all

?lvl=31&code=g12:2f3;b11:5f3;p11:6f6;r11:7f1;y12:5f3;q12:6f4;r12:4f3;i12:3f1;q10:4f1;y11:4f3;c13:3f0;c9:2f3;c9:3f3;r8:3f2;c8:6f2;y9:6f2;r10:5f2;b10:7f2;p10:6f2;p9:4f7;q8:4f5;c7:4f3;c7:5f3;c7:6f2;q9:5f4;b10:2f0;i10:3f0;c11:3f0;c13:4f1;y13:5f1;q13:6f6;p13:7f6;q13:8f2;b14:6f3;q14:7f4;i14:8f7;r15:7f0;c15:8f1;y12:7f2;c11:10f2;c11:11f0;p12:10f2;c12:11f0;y13:9f0;q13:10f4;r13:11f2;q13:12f5;c14:10f0;p14:11f7;q14:12f5;b15:11f0;y14:9f3;r11:9f3;q12:9f0;y12:8f0;c11:8f1;c9:7f1;c9:8f1;c9:9f1;c9:10f1;c9:11f1;b10:10f2;q10:11f5;c12:12f3;

[Xanthir]

I've spent some more time on my Manufactoria emulator. First, I've moved it to http://www.xanthir.com/manufactoria. Second, I've fixed the bug making GY readers fail sometimes.

Finally, and most excitingly, I've got much prettier board display! No more crappy ascii art for me. I spent some time reproducing the components in SVG, so now the board looks just like it does in the real game. The only thing I haven't done yet is create the entrance/exit tile image, but you know where those are anyway.

This was a fun opportunity to learn a bit more SVG, too - creating the conveyors was a good excuse to learn SVG animation.

Next step is adding a single-tape evaluation mode, and then making the robot and tape animate as it evaluates that tape. That should put me about 75% of the way to have a complete game emulator in javascript. ^_^

(Note - I've been doing all my dev in Chrome so far. I know it won't work right in IE, and no promises for Firefox or Opera.)

So, feel free to use this to quickly visualize a posted level without having to load up the entire game.

[Nabb]

Faster solution for robo-children:

Code: Select all

lvl=18&code=g12:3f3;p12:4f7;p14:11f3;i12:11f1;p9:4f7;p8:4f0;p8:5f0;p8:6f0;p8:7f0;p8:8f0;c8:3f2;c9:3f3;p8:10f3;p9:10f3;p10:10f3;c7:10f1;p8:9f6;c7:9f2;i12:10f7;p13:4f1;p11:4f1;p10:4f1;c16:3f0;p16:4f2;p16:5f2;p16:6f2;p16:7f2;p16:8f2;p16:9f2;p16:10f4;p16:11f3;c17:10f0;c17:11f1;p15:11f3;c15:3f3;r11:11f1;p11:10f5;c13:10f2;b14:10f3;c13:11f0;p15:4f7;p14:4f1;r11:7f3;c11:8f2;q12:6f0;p12:7f7;i12:8f5;c12:9f3;g13:6f0;b13:7f3;y13:8f2;c14:6f0;r14:7f3;p14:8f2;b14:9f1;c15:6f0;c15:7f1;c15:8f1;c12:5f3;

Anyone made a brainfuck interpreter yet? I was going to attempt one back when this game came out, but I couldn't be bothered making my own interpreter (for a larger board and faster execution).