12
\$\begingroup\$

A simple Manufactoria challenge. Compute the input modulo 7. The input will be in big-endian binary (blue=1, red=0). The output should be in the same format.

Test cases provided. The smallest part count wins.

http://pleasingfungus.com/Manufactoria/?ctm=Mod7;Input:_binary_number_big_endian._Output:_that_binary_number_mod_7;bbb:|brrr:b|brrrr:br|bb:bb|bbrrb:brr|brrrrb:brb|bbrb:bbr;13;3;1;

(if the input mod 7 is 0, output nothing.)

\$\endgroup\$
  • \$\begingroup\$ "code-golf" in this case means "fewest parts"? \$\endgroup\$ – John Dvorak Jan 21 '14 at 6:02
  • \$\begingroup\$ Since I haven't even solved the incrementation problem, I have no idea how to solve this. Manufactoria is fun. \$\endgroup\$ – Justin Jan 21 '14 at 6:15
  • \$\begingroup\$ @JanDvorak: yes. \$\endgroup\$ – Keith Randall Jan 21 '14 at 7:02
  • \$\begingroup\$ @KeithRandall We never tagged code-golf with manufactoria. We should either remove the tag here or add it to the other questions. \$\endgroup\$ – Howard Jan 21 '14 at 8:26
  • \$\begingroup\$ @Howard: I'd say add it (or fastest-code or busy-beaver or code-challenge or whatever best describes the scoring), and let manufactoria be a simple language tag. \$\endgroup\$ – Ilmari Karonen Jan 28 '14 at 14:15
5
\$\begingroup\$

### Manufactoria, 85 parts placed

The algorithm is quite straightforward: Compute the modulus using a state machine (the largest part with eight branches - one of the states is duplicated for logistical purposes), then encode and collect the results. Since almost every result contains a one digit, an extra compression step is employed to reduce the amount of parts.

Designed in yEd, then transcribed to Manufactoria.

Uses way too many conveyer belts, in my opinion.

\$\endgroup\$
5
\$\begingroup\$

58 43 parts

Screenshot on 43-part mod7 reduce in Manufactoria

http://pleasingfungus.com/Manufactoria/?lvl=33&code=c16:9f0;q15:9f3;q14:9f3;q13:9f3;c12:9f3;c16:10f1;r15:10f3;r14:10f3;b13:10f3;q12:10f4;p11:10f4;c16:11f1;i15:11f7;q14:11f7;q13:11f7;q12:11f7;c11:11f2;r15:12f3;b14:12f3;c12:12f3;c15:13f0;c14:13f0;c13:13f0;r13:12f3;y10:3f3;c10:4f2;g10:5f1;q10:6f4;y11:3f0;q11:4f6;r11:5f3;p11:6f4;b11:7f1;i12:4f7;c12:5f3;q12:6f0;g12:2f3;c12:3f3;p13:4f6;y13:3f0;c13:5f0;c12:7f3;b12:8f3;&ctm=Mod7;Input:_binary_number_big_endian._Output:_that_binary_number_mod_7;bbb:|brrr:b|brrrr:br|bb:bb|bbrrb:brr|brrrrb:brb|bbrb:bbr;13;3;1;

Keith Randall's idea of first converting the input to unary was pretty good, so I stole it. ;-) Conveniently, I'd just spent some time optimizing small binary-to-unary converters in Manufactoria, so just picked one of my almost-working solutions* from that challenge and combined it with a quickly optimized mod-7 counter.

This design is now at the point where just getting the robots from the top to the bottom is starting to require otherwise useless extra conveyors. Any significant further parts reductions will probably come from redesigning the layout to be taller and narrower.

(* That challenge required a) the design to fit onto a 7×7 board, and b) the unary output to be in red markers. If you look at the binary-to-unary converter part of the machine above, you'll note that, with one or two extra parts, it can easily satisfy either requirement, but alas, not both.)


Here's the previous 58-part version:

Screenshot of 58-part mod 7 reducer in Manufactoria, with states labeled

http://pleasingfungus.com/Manufactoria/?lvl=32&code=g12:2f3;q13:13f5;c14:13f0;c15:12f3;c9:6f2;c9:7f1;c9:8f1;c9:9f1;c10:4f3;c10:5f3;i10:6f5;c10:7f2;c10:9f0;b11:3f2;p11:4f1;c11:5f1;p11:6f2;p11:7f2;c11:8f3;p11:9f3;b11:10f2;c12:3f2;c12:4f2;c12:5f0;r12:6f3;c12:7f3;i12:8f1;i12:9f5;y12:10f3;c13:3f2;c13:4f3;i13:5f1;c13:6f3;c13:7f2;i13:8f0;c13:9f1;c14:3f3;c14:4f2;p14:5f5;c14:6f1;p14:7f6;p14:8f7;r14:9f3;c15:4f3;q15:5f0;c15:6f3;c15:7f3;i15:8f6;c15:9f3;q15:10f7;c15:11f3;r12:12f2;p13:12f7;b14:12f0;b14:11f3;b12:11f3;y14:10f3;y15:13f0;&ctm=Mod7;Input:_binary_number_big_endian._Output:_that_binary_number_mod_7;bbb:|brrr:b|brrrr:br|bb:bb|bbrrb:brr|brrrrb:brb|bbrb:bbr;13;3;1;

Like Jan Dvorak's solution, this is also based on a 7-state FSM. I've labeled the gates corresponding to each state in the screenshot to make it easier to read. The state machine itself, however, is really the easy part; the tricky part is generating the final output with a minimal number of gates.

One trick I found useful was the final copy loop that barrel-shifts everything written before the yellow marker to the end (while also stripping off the green marker): this allowed me to make use of the repetition in the high-order output bits by generating the outputs as:

0:  Y   ->
1: BY   ->   B
2:  YBR ->  BR 
3:  YBB ->  BB
4: RYBR -> BRR
5: BYBR -> BRB
6: RYBB -> BBR

This lets me mostly combine the output paths for outputs 2, 4 and 5 (which all begin with BR) and 3 and 6 (which begin with BB).

\$\endgroup\$
  • \$\begingroup\$ I have found no flaw in your design. Good job on saving space. \$\endgroup\$ – John Dvorak Feb 1 '14 at 18:24
  • \$\begingroup\$ Ps. Here's a nice test for state-machine based implementations like this: the number 8890 = BRRRBRBRBBBRBR should give the output 0, visiting every state twice (and state 0 once more at the end) and taking every possible state transition once. \$\endgroup\$ – Ilmari Karonen Feb 1 '14 at 21:43
2
\$\begingroup\$

60 parts

My solution is quite a bit different. It converts binary to unary first, then does the mod 7. I can't quite beat Ilmari.

enter image description here

\$\endgroup\$
0
\$\begingroup\$

I actually had no idea what I'm doing but it works and I might be the winner (if only the test-cases would be proof enough). :D

enter image description here

EDIT: Optimized it 2 times, a bit smaller now.(Removed rubbish)

\$\endgroup\$
  • \$\begingroup\$ Actually I don't know if it'll be working with bigger numbers (or different one than the test cases). \$\endgroup\$ – Leo Pflug Jan 21 '14 at 10:17
  • 1
    \$\begingroup\$ -1 only works for the test cases. If the number starts with 111, it will always be reported as being divisible by 7. This is simply not true. \$\endgroup\$ – John Dvorak Jan 21 '14 at 10:30

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.