Quickly divide in Manufactoria

10

1

Background

Manufactoria has been marketed as a game, but we code-golfers can see it for what it really is: a two-dimensional programming language. The Manufactoria programming language is based around a single queue, which contains a series of colorful markers. The instruction pointer moves around the game board using conveyor belts, and it encounters a series of writers and branches which read from and write to the queue.

The language is very easy to understand, so the quickest way to learn it is to play the first few levels of the game (linked above).

Challenge

Your challenge is to create a program that can divide one number by another number in the least amount of time.

The input to the program will be a string of X blue markers followed by Y red markers. The required output will be a string of red markers with a length of X/Y.

The game board to be used is found in this official contest level:

http://pleasingfungus.com/Manufactoria/?ctm=Divide_and_Conquer;Input_will_be_X_blues_followed_by_Y_reds,_output_X/Y_reds;bbbbbbrr:rrr|bbbrrr:r|bbbbr:rrrr|r:|bbbbbbbbbbbbrrrr:rrr|bbbbbbbbbbbbrrr:rrrr|bbbbbbbbbrrr:rrr|bbbbbbbbbbrr:rrrrr;13;3;0

It is 13x13 (the maximum size) and it is pre-equipped with the correct tests (see the scoring section).

Scoring

The score of your program is the total amount of time that it takes for the program to pass all of the tests in the official contest level. The total time is given on the level-complete screen.

While running the tests, you will most likely have to use the 50x accelerate slider in the bottom left in order to receive the results quickly (time acceleration does not affect the score).

Here is a list of division problems that are involved in the tests:

 6/2 = 3
 3/3 = 1
 4/1 = 4
 0/1 = 0
12/4 = 3
12/3 = 4
 9/3 = 3
10/2 = 5

Example I/O

12/3=4
in:  BBBBBBBBBBBBRRR
out: RRRR

10/2=5
in:  BBBBBBBBBBRR
out: RRRRR

9/3=3
in:  BBBBBBBBBRRR
out: RRR

0/1=0
in:  R
out:

PhiNotPi

Posted 2013-06-11T15:59:19.667

Reputation: 26 739

Cool stuff, that game! Don't really gave time to golf these days but will remember this. – tomsmeding – 2013-06-13T21:02:11.307

Answers

4

Score: 15:51

enter image description here

Does division by repeated subtraction. Uses a Y amongst the R to keep track of how much divisor we've subtracted so far. Uses Gs to count the quotient.

For instance, the state at the start of each outer loop (right after the initial G writer) for 12/4 is:

BBBBBBBBBBBB RRRR G
BBBBBBBB RRRR GG
BBBB RRRR GGG
RRRR GGGG

When there are no Bs left, the gadget at the bottom left strips Rs and then outputs #G-1 Rs.

The inner loop strips one B at a time and uses Y to keep track of position. Starting at the outer loop:

BBBBBBBB RRRR GG
BBBBBBB RYRRR GG
BBBBBB RRYRR GG
BBBBB RRRYR GG
BBBB RRRR GG

The inner loop is the 3x4 box in the lower right. The layout of the rest can probably be improved a bit, but the inner loop is tight.

http://pleasingfungus.com/Manufactoria/?lvl=34&code=c11:13f2;g12:2f3;p12:3f7;c13:3f3;p13:4f3;b12:4f2;r14:4f3;p14:7f7;r13:7f2;q14:8f7;g13:8f2;p14:9f4;r13:10f2;p14:10f7;b15:10f0;q14:11f7;p15:11f3;r16:11f1;p15:8f0;r15:9f1;c16:8f0;c13:2f0;c15:2f0;c16:2f0;c17:2f0;c11:3f3;c11:4f3;c11:6f3;c11:7f3;c11:8f3;c11:9f3;c11:5f3;p11:10f7;q11:11f6;q11:12f7;r10:12f2;c10:10f2;q16:10f5;y14:6f3;q14:5f3;g15:5f1;c15:4f1;c15:3f1;c17:9f1;c17:8f1;c17:7f1;c17:6f1;c17:5f1;c17:4f1;c17:3f1;y16:9f1;g17:10f1;q14:2f4;g14:1f3;&ctm=Divide_and_Conquer;Input_will_be_X_blues_followed_by_Y_reds,_output_X/Y_reds;bbbbbbrr:rrr|bbbrrr:r|bbbbr:rrrr|r:|bbbbbbbbbbbbrrrr:rrr|bbbbbbbbbbbbrrr:rrrr|bbbbbbbbbrrr:rrr|bbbbbbbbbbrr:rrrrr;13;3;0;

Keith Randall

Posted 2013-06-11T15:59:19.667

Reputation: 19 865

By drastically rearranging the parts of your design, I have been able to reduce the score to 13:28 with 53 parts. – PhiNotPi – 2013-06-12T15:30:56.793

Asked: 2013-06-11T15:59:19.667

Viewed: 666 times

Active: 2014-02-01T18:20:34.323