danyshaanan/ Snake Cube

## Snake Cube

      
    Raw
  

               Snake Cube
            
          
## .gitignore
*.log

## snake_cube.js
#!/usr/bin/env node

'use strict'

const equals = (a, b) => require('assert')(a === b, `\n${a}\n${b}`)

const units = [[1,0,0], [-1,0,0], [0,1,0], [0,-1,0], [0,0,1], [0,0,-1]]
const name = u => ['l-r','u-d','f-b'][u.findIndex(Boolean)][u.find(Boolean) + 1]

const axis = v => v.findIndex(Boolean)
const perp = (v, u) => axis(v) !== axis(u)
const perps = units.map(u => [0,1,2,3,4,5].filter(i => perp(u, units[i])))

const spaceGraph = size => {
  const cubeOfVectors = size => {
    const d1 = [...Array(size)].map((v, i) => i)
    const r = A => A.reduce((o, a) => [...o, ...d1.map(i => [...a, i])], [])
    return r(r(r([[]])))
  }
  const add = (v, u) => v.map((_, i) => v[i] + u[i])
  const all = cubeOfVectors(size)
  const o = all.reduce((o, v, i) => Object.assign(o, { [v]: i }), {})
  return all.map(v => units.map(u => o[add(v, u)]))
}

const startingPoints = size => [,,[0],[0, 2, 4, 13], [4]][size]

////////////////////////////////////////////////////////////////////////////////

const solve = snake => {
  const size = Math.cbrt(snake.length)
  if (new RegExp(`S{${size-1}}`).test(snake)) return
  const space = spaceGraph(size)
  const available = space.map(Boolean)

  const rec = (location, direction, i) => {
    if (space.length <= i) return []
    if (location === undefined) return false
    if (!available[location]) return false
    for (const nextDir of snake[i] === 'C' ? perps[direction] : [direction]) {
      available[location] = false
      const path = rec(space[location][nextDir], nextDir, i + 1)
      if (path) return [nextDir, ...path]
      available[location] = true
    }
  }

  const path = startingPoints(size).reduce((p, i) => p || rec(i, 0, 0), false)

  if (path) {
    equals(available.filter(Boolean).length, 0)
    equals(path.length, snake.length)
    return path.map(u => name(units[u])).join('')
  }
}

////////////////////////////////////////////////////////////////////////////////

const solutions = {
  ECCCCCCE: 'rdlbrull',
  ECCCCCCCCCCCCCCCCCCCCCCCCCE: undefined,
  ESCSCSCCCCSCCCCCCCCCCCCCCCE: 'rrddbbuldfflurbrublflbdfdbb',
  ESCCCSCSCCCCCCCCCCCCCSCSCCE: 'rrdblluurflfrdldbrfruubbdll',
  ESCSCSCCSCSCSCCCCSCCSCCSCSE: 'rrddllbrruullbrdfflbbdrruuu',
  ESCSCSCSCCCCSCSCCCSCCSCCCSE: 'rrddllbbrfruullbdffrbburddd',
  ESCCCCCCCCCSCCCCCCCSCSCCCCE: 'rrdldrblbruufdlbulddffuburr',
  ESCSCCCCSCCCCCCCCSCCCSCCCSE: 'rrddlbruulblfdbdffurbbdruuu',
  ECCCCSCSCCCCCCCCCCCSCSCCCCE: 'rdrubblldrdlfrurbdfflluburr',
  ESCCSCCCSSCCSCCSCCSCCCCCCCCCSCSCCCCCCSCSSCCCCSSCCSCCCCCCCCCCSSCE:
  'rrdlldrbbblffubbrffrdfrbufubbddlubdruulllfubrrrflldrfuldlufrrrbb',
  ECCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCE:
  'rdrdrubldrblurulurbdluldlufrdlfufrbrfrbdflbldlfdrblbrulbdrurdruu'
}

////////////////////////////////////////////////////////////////////////////////

const forEachSnakeOfSize = (size, cb) => {
  let snakesCount = 2 ** (size ** 3 - 2)
  for (let i = 0; i < snakesCount ; i++) {
    const bin = (i + snakesCount).toString(2).slice(1)
    const snake = [...'EE'].join(bin.replace(/[01]/g, i => 'CS'[i]))
    cb(snake)
  }
}

let c = 0 // Verify that `solutions` includes all solveable 2x2x2 snakes:
forEachSnakeOfSize(2, snake => { c++; equals(solve(snake), solutions[snake]) })
equals(c, 64) // ...and that there are 64 2x2x2 snakes.

if (process.env.all3) {
  forEachSnakeOfSize(3, snake => {
    const [t, path] = [Date.now(), solve(snake)]
    if (path) console.log(`${snake} => ${path} (${Date.now() - t}ms)`)
  })
}

////////////////////////////////////////////////////////////////////////////////

Object.keys(solutions).forEach(snake => {
  const [t, path] = [Date.now(), solve(snake)]
  equals(path, solutions[snake])
  console.log(`${snake} => ${path} (${Date.now() - t}ms)`)
})

## snake_cube.py
#!/usr/bin/python

#
# A recursive brute force solver for the snake cube puzzle.
#
# Read also:
# http://en.wikipedia.org/wiki/Snake_cube
# http://www.mathematische-basteleien.de/snakecube.htm
# http://www.jaapsch.net/puzzles/snakecube.htm
#

import copy, operator

class Vector( object ):
    def __init__( self, coordinates ):
        self.coordinates = coordinates
    def dot( self, vector ):
        return sum( map( operator.mul, self.coordinates, vector.coordinates) )
    def add( self, vector ):
        return Vector( map( operator.add, self.coordinates, vector.coordinates) )
    def perpendicular( self ):
        return [ vector for vector in units if Vector.dot(self,vector) == 0 ]
    def echo( self ):
        return str(self.coordinates)
    def name( self ):
        for unit in unitsDict:
            if self.coordinates == unit[0]:
                return unit[1]
        return 'none   '

class Space( object ):
    def __init__( self, dimensions, size ):
        self.dimensions = dimensions
        self.mx = [float('-inf')] * self.dimensions
        self.mn = [float('+inf')] * self.dimensions
        self.vectors = []
        self.pointer = Vector([0] * self.dimensions)
        self.size = size
    def fill( self, vector ):
        self.vectors.append(vector)
        self.mx = map(max, self.mx, vector.coordinates)
        self.mn = map(min, self.mn, vector.coordinates)
    def filled( self, location ):
        for vector in self.vectors:
            if location.coordinates == vector.coordinates:
                return True
        return False
    def fit( self ):
        return max(map(operator.sub, self.mx, self.mn)) + 1 <= self.size

def nextDirections(direction, turn):
    if turn:
        return direction.perpendicular()
    else:
        return [direction]

def rec(tail, space, direction):
    if tail == []:
        return True
    space.pointer = Vector.add(space.pointer,direction)
    if space.filled(space.pointer):
        return False
    space.fill(space.pointer)
    if not space.fit():
        return False
    for d in nextDirections(direction, tail.pop()):
        result = rec(copy.deepcopy(tail), copy.deepcopy(space), d)
        if result:
            print space.pointer.echo(), (tail == [] and '       ' or d.name()), tail
            return result

unitsDict = [
    ([1,0,0],  'right  '),
    ([-1,0,0], 'left   '),
    ([0,1,0],  'down   '),
    ([0,-1,0], 'up     '),
    ([0,0,1],  'back   '),
    ([0,0,-1], 'forward')
]
units = [ Vector(unit[0]) for unit in unitsDict ]

size = 3
snake = [0,0,1,0,1,0,1,0,1,1,1,1,0,1,0,1,1,1,0,1,1,0,1,1,1,0,0]

# size = 4
# snake = [0,0,1,1,0,1,1,1,0,0,1,1,0,1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,0,1,0,0,1,1,1,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,0,0,1,0]

result = rec(copy.deepcopy(snake), Space(3,size), Vector([1, 0, 0]))

print '                 ', snake
print result
	#!/usr/bin/env node

	'use strict'

	const equals = (a, b) => require('assert')(a === b, `\n${a}\n${b}`)

	const units = [[1,0,0], [-1,0,0], [0,1,0], [0,-1,0], [0,0,1], [0,0,-1]]
	const name = u => ['l-r','u-d','f-b'][u.findIndex(Boolean)][u.find(Boolean) + 1]

	const axis = v => v.findIndex(Boolean)
	const perp = (v, u) => axis(v) !== axis(u)
	const perps = units.map(u => [0,1,2,3,4,5].filter(i => perp(u, units[i])))

	const spaceGraph = size => {
	const cubeOfVectors = size => {
	const d1 = [...Array(size)].map((v, i) => i)
	const r = A => A.reduce((o, a) => [...o, ...d1.map(i => [...a, i])], [])
	return r(r(r([[]])))
	}
	const add = (v, u) => v.map((_, i) => v[i] + u[i])
	const all = cubeOfVectors(size)
	const o = all.reduce((o, v, i) => Object.assign(o, { [v]: i }), {})
	return all.map(v => units.map(u => o[add(v, u)]))
	}

	const startingPoints = size => [,,[0],[0, 2, 4, 13], [4]][size]

	////////////////////////////////////////////////////////////////////////////////

	const solve = snake => {
	const size = Math.cbrt(snake.length)
	if (new RegExp(`S{${size-1}}`).test(snake)) return
	const space = spaceGraph(size)
	const available = space.map(Boolean)

	const rec = (location, direction, i) => {
	if (space.length <= i) return []
	if (location === undefined) return false
	if (!available[location]) return false
	for (const nextDir of snake[i] === 'C' ? perps[direction] : [direction]) {
	available[location] = false
	const path = rec(space[location][nextDir], nextDir, i + 1)
	if (path) return [nextDir, ...path]
	available[location] = true
	}
	}

	const path = startingPoints(size).reduce((p, i) => p \|\| rec(i, 0, 0), false)

	if (path) {
	equals(available.filter(Boolean).length, 0)
	equals(path.length, snake.length)
	return path.map(u => name(units[u])).join('')
	}
	}

	////////////////////////////////////////////////////////////////////////////////

	const solutions = {
	ECCCCCCE: 'rdlbrull',
	ECCCCCCCCCCCCCCCCCCCCCCCCCE: undefined,
	ESCSCSCCCCSCCCCCCCCCCCCCCCE: 'rrddbbuldfflurbrublflbdfdbb',
	ESCCCSCSCCCCCCCCCCCCCSCSCCE: 'rrdblluurflfrdldbrfruubbdll',
	ESCSCSCCSCSCSCCCCSCCSCCSCSE: 'rrddllbrruullbrdfflbbdrruuu',
	ESCSCSCSCCCCSCSCCCSCCSCCCSE: 'rrddllbbrfruullbdffrbburddd',
	ESCCCCCCCCCSCCCCCCCSCSCCCCE: 'rrdldrblbruufdlbulddffuburr',
	ESCSCCCCSCCCCCCCCSCCCSCCCSE: 'rrddlbruulblfdbdffurbbdruuu',
	ECCCCSCSCCCCCCCCCCCSCSCCCCE: 'rdrubblldrdlfrurbdfflluburr',
	ESCCSCCCSSCCSCCSCCSCCCCCCCCCSCSCCCCCCSCSSCCCCSSCCSCCCCCCCCCCSSCE:
	'rrdlldrbbblffubbrffrdfrbufubbddlubdruulllfubrrrflldrfuldlufrrrbb',
	ECCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCE:
	'rdrdrubldrblurulurbdluldlufrdlfufrbrfrbdflbldlfdrblbrulbdrurdruu'
	}

	////////////////////////////////////////////////////////////////////////////////

	const forEachSnakeOfSize = (size, cb) => {
	let snakesCount = 2 (size 3 - 2)
	for (let i = 0; i < snakesCount ; i++) {
	const bin = (i + snakesCount).toString(2).slice(1)
	const snake = [...'EE'].join(bin.replace(/[01]/g, i => 'CS'[i]))
	cb(snake)
	}
	}

	let c = 0 // Verify that `solutions` includes all solveable 2x2x2 snakes:
	forEachSnakeOfSize(2, snake => { c++; equals(solve(snake), solutions[snake]) })
	equals(c, 64) // ...and that there are 64 2x2x2 snakes.

	if (process.env.all3) {
	forEachSnakeOfSize(3, snake => {
	const [t, path] = [Date.now(), solve(snake)]
	if (path) console.log(`${snake} => ${path} (${Date.now() - t}ms)`)
	})
	}

	////////////////////////////////////////////////////////////////////////////////

	Object.keys(solutions).forEach(snake => {
	const [t, path] = [Date.now(), solve(snake)]
	equals(path, solutions[snake])
	console.log(`${snake} => ${path} (${Date.now() - t}ms)`)
	})
	#!/usr/bin/python

	#
	# A recursive brute force solver for the snake cube puzzle.
	#
	# Read also:
	# http://en.wikipedia.org/wiki/Snake_cube
	# http://www.mathematische-basteleien.de/snakecube.htm
	# http://www.jaapsch.net/puzzles/snakecube.htm
	#

	import copy, operator

	class Vector( object ):
	def __init__( self, coordinates ):
	self.coordinates = coordinates
	def dot( self, vector ):
	return sum( map( operator.mul, self.coordinates, vector.coordinates) )
	def add( self, vector ):
	return Vector( map( operator.add, self.coordinates, vector.coordinates) )
	def perpendicular( self ):
	return [ vector for vector in units if Vector.dot(self,vector) == 0 ]
	def echo( self ):
	return str(self.coordinates)
	def name( self ):
	for unit in unitsDict:
	if self.coordinates == unit[0]:
	return unit[1]
	return 'none '

	class Space( object ):
	def __init__( self, dimensions, size ):
	self.dimensions = dimensions
	self.mx = [float('-inf')] * self.dimensions
	self.mn = [float('+inf')] * self.dimensions
	self.vectors = []
	self.pointer = Vector([0] * self.dimensions)
	self.size = size
	def fill( self, vector ):
	self.vectors.append(vector)
	self.mx = map(max, self.mx, vector.coordinates)
	self.mn = map(min, self.mn, vector.coordinates)
	def filled( self, location ):
	for vector in self.vectors:
	if location.coordinates == vector.coordinates:
	return True
	return False
	def fit( self ):
	return max(map(operator.sub, self.mx, self.mn)) + 1 <= self.size

	def nextDirections(direction, turn):
	if turn:
	return direction.perpendicular()
	else:
	return [direction]

	def rec(tail, space, direction):
	if tail == []:
	return True
	space.pointer = Vector.add(space.pointer,direction)
	if space.filled(space.pointer):
	return False
	space.fill(space.pointer)
	if not space.fit():
	return False
	for d in nextDirections(direction, tail.pop()):
	result = rec(copy.deepcopy(tail), copy.deepcopy(space), d)
	if result:
	print space.pointer.echo(), (tail == [] and ' ' or d.name()), tail
	return result

	unitsDict = [
	([1,0,0], 'right '),
	([-1,0,0], 'left '),
	([0,1,0], 'down '),
	([0,-1,0], 'up '),
	([0,0,1], 'back '),
	([0,0,-1], 'forward')
	]
	units = [ Vector(unit[0]) for unit in unitsDict ]

	size = 3
	snake = [0,0,1,0,1,0,1,0,1,1,1,1,0,1,0,1,1,1,0,1,1,0,1,1,1,0,0]

	# size = 4
	# snake = [0,0,1,1,0,1,1,1,0,0,1,1,0,1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,0,1,0,0,1,1,1,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,0,0,1,0]

	result = rec(copy.deepcopy(snake), Space(3,size), Vector([1, 0, 0]))

	print ' ', snake
	print result