Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

i came across this fun puzzle while being on vacation.

It was designed by Robert Abbott and painted into the grass of a Wisconsin farm. Robert succeeded into making it seem really easy to solve. Well, it is not. I spent hours with my friends wandering the puzzle and left frustrated.

I decided to solve it using computers. chose javascript because it made it easy to visualize the process and solution.

Initially i started with a brute force algorithm, which run for hours and got me nowhere. Than i shifted to this final one (below). I just kinda came up with this recursive solution that explores all paths, and terminates any path that comes across a previously visited node, so the one that makes it to the end should be the shortest one in (my) theory. I am wondering if this is a known algorithm (and how i botched it), and if there is a better way to achieve this. Also this algo appears to find the answer in 28 steps (including entry step).. A friend of mine solved this using an algo that works its way back from the end which supposedly solved it in 20 steps.

anyways, the working solution can be seen here.

here is the recursive function:

_delay = 50;
_successfulSteps = null; 
function findRecursive(params){
    var cell = params[0];
    var steps = params[1];
    var history = params[2];
    var x = getX(cell);
    var y = getY(cell);
    var steps = getCellSteps(cell);
    markCellActive(x,y);

    var h = [];
    for (var i = 0; i<history.length; i++) {
        h.push(history[i]);
    };
    h.push([getX(cell),getY(cell)]);

    if (steps == 0) {
        var sp = $('#solutionSpan')[0];
        sp.innerHTML = 'solved in ' + h.length + ' steps';
        return;
    }

    for (var i = history.length - 1; i >= 0; i--) {
        if (x == history[i][0] && y == history[i][1]) {
            // this cell already processed
            console.log('terminating recursion for: ' + y + ':' + x);
            return;
        }
    };

    var rightCell = getRightCell(x,y, steps);
    var leftCell = getLeftCell(x,y, steps);
    var upCell = getUpCell(x,y, steps);
    var downCell = getDownCell(x,y, steps);

            // add delay to visualize the process 
    if (rightCell){
        setTimeout(findRecursive, _delay, [rightCell, steps, h]);
    }
    if (leftCell){
        setTimeout(findRecursive, _delay, [leftCell, steps, h]);
    }
    if (upCell){
        setTimeout(findRecursive, _delay, [upCell, steps, h]);
    }
    if (downCell){
        setTimeout(findRecursive, _delay, [downCell, steps, h]);
    }

}

(i should note that this is not the prettiest code and i'm not looking for a way to reduce # of lines or anything, just to find a better algorithm)

share|improve this question
2  
The shortest path problem can be solved using Dijkstra's algorithm. –  Gareth Rees Nov 25 '12 at 20:56
    
since each node is forcing a # of subsequent steps, i believe it's not as simple as finding the least # of steps between 2 points. Those steps are already routed and the problem is finding that route. is that still the same as shortest path problem ? –  Sonic Soul Nov 25 '12 at 23:06
1  
@SonicSoul: Yes. This puzzle can be represented as a directed graph. Each node has a directed edge to each node that is N spaces away. –  Brian Nov 26 '12 at 16:03
    
Thanks for the cool puzzle. I am learning Scala and just completed an exhaustive, breadth-first search algorithm. I'm pretty sure it's ten times as long as it needs to be. :) –  David Harkness Nov 27 '12 at 3:29
add comment

1 Answer

up vote 2 down vote accepted

You're finding all solutions, but because the code overwrites the <span> for every solution found you only see the last one. Try this:

sp.innerHTML += 'solved in ' + h.length + ' steps<br/>';

You're performing a breadth-first search of all possible paths through the maze which is what I ended up going with. By scheduling timer events you're essentially queueing up cells. I did the same but with an actual queue of cells to visit.

This is the core of my Scala version.

// pathTo tracks the best path to each point
// moves(Point) returns the number in that cell

val queue = new Queue[Point]
queue enqueue new Point(0, 0)  // start from top-left
while (!queue.isEmpty) {
    val start = queue dequeue
    val path = pathTo(start)
    (UP, DOWN, LEFT, RIGHT) foreach { direction =>
        val end = start.move(direction, moves(start))
        if (end != None && !pathTo.contains(end)) {
            pathTo(end) = path + end
            queue enqueue end
        }
    }
}
share|improve this answer
    
actually i don't stop after first solution. if any others were found, it should print it again.. although that has not happened, but technically the code is not stopping after first success –  Sonic Soul Nov 27 '12 at 3:16
    
ok good point!.. heheh.. i do see it solved like 10 times now.. and the least steps was 19 :) –  Sonic Soul Nov 27 '12 at 3:32
    
i kind of assumed i'd see the span rewrite, since i had that delay.. but the delay was not big enough to notice the rewrites. –  Sonic Soul Nov 27 '12 at 3:57
    
If you're counting the starting square as the first step, I got the same answer as you. –  David Harkness Nov 27 '12 at 7:33
    
well my question was more about figuring out if this is the best algorithm.. if if there is a better way to find the answer.. but i'll accept if there arent any other suggestions –  Sonic Soul Nov 27 '12 at 17:36
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.