18
\$\begingroup\$

Write a Manufactoria program that will accept the empty input tape. But don't do it quickly! I mean, write the program quickly, but don't let it run quickly. The slower the program, the better, as long as it terminates eventually. The example program below takes 3:51 (the "total time" reported by the simulator).

enter image description here

http://pleasingfungus.com/Manufactoria/?lvl=36&code=g12:5f3;r9:8f1;p12:9f3;c13:9f0;r11:9f0;r10:9f0;r9:9f1;b11:8f0;b10:8f1;r9:7f2;c10:7f2;c11:7f2;c12:7f3;q12:8f3;y13:8f2;y14:8f2;y15:8f1;y15:7f0;y14:7f0;y13:7f0;g12:6f3;&ctm=Slow_Accepter!;Generate_the_slowest_possible_accepting_machine;:;7;3;0;

Your program starts with the empty tape. It must doodle around a bit, but eventually reach the output square. You may leave data on the tape if you wish. The slowest program on the 7x7 Manufactoria board wins!

Your right arrow key is your friend, it speeds up the simulator.

Bonus points for crashing the simulator!

\$\endgroup\$
  • \$\begingroup\$ So there's no requirements for accepting/rejecting input other than the empty tape? \$\endgroup\$ – Volatility Jul 12 '13 at 5:34
  • \$\begingroup\$ @Volatility: correct. \$\endgroup\$ – Keith Randall Jul 12 '13 at 5:39
  • \$\begingroup\$ Annoyingly, the simulator won't report the running time unless the tape is empty at the end, since it doesn't match the challenge's expected output. (Luckily it was easy for me to erase the tape at the end without needing too much extra space.) \$\endgroup\$ – breadbox Jul 15 '13 at 13:05
22
\$\begingroup\$

~1023 iterations ~1015 iterations ~108 iterations

Manufactoria setup

http://pleasingfungus.com/Manufactoria/?lvl=32&code=g9:7f2;b12:8f2;p13:8f5;p11:8f3;r14:8f0;q11:10f3;q13:7f1;y13:9f1;r10:10f1;c12:9f2;c9:9f2;i11:9f7;i10:9f4;c9:8f3;i10:8f2;c14:9f0;c15:9f0;c15:8f3;c15:7f3;c14:7f2;g12:7f0;c11:7f3;c10:7f2;q9:6f7;r10:6f1;r9:5f3;c11:6f0;r10:5f2;r11:5f1;r9:4f3;r10:4f0;r11:4f0;y12:5f2;y13:5f2;y14:5f3;y14:6f0;y13:6f0;y12:6f0;&ctm=Slow_Accepter!;Generate_the_slowest_possible_accepting_machine;:;7;3;0;

The machine is basically an odometer running in base three, using the red, blue and yellow symbols to stand for the digits 0, 1, and 2 respectively. The green symbol is used to mark the end of the number. At the start, the tape is initialized with 49 red symbols. This is done by the parts in the top three rows of the machine. The bottom four rows handle the task of incrementing the number in a loop. On each iteration, the two branch cells on left-hand side work out how to apply the increment to current number, and then the branch cells on the right-hand side copy the remaining, unaffected digits.

Previously I've tried to estimate the machine's running time, were it allowed to run to completion, but at this level it makes more sense to just go by the number of iterations. Roughly speaking, it takes about a minute to complete one iteration -- but even if it took a second that would only decrease the running time by a single order of magnitude.

\$\endgroup\$
  • 4
    \$\begingroup\$ Ok, I give up.. \$\endgroup\$ – Volatility Jul 15 '13 at 22:21
  • 2
    \$\begingroup\$ Don't give up! I've no doubt that this is still just scratching the surface. For example, compacting the odometer logic by merely one or two cells would allow an order-of-magnitude increase in running time. \$\endgroup\$ – breadbox Jul 15 '13 at 22:48
  • 1
    \$\begingroup\$ pleasingfungus.com/Manufactoria/…; \$\endgroup\$ – Keith Randall Jul 17 '13 at 0:58
  • 5
    \$\begingroup\$ If it helps, I've often submitted golf answers that were way behind the leader, just because it was a different approach. One of the things I love about this site is that it preserves the diversity of responses. \$\endgroup\$ – breadbox Jul 18 '13 at 2:24
  • 1
    \$\begingroup\$ @SimplyBeautifulArt One could conceivably improve by having pairs of symbols be the digits (in which case you could use 15 out of 16 rather than 3 out of 4). Of course, you would run into a lot of difficulty with the small board size in trying to implement that. \$\endgroup\$ – feersum Oct 23 '17 at 3:52
8
\$\begingroup\$

603:25

Online test

I was re-reading through the Manufactoria questions today, and suddenly had an idea which would dramatically slow down the process: instead of just having 50 values and changing colours 3 times, the new program does that, but then after that, it decrements the number of values by 1, and goes through the colour-changing again, until there is an empty tape at which time the program stops.

The queue won't store any more than 50 values at one time, so there's no use trying to push too many values onto the tape - they just get pushed off straight away. As before, the conveyor belts aim to maximise the time taken for the thing to run. In fact, there was minimal tweaking down to achieve a tremendous increase in run-time.

Still nowhere near breadbox's answer though.

\$\endgroup\$
  • \$\begingroup\$ Interesting how similar our solutions are. We both started with a 9x6 multiplier, and we put the branch and x6 group in the same place! Yours is more elegant though - you used every cell and finished with a clean tape. \$\endgroup\$ – Igby Largeman Jul 14 '13 at 23:15
5
\$\begingroup\$

33:33

Worked on this for quite a while (Volatility set the bar pretty high), but once I hit 33:33, I thought it was a neat time to stop at.

The strategy is pretty blunt: basically fill up the tape with one colour, then another, then another, and always try to traverse as many cells as possible between each write (or group of writes).

I'm sure there are ways to be found that we can go a lot further with this.

Busy Beaver

Level link

\$\endgroup\$
  • \$\begingroup\$ +1 I'll see what I can do to beat it ;) (although I'll probably not gonna get too far) \$\endgroup\$ – Volatility Jul 14 '13 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.