• Should use latest testing framework
    • It would be great to get a few more sample tests, with slightly more complex expected results. I pass the current sample tests easily, but I do not pass a single random test. Running the full tests produces so much output that it slows my (old) machine down considerably, so it is frustrating to be forced to run this constantly.
  • Actually I did feel dumb after seeing other solutions that are less sofisticated. I think my mistake here was to try to solve this and the performance edition at the same time. I should have kept it more simple. Lesson learnt.

  • I restarted from scratch with BFS and finally solved it, but didn't feel dumb :-) Looking at the other solutions I'm not particuarly proud of mine, I guess I'll have to work hard to solve th performance edition.

    Thanks again for the kata and the answers.

  • It isnt as complicatedWhen you get it you will feel dumb, I assure you. I sure did.

  • This is a fun and nasty 4-kyu kata but I'll solve it eventually :-) Mathematically the problem can be stated as follows: find the smallest integer k for which at least a vertex v exists such that for each coin c there is a walk (not path) with length k between c and v.

    I tried to compute as efficiently as I could the existance of such walks for each k with matrix multiplication but it's just too slow. I'm afraid I'm computing too much information and reading your suggestions above to another user I think I need to focus only on parity.

  • Always return the minimum number of steps possible to converge all 3 coins.

    Thanks for compliment :)

  • Ok, I don't understand the pseudo graph comment.

    I'm giving up for now.

    A concrete example:

    g = {0: {97, 52}, 1: {81, 78, 47}, 2: {3, 46, 82, 83, 87}, 3: {24, 33, 2, 40}, 4: {37, 54, 39}, 5: {88}, 6: {96, 8, 36}, 7: {65, 44, 92}, 8: {91, 90, 99, 6}, 9: {27, 31}, 10: {48, 11}, 11: {57, 10, 19}, 12: {81}, 13: {17, 57, 78, 86}, 15: {44}, 16: {82, 87}, 17: {13}, 18: {45, 62}, 19: {11}, 20: {45, 23}, 21: {91, 43}, 22: {61, 87}, 23: {43, 20}, 24: {3, 54}, 25: set(), 26: {66, 95}, 27: {96, 9}, 28: {58}, 30: {32, 35, 78}, 31: {40, 9, 90}, 32: {30, 47}, 33: {3, 61}, 34: {61, 77, 46}, 35: {91, 30}, 36: {97, 93, 6}, 37: {73, 4}, 38: {96}, 39: {4, 45}, 40: {3, 31}, 41: {48, 90, 69}, 42: set(), 43: {80, 21, 54, 23}, 44: {72, 7, 15}, 45: {18, 20, 39}, 46: {34, 2}, 47: {32, 1}, 48: {68, 41, 10, 53, 57}, 50: {72, 76}, 51: set(), 52: {0, 85}, 53: {48, 58}, 54: {24, 43, 4}, 55: {92}, 56: {88}, 57: {48, 11, 13}, 58: {28, 53, 68}, 59: set(), 60: set(), 61: {33, 34, 22}, 62: {18}, 63: set(), 64: set(), 65: {7}, 66: {26, 71}, 67: set(), 68: {48, 58}, 69: {41, 99}, 71: {66}, 72: {50, 44}, 73: {37, 92, 77}, 74: set(), 76: {50}, 77: {73, 34}, 78: {1, 13, 30}, 79: {92}, 80: {43, 95}, 81: {1, 12}, 82: {16, 2}, 83: {2}, 84: set(), 85: {52}, 86: {13}, 87: {16, 2, 22}, 88: {56, 92, 5}, 90: {8, 41, 95, 31}, 91: {8, 35, 21}, 92: {7, 73, 79, 55, 88}, 93: {36, 94}, 94: {93}, 95: {80, 26, 90}, 96: {27, 38, 6}, 97: {0, 36}, 99: {8, 69}}
    

    Which was just a random one the problem generated. My exhaustive BFS code shows the coins can converge on node 61 at depth 4. But with the coin starting on 96, it can move there in 3 steps. Or 4 steps if it takes a longer path by going through another node. So then this node can be reached in 3,4,5,6,7... steps. I have no idea how to handle this.

    Interesting kata though, ta.

  • Also, Bellman Ford is for weighted graphs. Which this is not. Optimization is possible.

  • This comment is hidden because it contains spoiler information about the solution

  • OK, I'll have to think carefully about how to implement BFS with thos changes.

    Another approach I tried was finding the shortest path length to each node from each starting coin position. I used Bellman Ford which is n^2, so it's 3n^2. So then I can go through each node and find the min number of steps to it from each coin. And I see the evenness/oddness there. But then it seems more or less impossible to work out if a coin could move there in a different way (following a different path) to change the parity. So say for node Z I have shortest distances of 3, 4, 4, I have to try and figure out if the first coin can take another path and get there in 4 steps...

    What do you think of this approach?

  • This optimization is obvious and dumb, I totally should have thought of it. Well done good sir, and thank you for your work.

  • You don't need to keep track of the depth at which you reach each node. If it is turn 100, does it matter whether I reached node Z at turn 2, turn 4, turn 6, or turn 8, etc? So long as a hit node Z with coin A on some prior even turn, every 2 turns after that, coin A will again hit node Z, and every combination of coin involving that coin A on that node Z will have to be considered.

    Re:edges, that can matter, depending on your imprementation, but not necessarily.

    Re: edges back to themselves: yes, that is an interesting edge case. Consider what that means for even/odd-ness. Also remember that you can backtrack. The point stands. Unless you have a node with no edges, in which case, that's probably an instant failure anyway.

  • But what about cases like where a node has an edge back to itself? Or perhaps we have node 1 which links to node 2 which links to node 3. And node 3 has an edge back to 1. Then we can get back to 1 in 3 moves, not 2... Or rather, as well as 2. So you can get there on both even and odd moves...

    Edit: I think I kind of get it now... You mean that each node in the graph can be marked as having been reached in odd or even steps... And I guess you keep track of which coins have been on which nodes and at what depth/even/odd etc. And to not revisit them too often, I guess maybe keep track of which edges have been used?

  • Loading more items...