Implementing the Snake Puzzle in Javascript

There is a well known series of research articles called functional pearls published by the Journal of Functional Programming (JFP). In a functional pearl a programming problem is explained together with an elegant solution using functional programming. The name functional pearl comes from the idea that a real pearl is formed from a grain of salt who has irritated oysters, functional programming pearls are grown from problems who have irritated functional programmers. While some of these functional pearls require advanced knowledge of functional programming many of these problems and their solutions can be understood with just basic knowledge of functional programming.

Unfortunately, most of these papers use languages like Haskell which limits the amount of people who can comfortably read such papers. In a recent talk I gave for beginner functional programmers who had no prior knowledge of Haskell I prepared a translation in Javascript of a functional programming pearl called “Solving the Snake Cube Puzzle in Haskell” by Mark p. Jones of the Department of Computer Science Portland State University, Portland, Oregon, USA.

In this post I guide you through an implementation of this solution in Javascript, rather than simply translating the Haskell solution into Javascript I made two adjustments. First my implementation makes use of the generator functionality of Javascript which leads to a solution where we “replace failure by a yields of successes” similar to the technique to “replace failure by a list of successes” by Philip Wadler. The second adjustment I made to the solution of Mark p. Jones is to allow more complex puzzles to be solved, this is mainly because I own a snake puzzle which cannot be solved by the original implementation.

What is the snake puzzle ?

A snake puzzle is a kids toy consisting of wooden blocks which are connect with an elastic wire. The toy can be fully unfolded in such a way that it resembles a snake. The challenge is to fold the snake in such a way that it forms a cube. If you have never played with such a toy it might help to have a look at the YouTube video bellow:

There are many variations on this basic toy, the version I received as a present has long sections instead of sections consisting out of individual blocks and has a number of cutouts which allows the blocks to be moved next to each other which allows for more bends.

Representing a snake puzzle

The first step in solving the puzzle is to make a representation of the snake as a data structure. We choose to represent the snake by a list of numbers where each number represents the length of the sections of the cube.

var snake = [1,2,2,3,2,2,3,2,2,3,2,2,1]

Because the cube lives in a three dimensional world we also need to represent the individual blocks of the snake. We represent coordinates by an object with three fields, x y and z. The origin of our coordinate system is the point (1,1,1), in order to represent this coordinate we can make use of javascript’s object literal syntax:

{x:1,y:1,z:1}

A first function that we need is an equality function to verify that two coordinates are the same. This will be needed to make sure that we are not producing solutions where two blocks occupy the same position. The equality over our position objects is straightforward, we simply verify that the x y and z coordinates are the same.

function equalCoodinates(a,b) {
    return (a.x == b.x) && (a.y == b.y) && (a.z == b.z);
}

Second, while searching for a solution we will need to make sure that our current solution is correct. One part of making sure that we are working towards a valid solution is to verify that all the pieces of the snake are still within the boundaries of the cube we are trying to create.

To test this we write a predicate constructor inCube which returns a predicate which will verify that a given position object lies within the boundaries of the cube. We verify this by making sure that all the coordinates of the point are within bounds.

function inCube(n) {
        return (pos) => {
            var valid = (i) => (1 <= i && i <=n);
            return (valid(pos.x) && valid(pos.y) && valid(pos.z));
        }
}

Many variations of snake puzzles exit but they all share a common interface.

var standard   = { valid    : inCube(3),
                   initSoln : [ [ {x:1,y:1,z:1} ]],
                   initDir  : {x:0,y:0,z:1},
                   sections : snake };

Iterate

In the original article the authors make use of a standard function from the Haskell prelude called iterate. The function iterate takes two arguments f and a and returns an infinite list of values where each element of the list \(x_i = f^i(a)\) where \(i\) is the index of the element in the list. For example, in Javascript syntax iterate((x)=>x+1),0) would create an infinite list [0,1,2,3,4, ... ] = [0,f(0),f(f(0)),f(f(f(0))),...]. This function is extremely useful to extend our snake puzzle in a certain direction.

Unfortunately, Javascript does not have support for infinite lists and in our particular use-case we always know exactly with how many pieces we need to extend our snake. We therefore create a bounded version of iterate which creates a finite list of n elements.

function iterate(f,i,n) {
    return new Array(n).fill().reduce((l,x)=>[f(l[0])].concat(l),[i]);
}

Armed with our iterate function we can now define what it means to generate a section of the snake in a certain direction.

function section(start, dir, len) {
    return iterate((pos) => ({ x: pos.x + dir.x, y: pos.y + dir.y, z: pos.z + dir.z }), start, len-1);
}

function noOverlap(soln, sect) {
    const prev  = soln.flat();
    return !sect.some((a) => prev.some( (b) => equalCoodinates(a,b)));
}

Generators

In this section I give a brief example of how to use generators in Javascript, feel free to skip this section if you are already familiar with the concept.

Javascript has support for so called generators functions. Generator functions are syntactically similar to normal functions but their execution model is quite different. First of all when you call a generator function the result is an iterator which allows you to receive all the values that the generator produces. Second, instead of returning a value a generator function yields results. The yield operation will do two things at the same time, first of all it will set the value in the iterator so that the client can read the result but it will also halt the generator. Once the function has yielded a result the client of the generator can later resume the generator (through the iterator) and possibly receive further results from the generator.

A generator function is defined by the keyword function* (note the *) and yielding results is done by the keyword yield. As an example let us define a generator function to generate an infinite amount of subsequent numbers.

Such a generator function called generate is shown below. It receives a number x as argument and immediately yields that value as a result. This means that the generator will be halted at that point in its execution and a result will be produced. When the generator is resumed at a later point in time it will recursively call itself. Remember that the result of calling a generator functions is a iterator, if we would yield the result of the recursive call we would yield an iterator. Instead we make use of the keyword yield* which will unpack the iterator for us and yield all the results of the iterator.

function* generate(x) 
{
    yield x;
    yield* generate(x+1);
} 

In the code example below we make use of our newly defined generator. We first call generate with the value 0 and store the resulting iterator in a variable called infinite_numbers. Subsequently we invoke the next method on our iterator object which results in object with a field value through which we can access the yielded value. In our example this will be the value 0. At this point our generator is halted, to obtain the next result we invoke the next method a second time resulting in the value 1.

var infinite_numbers = generate(0);
console.log(infinite_numbers.next().value);
console.log(infinite_numbers.next().value);

Using generators to enumerate possible directions

Now that we know about generators let us use them to make a generator for the possible directions in which we can expand our snake puzzle. At each point there are theoretically 6 possible directions in which the next section could point, of course some of these directions will be impossible due to the sections which are already placed in the cube, we will filter those out later.

The newDirection generator is implemented by first defining three functions to move the snake in the forward, left and right direction, this corresponding with the thee axises. It is however also possible to move the snake in the opposite direction. In order to account for this we also define the identity (id) and inversion (inv) function. Generation of all directions is now simple, we use a double nested for loop where we pick all possible rotations and their sign. For each combination we yield the new direction.

function* newDirection(dir) {
    var forward  = (dir) =>  {x:dir.x, y: dir.y, z: dir.z} ;
    var left     = (dir) =>  {x:dir.y, y: dir.z, z: dir.x} ;
    var right    = (dir) =>  {x:dir.z, y: dir.x, z: dir.y} ;

    var inv      = (dir) => { return {x:-dir.x, y: -dir.y, z: -dir.z} };
    var id       = (dir) => { return {x:dir.x, y: dir.y, z: dir.z} };

    for (let rotate of [left,right,forward]) {
        for (let sign of [id,inv]) {
            yield (rotate(sign(dir))); 
        }   
    }   
}

Extending a Solution

Now that we know how to generate all possible next directions we need abstractions to extend the current solution. Note that not all possible directions will result in a valid solution. It might be that the given direction leads to a puzzle where two piece of the snake would be at the same spot (clearly impossible) or where part of the puzzle would fall outside of the 3x3 cube (leading to an invalid configuration).

function* extend(p, start, soln, dir, len) {
    const sect = section(start,dir,len);
    if(sect.every(p.valid) && noOverlap(soln,sect)) {
        yield [sect, ...soln];
    }   
}

Generating all solutions

The final step of our implementation is to use all the abstractions we have built so far to generate all the possible solutions for our puzzle. The general strategy of solving the snake puzzle, as implemented here, is to perform a depth first search of the search space.

In each step we take the current (partial)solution move and:

• Generate the first position where we can extend the puzzle
• Generate the first directions in which we can extend the puzzle
• Verify that the extended solution is valid
• Recursively solve our extended solution

If any of these steps fail we need to go back and try the next possibility.

function* solution(p) {
    function* solve(soln, dir, sections) {
        if (sections.length >= 1) {
            const [len, ...lens] = sections;
            for (const moveDir of newDirection(dir)) {
                const nextPos = moveInDirection(soln[0][0],moveDir);
                for (const newdir of newDirection(dir)) {
                    for (const soln_ of extend(p,nextPos,soln,newdir,len)) {
                        yield* solve(soln_,newdir,lens);
                    }
                }
            }
        }  else {
            yield soln;
        }
    };
    yield* solve(p.initSoln, p.initDir, p.sections);
}