wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> Manufactoria
        
(Message started by: rmsgrey on May 30th, 2010, 7:19am)
Title: Manufactoria
Post by rmsgrey on May 30th, 2010, 7:19am
Came across this flash game recently. Anyone with much of a computer science background should recognise the underlying concepts.

http://pleasingfungus.com

Enjoy :)
Title: Re: Manufactoria
Post by Obob on May 30th, 2010, 1:23pm
Quite a fun little game!  Reminds me a bit of the automata theory class I took back in college.
Title: Re: Manufactoria
Post by Noke Lieu on May 30th, 2010, 10:14pm
It's gorgeous! well found!
Title: Re: Manufactoria
Post by towr on May 31st, 2010, 4:41am
Two more to go.. There's some really hard ones in there. I had hardly enough room for the A>B one. Or maybe I'm just not good at finding decent solutions  :P

[edit]Oh good grief, now they want me to add two numbers...[/edit]
Title: Re: Manufactoria
Post by rmsgrey on May 31st, 2010, 5:13am
A>B is the one that gives me most trouble - having solved it once, I started trying to improve my solution and ended up with something messy enough that I cleared it and then decided not to start over, making it the only level for which I don't have a solution stored.

For A+B, I have a non-optimal, but pleasingly (almost) symmetric, solution.
Title: Re: Manufactoria
Post by Noke Lieu on May 31st, 2010, 7:05pm
I love the moments where you've been trying stubbornly one path.. and then *thok* you realise how stupid you were being and that one gate in the right place replaces tonnes of stuff...
Title: Re: Manufactoria
Post by SMQ on Jun 2nd, 2010, 6:52am
It seems my adder is over-engineered: none of the tests involve [hide]strings of different lengths[/hide] or [hide]trimming leading zeros[/hide]. ;D

And for A > B I used [hide]B - A, ignore the result, accept on overflow[/hide].

--SMQ
Title: Re: Manufactoria
Post by towr on Jun 2nd, 2010, 7:03am
For A>B, [hide]I removed leading reds, then removed common prefix from A and B, and checked whether what remained of A was longer, or of equal length but starting with blue.[/hide]


You can also make your own levels, for example I made this one (http://pleasingfungus.com/?lvl=37&ctm=Level_Name!;output_is_input_twice_repeated;b:bb|bbrr:bbrrbbrr|:|brbrrbrrrb:brbrrbrrrbbrbrrbrrrb|rbrbrbbbbbbbbbbrbrbr:rbrbrbbbbbbbbbbrbrbrrbrbrbbbbbbbbbbrbrbr;13;3;0;). (My solution has 49 parts and takes 18:58.)
Title: Re: Manufactoria
Post by rmsgrey on Jun 2nd, 2010, 8:25am

on 06/02/10 at 06:52:06, SMQ wrote:
It seems my adder is over-engineered: none of the tests involve [hide]strings of different lengths[/hide] or [hide]trimming leading zeros[/hide]. ;D

And for A > B I used [hide]B - A, ignore the result, accept on overflow[/hide].

--SMQ

My adder handles both cases automatically.

Your A>B sounds like it might work better than mine, which followed much the same approach as towr, with a little bit of input validation thrown in:

[hide]Mark end of tape yellow, strip leading reds from A, copy rest of A, copy single green, strip leading reds from B, copy rest of B, copy single yellow (rejecting anything that doesn't match the pattern to that point). Then repeat: read first of A (if null, reject), then on each branch copy rest of A, copy separator, read first of B (if null, accept), if it matches the remembered first of A, copy the rest of B and the separator and loop. Otherwise, if A was blue, copy rest of B, copy separator, and feed to final stage; if A was red, copy rest of B, and separator, then strip the first of A then feed into final stage. In the final stage, repeat: copy rest of A; strip one from B and copy rest; strip one from A. If A runs out first, reject; if B runs out first, accept (tests for running out take place when copying the separators - hence having them different colours)[/hide]

The whole thing just barely fits on the level...
Title: Re: Manufactoria
Post by SMQ on Jun 2nd, 2010, 8:44am

on 06/02/10 at 07:03:44, towr wrote:
(My solution has 49 parts and takes 18:58.)

Trading a little time for lower component count, I have 37 parts in 19:33.  I'll post my variation in a little while.

Edit: a variation (http://pleasingfungus.com/?ctm=Copiers!;given_a_number_A_(not_0)_and_a_pattern_P_OUTPUT________P_repeated___A_times;bgb:b|brgbbrr:bbrrbbrr|brbgrbr:rbrrbrrbrrbrrbr|brbbbgb:bbbbbbbbbbbbbbbbbbbbbbb;13;3;0;) on towr's theme; my solution has 59 parts and takes 7:47.

Edit 2: updated Copiers! (http://pleasingfungus.com/?ctm=Copiers!;given_a_number_A_and_a_pattern_P_OUTPUT________P_repeated___A_times;bgb:b|bbgrbbr:rbbrrbbrrbbr|bbrg:|rgbbrrbrrb:|rrrg:|brbbbgr:rrrrrrrrrrrrrrrrrrrrrrr;13;3;0;) to allow and test A = 0.  My "reference" solution is now 68 parts and takes 8:08 on the new tests.

--SMQ
Title: Re: Manufactoria
Post by towr on Jun 2nd, 2010, 10:28am
Another one, calculate the remainder modulo 3 (http://pleasingfungus.com/?lvl=34&ctm=mod_three!;given_an_integer_calculate_the_remainder_modulo_3;r:r|b:b|br:br|brbbb:br|bbrbbb:b|brbrrrb:r|bbbbrbrr:b;7;3;1;)
(19 parts,  1:00)
Title: Re: Manufactoria
Post by malchar on Jun 2nd, 2010, 10:40am
Great find. A few tips that weren't obvious to me at first: You can make conveyor bridges by holding shift while placing a conveyor on top of another conveyor, and you can have robots enter switches from any side.
Title: Re: Manufactoria
Post by 14620561 on Jun 2nd, 2010, 6:50pm
very nice post.
i ahve accepted you post informations.
Title: Re: Manufactoria
Post by towr on Jun 3rd, 2010, 2:13am

on 06/02/10 at 08:44:19, SMQ wrote:
Edit 2: updated Copiers! (http://pleasingfungus.com/?ctm=Copiers!;given_a_number_A_and_a_pattern_P_OUTPUT________P_repeated___A_times;bgb:b|bbgrbbr:rbbrrbbrrbbr|bbrg:|rgbbrrbrrb:|rrrg:|brbbbgr:rrrrrrrrrrrrrrrrrrrrrrr;13;3;0;) to allow and test A = 0.  My "reference" solution is now 68 parts and takes 8:08 on the new tests.
I got 7:41 with 81 parts.
I don't seem to be very good with part-efficiency.
Title: Re: Manufactoria
Post by rmsgrey on Jun 3rd, 2010, 5:04am

on 06/02/10 at 10:40:08, malchar wrote:
Great find. A few tips that weren't obvious to me at first: You can make conveyor bridges by holding shift while placing a conveyor on top of another conveyor, and you can have robots enter switches from any side.


The other one that I didn't figure out at first is that you can reflect switches by hitting space, which can often be a space saver
Title: Re: Manufactoria
Post by SMQ on Jun 3rd, 2010, 7:16am

on 06/02/10 at 10:28:59, towr wrote:
Another one, calculate the remainder modulo 3 (http://pleasingfungus.com/?lvl=34&ctm=mod_three!;given_an_integer_calculate_the_remainder_modulo_3;r:r|b:b|br:br|brbbb:br|bbrbbb:b|brbrrrb:r|bbbbrbrr:b;7;3;1;)
(19 parts,  1:00)

12 parts, 0:45. ;)

--SMQ
Title: Re: Manufactoria
Post by towr on Jun 3rd, 2010, 7:43am

on 06/03/10 at 07:16:08, SMQ wrote:
12 parts, 0:45. ;)
Nice, I found it too now :) (At least I assume there aren't two 0:45 12 part solutions, aside from mirroring, or shifting it down a bit)
Title: Re: Manufactoria
Post by rmsgrey on Jun 7th, 2010, 7:38am

on 06/02/10 at 07:03:44, towr wrote:
You can also make your own levels, for example I made this one (http://pleasingfungus.com/?lvl=37&ctm=Level_Name!;output_is_input_twice_repeated;b:bb|bbrr:bbrrbbrr|:|brbrrbrrrb:brbrrbrrrbbrbrrbrrrb|rbrbrbbbbbbbbbbrbrbr:rbrbrbbbbbbbbbbrbrbrrbrbrbbbbbbbbbbrbrbr;13;3;0;). (My solution has 49 parts and takes 18:58.)

47/19:52

(and I've also found the 12/0:45 mod 3 solution. Very nice :))
Title: Re: Manufactoria
Post by towr on Jun 7th, 2010, 7:57am
I wish I could make a multiplier, but it seems to take so much space.. I did find out you can make the field 15x15 or even 17x17, though (although you can't see the outer ring then; but you can still build on it with a bit of effort).
Title: Re: Manufactoria
Post by TenaliRaman on Jun 7th, 2010, 9:20am
I am not sure I understand, how the site is computing time (IMO, it seems to make no sense to optimize for time :-/). On the other hand, making the whole thing more compact seems to have more benefit.

-- AI
Title: Re: Manufactoria
Post by towr on Jun 7th, 2010, 9:56am
The time is probably a measure of the number of steps taken. Like one second per step, or something.

[edit]It seems to be about 0.54 seconds per step.[/edit]
Title: Re: Manufactoria
Post by towr on Jun 10th, 2010, 5:46am
A similar sort of game, but without the underlying similarity to Turing machines: http://www.zachtronicsindustries.com/alchemy/alchemy.htm
Title: Re: Manufactoria
Post by Grimbal on Jun 12th, 2010, 10:51am
I just finished my adder.

After a few attempts that failed due to lack of space, I used a radically new approach.
Now my adder fits easily on the board.  Squeezing it a bit, I use only half of the space.  And I don't even touch the borders.  :o

53 parts.  It is just a bit slow.

http://florian.net/puzzle/pic/adder.png

PS: with the same approach I could probably do multiplication or exponentiation...
Title: Re: Manufactoria
Post by towr on Jun 12th, 2010, 2:45pm
How does it work?
Title: Re: Manufactoria
Post by Grimbal on Jun 13th, 2010, 6:16am
The actual addition takes 3 parts.

The rest is [hide]Converting the numbers to unary and the result back to binary.[/hide]

A bit more readable version here (http://pleasingfungus.com/?lvl=31&code=g8:6f2;c9:5f3;p9:6f2;q11:6f4;c10:6f2;c10:5f0;g11:5f0;b8:7f1;c8:8f0;q9:7f7;p9:8f1;b10:8f0;c7:11f2;b7:12f1;c8:10f2;p8:11f2;p8:12f5;g8:13f1;r9:10f2;r9:12f2;c9:13f0;r10:10f3;p10:11f2;b10:12f1;c10:13f0;r11:10f3;q11:11f0;c11:12f3;p11:13f5;r6:2f3;p6:3f2;b6:4f1;c6:5f1;b6:6f1;c6:7f1;r6:8f1;c7:8f0;g7:2f3;q7:3f4;c7:4f2;c8:4f2;g9:1f3;q9:2f2;r10:1f3;p10:2f4;r10:3f2;c11:2f0;b11:3f1;y12:2f0;y9:4f3;c9:3f3;c12:10f0;c11:7f2;c12:7f2;c14:7f3;p14:8f7;c14:9f3;c14:10f0;b15:8f0;c13:7f2;c13:10f0;c13:13f0;b10:7f2;)
Title: Re: Manufactoria
Post by towr on Jun 13th, 2010, 6:42am
Interesting. The best previous I know of (but not mine) had 72 parts. But, [hide]your solution wouldn't work for additions summing to over 50, because the tape is limited.[/hide]
Title: Re: Manufactoria
Post by Obob on Jun 13th, 2010, 7:20am
What happens when the tape overflows?
Title: Re: Manufactoria
Post by towr on Jun 13th, 2010, 7:30am
It simply overwrites the 50th spot again and again until you remove things from the front and everything shifts forward again.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board