Hacker News new | ask | show | jobs
by zuxfer 3880 days ago
help me, i can't get it to work for 1603.
1 comments

It works. Follow:

(1) 1 black then 1 white.

(6) 6 blacks then 1 white.

(0) 1 white.

(3) 3 blacks then 1 white.

And you end up at the bottom node, indicating it is divisible by 7.

You should be following the 1 white path before the n black paths, not afterwards. In particular, following "3 blacks then 1 white" in the last step, when the final digit is three, is an error; it will produce the wrong modulus for any number that is not divisible by 7.

    (1) 1 white then 1 black,  ending up in state 1
    (6) 1 white then 6 blacks, ending up in state 2
    (0) 1 white then 0 blacks, ending up in state 6
    (3) 1 white then 3 blacks, ending up in state 0
The graph keeps track of ((the number so far) mod 7); following a white arrow multiplies your total by 10, and following a black arrow increases your total by 1.
I can see how you'd like to hold the order of operations correct for readability purposes (especially if the states were labeled with digits), but I don't see where psyklic's method could produce an error for the divisibility test.

Your initial white doesn't change anything, since it brings you back to the starting node. Any whites after the the final digit either keep you on the starting node or keep you in the graph where.

The graph isn't just a divisibility test, it reports the remainder after division by seven. I specifically acknowledged that this error won't mutate a "divisible by 7" result into "not divisible by 7" (because any number that is divisible by seven will still be divisible by seven after multiplying it by ten), but in every other case it will give you the wrong answer. (e.g. "remainder 2" will mutate into "remainder 6".)