Manufactoria - Make Turing Machines with Conveyor Belts

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

Moderators: phlip, Moderators General, Prelates

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby phlip » Fri Jun 04, 2010 12:43 am UTC

It probably is, I just hadn't really thought about it too hard. The only non-obvious thing is the cyclic destructive tape, rather than the TM's linear nondestructive one... after all, if it was a stack instead of a queue, then it'd only be a push-down automaton, not a TM. But I guess you could use R/B as the real tape symbols and G/Y to mark the position of the head and the end of the string... and just read the entire string and write it again for every read or write, and just embed the TM directly into the grid. It would run abysmally slowly, an extra factor of n on top of the already slow TM speed, but Turing-completeness isn't about efficiency...

Code: Select all

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

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby WarDaft » Fri Jun 04, 2010 1:11 am UTC

It's a variable tag system. Actually it's somewhat more flexible than a variable tag system, but we can implement any given tag system we want in it given unbounded space and tape length. So yes, it's certainly Turing Complete with unlimited room.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

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

Re: Manufactoria / record solutions

Postby Nix » Fri Jun 04, 2010 2:00 am UTC

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:

I got a slightly faster speed record for Engineers than jareds's with the same 29 part size. I imagine there's a lot of room to improve by adding parts to read two at a time.

J.P. shrunk Generals from my 21 to 19 parts and was also a third faster. He also has a 48 part (old record is 61!) Ophanim which I haven't added yet because it may have an unused part (yes, my test version of the program detects those now), and I'm waiting for an optimized version without it or confirmation that it is actually needed in an obscure yet untested case.

A bunch of speed records by jareds. He tweaks five parts off his fast Teachers with a marginal speed increase too, and two parts off his speedy Police. In Judiciary (84 parts) and Seraphim (66) he builds massive machinery to improve considerably on previous speeds achieved with naive solutions by me and Dernam.


2010-06-04

This game forces you to create art sometimes. Now a beautiful butterfly joins the christmas tree and a number of perfect arrows and other assorted shapes in the records, as I made the really speed optimized Engineers I was hinting at above. And what a whopping speed increase it is: from 75360 down to 70444 steps, by spending 81 parts instead of 29. But it is actually eating two markers from both ends on each loop of the tape, and almost all of the idle traveling is once per loop, so it should really increase its lead on longer inputs than what are currently timed. Hum, I might add an informational extra column listing a performance measure on the longer inputs that are tested anyway.

(edit 1) A novel approach led to a 76k speed record in Robomecha, replacing jareds's 94k. The implementation may not be perfect, have fun trying to do better. (but no peeking!)

(edit 2) I'm on a roll! Beat Jani's Robocats speed record ever so slightly: 18 steps (out of 34k) and one part less.

(edit 3) J.P. finalized his submissions: added a 21 part Officers (3 part reduction from mine) to go with the Generals, and reduced his Ophanim to 46, slashing a nice 15 parts off Steve496's record 61.

(edit 4) I was half anticipating this: Seeing that such an improvement to his old record was possible, jareds improved my fresh speed record in Robomecha by about a thousand steps and one part. He certainly didn't peek at mine, and I still recommend anyone to try and discover the trick themselves instead, even more than any other level.

I packed my speed Engineers a little bit tighter, losing 4k steps and four parts.

(edit 5) Ball back to jareds. Robomecha gave up 3526 steps more when I went up to 49 parts.

(edit 6) Jani (not registered here) improved speed in three simple levels where I had hoped my records were already perfect. In Robofish he cuts just eight steps adding a part. In Robocats he improves from 34358 to 34070 and even gets by with 17 parts to my 19. In Robotanks the speed improvement is actually to the size record – keeping to 25 parts he cuts 50 steps.

(edit 7) Those were short lived. (sorry!) I came up with another six step improvement in Robofish (now going from 6 to 12 parts) that I really hope is finally optimal. In Robocats I went further down to 33958 in a hairy (fitting the level) solution that I'm quite sure isn't perfect itself, possibly far from that. I wish someone came up with an even better, elegant looking solution that I could look at and be convinced that it's perfect. For some reason this is a level I don't like optimizing for speed, no matter how much I like cats. Real cats though, maybe that's it.


2010-06-06

Jareds has nice new speed in Robocats coming down to 33153 getting by with 20 parts instead of my 28, and improved his own speed record in Academics as well, down 8k out of 317k and keeping the part count at 75.

J.P. took Steve496's Metatron record down by both losing a part and gaining speed. It's now at 72 parts.

(edit 1) Finally I managed to break Seraphim for speed. I was just trying to reach jareds's record (it was frustrating to even approach) but happened to improve it slightly. I knocked 625 steps off 357k and managed with 60 parts to his 66.

(edit 2) I found a faster 25 part Engineers, slicing 5k off Dernam's 110k steps. It took a while to get under 27 parts at all.

(edit 3) Changing algorithm from my previous tries, I too managed a 33 part Police, and it happens to be noticeably faster than Steve496's otherwise equal size record.

(edit 4) Jani had a new speed record for Robospies, and we had a back and forth exchange finding even better ones, until settling at 10382 in 25 parts found first by myself helped by his hint. The previous record was 12453 steps in 13 parts by jareds. Another speed record I made was for Androids, down from jareds's 11.8k to 9.2k. I'm quite sure the approach can be stretched even further.

(edit 5) Another set from jareds. He cuts one piece from his Judiciary (now 44) and improves speeds for his fast Police (239k to 213k) and Judiciary (373k to 328k). He also takes back fast Seraphim from me, saving 1156 steps out of 356k. Added later: It's apparently very similar, since with a small modification I got exactly the same out of mine. It may well be the best possible result.

(edit 6) One more from jareds: 6k steps and two parts off his fast Academics.

(edit 7) I removed 442 steps and 3 parts from my Roboplanes speed record solving from scratch.

(edit 8) Improved my fresh Androids speed with a simple twerk that killed 115 steps and two parts.


2010-06-07

Jani started another escalation of Robocats speed records, this time ending with my 46 part solution that works in 30094 steps. Previous record was 33153 in 20 parts by jareds.


2010-06-08

I managed to squeeze a relatively fast implementation of Ophanim to 44 parts, breaking J.P.'s size record of 46, with less than half the steps as well.

(edit 1) Again Jani found early levels that had lacking speed records, but unfortunately again I found a minor variation that improved them even further. Previously these had no separate speed records at all, now we save 8k steps in both Robocars and Robostilts by adding 8 parts to each.

(edit 2) I found a small improvement to Robolamp speed, improving my record by 110 steps, now in 19 parts.


2010-06-09

I tuned my new small Ophanim for speed, and got 903k steps with 60 parts to replace my old 124 part record of 1M. It's still reading just one bit at a time.

(edit 1) Jani added a speed record to another level similar to those touched yesterday: Roborockets loses 4k steps by adding 4 parts.

The 110 part Metatron by jestingrabbit posted in the thread is in fact faster than what we've seen so far, saving a nice 1.77M steps from the 6.3M achieved by the still current size record, a 72 parter by J.P.

J.P. improved his size record in Officers by one part, now at 20.

(edit 2) Jani owned the board of Robolamp intermediates and put a speed record of 25085 in 24 parts on top, replacing my 25225.


2010-06-10

Metatron speed record got better as jestingrabbit showed a 95 part, 4.0M step solution to beat his 110 part 4.5M stepper. Apparently it's not even final yet.

Jani beat my Robocats size record badly in speed. Still in 11 parts he manages it in 34312 steps laughing at my 38400.


2010-06-11 Moved the updated table and scores.txt to the new page. Edit history continues there.
Last edited by Nix on Fri Jun 11, 2010 6:02 pm UTC, edited 35 times in total.

User avatar
darkspork
Posts: 532
Joined: Tue Sep 23, 2008 12:43 am UTC
Location: Land of Trains and Suburbs

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby darkspork » Fri Jun 04, 2010 2:38 am UTC

TheChewanater wrote:
darkspork wrote:(for some problems) every one of the possible test cases


There are so many possibilities that even if you could test it in one machine code instruction, a 1.0 terahertz processor would take 12 days to test them all. I'd rather not wait that long.


I was thinking something weird. 8 bits is usually enough to demonstrate why a machine doesn't work, so a test of all possible 8 bit values should cover it then. That's 256 tests, which could probably be conducted while the others are going on visually (using only spare CPU) and could terminate if a test takes too long. Maybe insert an instruction limit and flag a test if it takes too long. If no failed tests are discovered, then throw up one of the long ones, to see if it's stuck in an infinite loop. Actually, considering that there are only two variables, (the queue and the "instruction pointer") it's fairly simple to build a table of previous values and pointer locations, and check current values against those for any duplicates. I think it's pretty safe to say that if you end up in the same place again with the same data that you had before in that location, you're in an infinite loop.

Another idea that might work would be to store a histogramic table of everyone's failed test cases, and silently check the machine against the test cases that cause the most frequent failures.
Shameless Website Promotion: Gamma Energy
My new esoteric programming language: GLOBOL
An experiment to mess with Google Search results: HARDCORE PORNOGRAPHY HARDCORE PORNOGRAPHY

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Xanthir » Fri Jun 04, 2010 4:42 am UTC

phlip wrote:On the topic of proving a machine works, I'll just link to Rice's theorem... it doesn't completely apply here (since the machines are actually FSMs, not TMs) but if it turns out the arbitrarily-large-grid-and-infinite-tape variant is Turing complete, then it would apply to that. And even here, I think it implies at least that it would be very challenging to do better than brute force for validation.

Given that you can do arbitrary looping, and can construct non-planar machines (by crossing the conveyors), I'd bet money that it was turing-equivalent.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby WarDaft » Fri Jun 04, 2010 1:51 pm UTC

Why would it not be turing-equivalent given unbounded room/tape?

We just construct a binary tree to represent any given 2-tag machine.

For example, the two tag machine given here http://en.wikipedia.org/wiki/Tag_system ... _sequences
Would be:
Spoiler:
Image
If we could not overlap belts, this would not be assured, but since we can, it's fairly simple to conceive of any given m-tag system being written.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby phlip » Fri Jun 04, 2010 2:14 pm UTC

As I said, the only reason I talked like it might not be Turing-complete is because I hadn't thought about it in depth yet, and was hedging my bets. Having done that thinking since then, yes, I know it's Turing-complete. Also, I hadn't heard of this tag system thing before, which is, as you say, easy to embed in the game.

Code: Select all

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

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby jestingrabbit » Sat Jun 05, 2010 9:00 am UTC

When I opened the game up today all my progress was wiped and crossovers weren't allowed. WarDaft used ten (by my count) in his two tag system. I wonder if its still Turing complete.

Edit: wait, when you hold shift you can make a crossover... So its still Turing complete, but if you couldn't do the crossovers it might not be.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Nix » Sat Jun 05, 2010 4:54 pm UTC

jestingrabbit wrote:So its still Turing complete, but if you couldn't do the crossovers it might not be.

You could still do a relatively harmless crossover through a switch. You'd need to know for example that in one direction the next on tape is not green or yellow, and in the other it's green.

By initializing and using the tape as red-green-data-red-green-data (where each data could be any color) you can do a crossover at any point in the tape, but not always two crossovers in a row without reading one in between. Any fixed number in a row is of course easy by adding more red-greens in between data.

Even more powerfully, assign one color as a temporary marker that can't be anywhere on the tape when entering a crossing, and here's a state-preserving crossing (I'm using green):
Spoiler:
Manufactoria-switch-crossing.png
Manufactoria-switch-crossing.png (3.46 KiB) Viewed 8266 times

That at least should make it Turing complete even without regular bridges.

Aw crap, I used one extra part in the picture. See if you can spot it. Edit: Guess what, a bit more than one. I can't believe I was that sloppy. Well, I wasn't thinking of optimizing when making it. A truly minimal functional equivalent is only 9 parts without the outside conveyors (of which there are 6 in the picture). If you can't make it yet, it's a good chance to learn some optimizing.

0rm
Posts: 81
Joined: Wed Feb 17, 2010 2:30 pm UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby 0rm » Sun Jun 06, 2010 8:12 am UTC

Why is this proving so difficult? I'm a programmer for christ sake! :evil:
They say it's unhackable; I think it can be hacked.
They say it's fast; I think it could be faster.
They say it's the best; I think it can be done better.

0rm
Posts: 81
Joined: Wed Feb 17, 2010 2:30 pm UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby 0rm » Sun Jun 06, 2010 11:08 pm UTC

Why do I feel like there are some concepts I am missing here? I have taken an algorithms class already, but for some reason, I can get everything before andorids on my own, and my solutions were shoddy at best. Here I am writing a freaking application framework in C++, and I can't figure out these puzzles which are nothing more than a model of CPU instructions.

Why do I feel like I am not picking up on something?
They say it's unhackable; I think it can be hacked.
They say it's fast; I think it could be faster.
They say it's the best; I think it can be done better.

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Tirian » Sun Jun 06, 2010 11:53 pm UTC

The technical answer is that everything up to Androids is solvable with a deterministic finite state automaton and it is provable that Androids is not. Your solution will be radically different from what you've been doing so far. It's not to say that it will be a difficult machine, just that you will need a different flash of insight.

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Nix » Mon Jun 07, 2010 12:06 am UTC

@0rm: Tirian is right, but still even the early levels can be challenging. The tape is quite a restricting element when you can only write to one end and read from another, and it's the only state apart from position. This has many unique low-level problems that never come up in programming, even assembly, although in lots of respects solving the problems has the same feel.

I had very much fun adapting my thinking to the game on the first play through. After that it was mostly finding more efficient ways to implement the same low-level function. Of course totally new algorithms for problems have been even more fascinating to find, but not that frequent. And finally, optimizing the part counts has lots of function preserving transformations that you learn to handle. Optimizing for speed adds yet another new interesting territory.

Some general hints that if you're me, you'd want to discover yourself:
Spoiler:
The smart use of branching to encode state in position is key. Knowing which symbol you read last, or some more complicated property of the recently read and usually not yet fully written back part of the tape, will help you decide what to write back on the tape if anything (or read more before you decide), before you join (or loop) the branches again. Note that writes happen to relatively the same position that the last reads were from, but need not be synchronous at all. Often you need to write back some of what you read as is, to be handled later (or returned), but even that you can do in batches of more than one marker when necessary.

In the later levels you'll often want to think of your overall algorithm in terms of full sweeps over the tape and what you can do on each sweep with the limited operations to get nearer to the goal. For using the tape as a string instead of a fifo, you'll often need to mark the start position on the tape with a unique color so you know when the next iteration over it begins. You'll still have the fourth color to use how you see fit.

Try to see the generality in the above, not just how you've used the concepts so far. The possibilities are quite broad.

As a practical matter, notice that you have a limited opportunity to peek at the next thing on tape without reading it off. That is, if you need to branch if it's yellow or green, but leave it to be read later otherwise, that's what the green/yellow branch part naturally does.

User avatar
Steax
SecondTalon's Goon Squad
Posts: 3038
Joined: Sat Jan 12, 2008 12:18 pm UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Steax » Mon Jun 07, 2010 3:02 am UTC

Here's a tip: Don't try to immediately use your programming knowledge as-is. Just try to grasp the basic idea first and build off from there, and eventually implement methods from programming (like sorts). It's easy to get mixed up and start misapplying concepts; for example, using yellow/green as temporary variables, while possible, isn't always the best route. They're often used, instead, to mark certain points in the tape, to allow manipulating red/blue within a particular boundary. In other words, go back to basics.
In Minecraft, I use the username Rirez.

Notch
Posts: 318
Joined: Tue Dec 12, 2006 5:52 pm UTC
Location: Stockholm, Sweden
Contact:

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Notch » Mon Jun 07, 2010 11:37 am UTC

I implemented a Rule 110 interpreter in it, effectively proving it Turing complete for an unbounded tape.

Check it out!

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby jestingrabbit » Mon Jun 07, 2010 4:07 pm UTC

0rm wrote:Why do I feel like there are some concepts I am missing here? I have taken an algorithms class already, but for some reason, I can get everything before andorids on my own, and my solutions were shoddy at best. Here I am writing a freaking application framework in C++, and I can't figure out these puzzles which are nothing more than a model of CPU instructions.

Why do I feel like I am not picking up on something?


I found android difficult too, but I was hung up trying to make sure that the tape read the same going in as going out if it was an acceptable tape. Its a lot easier if you remember that destructive testing is okay for "accept or reject" levels.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Nix » Mon Jun 07, 2010 4:33 pm UTC

jestingrabbit wrote:I found android difficult too, but I was hung up trying to make sure that the tape read the same going in as going out if it was an acceptable tape.

Did you actually finish it this way? Seems like an interesting challenge, even if not overly hard. I'll see what I can do.

Edit: The space is so cramped that my method of first having something bulky that works and then squeezing it tighter requires a larger level for the initial build. Maybe even the final one.

Oh shoot, Androids! I just made the equivalent for Robo-children, and it's much more complicated than it would have been for Androids. At least I got it to fit the space in Robo-children, for the smaller Androids it could have been painful. Not optimized either way but works (verified), in 55 parts:
Spoiler:
?lvl=18&code=y7:6f2;b7:7f1;p7:8f0;r7:9f1;r8:5f3;p8:6f2;b8:7f1;c8:8f0;c9:6f3;c9:7f2;c9:8f0;q9:9f6;g9:10f1;b10:6f2;c10:7f2;r10:8f3;p10:9f4;b10:10f1;g11:3f3;y11:4f3;c11:5f3;p11:6f3;q11:7f2;y11:8f3;p11:9f7;q11:10f5;y12:3f0;q12:4f4;c12:5f0;r12:6f2;r12:9f3;p12:10f2;b12:11f1;r13:3f3;p13:4f4;b13:5f1;y13:6f2;q13:10f1;c13:12f0;y14:3f3;c14:4f0;b14:5f3;p14:6f6;r14:7f1;r14:9f3;p14:10f2;c14:12f0;q15:3f5;g15:4f1;r15:5f1;q15:6f4;y15:7f1;q15:10f2;c15:11f3;c15:12f0;

Anyone wants to make their own for Androids or Robo-children and test them, replace these functions in the checker:
Spoiler:

Code: Select all

Result RC_colorRatio1(const Tape& input) {
    if (RC_colorRatio(input, 1, 1).outcome == Result::Accepted)
        return input;
    else
        return false;
}

Result RC_equalBlueThenRed(const Tape& input) {
    int count = 0;
    Tape::const_iterator ii = input.begin();
    for (; ii != input.end() && *ii == Blue; ++ii)
        ++count;
    for (; ii != input.end() && *ii == Red; ++ii)
        --count;
    if (ii == input.end() && count == 0)
        return input;
    else
        return false;
}

Edit: Input returning Androids, 44 parts, unoptimized but still ugly; and a smarter cleaner one in 27 parts (and the latter in 25, even less readable):
Spoiler:
?lvl=17&code=c9:4f3;c10:4f0;g10:5f2;q11:5f7;b10:6f2;p11:6f5;g12:6f2;p11:4f4;y12:4f0;c9:5f3;c9:6f3;r14:5f0;p13:5f5;c13:6f1;q13:4f5;g8:9f2;c9:8f3;q9:9f7;y10:9f2;b11:8f3;p11:9f6;b12:8f2;q12:9f4;c9:7f3;c13:7f0;c12:7f0;c11:7f0;c10:7f3;c10:8f3;c12:10f3;r11:10f0;p10:10f3;q10:11f7;c11:11f2;c15:7f0;i14:7f2;q14:8f6;g14:9f1;r15:8f2;q16:7f5;p16:8f1;c13:8f2;r14:6f2;c15:6f3;
?lvl=17&code=g12:5f3;y12:4f3;c12:7f3;c12:6f3;p12:9f7;q12:10f7;c12:8f3;c13:9f2;b14:9f1;p15:7f1;r14:7f2;p15:8f2;y14:8f2;b15:9f1;q15:6f6;y15:5f1;r15:4f1;p15:3f0;q14:3f0;q13:6f3;b14:5f0;p13:5f7;c13:4f3;p13:10f3;q13:11f7;r14:10f0;g14:4f0;
?lvl=17&code=g12:5f3;y12:4f3;c12:7f3;c12:6f3;p12:9f7;q12:10f7;c12:8f3;q13:6f3;b14:5f0;p13:5f7;p13:10f3;q13:11f7;r14:10f0;r13:7f2;y13:8f2;b13:9f1;p14:7f1;p14:8f2;b14:9f1;q14:6f1;p15:4f0;r15:5f1;y15:6f1;q14:4f7;g13:4f3;

That was even a stupid algorithm, I didn't think it through. Added the smaller although slower algorithm. And shrunk it, maybe even to the minimum possible.
Last edited by Nix on Mon Jun 07, 2010 7:42 pm UTC, edited 1 time in total.

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Tirian » Mon Jun 07, 2010 7:25 pm UTC

Steve496 wrote:That's not actually quite what I was advocating - I think there are some fairly significant implementation details with doing it that way. But it might work. What I did is

Spoiler:
Check for significant bit first (destructively), and then length after (also destructively), and compose the two results to figure out which is actually smaller.


Well, I sat down with a sheet of paper and wrote out a state diagram for Ophanim along these lines, which turned out to be much prettier than the 122 piece solution that then came out of it. And now, having seen the sample input, I don't have room to add the preliminary initial red pruner, so it gives the wrong answers for things like RRGB. But over half the time it passes all the tests.

?lvl=30&code=g12:2f3;p11:4f0;c12:3f3;b11:3f3;r11:5f1;c8:4f3;i8:6f1;c8:11f3;c8:12f3;c8:13f2;c9:13f2;c10:13f2;c11:13f2;c6:8f3;c6:9f2;c7:8f2;p7:9f6;c7:10f2;i8:8f5;i8:9f5;i8:10f5;c9:8f3;i9:9f7;c8:7f3;p12:4f7;p13:4f6;b13:3f3;r13:5f1;c16:4f3;i16:5f5;c16:12f3;c16:13f0;c15:13f0;c14:13f0;c13:13f0;c15:5f2;p17:5f6;b17:4f3;q18:5f6;g18:6f3;c16:6f3;c16:7f3;i16:8f1;i16:10f1;i15:6f3;c15:7f1;c15:8f3;c15:10f0;p14:6f2;c14:7f2;c14:10f0;g13:6f2;q13:7f4;c13:10f1;r17:6f1;c9:10f3;c9:11f2;p11:8f5;c10:8f1;i10:7f0;c12:8f1;c12:7f1;c12:6f0;c11:6f0;p13:9f5;b12:9f2;r14:9f0;c13:8f1;c14:5f2;p17:8f7;c18:7f0;c17:7f3;c18:8f3;c18:9f3;c18:10f0;i17:10f6;c16:9f3;c15:9f3;p17:11f7;i16:11f6;c17:12f0;q11:2f5;q13:2f1;p9:2f5;r10:2f0;b8:2f2;c9:1f2;c10:1f2;c11:1f3;q10:4f2;g10:3f0;p9:3f4;c9:4f3;c8:3f3;p15:2f5;b14:2f2;r16:2f0;c15:1f0;c14:1f0;c13:1f3;p15:3f6;q14:4f2;g14:3f2;c15:4f3;c16:3f3;q17:9f6;c11:7f0;c9:7f0;q6:6f6;g6:7f3;r7:5f3;p7:6f4;b7:7f1;c8:5f3;c10:6f0;c9:6f0;c9:5f3;b10:10f3;p10:11f6;r10:12f1;g11:10f1;q11:11f2;c11:9f1;

Huh. It just struck me that I didn't use any yellow in this machine, and I might be able to shave off almost a third of it if I did.

Steve496
Posts: 4
Joined: Sat May 29, 2010 1:15 am UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Steve496 » Mon Jun 07, 2010 8:05 pm UTC

If you'd like to take a look at the implementation, most of my high scores on Ophanim (which are neither the smallest nor the fastest at this point and, as such, aren't listed in the high scores but are still in the scores.txt file) use this general approach; just find some of the intermediates with my name on them. The larger ones will generally make it more clear what's going on; the smaller ones have been significantly mangled in the effort to remove pieces.

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Tirian » Mon Jun 07, 2010 9:24 pm UTC

Unfortunately, I've tried multiple strategies to decompress the scores file on my computer and none of them believe that it's gzipped.

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby jestingrabbit » Mon Jun 07, 2010 10:59 pm UTC

Nix wrote:
jestingrabbit wrote:I found android difficult too, but I was hung up trying to make sure that the tape read the same going in as going out if it was an acceptable tape.

Did you actually finish it this way? Seems like an interesting challenge, even if not overly hard. I'll see what I can do.


Yeah. It is cramped, but its quite doable.

Spoiler:
?lvl=17&code=p12:4f3;y11:4f0;b9:4f0;p8:4f0;g8:3f2;c9:3f3;p8:6f3;r9:6f1;r8:7f3;c12:5f3;c12:6f3;i12:7f1;c12:8f3;c12:9f3;i12:10f5;y9:10f2;r10:9f2;p10:10f2;b10:11f1;q11:8f1;p11:9f1;c9:7f3;c9:8f3;c9:9f3;c11:7f0;c10:7f0;c11:10f2;c10:4f0;g9:5f0;c8:5f3;q8:8f1;c13:7f0;r13:8f2;q13:10f3;q14:7f3;p14:8f1;r14:9f2;p14:10f2;b14:11f1;g15:7f0;q15:8f1;p15:9f1;q15:10f0;g15:11f1;
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Nix » Tue Jun 08, 2010 1:10 pm UTC

^ Nice! Even if it's larger than my small one and slower than my equal sized one, that approach is far more flexible, and simple to adapt for any deletion based algorithm.

Tirian wrote:Unfortunately, I've tried multiple strategies to decompress the scores file on my computer and none of them believe that it's gzipped.

Note that it's just the text file gzipped, not a .tar.gz. So "gunzip manufactoria-scores.txt.gz" should work if you have gunzip. If you're on Windows, maybe try 7-Zip.

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Tirian » Tue Jun 08, 2010 5:09 pm UTC

Nix wrote:"gunzip manufactoria-scores.txt.gz" should work if you have gunzip.


"gzip: manufactoria-scores.txt.gz: not in gzip format"

Neither 7-Zip nor Extract Now have any better luck, reporting that the folder is invalid.

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby phlip » Tue Jun 08, 2010 11:07 pm UTC

It works fine for me... try downloading the .gz again, maybe it got corrupted somehow.

Code: Select all

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

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Tirian » Tue Jun 08, 2010 11:28 pm UTC

Huh, trying again it still fails until the Windows apps but gunzip under Cygwin takes it. I just don't even, but I'll take it!!

0rm
Posts: 81
Joined: Wed Feb 17, 2010 2:30 pm UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby 0rm » Wed Jun 09, 2010 12:47 am UTC

jestingrabbit wrote:
0rm wrote:Why do I feel like there are some concepts I am missing here? I have taken an algorithms class already, but for some reason, I can get everything before andorids on my own, and my solutions were shoddy at best. Here I am writing a freaking application framework in C++, and I can't figure out these puzzles which are nothing more than a model of CPU instructions.

Why do I feel like I am not picking up on something?


I found android difficult too, but I was hung up trying to make sure that the tape read the same going in as going out if it was an acceptable tape. Its a lot easier if you remember that destructive testing is okay for "accept or reject" levels.


Well, after looking at a couple of solutions, it hit me like "DUH!!! The total count would be even." (That is androids, right? For x blues, make sure theres the same amount of reds?)
Spoiler:
So turn all blues into reds then set up a loop that knocks out the reds by twos, rejecting the robot if it has some left over when it hits the kick-out gate and turning any further blues it encounters into reds.
They say it's unhackable; I think it can be hacked.
They say it's fast; I think it could be faster.
They say it's the best; I think it can be done better.

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby phlip » Wed Jun 09, 2010 2:05 am UTC

0rm wrote:Well, after looking at a couple of solutions, it hit me like "DUH!!! The total count would be even." (That is androids, right? For x blues, make sure theres the same amount of reds?)
Spoiler:
So turn all blues into reds then set up a loop that knocks out the reds by twos, rejecting the robot if it has some left over when it hits the kick-out gate and turning any further blues it encounters into reds.

I'm not sure I'm reading correctly, but wouldn't that mean you'd accept something like "BRBB"?

Note to self: when I get home, to the computer that has all the levels unlocked, post a list of all the level names and their criteria, so I have something to refer back to...

[edit] List of levels (spoilered for length, and for being an actual spoiler):
Spoiler:
1 - Robotoast! - ACCEPT: Move robots from the entrance (top) to the exit (bottom)! [You put bread in. With a click, heat begins to build. Then - a sound - motion - fresh toast! ROBO-TOAST. 49.99.]
2 - Robocoffee! - If a robot's string starts with blue, accept. Otherwise, reject! [Coffee - ambrosia - the 'water of life.' But - so hard to make! WORRY NO MORE. Robo Coffee: Never Sleep Again.]
3 - Robolamp! - ACCEPT: if there are three or more blues! [Our hi-tech 'lavalamps' will sense your mood, glowing and moving as you think! 'Creepy'? Try 'incredible!']
4 - Robofish! - ACCEPT: if a robot contains NO red! [Robot fish! Sold with ten amazing pre-programmed swim patterns, and almost always waterproofed!]
5 - Robobugs! - ACCEPT: if the tape has only alternating colors! [Robot flies! Ever thought, 'if I could be a fly on the wall?' Well, YOU can't, but these are the next best thing!]
6 - Robocats! - ACCEPT: if the tape ends with two blues! [Robot kitties! Their lustrous fur is 100% authentic - each strand taken from the back of an real kitten, just for you!]
7 - Robobears! - ACCEPT: Strings that begin and end with the same color! [Enormous metal polar bears! They like to catch fish, even though they can't eat any. It's disarming! Then they eat you.]
8 - RC Cars! - OUTPUT: The input, but with the first symbol at the end! [They go 'vroom'! They're remote controlled! The best and last robo-toy your child will ever want!]
9 - Robocars! - OUTPUT: Replace blue with green, and red with yellow! [Robot-driven cars! Now, when you enjoy a glass or two of port on the way to work, you needn't feel guilty about it!]
10 - Robostilts! - OUTPUT: Put a green at the beginning, and a yellow at the end! [Want to tower above your fellow man? Of course you do! But you're probably afraid of falling. Well - FEAR NO LONGER!]
11 - Milidogs! - ACCEPT: With blue as 1 and red as 0, accept odd binary strings! [Our first defense contract: robot dogs! They sniff out the enemy with their mechani-noses, and then - well!]
12 - Soldiers! - OUTPUT: With blue as 1 and red as 0, multiply by 8! [Robot soldiers! Plated with armor, bristling with weapons, and ready to send the Reds all the way back to Moscow!]
13 - Officers! - OUTPUT: With blue as 1 and red as 0, add 1 to the binary string! [Robotic officers serve in the newly formed Metal Regiments, commanding by radio-wave with uncanny speed!]
14 - Generals! - OUTPUT: Subtract 1 from the binary string! (Input >= 1) [Robot generals analyze their goals and optimize, without human limits. They are literally unbeatable.]
15 - Robotanks! - ACCEPT: With blue as 1 and red as 0, accept binary strings > 15! [Robotic armour! Rated 30% cheaper than human-crewed equivalents, and nearly 60% better at crushing foes!]
16 - Robospies! - ACCEPT: With blue as 1 and red as 0, accept natural powers of four! [Designation: HUM/ELINT primary infiltration/investigation asset. Further details: classified]
17 - Androids! - ACCEPT: Some number of blue, then the same number of red! [Robots in the shape of men - and with minds to match! A breakthrough like none before!]
18 - Robo-children! - ACCEPT: An equal number of blue and red, in any order! [These robo-scamps are guaranteed to brighten your life, even without use of their fast, glowing eyes!]
19 - Police! - OUTPUT: Put a yellow in the middle of the (even-length) string! [Overwhelmed by rampant crime? Upgrade your police force! Robo Cops: They Only Shoot People Who Really Deserve It.]
20 - Judiciary! - ACCEPT: (Even-length) strings that repeat midway through! [Robotic judges! Completely incorruptible, and utterly infallible! You'll never need HUMAN justices again!]
21 - Teachers! - ACCEPT: X blue, then X red, then X more blue, for any X! [Classes taught by robot teachers have, on average, 68% higher standardized test scores. They're simply superior!]
22 - Politicians! - ACCEPT: If there are exactly twice as many blues as red! [Robo-politicians: built so carefully, test models have replaced their targets with a detection rate below 1%!]
23 - Academics! - OUTPUT: Reverse the input string! [Robot processors! The robot race can now debate Derrida, satire Socrates, and control the academic world!]
24 - Engineers! - ACCEPT: Perfectly symmetrical strings! [Robot engineers. Designed to build testing machines. Harmless.]
25 - Roborockets! - OUTPUT: Swap blue for red, and red for blue! [Guided by a clever robotic navigation capsule, these rockets can carry nearly thirty tons of cargo into low Earth orbit!]
26 - Roboplanes! - OUTPUT: All of the blue, but none of the red! [Using new, advanced 'jet engines', our automated planes will take you from here to there in half the time!]
27 - Rocket Planes! - OUTPUT: The input, but with all blues moved to the front! ['The earth is the cradle of the mind - but one cannot live forever in a cradle.' Man's devices sojourn out to the stars.]
28 - Robomecha! - OUTPUT: The input, but with the last symbol moved to the front! [Stilts are fine. But what's better - robot STILTS, or a GIANT WALKING ROBOT SUIT? We think you already know!]
29 - Seraphim - ACCEPT: Two identical strings, separated by a green! [-]
30 - Ophanim - ACCEPT: Read the tape as two numbers, A and B, split by a green: accept if A>B! [--]
31 - Metatron - OUTPUT: Read the tape as two numbers, A and B, split by a green: output A + B! [----]

Code: Select all

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

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby jestingrabbit » Wed Jun 09, 2010 3:23 pm UTC

My large and no doubt rather slow metatron.

Spoiler:
?lvl=31&code=p14:5f6;c14:4f1;i15:4f1;p14:3f5;p16:5f6;r16:6f1;r16:4f0;b13:3f2;b15:3f3;q14:2f1;g13:2f0;q17:5f0;b9:4f1;p10:4f7;b11:4f0;r8:3f2;i9:3f3;c10:3f3;p8:2f4;c9:2f0;p10:2f4;r8:1f3;i12:2f6;c11:2f0;c12:5f2;c13:5f2;y12:3f3;g12:4f3;c6:6f3;c9:5f0;i14:7f2;c10:1f3;q7:2f4;g7:1f0;r6:1f3;c6:2f3;c6:3f3;c6:4f3;c6:5f3;y7:3f3;b7:4f0;g10:5f0;q7:5f4;c8:5f0;c15:5f2;r9:6f3;p9:7f4;r9:8f2;c10:7f0;i10:8f4;b10:9f1;c11:6f3;p11:7f4;c11:8f3;p11:9f7;b12:9f0;q14:9f5;c17:8f3;c17:9f3;q11:10f7;g10:10f0;p13:11f6;r13:12f1;g14:10f1;q14:11f4;r9:10f3;y12:10f2;c8:11f2;c9:11f2;c10:11f2;c11:11f2;c12:11f2;c14:13f0;c13:13f0;i14:8f4;c17:6f3;c17:7f0;c16:9f1;q14:12f6;b15:11f3;p15:12f0;r15:13f1;c15:10f3;c17:10f3;c17:11f3;c17:12f0;c16:12f0;q15:9f6;i16:8f4;c15:8f2;c16:7f0;g12:7f0;q13:7f0;i14:6f3;c15:6f3;i15:7f1;r13:6f2;r7:6f3;c6:7f2;c7:7f3;c7:8f3;c7:9f3;b13:8f2;q8:7f0;y8:6f0;y8:8f3;b8:9f3;c7:10f2;c8:10f3;b13:10f3;

Surprised I finally got it all crammed into the box.

Edit: slight debug.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Nix » Wed Jun 09, 2010 5:03 pm UTC

jestingrabbit wrote:My large and no doubt rather slow metatron.

Yeah, embarassingly slow. It even made it to my list of slowness records. ...or was it speed records?

But I hope it's going to go soon, when I get my new solutions to Metatron finished.

By the way, if anyone feels like actually attempting slowness records, it's really quite fun in the early levels where you can't yet get the checker to timeout with a valid solution. We had some records for a number of levels with Jani a few days back. But you could wait until I get the program to keep the scores for them as well.

User avatar
joshz
Posts: 1466
Joined: Tue Nov 11, 2008 2:51 am UTC
Location: Pittsburgh, PA

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby joshz » Wed Jun 09, 2010 5:20 pm UTC

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;
You, sir, name? wrote:If you have over 26 levels of nesting, you've got bigger problems ... than variable naming.
suffer-cait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby jestingrabbit » Wed Jun 09, 2010 5:49 pm UTC

Nix wrote:or was it speed records?


Was not expecting that at all :P I'm rather chuffed that a simple "add with a carry" with a few short cuts was quickest.

Here's one that is embarrassingly slow, but which knocks a couple of parts off the minimal solution.

Spoiler:
?lvl=31&code=b7:8f2;p7:9f4;b7:10f1;r8:7f3;i8:8f7;c8:9f0;q9:5f1;b9:6f1;p9:7f5;c9:8f1;p9:9f5;g9:10f1;b10:4f3;p10:5f6;r10:6f1;r10:7f0;c10:9f0;y6:10f3;q6:9f2;r6:11f2;p7:11f7;b8:11f0;g6:12f2;q7:12f1;q9:11f2;y8:12f2;c9:12f1;b11:10f3;p11:11f0;r11:12f1;r12:11f0;q13:11f3;b13:12f2;q13:13f1;p14:12f3;q14:13f3;r15:12f0;y10:11f0;c12:7f3;p12:8f2;c12:9f2;b12:10f2;q13:8f2;c13:9f3;p13:10f3;c14:8f2;i14:9f0;b14:10f1;r15:7f3;p15:8f2;r15:9f0;y16:7f1;q16:8f0;c14:11f3;g12:6f3;g16:5f0;r14:6f2;p15:6f1;b16:6f0;q15:5f3;y14:5f0;q12:5f0;c13:5f0;y11:5f2;r14:3f0;p13:3f3;b12:3f2;y13:4f3;y12:2f2;g13:2f3;
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Nix » Wed Jun 09, 2010 6:11 pm UTC

jestingrabbit wrote:Here's one that is embarrassingly slow, but which knocks a couple of parts off the minimal solution.

I can guess what you did there. I'm not sure if I should list it, because it will never finish the tests with inputs up to 60 long (with the timeout removed), even though there should be no reason to expect it to fail in them either. And it is small.

By the way, you have one unused blue and red adder in it, and may even be able to knock out some more pieces after taking them off. J.P. can probably make an even smaller implementation though.

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby jestingrabbit » Wed Jun 09, 2010 6:39 pm UTC

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

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Tirian » Wed Jun 09, 2010 7:23 pm UTC

While drafting my own (no doubt to be embarrassing) solution to Metatron, I started testing a curious notion in the Level Editor and by the time I was done came up with seven new challenges that I thought people might enjoy. They range from the sublime to the ridiculous: I would particularly recommend the multiplication problem as the 21-part solution I came up with is very elegant. I should note that I have not solved the final problem myself; the casual mathematical reader would probably be able to guess my plan, but I couldn't say if it would fit in the workspace.

If anyone has any comments about extra tests that should be added, feel free to let me know. I tried to put in enough but not too many. Also, if Nicholas Feinberg is reading this and wishes to yoink any of these problems into the real release, he is more than welcome to do so.

Binary to Unary: ?ctm=Binary_to_Unary;Convert_the_binary_number_to_a_string_of_that_many_blues!;bb:bbb|r:|bbrb:bbbbbbbbbbbbb;13;3;1;
Unary to Binary: ?ctm=Unary_to_Binary;Count_the_blue_dots_and_express_it_as_a_binary_number!;bbb:bb|bbbb:brr|bbbbbbbbbbbbbbbbbbbbbbb:brbbb|:r;13;3;1;
Unary Addition: ?ctm=Unary_Addition;Given_B_blue_dots_and_R_red_dots,_return_B+R_blue_dots!;bbrr:bbbb|rrr:bbb|bbbbb:bbbbb;13;3;0;
Unary Subtraction: ?ctm=Unary_Subtraction;Given_B_blue_dots_and_R_red_dots_(B_>=_R_>_0),_return_B-R_blue_dots_and_R_red_dots!;bbr:br|bbbbbrrr:bbrrr|bbbbrrrr:rrrr;13;3;0;
Unary Multiplication: ?ctm=UnaryMultiplication;Given_B_blue_dots_and_R_red_dots,_return_B*R_blue_dots!;bbrrr:bbbbbb|bbbbbr:bbbbb|rrr:|bbb:;13;3;0;
Unary Minmax: ?ctm=Unary_MinMax;Given_B_blues_and_R_reds,_return_max_blues_and_min_reds!!_(see_tests_for_examples);brrrr:bbbbr|bbbrrr:bbbrrr|bbbbrrr:bbbbrrr|rrr:bbb;13;3;0;
Unary GCD: ?ctm=Unary_GCD;Given_B_blue_dots_and_R_red_dots,_return_GCD(B,R)_blue_dots!!!;bbbbrr:bb|bbbrrrrrr:bbb|bbbrr:b|bbbbbbrrrrrrrrr:bbb|bbbbbbbbbbbbbbbrrrrrr:bbb;13;3;0;

User avatar
Lothar
Posts: 63
Joined: Sat Dec 23, 2006 11:37 am UTC
Location: Berlin, Germany
Contact:

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Lothar » Wed Jun 09, 2010 7:35 pm UTC

joshz wrote: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;
Always program as if the person who will be maintaining your program is a violent psychopath that knows where you live.

If you're not part of the solution, you're part of the precipitate.

1+1=3 for large values of 1.

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby phlip » Thu Jun 10, 2010 1:44 am UTC

If we're sharing new levels, here's one that I was kinda surprised wasn't in the real set: Roboparrots!

Code: Select all

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

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby jestingrabbit » Thu Jun 10, 2010 12:32 pm UTC

One last attempt at a min step metatron. Some space left over, so I'm not convinced its the best that can be done, but it is quite quick.

Spoiler:
?lvl=31&code=b9:4f1;p10:4f7;b11:4f0;r8:3f2;i9:3f3;c10:3f3;p8:2f4;c9:2f0;r8:1f3;c6:6f2;c7:6f2;c8:6f2;c9:6f2;c10:6f2;c11:6f2;c7:3f3;c7:2f3;i12:3f1;b14:2f2;q15:1f1;p15:2f5;c15:3f1;b16:2f3;i16:3f1;c16:4f2;r17:3f0;p17:4f6;r17:5f1;q18:4f0;c18:5f3;c14:1f0;c13:2f3;p13:3f3;c14:3f0;i13:6f7;c13:5f3;r12:7f1;p12:6f6;b12:5f3;g12:8f1;q10:5f3;g11:5f2;r8:5f3;q7:4f3;g8:4f3;g9:5f0;y6:4f3;b6:5f3;b14:12f2;p15:12f3;r16:12f0;c16:6f3;c15:11f3;c17:11f0;c16:11f0;q15:13f7;c14:13f0;c13:13f0;c18:8f3;c18:6f3;y12:2f3;i13:4f5;p15:4f6;i15:5f4;q14:6f2;q14:5f5;c12:4f2;g14:4f2;g16:5f3;c18:7f3;c16:7f3;q13:11f7;r14:11f2;c12:11f3;c12:12f2;c13:12f2;b15:8f3;q16:8f7;c17:8f3;b8:7f1;y9:7f0;q10:7f5;g11:7f2;b9:8f3;p10:8f1;b11:8f0;r8:9f2;i9:9f5;c10:9f1;p8:10f0;c9:10f0;r8:11f1;g11:9f0;c12:9f0;p13:9f3;i15:9f1;c16:9f0;i17:9f6;c18:9f0;y8:8f1;q7:8f5;c7:10f1;c7:9f1;r6:7f1;y6:8f1;c15:10f3;c17:10f3;c13:10f3;c13:1f3;g11:3f0;c13:7f2;c14:7f3;q14:8f7;g13:8f0;c14:9f0;


Edit: no, wait, this one might be a little bit better.

Spoiler:
?lvl=31&code=b9:4f1;p10:4f7;b11:4f0;r8:3f2;i9:3f3;c10:3f3;p8:2f4;c9:2f0;r8:1f3;c7:3f3;c7:2f3;i12:3f1;p13:3f3;q10:5f3;b14:12f2;p15:12f3;r16:12f0;q15:13f7;c14:13f0;c13:13f0;y12:2f3;c12:12f2;c13:12f2;g11:3f0;c7:11f1;c7:12f1;r8:11f2;p8:12f0;r8:13f1;b9:10f3;i9:11f5;c9:12f0;q10:9f5;p10:10f1;c10:11f1;b11:10f0;g11:11f0;g11:9f1;g11:5f3;b11:6f3;p11:7f6;r11:8f1;r9:6f3;g9:5f3;b9:8f1;y9:9f1;c7:7f2;c8:7f2;c9:7f2;c12:10f3;r14:10f2;c15:10f3;i16:10f6;c17:10f0;i12:11f6;p13:11f5;c14:11f0;c16:11f0;c18:11f0;q13:10f1;c13:8f3;q13:9f7;g12:9f0;r7:8f1;y7:9f1;q8:9f5;y7:5f3;b7:6f3;q8:5f3;c7:4f2;c8:4f3;c8:10f1;c7:10f2;c10:7f2;c17:11f0;b15:9f3;q16:9f7;c17:9f3;g12:5f2;c12:4f3;c13:4f3;c14:3f0;b14:4f2;q15:3f1;p15:4f5;c15:5f1;b16:4f3;i16:5f1;c16:6f2;r17:5f0;p17:6f6;r17:7f1;q18:6f0;c18:7f3;c18:8f3;c18:9f3;c18:10f3;i13:5f7;c13:6f3;c13:7f3;p14:5f7;q12:7f2;c12:6f1;c14:6f3;c14:7f3;c15:8f2;c16:8f3;i15:11f6;c14:9f2;q14:8f3;


Edit: wait... wait.

Spoiler:
?lvl=31&code=b9:4f1;p10:4f7;b11:4f0;r8:3f2;i9:3f3;c10:3f3;p8:2f4;c9:2f0;r8:1f3;c7:3f3;c7:2f3;i12:3f1;p13:3f3;q10:5f3;b14:12f2;p15:12f3;r16:12f0;q15:13f7;c14:13f0;c13:13f0;y12:2f3;c12:12f2;c13:12f2;g11:3f0;c7:11f1;c7:12f1;r8:11f2;p8:12f0;r8:13f1;b9:10f3;i9:11f5;c9:12f0;q10:9f5;p10:10f1;c10:11f1;b11:10f0;g11:11f0;g11:9f1;g11:5f3;b11:6f3;p11:7f6;r11:8f1;r9:6f3;g9:5f3;b9:8f1;y9:9f1;c7:7f2;c8:7f2;c9:7f2;c12:10f3;r14:10f2;c15:10f3;i16:10f6;c17:10f0;i12:11f6;p13:11f5;c14:11f0;c16:11f0;c18:11f0;q13:10f1;c13:8f3;q13:9f7;g12:9f0;r7:8f1;y7:9f1;q8:9f5;y7:5f3;b7:6f3;q8:5f3;c7:4f2;c8:4f3;c8:10f1;c7:10f2;c10:7f2;c17:11f0;b15:9f3;q16:9f7;c17:9f3;c14:3f0;c18:9f3;c18:10f3;c13:7f3;q12:7f2;c14:7f3;c15:8f2;c16:8f3;i15:11f6;c14:9f2;q14:8f3;p15:5f5;c15:6f1;b16:5f3;i16:6f1;c16:7f2;r17:6f0;p17:7f6;r17:8f1;q18:7f0;c18:8f3;b14:5f2;p14:6f7;c13:5f3;i13:6f7;c12:5f3;g12:6f2;q15:3f1;c8:6f2;c15:4f1;c12:4f3;c13:4f3;
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

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

Re: Manufactoria / Checker and score keeper program

Postby Nix » Thu Jun 10, 2010 7:41 pm UTC

A new version of the checker/score keeper (see for basic usage help) is attached to this post. Previous version was here.

Important changes:
  • Warning if a part is not used (that is, not even entered) in any of the test cases.
  • Keeps track of slowest solutions to each level in addition to the traditional records.

If the program notices an unused part, you shouldn't blindly try to remove it, in case it is needed with a long input that isn't tested. For example, this occurs in Berengal's Robo-children speed record. Specially crafted long inputs (or very long random ones) would have to be tested in order to use all the parts, but without them it would fail. Do not submit a cut version of such a solution even if the program currently reports it as better. A new version or an interested viewer will catch it in the future.

The slowness records work as follows. A slowness record solution must return or reject any input as expected normally. An infinite loop is not slowness, it's an error. Otherwise, basically the more total steps spent the better, but if any individual test input requires more than 50k steps, the slowness is considered maximal, and such entries are considered equal in step counts. If the step counts are equal, the solution that has less parts is better. In the later levels where the 50k barrier can be broken, you should aim to break it in as few parts as possible. Otherwise, just go for as many steps as possible.

Running 100k steps on an input (more for long inputs) still causes the program to assume it's an infinite loop. If this is a problem, you can edit the initialization of maxRounds (just search the code). If that is common, I'll add a command line option to override it in a later version.

I've seeded the scores.txt with some deliberate slowness records by me and Jani, otherwise listed is just the slowest entry that's been in the normal records. I'll start keeping the slowness records on display in this thread later if this catches. Do send me anything that's a deliberate slowness record and it will at least be in scores.txt.
Attachments
manufactoria-checker.cpp.gz
(10.67 KiB) Downloaded 164 times

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Xanthir » Thu Jun 10, 2010 10:09 pm UTC

phlip wrote:If we're sharing new levels, here's one that I was kinda surprised wasn't in the real set: Roboparrots!

Yay, I liked roboparrots. Simple but non-trivial, with fun opportunities for optimization. Smallest machine I've been able to get so far is 43 parts:
?lvl=32&code=b11:11f2;p12:11f3;q12:12f2;r13:11f0;g12:2f3;g12:3f3;i10:5f4;q10:6f0;c11:4f2;c12:5f3;p12:6f3;c12:7f3;c12:8f3;c12:9f3;c13:4f0;r13:5f3;p13:6f2;b13:7f1;i14:5f0;q14:6f6;y12:4f3;c10:4f2;c14:4f0;c12:10f3;r15:6f3;g14:7f2;p15:7f2;b15:8f1;c16:6f1;c16:7f1;c16:5f0;c15:5f0;r9:6f3;p9:7f4;b9:8f1;g10:7f0;c8:6f1;c8:5f2;c9:5f2;c8:7f1;p11:6f0;b11:5f3;r11:7f1;&ctm=Roboparrots!;OUTPUT:_the_input,_repeated_twice!;b:bb|brbb:brbbbrbb|:|rrb:rrbrrb|bbrbrr:bbrbrrbbrbrr;13;3;0;
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Tirian » Thu Jun 10, 2010 10:24 pm UTC

Here's my candidate for a slow Academics:

?lvl=23&code=y12:2f3;p12:3f3;b11:3f2;r13:3f0;g12:4f3;g12:5f3;p14:4f0;r14:5f1;b14:3f3;q13:5f1;c13:4f3;b11:9f2;p12:9f3;q12:10f1;r13:9f0;c13:10f2;q14:9f2;p14:10f2;q14:11f6;y16:9f1;i16:10f4;c16:11f1;c12:6f3;i12:7f1;r15:8f2;p16:8f1;b17:8f0;b15:12f2;b15:11f2;r15:9f2;g14:8f0;g14:12f0;c8:13f2;c9:13f2;c10:13f2;c11:13f2;p8:6f0;y8:7f0;r7:7f1;i7:6f0;c6:7f3;c6:8f3;c6:9f3;c6:10f3;c6:11f3;y8:5f1;b8:4f0;c7:5f1;c7:4f1;q6:6f0;p7:3f1;b8:3f0;r6:3f2;q7:2f5;g8:2f2;p9:2f2;r9:1f3;b9:3f1;q10:2f0;c10:3f3;c10:4f3;c10:5f2;c11:5f2;c6:12f2;p7:12f2;r7:11f3;b7:13f1;q8:12f0;c13:12f0;c12:12f1;c12:11f0;p11:11f0;b11:10f3;r11:12f1;b10:11f0;c13:8f1;c13:7f0;c12:8f3;q9:7f2;c9:10f1;c9:11f1;c9:9f1;c9:8f1;b11:6f3;p11:7f0;r11:8f1;r10:7f0;g9:6f0;c15:10f2;c17:10f3;c17:11f3;c17:12f3;c17:13f0;c16:13f0;c15:13f0;q14:13f1;q13:13f1;q16:7f3;g17:7f1;i17:6f4;i17:4f0;i17:3f0;i17:2f4;c17:1f0;c16:1f0;c15:1f0;c14:1f0;c13:1f3;c13:2f2;c14:2f2;c15:2f2;c16:2f2;c18:2f3;c18:3f0;c16:3f0;c15:3f3;i15:4f1;c15:5f3;c15:6f2;c16:6f2;c18:6f1;c18:5f1;c18:4f0;c17:5f1;c16:4f0;

I suspect that the naive strategy here for picking the last dot in a R/B string would be applicable to a fair number of levels. I also more than suspect that anyone could improve (deprove?) on this solution by making the pathing even more labyrinthine than what I came across with minimal effort.

In other news, I solved passed solved! Metatron!! I really must discover how the rest of you are picking the last character from a string, because I think I must be doing it woefully inefficiently.


Return to “Coding”

Who is online

Users browsing this forum: Soupspoon and 10 guests