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
KrazyerKate
Posts: 431
Joined: Sat Oct 17, 2009 2:04 pm UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby KrazyerKate » Sun May 30, 2010 12:10 pm UTC

I seem to be doing fine with the binary ones where I just do a couple sample inputs on paper and figure out a pattern, but I'm having trouble with the bottom half where I'm just supposed to manipulate strings. could I get a hint about Police, Teachers, or Rocket Planes?

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby jaap » Sun May 30, 2010 12:54 pm UTC

KrazyerKate wrote:I seem to be doing fine with the binary ones where I just do a couple sample inputs on paper and figure out a pattern, but I'm having trouble with the bottom half where I'm just supposed to manipulate strings. could I get a hint about Police, Teachers, or Rocket Planes?

Teachers is just the same as Androids, but with 3 stages instead of 2.
Rocket planes has been mentioned a couple of times before in this thread - Instead of moving blues to the front, move the reds to the back.
Police is tricky. I'm not so sure the method I used is best:
Spoiler:
1. Write a yellow, a green, and a yellow at the end of the tape.
2. Shift the first yellow to the left, the next yellow to the right.
3. repeat 2, until the yellow markers meet at the middle.
4. remove one yellow, skip to the end and remove the green.g

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby phlip » Sun May 30, 2010 1:16 pm UTC

That's the strategy I used for Police as well.

Code: Select all

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

User avatar
KrazyerKate
Posts: 431
Joined: Sat Oct 17, 2009 2:04 pm UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby KrazyerKate » Sun May 30, 2010 2:28 pm UTC

Here's my Teachers solution:
Spoiler:
Every time I saw a blue I'd look for a red, then another blue. it gives me a 'success', but I think my solution would accept any string that had a 2:1 ratio of blues and reds, even if they weren't in the right order. Is there a solution that only accepts X blues, then X reds, then X blues?

Spoiler:
?lvl=21&code=c12:9f3;c12:10f3;c12:11f3;c12:12f3;c12:2f3;c12:4f3;c12:5f3;p12:6f3;c12:7f3;c12:8f3;c12:3f3;c9:7f3;p9:8f3;b10:5f3;p10:6f0;c10:7f0;r10:8f0;g11:6f0;p7:6f1;c8:8f0;c7:8f1;c7:7f1;r6:6f2;b8:6f0;q7:5f2;c7:4f1;c7:3f2;c8:3f2;c9:3f2;c10:3f2;c11:3f2;


edit: what, no nested spoilers?

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby jaap » Sun May 30, 2010 2:40 pm UTC

KrazyerKate wrote:Here's my Teachers solution: [...] Is there a solution that only accepts X blues, then X reds, then X blues?

Sure there is. Here's mine:
Spoiler:
?lvl=21&code=c12:12f3;c12:10f3;c12:11f3;c12:7f3;c12:8f3;c12:9f3;r8:2f2;p9:2f1;p9:3f4;b9:4f1;b10:1f3;p10:2f6;i10:3f6;q11:2f7;c11:3f0;y12:2f3;p12:3f3;c12:4f3;c12:5f3;c12:6f3;

How it works:
Spoiler:
It checks for blue string, red string, blue string, but reduces the length of each string by one as it reads it.
This repeats until the string is empty (accept) or the string is no longer blue-red-blue (reject).

User avatar
Dason
Posts: 1310
Joined: Wed Dec 02, 2009 7:06 am UTC
Location: ~/

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Dason » Sun May 30, 2010 4:49 pm UTC

jaap wrote:How it works:
Spoiler:
It checks for blue string, red string, blue string, but reduces the length of each string by one as it reads it.
This repeats until the string is empty (accept) or the string is no longer blue-red-blue (reject).

That's exactly how I did it.
double epsilon = -.0000001;

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

Re: Manufactoria / record solutions

Postby Nix » Sun May 30, 2010 5:22 pm UTC

The record score table was here, now moved to the new page. I'm leaving the edit history behind.


Additions since the ones in my previous post:

The entries posted in this thread since I last updated.

Steve496 optimized Robobugs from 13 down to 11 parts also beating the speed record. This has to be optimal both ways for this simple level, it's so elegant.

Steve496 also tore Generals from 29 down to 23 parts, and had small but not fast solutions for Police and Judiciary (89 to 51). His Politicians in 27 improved on his previous 29 parts and beat JavaBean's previous 36 part speed record of 107072 as well, but Steve496 went better and shows an even faster 57081 steps in 47 parts.

Steve496 also noted that my 21 part solution to Robo-children missed the obvious when going for speed: I had forgotten extra conveyors before instead of after the main body. He kindly let me keep the record to my name, until he can come up with something better.

Dernam (not registered here) improved Steve496's speed in 25 part Engineers, likely (I'm not in the habit of looking at solutions until I've matched them myself) using a different algorithm to get 110k instead of 172k steps, but still reaching the same size. The pure speed record still belongs to JavaBean with 96k in 27 parts.


2010-05-30

Added jaap's solution below and hopefully made the list more readable.

Made speed records in Robolamp, Robocats, Robobears, Milidogs and Robomecha (crazy) with more parts. Also Robofish, which was prompted by JavaBean sending a worse new speed record which I didn't look at.

Broke the Lothar/Nix size record in Officers by just one part (now 24) solving from scratch. The solution also adapted to Generals to improve from Steve496's 23 part solution to 21 parts.

Had to continue and try Officers for speed, and it worked surprisingly well, breaking my old speed record and doing it in the same 24 parts as my fresh size record. This may be unbeatable on both counts (that was stupid). Still improved speed by adding machinery to strip leading zeroes. Adapted, the same solution broke my old 29 part speed record in Generals, in 24 parts as well.

Two parts knocked off Steve496's record in Rocket planes by jareds, reaching 16.


2010-05-31

A set of records from jareds. He has speed records for Androids (crediting Berengal for the idea) and Robospies, and manages to downsize Robo-children to 20 breaking my record of 21. In Teachers he offers a faster small solution beating Steve496's 23494 step 19 parter with a 20495 one.

Steve496 has an impressive reduction of his own record from 75 parts to 64 in Ophanim.

Broke my yesterday's speed record of 114k with 81k in Officers with a 103 part monstrosity that reads four or five bits per loop and therefore doesn't even loop with most inputs. It probably has room for small improvement, but my head hurts enough as it is. The adaptation to Generals is quite different, and simpler at least at 79 parts.

Improved my Robotanks record in size and speed. The 25 part new size record is already faster than the old 27 parter, but I got nice extra speed too, using 44 parts.


2010-06-01

Another set from jareds. He broke speed records in Police, Teachers (eating up to six per loop) and Academics (copying two at a time) adding lots of pieces to each. Engineers he managed with just two pieces extra (four more than the size record), and in Robomecha he erased my 41 part speed record with only 21 while the size record is 19.

Steve496 still improved his Ophanim size from 64 to 61 parts with a new, almost three times slower (with the test set) algorithm.

I managed to squeeze Robo-children down to 18 parts in a funny little solution, two better than jareds's previous record. I also optimized my speed Generals from yesterday slightly, reducing it to 67 parts in the process.

Made an improbable new size record in Rocket planes, one smaller than jareds's 16 parts. And then even twerked it down to 14. There's no way that can be beaten in size (prove me wrong!) even if a faster 14 part solution may be possible.

Did Rocket planes for speed as well with an unintuitive approach, improving Berengal's 111k steps to 72k in 50 parts.

There's one minimal but advanced construct that's proving its worth again and again:
Spoiler:
A red/blue switch and a green/yellow switch next to each other with their neutral "forward" arrows pointed at each other. It acts as a fast and compact three (or four) way switch that can be entered from either direction, usually with a bonus direction at the green arrow (or yellow if you so prefer). Often it proves useful just to have an entry to the red/blue switch on the same side as the exit.


2010-06-02

Added EstLladon's Academics from below, breaking jaap's 29 part record with 28.

Steve496 owned Metatron by going two parts below Lothar's 75 part record and breaking enne's speed record with the same solution.

Jani (not registered here) went faster than me in Robocats (a reduction of just 333 steps and one part) as well as Roboplanes (almost surely optimal 9 part intermediate in scores.txt). I had lazily thought that the size record would be optimal both ways, but now went and improved Roboplanes even more myself by throwing 17 parts at it.

Steve496 shrunk Politicians to 24 parts beating his own 27.

I made a faster 38 part Police to beat Steve496's same sized record. Being almost a third faster and I assume a different algorithm, it seems pure luck to hit the exact same size. The new one is almost a match for jareds's 67 part speed record, but isn't easily twerked to break that with more parts.

Immediately hit back by Steve496 – he shows a 35 part Police. Mine is still way faster but that immediately lost its glamour. Steve496 also reduces his Judiciary size record from 51 to 49 parts.

Somehow managed to wrangle my Police down to 35 parts too. I kept the algorithm and lost just a little speed, so it's still faster than Steve's.


2010-06-03

Steve496 went better again in Police, down from 35 to 33 parts.

I got a new smallest in Politicians, one less than Steve496's old 24 part record.

Jareds has a new smallest Judiciary beating Steve496's 49 parts in 45, and Seraphim that at 21 wins over Dernam's old record of 23.

Squeezed a 25 part solution out of Academics, winning EstLladon's 28.


Moved the updated table and scores.txt to the new page. Edit history continues there.
Last edited by Nix on Sun Jun 06, 2010 11:02 am UTC, edited 38 times in total.

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

Re: Manufactoria / record solutions

Postby jaap » Sun May 30, 2010 5:42 pm UTC

Nix wrote:Here are the smallest and fastest solutions for each level.

The only one that I can beat in size is Academics, with 29 parts:
Spoiler:
?lvl=23&code=y12:2f3;g12:3f3;c12:6f3;c12:7f3;c12:8f3;b11:11f2;p12:11f3;q12:12f0;r13:11f0;q12:10f2;c12:9f3;c13:3f0;b13:4f2;c13:5f2;q14:3f1;p14:4f5;c14:5f1;y15:3f3;r15:4f0;p12:5f3;y9:3f3;b9:4f2;q10:3f5;p10:4f5;c10:5f1;c11:3f2;r11:4f0;c11:5f0;c12:4f3;

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Tirian » Tue Jun 01, 2010 1:01 am UTC

Good grief, that sucked up my long weekend quite effectively, and I have yet to settle on a design for Ophanim. Are you all cheating by assuming that the input length isn't too long? I'm a little worried over how much of the factory floor is going to get eaten up by an honest non-destructive length comparer.

Now someone needs to do for brainfuck what this game did for FSM's.

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby WarDaft » Tue Jun 01, 2010 1:47 am UTC

That actually sounds like an interesting idea. No promises, but I'll give it a shot.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

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

Re: Manufactoria / record solutions

Postby Xanthir » Tue Jun 01, 2010 4:09 am UTC

jaap wrote:
Nix wrote:Here are the smallest and fastest solutions for each level.

The only one that I can beat in size is Academics, with 29 parts:
Spoiler:
?lvl=23&code=y12:2f3;g12:3f3;c12:6f3;c12:7f3;c12:8f3;b11:11f2;p12:11f3;q12:12f0;r13:11f0;q12:10f2;c12:9f3;c13:3f0;b13:4f2;c13:5f2;q14:3f1;p14:4f5;c14:5f1;y15:3f3;r15:4f0;p12:5f3;y9:3f3;b9:4f2;q10:3f5;p10:4f5;c10:5f1;c11:3f2;r11:4f0;c11:5f0;c12:4f3;

Dammit, the *one* level where I feel I could have a legitimate chance of posting a new record. I load up your solution, and it's piece-for-piece identical with mine. I didn't even think I'd loaded anything for a sec.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Steve496 » Tue Jun 01, 2010 4:29 am UTC

Tirian wrote:Good grief, that sucked up my long weekend quite effectively, and I have yet to settle on a design for Ophanim. Are you all cheating by assuming that the input length isn't too long? I'm a little worried over how much of the factory floor is going to get eaten up by an honest non-destructive length comparer.


So structure it so you can use a destructive length comparer. That's how I did it.

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby phlip » Tue Jun 01, 2010 4:55 am UTC

Steve496 wrote:So structure it so you can use a destructive length comparer. That's how I did it.

Oh? Oh! So that's how you do it... why didn't I think of that straight away?

A hint:
Spoiler:
You want to be able to compare the two strings for length. And then, when you're done, you want to be able to compare the two strings bitwise, the first bit of one with the first bit of the other, and so on. If you're familiar with functional languages and list manipulation, you'll know there's a simple manipulation that'll let you easily compare both of these...
Spoiler:
It's called zip - interlace your two inputs, and you'll be able to easily tell if one runs out first, and then you'll be able to easily read, say, the first bit of each number (it'll be the first two bits on the tape).

Code: Select all

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

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Steve496 » Tue Jun 01, 2010 5:36 am UTC

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.

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby WarDaft » Tue Jun 01, 2010 7:25 am UTC

Oh well that's not annoying at all.

So, I finished a preliminary version of the game mentioned 5-6 posts back. Here it is: http://www.webstrong.ca/dev/Iteratus/
Then Flash randomly decided to destroy the source file.. so it might be a while before I develop it any further. Hopefully there are no bugs. There is no goal, it just starts you off with an initial value between 10000 and 20000 (the first goal was going to be determining if it was prime) which it can erase in a few minutes to give you a blank slate. It should be computationally functional otherwise, and the grid has no preset bounds. Select a square to place a part. The Teleport option is actually somewhat more powerful than the [ and ] operators, but you can pretend it's not.

Also, when placing pieces, some of the icons are wrong, but the text labels are correct. Positive Y is down, positive X is right.






If it had taken more than a couple hours I would be really quite frustrated right now.
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 / Checker and score keeper program

Postby Nix » Tue Jun 01, 2010 3:02 pm UTC

A new version of the checker/score keeper is attached to this post.

Important changes:
  • Verifies solutions with a constant set of random longer inputs (with relaxed time limit and tape capacity), but doesn't count the results toward speed. Can be disabled.
  • More information when making an entry: if a new record was for speed and/or size or an intermediate, or if the entry matches an old record in one stat or both.
  • More readable score output that by default only includes the smallest and the fastest solution, just like in the score list in my post.
  • Option to verify the contents of the score file.

Checking of longer inputs might not be that useful since you wouldn't normally have a solution that works with up to 10 input markers, but by accident doesn't on more. However, it does catch deliberate false solutions like this:

Steve496 wrote:Technically not a solution to Robochildren, but passes both your test program and the game's tests:

?lvl=18&code=c12:6f3;c12:7f3;c12:8f3;c12:9f3;c12:10f3;c12:11f3;c12:4f3;c12:5f3;p9:3f3;p10:3f3;p11:3f3;p12:3f3;p13:3f3;p14:3f3;p15:3f3;p8:3f3;p7:3f3;p16:3f3;p17:3f3;


The above is now detected as failing: Robo-children! (18) Rejected when should have accepted [BBBBBBRRRRRR]

Apparently testing enough of longer inputs, albeit chosen at random, will catch at least this simple kind of thing without level specific twerking of the tests. That the first catching input happens to be the simplest possible one here is entirely down to luck; I'm only running 100 inputs per length. Of course in some levels a solution could fail only if a long input is e.g. all blues, and won't be caught, but this is a good start. I'm now using input lengths up to 60 limited by using 64-bit integers in checking the binary levels. If it served a purpose, of course I could use an arbitrary precision library or code a bitwise solution myself. Heck, I've already done it in Manufactoria!

Edit: next version here (always find the newest one through the first link)
Last edited by Nix on Tue Jun 15, 2010 3:06 pm UTC, edited 1 time in total.

EstLladon
Beat you to the park. From RUSSIA.
Posts: 483
Joined: Tue Oct 17, 2006 10:23 am UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby EstLladon » Wed Jun 02, 2010 10:36 am UTC

I think it is new record! Academics in 28 parts:

Spoiler:
?lvl=23&code=c13:13f0;g12:2f3;c13:5f3;c13:6f3;c13:7f3;c13:8f3;c13:9f3;c13:10f3;c13:11f3;c13:12f3;r9:2f2;g9:3f1;g9:5f3;b9:6f2;p10:2f7;q10:3f1;p10:4f4;q10:5f7;p10:6f5;b11:2f0;c11:3f2;i11:4f0;c11:5f1;r11:6f0;q12:3f3;y12:4f0;c13:3f3;c13:4f3;
From Russia with math.

andy11235
Posts: 38
Joined: Thu Oct 16, 2008 6:21 am UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby andy11235 » Wed Jun 02, 2010 11:16 am UTC

You know what would make this game harder? Playing the official version on Kongragate that doesn't allow bridges. That's a bug, not intentional. It's still possible to have them by loading saved games, I think.

I then made the game even harder by not realising I could flip the direction of a gate, preventing me from doing mirrored paths. It gave me all sorts of trouble, but I got up to the last level (and I'm trying to work out if it's going to be possible without bridges).

This level is an example of how this made things difficult. Rocket planes is easy enough, but I would usually get blocked from the exit when I don't have any reds and end up stuck in the middle. Instead of using a bridge (which would be awesome), I hack my way through with a yellow and refactor the solution a little to make it more efficient (but still bubble sort ish).

?lvl=27&code=g12:5f3;c12:4f3;p12:6f3;p13:6f2;r13:5f3;b13:7f3;r13:8f3;c10:8f1;c10:7f1;c10:6f1;b11:6f2;c14:11f0;c13:11f0;y12:7f3;c10:11f2;c11:11f2;q14:6f0;r14:7f3;c14:8f3;c14:9f3;c14:10f3;c12:9f0;c13:9f0;q12:8f0;p11:9f0;q10:9f2;c10:10f3;c10:5f2;c11:5f2;r11:10f1;b11:8f3;

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby phlip » Wed Jun 02, 2010 12:07 pm UTC

andy11235 wrote:Playing the official version on Kongragate that doesn't allow bridges.

Works fine for me... :-/

Maybe something's wrong with your shift key?

Code: Select all

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

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Nix » Wed Jun 02, 2010 12:39 pm UTC

andy11235 wrote:Playing the official version on Kongragate that doesn't allow bridges.

I have a problem with bridges in it sometimes too. It's somehow related to the alt key, and can be fixed by alt-clicking as if to place the bridge with alt instead of shift, at least that's how I do it. Then shift-clicking starts to work again.

andy11235
Posts: 38
Joined: Thu Oct 16, 2008 6:21 am UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby andy11235 » Wed Jun 02, 2010 12:41 pm UTC

phlip wrote:
andy11235 wrote:Playing the official version on Kongragate that doesn't allow bridges.

Works fine for me... :-/

Maybe something's wrong with your shift key?


Ah, right. My shift must have been sticking, because it works on this computer.
Got to get my keyboard checked...

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby phlip » Wed Jun 02, 2010 1:09 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.

Hmm, you're right, it was hard to get it to fit... this is what I ended up with, without optimisation:
Spoiler:
?lvl=30&code=c8:13f2;c9:13f2;c10:13f2;c11:13f2;c16:13f0;c15:13f0;c14:13f0;c13:13f0;q6:4f5;c6:5f1;c6:6f1;c6:7f1;c6:8f1;c6:9f1;c6:10f1;c6:11f1;c7:4f2;b7:7f0;c8:4f2;b8:6f3;p8:7f0;r8:8f1;i8:11f1;c9:4f2;q9:6f0;g9:7f0;c9:8f3;c9:9f0;r9:11f0;c10:4f2;b10:5f3;p10:6f0;r10:7f1;c10:8f0;b10:9f2;b10:10f3;p10:11f0;r10:12f1;c11:4f3;c11:5f2;c11:6f0;c11:7f1;p11:8f0;p11:9f3;q11:10f6;g11:11f0;c12:8f0;r12:9f0;c8:9f3;c8:10f3;c8:12f3;c7:11f0;g12:2f2;p13:2f2;c13:1f3;b13:3f2;c14:3f1;c14:2f2;p15:2f2;b15:3f1;r15:1f3;c13:6f2;g13:8f0;c14:6f2;q14:8f7;c15:6f2;b15:7f3;p15:8f0;r15:9f1;r16:5f2;p16:6f2;b16:7f2;c16:8f0;p16:10f0;p16:11f4;p16:12f0;c17:5f2;c17:6f3;i17:7f5;i17:8f1;q17:9f3;c17:11f0;c18:5f3;c18:6f3;c18:7f3;g18:8f0;c18:9f3;p18:10f3;q18:11f7;c12:5f3;c12:6f2;q16:2f5;g17:2f3;c17:3f0;c16:3f3;c16:4f0;c15:4f0;c14:4f0;c13:4f0;c12:4f1;c12:3f0;c11:3f1;c11:2f0;p10:2f4;c10:1f3;b10:3f0;c9:3f1;c9:2f0;p8:2f4;b8:3f1;r8:1f3;q7:2f1;g6:2f3;c6:3f2;c7:3f3;

Now I've just got Judiciary and Metatron left...

Code: Select all

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

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Xanthir » Wed Jun 02, 2010 1:44 pm UTC

Shit, I'd come up with a *significant* optimization for Robotanks, only to open up the level and discover that it doesn't allow yellow/green. Dammit.

(The optimization was to swap the reds for yellows after finding the first blue. That would allow a *significantly* more compact testing for each digit - 4 parts per digit with no transportation costs, versus the standard 6 parts + possible transport. Depending on the string, the reduction in travel time during the digit testing could even make up for the extra time spent translating the colors.)
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Berengal » Wed Jun 02, 2010 3:30 pm UTC

Why does the color matter in Robotanks after finding the first blue?
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Nix » Wed Jun 02, 2010 3:36 pm UTC

Xanthir wrote:Shit, I'd come up with a *significant* optimization for Robotanks, only to open up the level and discover that it doesn't allow yellow/green. Dammit.

(The optimization was to swap the reds for yellows after finding the first blue. That would allow a *significantly* more compact testing for each digit - 4 parts per digit with no transportation costs, versus the standard 6 parts + possible transport. Depending on the string, the reduction in travel time during the digit testing could even make up for the extra time spent translating the colors.)

It doesn't have any writers. Even with only red and blue you could replace blues with reds in each counting step, and I have it down in 17 parts. With yellow, even better 11 parts.

Hacked codes that the game accepts but my program doesn't (made in same-sized Robo-children and changed lvl=18 to 15):

Without yellow: ?lvl=15&code=c12:3f3;p12:4f2;c12:5f0;p11:5f0;r11:4f3;p11:6f3;r10:6f2;c12:6f2;p13:6f6;r13:5f3;p13:7f7;r14:7f0;c12:7f3;c12:8f3;c12:9f3;c12:10f3;c12:11f3;
With yellow: ?lvl=15&code=r11:6f2;c12:3f3;p12:4f2;y12:5f3;p12:6f3;q12:7f2;p12:8f6;p12:9f6;p12:10f6;p12:11f6;r13:6f0;

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Tirian » Wed Jun 02, 2010 3:40 pm UTC

phlip wrote:Now I've just got Judiciary and Metatron left...


Huh. I won't say that Judiciary is as easy as Generals, but there are problems that took hours to solve and problems that took moments, and Judiciary is one of the latter.

Dr. Willpower
Posts: 197
Joined: Wed May 28, 2008 3:55 pm UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Dr. Willpower » Wed Jun 02, 2010 6:18 pm UTC

Robolamps:
Spoiler:
?lvl=3&code=c12:9f3;p12:6f2;p12:7f2;p12:8f2;c12:5f3;


I am pretty sure this always sometimes works. 5 parts.

Also,
Robobears:
Spoiler:
?lvl=7&code=c12:5f3;c12:6f3;c12:9f3;c12:10f3;c12:4f3;c14:11f1;c11:9f2;c10:11f1;c13:9f0;p10:9f6;p10:10f6;p14:9f4;p14:10f4;c10:8f3;c11:8f0;p12:8f3;c13:8f2;c14:8f3;c12:7f3;


Unless I am mistaken and someone has already bested me.
EDIT: I am very mistaken.
Last edited by Dr. Willpower on Wed Jun 02, 2010 8:10 pm UTC, edited 2 times in total.
Image
Hat me, bro

JavaBean
Posts: 6
Joined: Fri Dec 15, 2006 9:13 am UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby JavaBean » Wed Jun 02, 2010 6:50 pm UTC

That works only if the three blues are all in a row; your solution rejects [BBRB]. If it were as simple as your 5-part solution, you wouldn't be the first to notice.

thebluemachine
Posts: 2
Joined: Wed Jun 02, 2010 6:48 pm UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby thebluemachine » Wed Jun 02, 2010 6:54 pm UTC

Hello all, sorry if I am posting wrongly, this is my first time.

I think I found a 15-part solution to Robo-Children. It passes all the tests, but I know that's sometimes not enough for a full solution. Give it a try and let me know.

Spoiler:
?lvl=18&code=g12:3f3;p12:5f3;p11:5f4;c11:4f2;c12:4f3;p13:5f6;r13:6f1;b11:6f1;c13:4f0;c12:6f3;c12:8f3;c12:9f3;c12:10f3;c12:11f3;q12:7f6;

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby jaap » Wed Jun 02, 2010 7:36 pm UTC

thebluemachine wrote:I think I found a 15-part solution to Robo-Children.

It accepts blue-blue-red, which it should reject.
Note that there is no green writer/reader in the main part of the program, so it can only ever go once through the dots on the tape till it hits the green end marker. The blues or reds you skip over in your first pass are never read again and are still on the tape when it is accepted/rejected.

Dr. Willpower
Posts: 197
Joined: Wed May 28, 2008 3:55 pm UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Dr. Willpower » Wed Jun 02, 2010 8:09 pm UTC

JavaBean wrote:That works only if the three blues are all in a row; your solution rejects [BBRB]. If it were as simple as your 5-part solution, you wouldn't be the first to notice.


Well, I thought it was peculiar when it worked. But thinking about it on the ride home I realized that the tests probably weren't that thorough. Then I realized BBRB would fail.
Image
Hat me, bro

thebluemachine
Posts: 2
Joined: Wed Jun 02, 2010 6:48 pm UTC

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby thebluemachine » Wed Jun 02, 2010 10:56 pm UTC

jaap wrote:
thebluemachine wrote:I think I found a 15-part solution to Robo-Children.

It accepts blue-blue-red, which it should reject.
Note that there is no green writer/reader in the main part of the program, so it can only ever go once through the dots on the tape till it hits the green end marker. The blues or reds you skip over in your first pass are never read again and are still on the tape when it is accepted/rejected.

Thanks Jaap. I figured I had made a mistake somewhere as everyone else on this forum seems a lot smarter than I am! I must have just got lucky with the particular set of random tests that the game gave me.

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby phlip » Wed Jun 02, 2010 10:59 pm UTC

OK, next challenge: get Linux running on this thing.

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 » Thu Jun 03, 2010 1:15 am UTC

WarDaft wrote:Oh well that's not annoying at all.

So, I finished a preliminary version of the game mentioned 5-6 posts back. Here it is: http://www.webstrong.ca/dev/Iteratus/


That's cute. Honestly, though, I was thinking more about mimicking the judging and ratcheting problem difficulty aspects of Manufactoria more than the 2-D GUI. Still, rock on.

User avatar
Dason
Posts: 1310
Joined: Wed Dec 02, 2009 7:06 am UTC
Location: ~/

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Dason » Thu Jun 03, 2010 1:28 am UTC

phlip wrote:OK, next challenge: get Linux running on this thing.

There's probably an emacs command to do that for you
double epsilon = -.0000001;

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

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby WarDaft » Thu Jun 03, 2010 2:50 am UTC

Tirian wrote:
WarDaft wrote:Oh well that's not annoying at all.

So, I finished a preliminary version of the game mentioned 5-6 posts back. Here it is: http://www.webstrong.ca/dev/Iteratus/


That's cute. Honestly, though, I was thinking more about mimicking the judging and ratcheting problem difficulty aspects of Manufactoria more than the 2-D GUI. Still, rock on.
Well yeah, that's just how far I got before the source file self destructed =/
When I get another bunch of free time I'll re-build it and go from there.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

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 » Thu Jun 03, 2010 11:02 pm UTC

Might I make a suggestion for the programmer of this game? The five offered test cases are few enough that bad machines are frequently accepted. Now, although these test cases frequently take an amount of time measured in minutes to complete, our computers could easily process dozens of test cases in immeasurable time by not displaying them. That is why I propose that the computer randomly generate a large number of or even (for some problems) every one of the possible test cases, and test all of them silently. If one of these test cases fails, then use that for the second "random" test. I think that would be rather simple and could improve the tests vastly.
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
TheChewanater
Posts: 1279
Joined: Sat Aug 08, 2009 5:24 am UTC
Location: lol why am I still wearing a Santa suit?

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby TheChewanater » Thu Jun 03, 2010 11:56 pm UTC

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.
ImageImage
http://internetometer.com/give/4279
No one can agree how to count how many types of people there are. You could ask two people and get 10 different answers.

User avatar
phlip
Restorer of Worlds
Posts: 7557
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:07 am UTC

That's a good idea, actually. You wouldn't want it just churning through a bunch when it's about to run the random test, ActionScript is pretty horrendously slow. But it could try doing them in the background, say one every second or something, while the previous test cases are being run the traditional way. Which also has the advantage that more complex puzzles that take longer to run will have more time to churn through the state space looking for errors. You'd need some way to detect infinite loops though... after all, there's three ways the machine can handle a robot... it can accept it, reject it, or never stop looping. I guess some kind of maximum step count would do, and then if you don't find an input where the machine breaks, you can feed it one where it hit the timeout, on the offchance that it is, in fact, an infinite loop.

I know the creator of the game has posted here, but I don't know if they're still reading the thread... you'd probably have better luck if you went to their site and suggested it there. There was an official feedback link in their post last page.

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.

Code: Select all

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

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: Manufactoria - Make Turing Machines with Conveyor Belts

Postby Token » Fri Jun 04, 2010 12:35 am UTC

phlip wrote:but if it turns out the arbitrarily-large-grid-and-infinite-tape variant is Turing complete, then it would apply to that.

Is there some reason you think it wouldn't be Turing complete? It seems obvious to me that it is, but I could be missing something.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 6 guests