Manufactoria - Make Turing Machines with Conveyor Belts

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

Nix
Posts: 93
Joined: Mon Mar 09, 2009 8:14 am UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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
Posts: 25
Joined: Thu Apr 16, 2009 10:32 pm UTC

Re: Manufactoria / record solutions

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
Posts: 93
Joined: Mon Mar 09, 2009 8:14 am UTC

Re: Manufactoria / record solutions

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.

User avatar
Xanthir
My HERO!!!
Posts: 5228
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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).
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

turingnow
Posts: 4
Joined: Sat Jun 26, 2010 11:18 am UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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
Posts: 3
Joined: Sat Jul 10, 2010 12:55 pm UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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;

User avatar
Xanthir
My HERO!!!
Posts: 5228
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Tehforsch
Posts: 3
Joined: Sat Jul 10, 2010 12:55 pm UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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

User avatar
kjsharke
Posts: 70
Joined: Fri Dec 07, 2007 3:53 pm UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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:
I do like aspects of my solution, but the engineers part in particular looks like a kludge of conveyors. I don't know if that can be helped, but I do think prettier solutions are possible, so if anyone tries it, I'm curious to see.


?lvl=29&code=b7:6f2;y7:8f3;b7:9f2;c8:2f3;c8:3f3;c8:4f2;q8:5f6;p8:6f5;c8:7f1;q8:8f3;p8:9f5;b8:10f1;y8:11f1;c9:2f0;b9:3f2;p9:4f6;r9:5f2;r9:6f0;g9:7f0;b9:8f1;r9:9f0;b9:10f2;q9:11f5;c10:2f0;c10:3f3;i10:4f5;y10:5f3;c10:6f3;i10:7f6;c10:8f3;c10:9f3;c10:10f3;p10:11f3;g11:2f0;y11:3f1;q11:4f1;c11:7f0;r11:8f1;b11:9f2;r11:10f0;q11:11f1;y12:3f0;c12:4f2;q12:8f7;p12:9f5;r12:10f1;y12:11f1;b13:3f3;c13:4f3;y13:5f2;r13:6f1;y13:8f3;r13:9f0;b14:2f3;i14:3f6;c14:4f3;c14:5f2;i14:6f2;r14:7f1;c15:2f0;q15:3f5;i15:4f0;p15:5f6;q15:6f3;c15:7f0;p16:3f2;g16:4f0;i16:5f4;p16:6f2;q17:5f2;i17:6f5;c14:12f0;c16:8f3;p16:9f3;c17:8f0;r17:9f0;c14:10f3;c14:11f3;b15:9f2;c17:7f3;q16:10f5;c15:10f0;g17:10f0;c13:12f0;?lvl=29&code=b7:6f2;y7:8f3;b7:9f2;c8:2f3;c8:3f3;c8:4f2;q8:5f6;p8:6f5;c8:7f1;q8:8f3;p8:9f5;b8:10f1;y8:11f1;c9:2f0;b9:3f2;p9:4f6;r9:5f2;r9:6f0;g9:7f0;b9:8f1;r9:9f0;b9:10f2;q9:11f5;c10:2f0;c10:3f3;i10:4f5;y10:5f3;c10:6f3;i10:7f6;c10:8f3;c10:9f3;c10:10f3;p10:11f3;g11:2f0;y11:3f1;q11:4f1;c11:7f0;r11:8f1;b11:9f2;r11:10f0;q11:11f1;y12:3f0;c12:4f2;q12:8f7;p12:9f5;r12:10f1;y12:11f1;b13:3f3;c13:4f3;y13:5f2;r13:6f1;y13:8f3;r13:9f0;b14:2f3;i14:3f6;c14:4f3;c14:5f2;i14:6f2;r14:7f1;c15:2f0;q15:3f5;i15:4f0;p15:5f6;q15:6f3;c15:7f0;p16:3f2;g16:4f0;i16:5f4;p16:6f2;q17:5f2;i17:6f5;c14:12f0;c16:8f3;p16:9f3;c17:8f0;r17:9f0;c14:10f3;c14:11f3;b15:9f2;c17:7f3;q16:10f5;c15:10f0;g17:10f0;c13:12f0;


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

Code: Select all

--- manufactoria-checker.cpp    2010-06-26 15:26:32.000000000 -0400
+++ manufactoria-checker-alt.cpp 2010-07-24 21:44:00.000000000 -0400
@@ -413,6 +413,22 @@
     return output;
 }

+Result RC_insertGreenBetween(const Tape& input) {
+    if (input.size() % 2 != 0)
+        throw BadInputLength();
+    const int half = input.size() / 2;
+    for (int ii = 0; ii < half; ++ii)
+        if (input[ii] != input[ii + half])
+            return false;
+    Tape output;
+    for (int ii = 0; ii < half; ++ii)
+        output.push_back(input[ii]);
+    output.push_back(Green);
+    for (int ii = half; ii < (int)input.size(); ++ii)
+        output.push_back(input[ii]);
+    return output;
+}
+
 Result RC_repeatedStringWithGreen(const Tape& input) {
     if (input.size() % 2 != 1)
         return false;
@@ -790,6 +806,7 @@
     { 26,  7, "",      "Roboplanes!",    LevelData::RedBlue         , RC_removeReds },
     { 27,  9, "",      "Rocket planes!", LevelData::RedBlue         , RC_sort },
     { 28, 11, "",      "Robomecha!",     LevelData::RedBlue         , RC_lastToFront },
+    { 290, 11, "",     "altSeraphim!",   LevelData::RedBlue         , RC_insertGreenBetween },
     { 29, 11, "",      "Seraphim",       LevelData::SeparatedStrings, RC_repeatedStringWithGreen },
     { 30, 13, "",      "Ophanim",        LevelData::SeparatedStrings, RC_compareTwo },
     { 31, 13, "",      "Metatron",       LevelData::SeparatedStrings, RC_addTwo },


Edit: for Xanthir

Axidos
Posts: 167
Joined: Tue Jan 20, 2009 12:02 pm UTC
Location: trapped in a profile factory please send help

Re: Manufactoria / record solutions

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?

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5963
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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 213=~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 28=256 steps for every sequence. Its quite easy to get to that sort of number.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
Xanthir
My HERO!!!
Posts: 5228
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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.)
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

ignatius
Posts: 2
Joined: Thu Sep 02, 2010 6:36 pm UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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.

User avatar
Xanthir
My HERO!!!
Posts: 5228
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

ignatius
Posts: 2
Joined: Thu Sep 02, 2010 6:36 pm UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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) ... ;-)

User avatar
Xanthir
My HERO!!!
Posts: 5228
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

turingnow
Posts: 4
Joined: Sat Jun 26, 2010 11:18 am UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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

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

conradceo
Posts: 1
Joined: Wed Sep 22, 2010 8:51 pm UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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:
if B=0, fix formatting and output; else, A++, B--, goto start

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.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5963
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
scarecrovv
It's pronounced 'double u'
Posts: 674
Joined: Wed Jul 30, 2008 4:09 pm UTC
Location: California

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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.* :P

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.
Last edited by skeptical scientist on Mon Nov 15, 2010 11:32 am UTC, edited 2 times in total.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5963
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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:
The basic function that you need in just about every level worth thinking about is a "guarded read", where you read a string of red and blue until you hit a green, and write the string without the last red or blue, and store what that last dot was as a spacial variable. Here's a picture of a few ways to do that.
guardedreads.png
guardedreads.png (12.1 KiB) Viewed 6677 times
The top left configuration was my first attempt, averaging about 3*n steps to get the job done, and rather huge. So it basically sucks. You can see two of them, a little mangled because they're not reading arbitrary strings but binary numbers (this slightly improves performance too), in my -- ++ solution to metatron.

Top right is one that a lot of people favour. Its very compact, but you're looking at about 4*n steps to get the job done. Good for minimal size, bad for speed.

The configuration at the bottom is what I arrived at after a lot of work on making a fast metatron. Whereas the first two take input from the north where you'd expect and spit out the bot in a different place, this configuration needs a lot of surrounding space, preprocessing the string so that you know what the first colour is, introducing the bot into the reader at one particular locale in the case of binary strings, or one of two possible locales otherwise. You also need surrounding gates and paths set up in such a way that they can deal with both input and output passing through them. They are optimal for speed though, coming in at just 2*n. Definitely worth the hassle for the speed up, but real bastards to work with.


So there you go, my thoughts on guarded reads.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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:
I find it helpful to think of the tape as a loop, and the start of the tape as simply being the part of the loop we are currently reading. This is because it is very easy to move the front symbol to the back, and this is a commonly used function in any solution that involves recursion. With this in mind, you generally want to mark a certain spot on the loop, namely the beginning/end (both, since it's a loop) of the initial input, with a yellow or a green.

Now, how can you quickly read to the green marker you made, keeping the symbols in the loop intact? There's a very easy way to do this, using only 6 devices and no conveyors: point a red/blue junction and a green/yellow junction at each other, and point red/blue/yellow writers at the corresponding arrows. The green writer goes next to the green arrow as well, but pointing out instead of back in.
Last edited by skeptical scientist on Mon Nov 15, 2010 12:04 pm UTC, edited 1 time in total.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
phlip
Restorer of Worlds
Posts: 7543
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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

The horrible buffer I always used was:
Spoiler:
buffer.png
buffer.png (1.85 KiB) Viewed 6670 times

One on the left if I knew the string wasn't empty, one on the right if I needed to handle an empty string.

Later on in the puzzle when I inevitably ran out of space, I usually had to twerk it a bit to get it to fit properly.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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:
?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;
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5963
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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.
Screen shot 2010-11-16 at 1.09.08 PM.png
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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
Xanthir
My HERO!!!
Posts: 5228
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Sema
Posts: 7
Joined: Tue Sep 07, 2010 10:37 pm UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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
Posts: 1
Joined: Wed May 25, 2011 2:27 am UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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
Posts: 1
Joined: Sat Dec 03, 2011 5:55 pm UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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

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.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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

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.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

User avatar
jaap
Posts: 2073
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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

jaap wrote:
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.

Thank you.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

mr-mitch
Posts: 477
Joined: Sun Jul 05, 2009 6:56 pm UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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:
It relies on the fact bits either propagate the carry, delete the carry, or generate a carry, regardless of the carry in (the +1).
So it works out all the propagate bits, and the bit before each propagate section and puts a Y.
Then, it loops over the grammar Y1 -> 10, Y0 -> 01.


code:
Spoiler:
?lvl=13&code=g12:2f3;p12:3f3;b11:3f2;p13:3f2;r13:2f3;y13:4f1;q12:4f0;b14:3f1;c14:2f1;q14:1f3;g15:1f2;r12:5f3;i12:6f1;c12:7f3;c12:8f3;c12:9f3;c12:10f3;i12:11f5;c12:12f3;c16:1f3;c16:2f3;c16:3f3;c16:4f3;q16:5f7;q17:5f6;y17:4f3;c14:6f1;i14:5f0;c14:4f2;c15:4f2;b15:6f3;p15:7f0;r15:8f1;c16:7f0;c16:6f3;c15:5f0;c13:5f3;c14:7f1;c18:5f3;c18:6f3;c18:7f3;c18:8f3;c18:9f3;p16:11f0;c18:10f3;c18:11f0;c17:11f0;b16:10f0;r15:10f0;r16:12f0;b15:12f0;c14:12f1;c14:11f1;c14:10f1;c14:9f1;c14:8f1;c11:6f0;i10:6f6;p9:6f0;r9:7f1;b9:5f3;q8:6f4;q8:8f7;y9:8f0;p8:9f3;b7:9f2;r9:9f0;c6:10f1;c6:9f1;c6:8f2;c7:8f2;c7:6f1;c7:5f1;c8:4f2;c9:4f2;c7:4f2;c10:4f3;c10:5f3;c10:7f2;c11:7f2;q8:10f3;y7:10f0;c10:11f2;c11:11f2;c13:11f2;g13:6f0;c8:5f1;y8:7f3;c9:10f3;c8:11f2;g9:11f2;
Attachments
manufactoria_adder.JPG

User avatar
Xanthir
My HERO!!!
Posts: 5228
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

mr-mitch
Posts: 477
Joined: Sun Jul 05, 2009 6:56 pm UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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
Last edited by mr-mitch on Thu Jun 07, 2012 6:42 am UTC, edited 1 time in total.

User avatar
Xanthir
My HERO!!!
Posts: 5228
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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. ^_^
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

mr-mitch
Posts: 477
Joined: Sun Jul 05, 2009 6:56 pm UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

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

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


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 17 guests