4 kyu

Snake Cube Solver

21 of 57Paul Robertson
Description
Loading description...
Recursion
Geometry
Puzzles
Algorithms
Game Solvers
Graph Theory
View
AllIssues2Questions2Suggestions3Show Resolved
  • Please sign in or sign up to leave a comment.
  • Blind4Basics Avatar

    Python translation. Please review and approve.

    (I'll update the JS version, to mix both kinds of outputs in the random tests | done)

  • user9644768 Avatar

    Second image in the description is broken.

  • Glyxerine Avatar

    I can not figure out the sentence:

    "For the purposes of this kata, the complete solution occupies a cube with vertices:

    (0,0,0) (2,0,0) (0,2,0) (0,0,2) (2,2,0) (2,0,2) (0,2,2) (2,2,2)

    and starts with the first cube in the corner position (0,0,0)."

    Anybody can explain it. The valid solution is any 27-length path sastified the binary array, begin with [0, 0, 0] and end with any other corners?

  • dennick80 Avatar

    what is the correct configuration for solution in JS? trying with return [[0,0,0],[1,0,0],[2,0,0], ... ] and getting "[] - Solution does not match configuration"

    • Paul Robertson Avatar

      The test checks that your solution matches the given starting configuration (a list of 1s and 0s) of the snake. For example, the three values you give, correspond to a configuration starting with [0,0,...].

  • JohanWiltink Avatar
  • Voile Avatar

    Shouldn't a valid solution return Just _ and no solution return Nothing?

  • JohanWiltink Avatar
    • Why the restriction that the solution must start at (0,0,0)? Why couldn't it start at any valid coordinate?
    • When a solution snakes through itself ( using certain coordinates multiple times ), the error message says it goes outside the box, even if it doesn't.
    • Why no random tests with impossible snakes? Those would occur with truly random snakes ( quite possibly more often than possible ones ), and testing with them shouldn't be hard.

    .. but a very nice kata anyway. :]

    • Paul Robertson Avatar

      Yes, all those points could be addressed. I'll try to improve the validation function soon.

    • Paul Robertson Avatar

      I have added random unsolvable snakes, and added a check for self-intersecting solutions.

      I'm not sure about dropping the restriction that solutions start at (0,0,0) The problem is that it adds five new initial states (Starting position + initial direction). It makes the solving function much slower to execute in ghci.

    • JohanWiltink Avatar

      I'll take your word for it. Leave it at (0,0,0).

      Really random snakes are uninteresting, I found, even without the (0,0,0) restriction.

      Suggestion marked resolved by JohanWiltink 5 years ago
    • JohanWiltink Avatar

      I'm not sure about dropping the restriction that solutions start at (0,0,0). The problem is that it adds five new initial states (Starting position + initial direction). It makes the solving function much slower to execute in ghci.

      Actually, two new states. Snakes can only start on dark-coloured positions in the cube.

      Also, I'm going to do some more testing with random snakes. There may yet be interesting ones.

    • Paul Robertson Avatar

      Yes, you are quite right.

      I suppose there are 2^27 = 134217728 possible snakes. But snakes with two or more adjacent 0's will never have a solution (I think that would be at least half of them). I have read that there are only 11487 different snakes which have a solution - not very many!

      I have owned a wooden 4x4x4 'king snake cube' for about 5 years. Despite many hours of effort, I have never been able to solve it. Of course, a computer program can find a solution in a few seconds.

    • koenr Avatar

      I also own a 4x4x4 snake cube, and also couldn't solve it. A few years back i wrote a Haskell program to solve it, i could reuse my code today. :) Thanks for making this.