JSFiddle - React, Tailwind, and code Playground

by cheeken

HTML

<div><h1>Demo for stackoverflow answer to <a href="http://stackoverflow.com/questions/9041853/interview-puzzle-jump-game/9041971#9041971" target="_blank">Interview puzzle: Jump Game</a></h1></div><br/>


<form><label>array a = <input type="text" id="input" style="width: 400px;"/></label></form>
<br/>
<pre>

</pre>

JavaScript

Array.prototype.last = function() {
    return this[this.length - 1];
};

var jumpGame = function(list) {
    // Generate the list of sums
    var sums = [];
    var i;

    for (i = 0; i < list.length; i++) {
        sums.push(i + list[i]);
    }

    // Remember our moves
    var moves = [0];

    if (list.length == 1) {
        return moves;
    }

    while (1) {
        var currentPosition = moves.last();
        var jumpValue = list[currentPosition];

        // See if we can jump to the goal
        if (list.length - 1 - currentPosition <= jumpValue) {
            moves.push(list.length - 1);
            return moves;
        } else {
            var maxIndex = currentPosition;
            for (i = currentPosition; i <= currentPosition + jumpValue; i++) {
                if (!maxIndex || sums[i] > sums[maxIndex]) {
                    maxIndex = i;
                }
            }
            if (maxIndex == currentPosition) {
                return;
            }
            moves.push(maxIndex);
        }
    }
};

$("form").submit(function(event) {
    event.preventDefault();
    var splits = $('#input').val().split(/\s*,\s*/);
    $('#input').val("");
    try {
        var l = splits.map(function(v) {
            var i = parseInt(v, 10);
            if (!isNaN(i)) {
                return i;
            }
            else {
                throw "Invalid input.";
            }
        });
        var r = jumpGame(l);
        if (!r) {
            alert("No solution found.");
        }
        else {
            $("pre").text("a = [" + l.join(", ") + "]\n\nSolution of " + (r.length - 1) + " steps:\n" + r.map(function(v) {
                return "a[" + v + "]=" + l[v];
            }).join(" -> "));
        }
    } catch (e) {
        alert("Something went wrong. " + e);
    }
});

$('#input').val("2,6,1,15,1,1,1,1,1,1,1,1,1,1,1,1").focus();