xkcd

by **Xanthir** » Thu Jun 07, 2012 6:12 pm UTC

Regarding your bounds, using my total coverage tester, I get the following data:

Code: Select all: 4 4046 126/run 5 10228 + 6k 193/run 6 24958 + 14k 230/run 7 59188 + 36k 267/run 8 137206 + 77k 304/run 9 312976 +175k 343/run

So it looks like increasing the tape length by 1 adds about 40 steps to the average running time. So, the algorithm is linear.

by **mr-mitch** » Thu Jun 07, 2012 6:25 pm UTC

I don't seem to believe that, though.

In the worst case, it replaces all the Bs with Ys (so that's roughly N steps).
Then it loops through the string and until there are no Ys, it does YB->BR, YR->RB, so that's N Ys, and thus N steps for each N Ys. The break-condition takes N steps as well.

So shouldn't it be about 2N + N²?

In the expected case it's different because the worst case time of the algorithm depends on the longest section of Bs in the initial tape.

Thanks for your help though.

by **Xanthir** » Thu Jun 07, 2012 6:33 pm UTC

Based on what you say about your algorithm's worst case, it's very reasonable that the n^2 term is too small to show up in the average data. It's like quicksort, which is actually O(n^2), but acts like O(n*log(n)) in the average case.

For most tapes, the n^2 part of the algorithm is swamped by the linear part.

by **Jplus** » Tue Jun 19, 2012 11:02 pm UTC

@Xanthir: I hereby confirm that your emulator works perfectly well in Safari. (Could it not do so, given that Chrome supports it as well?)

by **Xanthir** » Thu Jun 21, 2012 11:15 pm UTC

Safari and Chrome only share WebKit, their rendering engine. Their JS engines are completely different, and so programs might work in one and not the other.

by **Xanthir** » Mon Oct 22, 2012 9:15 am UTC

Jeezus, I nerd-sniped myself on Manufactoria again. Just finished Ophanim, with a better solution than my best of last time. I don't think I ever managed to finish Metatron myself, actually - I'll attempt it tomorrow.

by **mr-mitch** » Tue Oct 23, 2012 9:46 am UTC

You've sniped me too. Is there a list of levels somewhere, so that I don't have to retry all the lower levels? I got up to the new levels again, but closed my browser and lost it all.

by **Xanthir** » Tue Oct 23, 2012 3:35 pm UTC

Huh? Assuming you aren't blocking things from Flash, it should save your progress automatically.

by **Derek** » Sun Oct 28, 2012 9:00 pm UTC

Damn this is a fun game. I beat all the regular levels over the last two days and I'm working on the bonus levels now.

I really wish the numbers were little endian for the math problems though

by **Dopefish** » Sun Oct 28, 2012 10:22 pm UTC

It amuses me that I completely understand the first half or so of this thread from playing the game, but it's turned into implementing various algorithms that I don't know about as a non-computer scientist and proper analysis of the scaling of those solutions.

I'm stuck on 4 or 5 levels now, two of which I'm pretty sure I have a solution for, but those solutions require me to know how to solve the other problems (e.g. if I knew how to move all the blues to the front [or equivalently, reds to the back], then I'd be able to implement all sorts of nifty things that deal with that sorted set-up...), so I just need a break through moment on one to get momentum again. I'm pretty sure sorting them shouldn't be terribly difficult, but hum...

Anyway, I notice both this and the similar logic box game involve 4 possible states (red/blue/green/yellow). Is there any particular significance to that? I was under the impression that these modeled how computer actually worked on a low level, but I thought computers boiled down to just 1's and 0's, not 1's and 0's and 2 other states.

Many of my solutions for the later levels that allow green/yellow markers I only ended up using one colour of (typically just to mark the beginning of a string) as opposed to both. If space wasn't a concern, could those later levels actually be solved without using yellow/green at all? Or do those tasks really need a minimum of 3 states to solve?

by **Snark** » Mon Oct 29, 2012 3:48 am UTC

Working on Officers, Police, and Academics.

Finally finished Robomecha.

Super fun game.

by **Derek** » Mon Oct 29, 2012 6:28 am UTC

Got Ophanim. Getting everything within the workspace was quite tricky. Usually I keep state by using alternate paths, but for this one I had to write state bits to the tape. My solution:

Overview:

Spoiler:

Code:

Spoiler:

by **Jplus** » Mon Oct 29, 2012 10:40 pm UTC

Dopefish wrote:Anyway, I notice both this and the similar logic box game involve 4 possible states (red/blue/green/yellow). Is there any particular significance to that? I was under the impression that these modeled how computer actually worked on a low level, but I thought computers boiled down to just 1's and 0's, not 1's and 0's and 2 other states.

+1 for the cutest computer-related remark I've seen in years.

(Answer: neither Manufactoria nor Logic Box model the way actual computers work on a low level. If you're interested, the similar but somewhat harder game Kohctpyktop comes closer.)

by **phlip** » Tue Oct 30, 2012 4:05 am UTC

Even Konstructor isn't perfect, as IIRC every cell is pulled down (ie if it's not connected to any signals, it automatically gets a 0 value, rather than being some floating indeterminate value) which means you only need to have extra pins for power, and not ground. But it's still pretty close to how ICs work.

The reason that Manufactoria needs the extra states is that the tape isn't a good model for TM memory... in particular, the strict queue nature of it. Say you only had the R/B states, and you want to read the last bit on the tape (as one of the puzzles requires you to do). So you read all the bits off the tape until you get to the end. At that point, if you haven't written any new bits to the tape, then all memory of those earlier bits is lost, or some limited amount of information about them is stored in where the robot's standing on the grid... which is obviously limited by how big your machine is. On the other hand, if you do write to the tape, you can't tell where the original end of the tape is, without having G/W to use as a position marker.

by **Dopefish** » Tue Oct 30, 2012 5:17 am UTC

Jplus wrote: If you're interested, the similar but somewhat harder game Kohctpyktop comes closer.

Oh geez, somewhat harder is a bit of an understatement. Not necessarily because of the logic involved, but because the almost total lack of explanation of whats what, and the help video is only marginally beneficial. Still, after about an hour of testing things and re-watching the help video repeatedly, I think I've got the mechanics figured out and have now completed the first two levels (to be fair, the first level is given in the video), and can start grappling with the logic instead.

Anyway, thanks for that. Carry on with implementing Linux within Manufactoria, or whatever deep coding magics y'all are working on now.

by **Derek** » Tue Oct 30, 2012 5:29 am UTC

I've got a great solution to Metatron (add two numbers), but the grid is too small to contain the termination check.

phlip wrote:Even Konstructor isn't perfect, as IIRC every cell is pulled down (ie if it's not connected to any signals, it automatically gets a 0 value, rather than being some floating indeterminate value) which means you only need to have extra pins for power, and not ground. But it's still pretty close to how ICs work.

The reason that Manufactoria needs the extra states is that the tape isn't a good model for TM memory... in particular, the strict queue nature of it. Say you only had the R/B states, and you want to read the last bit on the tape (as one of the puzzles requires you to do). So you read all the bits off the tape until you get to the end. At that point, if you haven't written any new bits to the tape, then all memory of those earlier bits is lost, or some limited amount of information about them is stored in where the robot's standing on the grid... which is obviously limited by how big your machine is. On the other hand, if you do write to the tape, you can't tell where the original end of the tape is, without having G/W to use as a position marker.

I don't think you need 4 states for Manufactoria. You can map the four states onto pairs of bits: Let R be RR, B be RB, G be BR, and Y be BB. Writers are trivial to implement, and readers are only a bit harder (the issue is that to implement a pass through, you'll have to reprint the first bit and loop back through the entire queue to get it into the right position. It's also very easy to write an encoder or decoder from one representation to the other. Solutions would take a lot more space though.

by **phlip** » Tue Oct 30, 2012 5:30 am UTC

Derek wrote:It's also very easy to write an encoder or decoder from one representation to the other.

This is the bit that I disagree with... sure, you can write a thing that goes through and reads R's and B's and writes RR's and RB's, but how does it know when it's done?

by **jestingrabbit** » Tue Oct 30, 2012 6:45 am UTC

phlip wrote:
Derek wrote:It's also very easy to write an encoder or decoder from one representation to the other.

This is the bit that I disagree with... sure, you can write a thing that goes through and reads R's and B's and writes RR's and RB's, but how does it know when it's done?

Yeah, if you were guaranteed that the input was in the new format, then sure you don't need the extra colours, but if the input is unencoded, then you need the extra colours for precisely the reason you described.

Derek wrote:I've got a great solution to Metatron (add two numbers), but the grid is too small to contain the termination check.

The size restriction is part of the problem, dude :wink:

by **Derek** » Tue Oct 30, 2012 7:33 am UTC

phlip wrote:
Derek wrote:It's also very easy to write an encoder or decoder from one representation to the other.

This is the bit that I disagree with... sure, you can write a thing that goes through and reads R's and B's and writes RR's and RB's, but how does it know when it's done?

Fine, do this: R -> RRR, B -> RRB, G -> RBR, Y -> RBB, meta-marker -> B

A valid encoded string contains characters of 3 bits each, and the first bit is always R.

To encode a string:
1. Write a meta-marker (B).
2. If the next bit is B, consume it and finish. Otherwise, go to (3).
3. Read the next two bits and write out R, B, G, or Y as appropriate.
4. Go to (2).

To create a RB branch (GY is symmetric):
1. Write a meta-marker (B).
2. Read the next three bits. If RRR, exit 1, if RRB, exit 2. Otherwise, write the bits back and go to (3).
3. If the next bit is B, consume it and exit 3. Otherwise, copy the next three bits and go to (3).

by **phlip** » Tue Oct 30, 2012 10:44 am UTC

That still doesn't do the reverse, where you're given an arbitrary input string and try to encode it in your scheme.

The real puzzles would be unsolvable too, if the input strings could be any arbitrary sequences of R/B/G/W... you need the ability to store something out-of-band that can be used as a marker.

by **Derek** » Tue Oct 30, 2012 3:12 pm UTC

I wrote the encoding step wrong, but what I meant to say wouldn't work either (this is what happens at 2:30 am).

The branch implementation is correct though, and shows that you only need red and blue symbols if your inputs and outputs are encoded correctly. So to the question of "Is a 2-symbol version of Manufactoria Turing Complete?" the answer is still yes.

EDIT: I finally got my termination check small enough to complete Metatron:

Code:

Spoiler:

Screenshot:

Spoiler:

by **jestingrabbit** » Wed Oct 31, 2012 11:11 am UTC

And of course people posting here has dragged me back in. Here's a rather silly metatron that I've been thinking about.

Spoiler:

Unary.

by **Xanthir** » Thu Nov 01, 2012 4:18 pm UTC

Oh gosh, that is silly, and very very clever. Definitely the smallest non-crazy-packed machine for that level I've ever seen.

Also, as yet another public service announcement, I'd like to again plug my Manufactoria emulator: http://xanthir.com/manufactoria

Just take your level string save, and replace the url part (the part before the ?) with my url. Bam, you have a link to your level reproduced in the emulator. You can see the board (animated!) and run both arbitrary single testcases or do easy total-coverage testing with it. For example, here's jestingrabbit's level.

(My next feature should be to give it a secondary mode where you can link to it as an image and it'll just return an SVG of the board.)

(My other next feature will be the ability to actually see the machine running when you give it a single testcase.)

xkcd

Manufactoria - Make Turing Machines with Conveyor Belts

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Who is online