Manufactoria - Make Turing Machines with Conveyor Belts

[Vault]

Manufactoria

Basically the object is to accept or reject different patterns of colored dots using conveyor belts and branches. Later you get to add your own dots. Given an infinite robot grid, the game is probably Turing complete.

This thread is split off of the discussion in the FT thread.
-------------

Currently I'm stuck on the Rocket Planes level. It wants me to sort the dots, and so far I am incapable of figuring out how to sort on top of only a queue.

[joshz]

If I could have some way of storing variables, that would make it far easier, but I'm not sure how.

[Steax]

For which part? The lower half supports adding in your own markers, so that's basically writing your own variables.

Also, has anyone found out how to save the game? It's kind of irritating to have to keep saving the codes. I want to see the big tree diagram-thing.

[Vault]

I found the bottom half a lot easier than the top half for just that reason. You can just set a marker on the end, do the necessary transformations with one or two BR gates, and get rid of the marker you set right before it goes through the end.

And what do you mean by save? My progress has been preserved as I've gone away and come back to it.

[Steax]

Oh, I didn't realize it auto-saved. Just tried it and it does load back. No problem with that then.

And yes, I found the lower half a lot easier. Being allowed to add in my own variables also eases my head a lot.

I'm also stuck on rocket planes, but I'm edging closer to it...

[Ephphatha]

This game is addictive. I finally managed to get past Robomecha after being stuck on it for a while when I worked out that I can send it to a particular track and use that to indicate the second last value read. Ended up with a design that used 34 pieces (the first working version was about 50).

Edit: Having trouble on Android . Any hints on what I should be doing?

EditEdit: Got it, but I'm sure my solution actually had an infinite loop in it if more reds than blues were provided... Lucky that situation never came up.

EditEditEdit: Oh wow, Soldiers! was stupidly easy.

[joshz]

By variable, I really mean a counting variable. So I can count number of blues and reds, or stop reading after the nth dot.

[phlip]

Hey, looking at the credits, it's made by the same guy as Конструктор... I thought they looked similar.

[edit] Wait, no, just inspired by it. Still, the appearance and sense of humour is very similar.

[Ephphatha]

Currently doing robo children with, no joke, the worst possible solution. I bubblesort the list (think I took it from my solution to rocket planes) then read through the list until I find the end of the blues and the start of the reds, drop one of each, and repeat. If there's a solo element left, fail. One of the random inputs (or maybe it's a scripted input, I dunno) is a tape of about 30 symbols, with the last 10/15 blue and a few blues scattered randomly. I've had it running on the fastest speed for the past 10 minutes and it's still not through the sorting phase yet...

Spoiler:

You've probably all got this already, but the proper way of doing it is (I think) making a NOR gate. If two symbols are the same, replace them with 1 of the same colour. If they're different, drop them.

[jaap]

By variable, I really mean a counting variable. So I can count number of blues and reds, or stop reading after the nth dot.

You can't do that. Here are a few hints/techniques that may help.

Spoiler:

Remember that on many of the levels you may change what the tape reads in any way you like. If the level's task is only to verify that the tape pattern has a particular property, then when the robot arrives at the exit it doesn't matter what the tape contains.

Spoiler:

Adding a yellow or green dot on the end makes for a handy marker to see whether the whole tape has been read through once.

Spoiler:

If you need to check that the tape pattern has a certain property, you can usually rewrite the tape in such a way that does not change whether or not that property holds, but does make the pattern simpler (e.g. shorter). Repeat until the pattern is so simple that it is easily checked for acceptability.

Spoiler:

For example, if you want to ensure the tape had an equal number of reds and blues, then remove one red and one blue on each complete read-through of the tape, and repeat. If the tape eventually becomes empty then was acceptable, but if at any stage you cannot find both a red and a blue then it should be rejected.

[Briareos]

I'm stuck on Androids as well. Since it's the classic example of a non-regular language, I keep wanting to use a push-down automaton. But I think having that design stuck in my head is making it more difficult for me.

[Ephphatha]

If you want a hint, unspoiler below. (I had to redo it actually, I deleted my solution somehow )

Spoiler:

You only care about how many consecutive blues, then reds, there are. Everything after the first run of reds you can discard.

Spoiler:

After you've trimmed your input to a run of blues, then a run of reds, you want to see if they're equal. If you get rid of one red and one blue each iteration, you're golden.

[Vault]

I still haven't got past the sorting one. The solution that I came up with works for the most part, but is prone to getting stuck in an infinite loop. (Which I guess means that it doesn't actually work).

[TheChewanater]

This game is really making me appreciate my CPU more.

I'm stuck on android right now. My biggest problem is that the board is too small for my ugly solution.

[evilbeanfiend]

I still haven't got past the sorting one. The solution that I came up with works for the most part, but is prone to getting stuck in an infinite loop. (Which I guess means that it doesn't actually work).

hint

Spoiler:

try first designing a machine that checks if the sequence is sorted

also a number of my saved machines seem to have become corrupted have to do them again now

[Berengal]

I've got a real decent solution for robo-children now. It's worst-case is O(n log_5 n), but it usually works in O(n) with a kick-ass constant factor.

[TheChewanater]

EDIT AGAIN: Well, that actually doesn't always do what I expect it to.

EDIT: This seems to work some of the times.

Oops, I misunderstood the Android one. I thought it just needed to have the same number of each, so I did this:

Spoiler:

screenshot1.png (4.23 KiB) Viewed 12334 times

Which worked great until I got to one with the same number of reds and blues but all scrambled up.

[D4N_]

I basically just joined (after a long time lurking) to say how awesome this game is. I just finished Androids and have already wasted a few hours on this game. It seems a lot of the taking the dots as binary levels are pretty simple if you're already familiar with binary. I'm still stuck on the Rocket Planes level but will probably give it a good go again later.

[Briareos]

Just finished a disastrously inefficient implementation of Rocket Planes. Back to work on Androids.

EDIT: Got it! I think working on Rocket Planes helped a lot. Now to look at you guys' spoilers.

EDIT: Soldiers? That was straightforward.

[levantis]

can anybody tell how to reverse a string or place an element in the front?
by the way, about the equality - you can place a marker at the end for a blue and delete it for a red. placing a lot of markers in the beginning avoids underflow.
also, you can drop the adjacent red/blue and replace consecutive runs with green/yellow respectively. then repeat with different colors. dunno why, but it worked all the time.

[JavaBean]

I'm surprised everyone is having so much trouble with Rocket Planes - that wasn't the one that tripped me up. The general approach I used was

Spoiler:

Rather than move blues to the front, move reds to the back

A more detailed (still pseudo-code) algorithm:

Spoiler:

• Copy/skip any number of blues
• Consume the first red
• Copy reds until you find a blue - if no blue, the list is now sorted and you just reprint the red
• Write the blue back
• Copy the rest of the tape
• Write the red you consumed at the start
• Recurse

That is, rather than moving blues to the front I found it a lot easier to move reds to the back.

For an actual answer, if you're into that kind of thing:

?lvl=27&code=p12:7f3;b11:7f2;r14:6f3;p14:7f2;c13:7f2;c16:8f3;c16:9f3;c16:10f3;c16:11f0;c15:11f0;c14:11f0;c13:11f0;b14:8f3;p14:9f3;r15:9f0;q14:10f1;i12:10f6;c10:8f1;c10:7f1;c10:6f2;c11:6f2;r13:10f0;b13:9f2;g12:6f3;c12:4f3;c12:5f3;q12:8f0;c12:9f3;c11:10f0;c10:10f1;c10:9f1;q15:8f3;r15:7f3;

On the other hand, I'm glad someone had enough trouble with Rocket Planes to start this thread - it's an excellent game and I wouldn't have found it otherwise. I'm having a heck of a time testing A>B; does anyone else think the binary numbers ought to be given to us with the least significant bit first, rather than last? It would make every numerical program easier, as far as I can see.

Also, to reverse a string: that one is tricky. It's easy enough to move the first symbol to the back, but that's only the first step. I found a useful question to ask myself was:

Spoiler:

How do you know whether an element at the back of the list was there originally, or has already been reversed by you?

The answer I came up with for my solution was:

Spoiler:

Write a yellow in front of it when you move it, and strip all the yellows out once each element has a yellow attached.

[joshz]

For androids, does it need to be n blue in a row then n red in a row? Because I accepted BBRBBRRRBR and it said I should've rejected it.

[Token]

Man, I loved this game. It was surprisingly fun going over my early solutions once I'd finished, and seeing how easy it then was to make everything much more elegant.

As far as Androids: it needs to be N consecutive blues, then N consecutive reds, then nothing. There's at least one fairly neat solution.

Spoiler:

?lvl=17&code=g12:4f3;p12:6f3;c12:7f3;c12:8f3;c12:9f3;c12:10f3;q11:4f5;p11:6f4;b11:7f1;p11:5f1;r10:5f2;i12:5f7;

[TheChewanater]

I agree with everyone who says soldiers was too easy. Took two seconds.

So, what sort of property do powers of four have in binary that makes them easily recognizable?

[joshz]

Is there any that just requires the same number of reds and blues? Cause I solved that.

[D4N_]

Robo-Children requires the same number of reds and blues in any order, so yes.

It seems that if you can find a small enough sort (in terms of space on the board) then you can find out if there are the same number of reds and blues by combining it with the Android solution, shame there isn't a way to plug solutions together to make more complicated ones.

[TheChewanater]

I used the same algorithm for androids as robo-children. In reality, this wouldn't work for all sceneries in the androids level, but I don't care. It worked for me, was efficient, and was reusable.

[joshz]

OK, so what I have right now for android accepts same number in any order. How do I modify that to make it accept only in a row order? Also, my current alg is extremely inefficient (space-wise) so I'm not sure how much I could fit.

Spoiler:

Code: Select all

?lvl=17&code=g12:4f3;c12:5f3;p12:6f3;p10:6f0;c11:5f2;b10:5f2;c10:7f2;c11:7f1;i11:6f0;i13:6f3;p14:6f2;r14:5f0;c13:5f0;c14:7f0;c13:7f1;p12:8f3;c13:8f2;c14:8f2;p15:8f2;c15:9f0;c14:9f0;q12:7f0;c12:10f3;c11:8f0;c10:8f0;p9:8f0;c9:9f2;c10:9f2;c12:9f3;c11:9f2;c13:9f0;

[Dason]

OK, so what I have right now for android accepts same number in any order. How do I modify that to make it accept only in a row order? Also, my current alg is extremely inefficient (space-wise) so I'm not sure how much I could fit.

Spoiler:

Code: Select all

?lvl=17&code=g12:4f3;c12:5f3;p12:6f3;p10:6f0;c11:5f2;b10:5f2;c10:7f2;c11:7f1;i11:6f0;i13:6f3;p14:6f2;r14:5f0;c13:5f0;c14:7f0;c13:7f1;p12:8f3;c13:8f2;c14:8f2;p15:8f2;c15:9f0;c14:9f0;q12:7f0;c12:10f3;c11:8f0;c10:8f0;p9:8f0;c9:9f2;c10:9f2;c12:9f3;c11:9f2;c13:9f0;

I haven't looked at your solution yet but to solve the problem why don't you just check to see if you have the pattern (X blue)(Y Red)(Nothing else), if not then reject, otherwise send it into what you have.

[joshz]

That's what I'm thinking of doing, I'm just not sure how to fit it. I'll post a screenshot in the morning (7-8ish hours) so you won't have to load my level.

[Ephphatha]

So, what sort of property do powers of four have in binary that makes them easily recognizable?

Spoiler:

Only one set bit, and an even number of trailing 0's

My solution to that has:

Spoiler:

6 conveyers and 3 r/b branches.

A few undocumented features I've found (and some I've had to be told):
Space flips a branch.
You can make bridges by placing two perpendicular conveyers on the same square.
You can feed a branch from any side.

I kinda like my solution to androids, I can screenshot it if people want but I'll spoiler the procedure below. Try solve it yourself though, it's fun

Spoiler:

1. Mark the start.
2. Copy blues until you hit a red. If you hit the marker, go to 5.
3. Copy reds until you hit a blue. If you hit the marker, go to 5.
4. Discard the rest of the input until you hit the marker.
5. Read and reprint the marker.
6. Read a symbol. If blue, continue. If red, dump robot. If marker, go to finish.
7. Read a symbol. If blue, write it back on the tape. If red, continue. If marker, dump robot.
8. Read and reprint any remaining reds. When you hit the marker, go to 5.

[jaap]

A few undocumented features I've found (and some I've had to be told):
Space flips a branch.

Damn! I didn't know that.
Another nice feature is that you can copy/paste (select an area, shift-c to copy, shift-v to paste). This works between levels too, so that you can copy parts from one level to the next.

ETA:
My solution to androids seems a bit simpler:

Spoiler:

1. Mark the start.
2. Read a symbol. If blue, continue. If red, dump robot. If marker, go to finish.
3. Read and reprint any following blues.
4. If we hit a non-red (i.e. marker) at the end of 3, then dump robot.
5. Read and reprint any following reds.
6. If we hit a blue at the end of 6, then dump robot.
7. Read and reprint marker, and go to 2.

?lvl=17&code=y12:4f3;p12:5f3;p9:6f3;b8:6f1;c8:5f2;c9:5f3;c11:5f0;c10:5f0;p10:7f3;r11:7f1;c10:6f3;c11:6f0;q10:8f3;c9:8f3;c9:9f3;c9:10f2;c10:10f2;c11:10f2;i12:10f7;c13:10f2;c14:10f2;c15:10f1;c15:9f1;c15:8f1;c15:7f1;c15:6f1;c15:5f1;c14:4f0;c13:4f0;c12:7f3;c12:8f3;q13:7f3;c12:9f3;c13:6f3;c12:6f2;c15:4f0;

[phlip]

Space flips a branch.

Huh, that'll come in handy.

You can make bridges by placing two perpendicular conveyers on the same square.

That is documented... somewhere. I'm at work at the moment, so I can't check, but I know the game has told me about that. The tooltip when you select the conveyor tool maybe?
[edit] Yeah, at the bottom of the screen when you have the conveyor selected, it says "Click or drag to place; shift-click to bridge!"... the same thing says "space to flip!" on branches, but I just never noticed.
[edit again] Ah, those status messages aren't on the version of the game linked in the OP... but they are there on Kongregate. I think the latter is a later version (it says v1.13c on the main menu, whereas the jayisgames one doesn't have a version number there at all).

You can feed a branch from any side.

It's only on reading this that I actually realised that the unused edge of a branch actually looks kinda like it's supposed to be an input... the idea that the input direction of a branch would matter never occured to me. The conveyor bridge is the only part where the input direction has any effect on the actions.

But yeah, you can do a "move all blues at the head of the tape to the end" type deal by just putting in an R/B branch, and a blue writer on the blue branch pointing right back at the switch again.

[Berengal]

I'm pretty sure I saw the space flipping and bridging being explained the first time I played it, because I've known about those all along. I can't seen to find where now though.

Also, robo-children:

Spoiler:

?lvl=18&code=c12:8f3;c12:9f3;c12:10f3;c12:11f3;c7:4f2;b7:5f1;c7:6f1;g7:7f1;c8:4f2;p8:5f3;p8:7f3;c9:4f2;p9:5f3;p9:7f3;c10:4f2;c11:4f2;p11:5f3;p11:7f3;c12:4f3;p12:5f3;q12:6f0;p12:7f3;c13:4f0;p13:5f3;p13:7f3;c14:4f0;c15:4f0;p15:5f3;p15:7f3;c16:4f0;p16:5f3;p16:7f3;c17:4f0;r17:5f1;c17:6f1;g17:7f1;g12:3f3;p10:5f3;p10:7f3;p14:5f3;p14:7f3;

[Dason]

I'm pretty sure I saw the space flipping and bridging being explained the first time I played it, because I've known about those all along. I can't seen to find where now though.

Also, robo-children:

Spoiler:

?lvl=18&code=c12:8f3;c12:9f3;c12:10f3;c12:11f3;c7:4f2;b7:5f1;c7:6f1;g7:7f1;c8:4f2;p8:5f3;p8:7f3;c9:4f2;p9:5f3;p9:7f3;c10:4f2;c11:4f2;p11:5f3;p11:7f3;c12:4f3;p12:5f3;q12:6f0;p12:7f3;c13:4f0;p13:5f3;p13:7f3;c14:4f0;c15:4f0;p15:5f3;p15:7f3;c16:4f0;p16:5f3;p16:7f3;c17:4f0;r17:5f1;c17:6f1;g17:7f1;g12:3f3;p10:5f3;p10:7f3;p14:5f3;p14:7f3;

That's beautiful. I didn't realize until reading the recent posts that you could feed into a branch from the sides. I was essentially doing what you have but it's much more a of a clusterfuck because I didn't realize you could feed into the sides.

[Glom]

Ok maybe I'm missing something important here. But I'm doing the Robospies puzzle. The puzzle with blue as 1, and red as 0. Accept natural powers of four.
(4, 16, 64... or 100, 10000, 1000000... in binary)
My machine would do that... and it works fine for the first two tests... Gives me 4 first; It accepts. Gives me 2 next; It rejects. But then it gives me 1... Just a blue dot. My machine correctly rejects 1, since it is NOT a power of four. And yet the game says that I should have accepted it.
Is something wrong with the game, or is 1 actually a power of four and I just missed something important?
Here's my machine:

Spoiler:

?lvl=16&code=p12:4f3;c13:4f0;c11:4f3;p11:6f3;c11:5f3;c12:6f3;p12:7f3;i11:7f1;i10:7f0;i10:6f0;c10:5f2;c13:7f3;c13:9f3;c13:10f3;c13:11f0;p13:8f3;i12:8f1;i11:8f6;i10:8f0;c14:8f1;c14:7f1;c14:6f0;c13:6f0;

I got it to work doing this:

Spoiler:

?lvl=16&code=p12:4f3;c13:4f0;c11:4f3;p11:6f3;c11:5f3;c12:6f3;p12:7f3;i11:7f1;i10:7f0;i10:6f0;c10:5f2;c13:7f3;c13:9f3;c13:10f3;c13:11f0;p13:8f3;i12:8f1;i11:8f6;i10:8f0;c14:8f1;c14:7f1;c14:6f0;c13:6f0;c11:9f3;c11:10f3;c11:11f2;

But it still doesn't seem right. Since... it's wrong!

[TNorthover]

The puzzle with blue as 1, and red as 0. Accept natural powers of four.
(4, 16, 64... or 100, 10000, 1000000... in binary)
[...]
But then it gives me 1... Just a blue dot. My machine correctly rejects 1, since it is NOT a power of four.

4^0 = 1

[Glom]

4^0 = 1

derp, that's what I get for playing this stupid game at 4 am

[D4N_]

Just finished Rocket-planes. I built it the wrong way round at first so that it shifted blues to the back, so finding out that space flips the branches was really useful. My solution is seriously inefficient though, over 3 minutes on one input (although i haven't trimmed out any unnecessary components yet). Has anyone found an efficient algorithm for this?

[joshz]

What I have now for androids:

Spoiler:

How can I fit in the logic that only accepts colors in a row?

Oops, that doesn't even work all of the time even for really nice ones. If it doesn't reduce to one of each in one time through, then it fails.