12
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.
(if the input mod 7 is 0, output nothing.)
Keith Randall
Posted 2014-01-21T00:58:36.697
Reputation: 19 865
5
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.
John Dvorak
Posted 2014-01-21T00:58:36.697
Reputation: 9 048
5
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:
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).
Ilmari Karonen
Posted 2014-01-21T00:58:36.697
Reputation: 19 513
I have found no flaw in your design. Good job on saving space. – John Dvorak – 2014-02-01T18:24:34.220
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. – Ilmari Karonen – 2014-02-01T21:43:06.763
2
My solution is quite a bit different. It converts binary to unary first, then does the mod 7. I can't quite beat Ilmari.
Keith Randall
Posted 2014-01-21T00:58:36.697
Reputation: 19 865
You know, you probably could if you optimized that converter.
– Ilmari Karonen – 2014-02-02T17:32:02.4600
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
EDIT: Optimized it 2 times, a bit smaller now.(Removed rubbish)
Leo Pflug
Posted 2014-01-21T00:58:36.697
Reputation: 185
Actually I don't know if it'll be working with bigger numbers (or different one than the test cases). – Leo Pflug – 2014-01-21T10:17:56.470
1-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. – John Dvorak – 2014-01-21T10:30:57.550
"code-golf" in this case means "fewest parts"? – John Dvorak – 2014-01-21T06:02:52.747
Since I haven't even solved the incrementation problem, I have no idea how to solve this. Manufactoria is fun. – Justin – 2014-01-21T06:15:42.823
@JanDvorak: yes. – Keith Randall – 2014-01-21T07:02:12.400
@KeithRandall We never tagged [tag:code-golf] with manufactoria. We should either remove the tag here or add it to the other questions. – Howard – 2014-01-21T08:26:19.460
@Howard: I'd say add it (or [tag:fastest-code] or [tag:busy-beaver] or [tag:code-challenge] or whatever best describes the scoring), and let [tag:manufactoria] be a simple language tag.
– Ilmari Karonen – 2014-01-28T14:15:22.520