Page 4 of 9

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Fri Jun 04, 2010 12:43 am UTC
by phlip
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...

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Fri Jun 04, 2010 1:11 am UTC
by WarDaft
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.

Re: Manufactoria / record solutions

Posted: Fri Jun 04, 2010 2:00 am UTC
by Nix
The record score table was here, now moved to the new page. I'm leaving the edit history behind.


Updates since moving to this page:

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.

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Fri Jun 04, 2010 2:38 am UTC
by darkspork
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.

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Fri Jun 04, 2010 4:42 am UTC
by Xanthir
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.

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Fri Jun 04, 2010 1:51 pm UTC
by WarDaft
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.

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Fri Jun 04, 2010 2:14 pm UTC
by phlip
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.

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Sat Jun 05, 2010 9:00 am UTC
by jestingrabbit
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.

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Sat Jun 05, 2010 4:54 pm UTC
by Nix
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 9497 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.

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Sun Jun 06, 2010 8:12 am UTC
by 0rm
Why is this proving so difficult? I'm a programmer for christ sake! :evil:

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Sun Jun 06, 2010 11:08 pm UTC
by 0rm
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?

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Sun Jun 06, 2010 11:53 pm UTC
by Tirian
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.

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Mon Jun 07, 2010 12:06 am UTC
by Nix
@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.

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Mon Jun 07, 2010 3:02 am UTC
by Steax
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.

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Mon Jun 07, 2010 11:37 am UTC
by Notch
I implemented a Rule 110 interpreter in it, effectively proving it Turing complete for an unbounded tape.

Check it out!

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Mon Jun 07, 2010 4:07 pm UTC
by jestingrabbit
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.

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Mon Jun 07, 2010 4:33 pm UTC
by Nix
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.

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Mon Jun 07, 2010 7:25 pm UTC
by Tirian
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.

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Mon Jun 07, 2010 8:05 pm UTC
by Steve496
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.

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Mon Jun 07, 2010 9:24 pm UTC
by Tirian
Unfortunately, I've tried multiple strategies to decompress the scores file on my computer and none of them believe that it's gzipped.

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Mon Jun 07, 2010 10:59 pm UTC
by jestingrabbit
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;

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Tue Jun 08, 2010 1:10 pm UTC
by Nix
^ 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.

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Tue Jun 08, 2010 5:09 pm UTC
by Tirian
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.

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Tue Jun 08, 2010 11:07 pm UTC
by phlip
It works fine for me... try downloading the .gz again, maybe it got corrupted somehow.

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Tue Jun 08, 2010 11:28 pm UTC
by Tirian
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!!

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Wed Jun 09, 2010 12:47 am UTC
by 0rm
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.

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Wed Jun 09, 2010 2:05 am UTC
by phlip
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! [----]

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Wed Jun 09, 2010 3:23 pm UTC
by jestingrabbit
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.

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Wed Jun 09, 2010 5:03 pm UTC
by Nix
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.

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Wed Jun 09, 2010 5:20 pm UTC
by joshz
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;

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Wed Jun 09, 2010 5:49 pm UTC
by jestingrabbit
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;

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Wed Jun 09, 2010 6:11 pm UTC
by Nix
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.

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Wed Jun 09, 2010 6:39 pm UTC
by jestingrabbit
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;

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Wed Jun 09, 2010 7:23 pm UTC
by Tirian
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;

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Wed Jun 09, 2010 7:35 pm UTC
by Lothar
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;

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Thu Jun 10, 2010 1:44 am UTC
by phlip
If we're sharing new levels, here's one that I was kinda surprised wasn't in the real set: Roboparrots!

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Thu Jun 10, 2010 12:32 pm UTC
by jestingrabbit
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;

Re: Manufactoria / Checker and score keeper program

Posted: Thu Jun 10, 2010 7:41 pm UTC
by Nix
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.

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Thu Jun 10, 2010 10:09 pm UTC
by Xanthir
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;

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Posted: Thu Jun 10, 2010 10:24 pm UTC
by Tirian
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.