Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
package yuima.funcpearls
import scala.annotation.tailrec
/** Scala implementation of "Solving the Snake Cube Puzzle in Haskel."
* http://web.cecs.pdx.edu/~mpj/snakecube/revised-SnakeCube.pdf
*
* Note: No implementation for a function "advance" in section 9.
*
* @author Yuichiroh Matsubayashi
* Created on 14/11/28.
*/
object SnakeCube {
type Section = List[Position]
type Solution = List[Section]
val snake = List(3, 2, 2, 3, 2, 3, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 3)
val standard = SnakeCubePuzzle(
sections = snake,
valid = inCube(3)(_),
initialSolution = List(List(Position(1, 1, 1))),
initialDirection = Direction(0, 0, 1)
)
val meanGreen = standard.copy(sections = List(3, 3, 2, 3, 2, 3, 2, 2, 2, 3, 3, 3, 2, 3, 3, 3))
val king = standard.copy(valid = inCube(4)(_), sections = List(
3, 2, 3, 2, 2, 4, 2, 3, 2, 3, 2, 3, 2, 2, 2,
2, 2, 2, 2, 2, 3, 3, 2, 2, 2, 2, 2, 3, 4, 2,
2, 2, 4, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 2)
)
val king1 = king.copy(initialSolution = List(List(Position(2, 1, 1))))
val king2 = king.copy(initialSolution = List(List(Position(1, 2, 2))))
/** Colors used for visualization.
* Cubes having an odd index are brown and even index are white. */
val colors = Iterator.continually(Seq("brown", "white")).flatten
def main(args: Array[String]) {
solutions(standard).foreach(println)
}
/** gets solutions of a puzzle using a brute force algorithm. */
def solutions(p: SnakeCubePuzzle) = {
def solve(solution: Solution)(prevDir: Direction)(sections: List[Int]): List[Solution] = sections match {
case Nil => List(solution)
case length :: secs =>
newDirections(prevDir).flatMap { newDir =>
extend(p)(solution)(newDir)(length).flatMap { newSolution => solve(newSolution)(newDir)(secs) }
}
}
solve(p.initialSolution)(p.initialDirection)(p.sections)
}
/** gets possible directions for a next move. */
def newDirections(prev: Direction) = List(
Direction(prev.v, prev.w, prev.u),
Direction(-prev.v, -prev.w, -prev.u),
Direction(prev.w, prev.u, prev.v),
Direction(-prev.w, -prev.u, -prev.v)
)
/** extends current move sequences with a move toward a particular direction.
* Note: we must ensure that all of the positions in next section are valid in the given puzzle,
* and we must also check that none of the positions in next section have already been occupied by
* other sections in the starting solution.
* @param p puzzle definition
* @param solution the move sequence so far
* @param dir the direction of a next move
* @param length the cube length of the next section
**/
def extend(p: SnakeCubePuzzle)(solution: Solution)(dir: Direction)(length: Int) = {
val start = solution.head.head
val nextSec = section(start)(dir)(length)
if (nextSec.forall(p.valid) && solution.forall(sec => (nextSec intersect sec).isEmpty)) List(nextSec :: solution)
else Nil
}
/** obtains small-cube positions for a next move.
* @param start the beginning position of the move.
* @param d the direction of the move.
* @param length the small-cube length of the move.
* */
def section(start: Position)(d: Direction)(length: Int) = {
def pieces = Stream.iterate(start) { pos: Position => Position(pos.x + d.u, pos.y + d.v, pos.z + d.w) }
pieces.take(length).tail.reverse.toList
}
/** creates a variant of a puzzle by reversing the order of the sections. */
def reversePuzzle(p: SnakeCubePuzzle) = p.copy(sections = p.sections.reverse)
/** checks whether a given cube location is valid for a solution (it should be inside of the large cube).
* @param size the cube size of the solution (i.e. the cube is size * size * size)
* @param pos the position of a target cube.
**/
def inCube(size: Int)(pos: Position) = {
def inRange(k: Int) = 1 <= k && k <= size
inRange(pos.x) && inRange(pos.y) && inRange(pos.z)
}
/** converts an objective of the puzzle to a different one --that is to find the most-compact,
* flat form where all of the sections in a single level. (i.e. z == 1 for all cubes) */
def flatPuzzle(p: SnakeCubePuzzle) = p.copy(valid = (pos: Position) => pos.z == 1)
/** returns sketch format data representing a one of the solution. */
def showSteps(p: SnakeCubePuzzle) = steps(solutions(p).head).map(showCubes).mkString("\n")
def steps(solution: Solution) = solution.map(_.reverse).reverse.tail
/** returns polygon info of cubes for the sketching tool.
* @param positions the cube positions
**/
def showCubes(positions: List[Position]) = positions.map(p => cube2sketch(colors.next)(p)).mkString("\n")
/** returns polygon info of a single cube for the sketching tool. */
def cube2sketch(color: String)(a: Position) = {
val prefix = s"polygon[fill=$color]"
val Position(x, y, z) = a
val b = (x, y, z - 1)
val c = (x, y - 1, z)
val d = (x - 1, y, z)
val e = (x, y - 1, z - 1)
val f = (x - 1, y, z - 1)
val g = (x - 1, y - 1, z)
val h = (x - 1, y - 1, z - 1)
val faces = List(List(a, d, g, c), List(b, e, h, f), List(a, b, f, d), List(c, g, h, e), List(a, c, e, b), List(d, f, h, g))
faces.map(f => prefix + f.mkString("")).mkString("\n")
}
/** SnakeCube puzzle */
case class SnakeCubePuzzle(sections: List[Int],
valid: Position => Boolean,
initialSolution: Solution,
initialDirection: Direction)
case class Direction(u: Int, v: Int, w: Int) {
require(u.abs + v.abs + w.abs == 1 && u.abs <= 1 && v.abs <= 1 && w.abs <= 1)
}
case class Position(x: Int, y: Int, z: Int) {
override def toString = Seq(x, y, z).mkString("(", ",", ")")
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.