Manufactoria - Make Turing Machines with Conveyor Belts

Nix · Postby **Nix** » Mon Jul 19, 2010 5:16 pm UTC

turingnow: Rejected when should have accepted [BBRGRBRR]. I didn't look so I don't know if you can fix this.

aduubian · Postby **aduubian** » Wed Jul 21, 2010 5:13 am UTC

Nix wrote:Here are the smallest and fastest known solutions for each level. Their correctness has been verified (up to a limit) and speed (in total execution steps to process a constant test set of inputs) measured with my checker and score keeper program
17 Androids! 12 parts 16098 steps ( 63041 in game) by Nix
42 parts 9051 steps ( 36204 in game) by Nix

I think I found a better solution for Androids! (does it count if it wouldn't work if they tested a sequence that they don't test?)
with the enter door on a5, I put BR gates oriented R-right on b3 and b5, and a BR gate R-left on b4. right belts on c3 and c4, down belts on c5, d5, e5, f5, g5, h5. It works only because an even number of blue followed by an even number of red is not tested. This gives me 11 parts, but I'm not sure how many steps

Nix · Postby **Nix** » Wed Jul 21, 2010 11:07 am UTC

aduubian: Try it in a recent version of the game and you'll see that it also now tests a huge number of inputs to find a fail (though yours will already fail on quite a simple input). To get on my list, in principle the solutions have always had to work on any input, and for that my program has tested them on quite a bunch.

If you do make a record solution, you can and should post the save code from the game (click the disk icon and copy-paste) instead of a description.

Xanthir · Postby **Xanthir** » Wed Jul 21, 2010 1:07 pm UTC

Or, better, take that save code you got from Nix's description, and slap it on the end of a link to http://www.xanthir.com/manufactoria, like turingnow most recently did with his solution for Ophanim. (Once you click that link, check out how the part of the url from the ? onward is just the level code that you get from the game.) That way everyone can just click a link to see, and run, your level.

You can also use my emulator to quickly do total-coverage testing of your machine. As Nix said, we don't accept a machine onto the lists unless it passes for all possible inputs (as far as we can tell - for most levels, just testing it on every possible input of length 10 or below is sufficient).

turingnow · Postby **turingnow** » Wed Jul 21, 2010 5:30 pm UTC

Nix wrote:turingnow: Rejected when should have accepted [BBRGRBRR]. I didn't look so I don't know if you can fix this.

Oops. I see where I went wrong. The in-game testing only does input length 7. All is not lost though.
All that time spent optimizing (cheating) for length 7 probably helped me come up with this new Ophanim.

Thanks to Xanthir for his online checker.
Thanks to Nix for his database.
Thanks also for the c++ checker even though I cant get Ubuntu to install in Virtual PC.

Tehforsch · Postby **Tehforsch** » Thu Jul 22, 2010 12:40 pm UTC

I don't think there's a simpler way for robo-children than that, although it may not work for really large tests it passed all of them ... But its not really satisfying:

Code: Select all

?lvl=18&code=p12:3f7;p11:3f7;p10:3f7;p9:3f7;p8:3f7;p7:3f7;p13:3f7;p14:3f7;p15:3f7;p16:3f7;p17:3f7;c12:4f3;c12:5f3;c12:6f3;c12:7f3;c12:8f3;c12:9f3;c12:10f3;c12:11f3;

Xanthir · Postby **Xanthir** » Thu Jul 22, 2010 3:18 pm UTC

Tehforsch: Use a url like this to share your level.

And no, that's not a useful machine. It will obviously fail for a tape with six blue followed by six red, for example. If used in the actual game, it should fail and call you a cheater, as this level specifically tests a super-long string to fail machines like this.

Tehforsch · Postby **Tehforsch** » Thu Jul 22, 2010 5:10 pm UTC

And no, that's not a useful machine. It will obviously fail for a tape with six blue followed by six red, for example. If used in the actual game, it should fail and call you a cheater, as this level specifically tests a super-long string to fail machines like this.

Yes thats what I meant by "its not really satisfying" and after having used this I built a real solution for the level which won't fail for large inputs, I was just amused because this thing actually made the level easier than Androids. (I didn't know there was a newer version before ... )

kjsharke · Postby **kjsharke** » Sun Jul 25, 2010 1:48 am UTC

I'm late to the parade, but here is an alternate challenge--

Seraphim took me a long time because I misunderstood the instructions: I thought you were given a string of reds and blues (as before), and you had to insert a green in the middle if it repeated itself, or trash it otherwise (so like Judiciary, but nondestructive and on a smaller board). I never actually tried to test it until I had something working, though I did see that some of you had very small solutions, which blew my mind.

My solution:

Spoiler:

If you want to check it, you can patch Nix's checker and change the level code to 290:

Spoiler:

Edit: for Xanthir

Axidos · Postby **Axidos** » Sun Jul 25, 2010 2:03 pm UTC

Nix wrote:aduubian: Try it in a recent version of the game and you'll see that it also now tests a huge number of inputs to find a fail (though yours will already fail on quite a simple input). To get on my list, in principle the solutions have always had to work on any input, and for that my program has tested them on quite a bunch.

If you do make a record solution, you can and should post the save code from the game (click the disk icon and copy-paste) instead of a description.

That version's malevolence engine is taking 32764 time units to test the first level and 32762 to test the second. Should they really be such large numbers?

Postby **jestingrabbit** » Sun Jul 25, 2010 2:46 pm UTC

If its a level where it tests all sequences that are at least 12 in length, that's about 2¹³=~8k different sequences that need testing. If you take just 4 steps for each string you need to test, that's enough to get 32k. If its a six long level, you need an average of 2⁸=256 steps for every sequence. Its quite easy to get to that sort of number.

Xanthir · Postby **Xanthir** » Wed Aug 11, 2010 10:48 pm UTC

Interestingly, IE9 pp4 now runs my emulator correctly. It doesn't animate the SVG yet, so the conveyor belts are static, and it has a somewhat strange limitation on url length right now that makes it refuse to open larger solutions, but otherwise the functioning is perfect.

(You do have to kick it into using IE9 rendering mode to make the SVG display - it's trying to default the page to IE7 rendering right now.)

ignatius · Postby **ignatius** » Thu Sep 02, 2010 11:35 pm UTC

Obviously, I'm somewhat late to the party, so I hope that there are still some non-robotic entities out there to read this! Anyway, for what it's worth, here are three custom levels I made:

Robojournalists!
Our robotic investigators bring you today the news of tomorrow - and for all other days, too.
Produce as many yellows as told by the binary input (blue=1, red=0)

Roboeditors!
ROX News, the Robotic Objective eXaminer. fair & balanced [tm]* and 100% cognitive consonant.
Accept only strings containing a red sequence longer than any blue sequence!

Robolawyers!
RAG, the robotic advocate corps, for child molesters, bankers and YOU. Now with 100% less ethics!
With BLUE as opening and RED as closing bracket, check syntax of strings!

All games are playtested, so I hope there won't be too many bugs left. Could't try the links, though ...

ignatius

* no kidding, "fair & balanced" IS a registered trademark of FNC.

Xanthir · Postby **Xanthir** » Fri Sep 03, 2010 5:20 am UTC

ignatius wrote:Obviously, I'm somewhat late to the party, so I hope that there are still some non-robotic entities out there to read this! Anyway, for what it's worth, here are three custom levels I made:

Robojournalists!
Our robotic investigators bring you today the news of tomorrow - and for all other days, too.
Produce as many yellows as told by the binary input (blue=1, red=0)

I see what you did there.

ignatius · Postby **ignatius** » Fri Sep 03, 2010 11:46 pm UTC

Xanthir wrote:I see what you did there.

Not sure what you mean, but as I never could get those links links to work with my setup, either, I styled the url after phlip's Roboparrots! post. If it doesn't work, just paste the "?cmt=.." string into the level-editor load box.

If you referred to the problem, yes, it's simply a binary to unary conversion.

If you referred to the subversive content (you ARE from Texas after all), remember that I'm just a degenerate Eurojerk and that the Robots all come from Asia, anyway (duck) ... ;-)

Xanthir · Postby **Xanthir** » Sat Sep 04, 2010 7:27 am UTC

ignatius wrote:
Xanthir wrote:I see what you did there.

Not sure what you mean

Robojournalists generate a lot of yellow, yellow journalism, etc.

turingnow · Postby **turingnow** » Tue Sep 07, 2010 8:56 pm UTC

ignatius, thanks for the new levels.
Here's my roboeditors solution.

conradceo · Postby **conradceo** » Wed Sep 22, 2010 9:42 pm UTC

Greetings, robot consultant.

Our tester was involved in a freak robot accident and is now in a coma. For Teresa, we are all hoping for the best outcome. This leaves us in a bind. We need the three designs she was working on to be completed soon.
Design 19
Design 20
Design 31

I'm not much of a tester myself, so I don't know how difficult the task I am asking for is. Good luck.

Conrad Ceo
Pointy-Haired Boss
Acne Robots Inc.

skeptical scientist · Postby **skeptical scientist** » Mon Nov 15, 2010 7:03 am UTC

Thread necro! I don't usually read the coding forum so I missed this thread, but someone linked the game in the comic thread for Friday's comic, and so I wasted most of my weekend. I wish I'd seen it sooner!

jestingrabbit wrote:You're right, its down to 64 now. And yes, the heat death of the universe would arrive before it terminates on some very simple input.

Spoiler:
?lvl=31&code=q6:8f2;y6:9f3;r6:10f2;g6:11f2;b7:7f2;p7:8f4;b7:9f1;p7:10f7;q7:11f1;r8:6f3;i8:7f7;c8:8f0;b8:10f0;c8:11f2;q9:4f1;c9:5f1;p9:6f5;c9:7f1;p9:8f5;g9:9f1;q9:10f2;y9:11f1;c10:4f2;r10:6f0;c10:8f0;b10:10f3;p10:11f0;b11:4f2;c11:7f3;p11:8f2;c11:9f2;b11:10f2;r11:11f0;g12:3f3;p12:4f3;y12:5f3;q12:6f0;g12:7f0;q12:8f2;c12:9f3;p12:10f3;q12:11f3;b12:12f2;r13:4f0;c13:5f0;r13:6f2;c13:8f2;i13:9f0;b13:10f1;c13:11f3;p13:12f3;q14:5f3;p14:6f1;r14:7f3;p14:8f2;r14:9f0;r14:12f0;g15:5f0;b15:6f0;y15:7f1;q15:8f0;y12:2f3;c14:13f0;q13:13f7;

Jestingrabbit, mind telling me what it's doing, so I don't have to figure it out from your (exceedingly poorly commented!) code? My solution was the horribly inefficient

Spoiler:

but I'm guessing yours was a good deal worse, based on the comment.

Also, if anyone knows what J.P.'s solution is, or why it's so slow, I'm curious.

Postby **jestingrabbit** » Mon Nov 15, 2010 8:20 am UTC

No no, that was exactly what I was doing. The thing is, if you just input 2^n and 1, you'll be cranking for a *long* time, the complexity of the algorithm is something like C*n^2*2^n where C is on the order of about 20, and that will be plenty slow if you let n=120 for instance. Compared to my speed solution, which would solve it in linear time, and even on worst case is O(n^2) (n the length of the input), the slow solution is monumentally slow.

I might have made a bit of an exageration, but not a big one.

scarecrovv · Postby **scarecrovv** » Mon Nov 15, 2010 9:02 am UTC

I just finished engineers! I am now obsolete! Yay! That was fun. Now on to the extra ones that appeared at the bottom.

skeptical scientist · Postby **skeptical scientist** » Mon Nov 15, 2010 9:41 am UTC

jestingrabbit wrote:the complexity of the algorithm is something like C*n^2*2^n where C is on the order of about 20

That's true. I need to get out of the habit of thinking of running times in terms of f(number represented by input) rather than f(size of input). I was thinking, based on that bad habit and the running times of the sample inputs (which were in the neighborhood of 5-10 minutes) that heat death was a horrible exaggeration, but actually one would only need an input of length ~100 to start approaching it, and legal inputs (under the game's cap of 50) would take longer than the age of the universe.

Just for fun, I decided to try running it on the worst-case input of length 10. I estimate it will take about an hour to run.*

Has anyone tried to do primality testing yet? I'm sure I don't want to try making one that will fit, but then I'm using around five times the number of components as other people here to do relatively simple things like reversing a string.

*Edit: it would have been done by now, but it's been running long enough that the flash app is starting to lag. This could take a while.

Postby **jestingrabbit** » Mon Nov 15, 2010 11:13 am UTC

skeptical scientist wrote:Has anyone tried to do primality testing yet? I'm sure I don't want to try making one that will fit, but then I'm using around five times the number of components as other people here to do relatively simple things like reversing a string.

Primality testing... would be more than a little tricky. Even using space efficient forms would still leave you with a hell of a task, whether you set it in unary or binary.

Given how cold the thread is, I figure there's not much to lose in presenting some sort of crib notes on how to do stuff, or really just one thing.

Spoiler:

So there you go, my thoughts on guarded reads.

skeptical scientist · Postby **skeptical scientist** » Mon Nov 15, 2010 11:44 am UTC

Speaking of bad addition algorithms, the one I implemented:

Code: Select all

add(a,b){
if b==0 return a;
else return add(a++,b--);

is nowhere near as slow as the original buggy implementation, which performed the following:

Code: Select all

add(a,b){
if b==0 return a;
else return add(b--,a++);

It took me a minute to figure out that it was looping (running the machine at 50x speed), and another couple of minutes to figure out why, since figuring out what the machine is doing isn't quite like reading code. Fortunately this bug was easily fixed, once I realized what was happening.

jestingrabbit wrote:The basic function that you need in just about every level worth thinking about is a "guarded read".

That's true. I used basically the top right one (except upside down). When I first did it, I had a few extra conveyors in there, making it 50% slower and 40% bulkier, until I realized they were completely superfluous.

The bottom one is clever. It looks like, in addition to being faster, it could also be used as a much more compact way of getting something that stops reading when it gets either a yellow or a green, which I had to do for my adder. My version was much bulkier.

P.S. 184 subtractions down, 71 to go.

Edit: another couple tips:

Spoiler:

YouTube · Postby **phlip** » Mon Nov 15, 2010 11:58 am UTC

The horrible buffer I always used was:

Spoiler:

skeptical scientist · Postby **skeptical scientist** » Mon Nov 15, 2010 12:13 pm UTC

The conveyor belt to i/o device ratio is probably a pretty good way to tell how polished a solution is. My adder is mostly conveyor belts, so it's clearly not very well designed. Of course, few conveyor belts just means that you implemented an algorithm efficiently, not that the algorithm you chose was a good algorithm to use.

P.S. I'm almost done adding 1+255 - only 39 subtractions to go. I should be done in another half hour or so. From this and the above conveyor-belt remark you can tell that I implemented a horrible algorithm poorly. But it worked, and that was good enough to finish the last level in the game.

Edit: finished. All-told, it took nearly 3 hours to perform the computation 1+255 on my metatron solution, running at 50x speed the entire time. If anyone curious, here's my code:

Spoiler:

Tirian · Postby **Tirian** » Mon Nov 15, 2010 3:39 pm UTC

As fate would have it, I was just thinking about this thread over the weekend because I was putting some time into Tile Factory. It's closer to the spirit of the Zachtronics games than Manufactoria, but I think it might please many of the same fans. (And the interface is infinitely better than, say, KOHCTPYKTOP.)

Like Manufactoria, it also has a wicked steep learning curve toward the end. I was thinking that I'd love to see some user-created levels that could help me see my own way through the last seven levels.

Postby **jestingrabbit** » Tue Nov 16, 2010 2:42 am UTC

Phlip, I think I used that buffer early on, but it pretty quickly became my top left style. Its just too broad. More than two or three on the field is way too much space on something that needs to be done so frequently.

As for conveyor to i/o ratio, my final metatron is pretty much a master work of cramming more crap onto the screen. Here's a picture.

I've highlighted the four buffers I use. The middle one works out the last bit of the first number, and sends the bot on to one of the readers on the left, which find the last bit of the second number. The one on the right is all about the case where you run out of one number but not the other. It processes through that case as quickly as possible. I remember wanting to do a little more, trying to cram another path from the north to south on the eastern edge, but I don't remember what it was I wanted to do. I'm happy with it as it stands. Very happy with it. I don't need to go back to obsessively trying to shoehorn another few features into it. Not at all.

The most interesting puzzle that nearly made me go back to it all was called "rainbow" I think. You had to accept if there were all the colours in the string, reject otherwise. Really was an assault on my approach to the latter levels.

Xanthir · Postby **Xanthir** » Tue Nov 16, 2010 4:59 am UTC

skeptical scientist wrote:Edit: finished. All-told, it took nearly 3 hours to perform the computation 1+255 on my metatron solution, running at 50x speed the entire time. If anyone curious, here's my code:
Spoiler:
?lvl=31&code=y7:1f3;q7:2f6;g7:3f3;b8:1f3;p8:2f0;r8:3f1;p11:2f0;r10:2f1;b11:1f0;c10:1f0;c9:1f3;c9:2f0;p7:4f7;q6:4f6;c6:6f3;c6:7f3;c6:8f3;c6:9f3;c6:10f3;c6:11f3;p7:12f6;b7:11f3;r7:13f1;c6:12f2;q8:12f6;c8:13f2;c9:13f2;c10:13f2;c11:13f2;c8:4f2;c10:4f3;c10:5f3;c8:6f3;b8:7f2;q9:6f0;i9:7f5;c10:6f0;c10:7f2;p11:6f3;c11:7f1;q12:6f6;i12:7f1;y12:8f2;c13:6f3;r13:7f0;y12:5f2;y13:5f2;q14:5f3;c14:8f1;c14:7f1;c13:8f2;c14:6f2;c15:6f1;c11:3f1;c9:4f2;r9:8f0;c6:5f3;c7:5f3;c7:6f3;c7:7f3;c7:8f3;c7:9f3;c7:10f2;r9:5f0;b8:5f0;q8:10f2;b8:11f1;c8:8f3;g15:5f1;g14:3f0;r14:4f2;q15:3f1;p15:4f1;b16:4f0;g12:2f0;c13:3f3;c13:4f0;c12:4f0;c11:4f3;c11:5f3;c9:9f2;c16:8f2;q16:9f5;p16:10f2;q16:11f3;c16:12f2;r17:8f3;i17:9f5;c17:10f0;i17:11f4;b17:12f1;b18:9f1;c18:8f1;c18:7f1;c18:6f1;c18:5f1;c18:4f1;c18:3f1;c15:2f0;c14:2f0;c13:2f0;q16:7f3;r15:7f2;c17:7f2;y18:11f3;y15:11f3;c18:13f0;c17:13f0;c16:13f0;c15:13f0;c14:13f0;c13:13f1;g11:10f2;c15:9f1;b15:8f1;c13:10f2;c14:10f2;c10:9f2;q12:10f6;c8:9f2;c11:9f3;c15:10f2;c12:9f2;c13:9f2;c14:9f2;c12:11f0;p17:2f0;b17:1f3;r17:3f1;q16:2f7;g18:2f0;r10:10f3;p10:11f2;b10:12f1;y11:12f1;q11:11f4;c13:11f0;y15:12f0;q14:12f7;g13:12f1;c18:12f3;

Don't forget that my Manufactoria emulator is still up and running. I haven't tried it on a really inefficient machine yet, but at the very least it gives you an easy way to link to solutions without waiting for Flash to load.

Edit: As expected, it handles the machine just fine. 1+255 completes in a fraction of a second, processing 69808 steps and finishing with a BRRRRRRRR tape. Printing the intermediate computation steps takes about 10 seconds on my computer, then the browser slows to a crawl attempting to render all that SVG.

You don't really pick up a noticeable computation delay until you starting adding 11-bit numbers, at least on my machine and browser.

Sema · Postby **Sema** » Tue Feb 01, 2011 12:51 pm UTC

How do you play this game? I'm stuck on the 3rd stage. Thanks for the tips and what do I need to know before I can play.

nuborn · Postby **nuborn** » Fri Jun 03, 2011 2:26 am UTC

I finally found out that the reason I could not bridge convayors was that I was playing in Opera XD.
It was a relief to open the game in Firefox and see that bridging worked (I had not seen what they looked like untill I saw a picture in this thread). Now I can hopefully figure out the next levels.
Also, very nice game (and challenging). I almost gave up when I was stuck at Androids for some time, and then I was surprised how the solution was not very complex at all, and almost seemed obvious.

TheMeanPenguin · Postby **TheMeanPenguin** » Sat Dec 03, 2011 6:13 pm UTC

gah

I got through seraphim before realizing you could make conveyor belts cross each other. not a good time to get nerd-sniped either with finals next week. venting my frustration on a dead forum thread won't help.

tomtom2357 · Postby **tomtom2357** » Mon Jun 04, 2012 4:23 pm UTC

TheMeanPenguin wrote:gah I got through seraphim before realizing you could make conveyor belts cross each other. not a good time to get nerd-sniped either with finals next week. venting my frustration on a dead forum thread won't help.

For some reason, the game won't let me cross conveyors, is there something you have to do first? However, it seems to allow me to cross conveyors when I copied and loaded a saved machine.

jaap · Postby **jaap** » Mon Jun 04, 2012 9:35 pm UTC

tomtom2357 wrote:
TheMeanPenguin wrote:gah :x I got through seraphim before realizing you could make conveyor belts cross each other. not a good time to get nerd-sniped either with finals next week. venting my frustration on a dead forum thread won't help.

For some reason, the game won't let me cross conveyors, is there something you have to do first? However, it seems to allow me to cross conveyors when I copied and loaded a saved machine.

Hold down shift when you place the belt.

tomtom2357 · Postby **tomtom2357** » Wed Jun 06, 2012 4:46 am UTC

jaap wrote:
tomtom2357 wrote:
TheMeanPenguin wrote:gah I got through seraphim before realizing you could make conveyor belts cross each other. not a good time to get nerd-sniped either with finals next week. venting my frustration on a dead forum thread won't help.

For some reason, the game won't let me cross conveyors, is there something you have to do first? However, it seems to allow me to cross conveyors when I copied and loaded a saved machine.

Hold down shift when you place the belt.

Thank you.

mr-mitch · Postby **mr-mitch** » Wed Jun 06, 2012 5:18 pm UTC

Thank you for the procrastination from study.

I thought I'd share my +1 solution, it is quite fast.

Spoiler:

code:

Spoiler:

Xanthir · Postby **Xanthir** » Wed Jun 06, 2012 6:03 pm UTC

Mr Mitch: Use my emulator to share machines. In Manufactoria, go to the save/load screen (the disc icon in the level editor). You'll see a long url. Replace the first part (the stuff before the ?) with "http://xanthir.com/manufactoria". It's now a link to my emulator, which can be used to easily see the machine and run tests on it.

In your case, it will produce a url like this.

mr-mitch · Postby **mr-mitch** » Wed Jun 06, 2012 7:12 pm UTC

Wow, thanks; it's very nice.

It shows I forgot to remove some of a previous algorithm. They screw up inputs of the form 11* and []. Interestingly these weren't part of the test cases I faced.

I fixed it, the code is now

Spoiler:

I can't figure out a bounds on the algorithm.
Some data points are
B, 72 steps
2^11-1, 1026
2^101-1, 46206
2^1001-1, 4062006
2^1011-1, 4143026

Xanthir · Postby **Xanthir** » Wed Jun 06, 2012 11:14 pm UTC

I'm confused about why you decided to once again post the code, instead of making a link like I just explained. ^_^

mr-mitch · Postby **mr-mitch** » Thu Jun 07, 2012 6:41 am UTC

It was 4am? I've edited the post, it's now a url.

Who is online