2048 In Javascript, Crummy Text Edition

We begin with the algorithm to generate the sequences. We start having been given the width (\(w\)), height (\(h\)), whether or not we are doing a "left/right" sequence (\(lr\)), an operation to initialize a collection (\(INIT\)), an operation which is responsible for adding to a collection (\(ADD\)), and a an operation that will calculate the current value we are adding (\(CALC\_CURRENT\)). We will use variables to maintain what row we are on (\(r\)), what column we are on (\(c\)), the collection of all sequences (\(a\)), finally the current sequence we are making (\(s\)).

The values that we will have for \(CALC\_CURRENT\) will be \(r \times w + c\) for horizontal sequences, and \(r + c \times h\) for vertical ones.

1. [initialize] \(a \gets INIT()\), \(r \gets 0\)
2. [swap w&h?] if \(!lr\), swap \(w\) and \(h\)
3. [begin current list] \(s \gets INIT()\), \(c \gets 0\)
4. [add list to total] \(ADD(a, s)\)
5. [add next value to s] \(ADD(s, CALC\_CURRENT(w, h, r, c))\)
6. [increment c] \(c \gets c + 1\), if \(c < w\) goto 4.
7. [increment r] \(r \gets r + 1\), if \(r < h\) goto 2.
8. [terminate] \(a\) contains all subsequences

Not going to lie, that actually looks and sounds more complicated than the code. I'm new and/or not good at this. Apologies for the far from idiomatic JavaScript. Keeping it closer to how I wrote the algorithm above. And yes, even that could probably be cleaned up.

function makeSequences(w, h, lr, INIT, ADD, CALC_CURRENT) {
    var c = 0, r = 0, s = null, a = INIT();
    if (!lr)  {
        var x = w;
        w = h;
        h = x;
    }
    for (r; r < h; r++) {
        s = INIT();
        ADD(a, s);
        for (c = 0; c < w; c++) {
            ADD(s, CALC_CURRENT(w, h, r, c));
        }
    }
    return a;
};

Again, not going to pretend that calling this function is the cleanest thing in the world. Especially if I was willing to code golf, I could just have it such that we did not have to pass the width and height to all functions. No matter, it isn't that bad. (For that matter, if I was just wanting to implement a 4x4 grid for this, I would just code in the sequence and be done with it. Looking forward to possibly playing with different size/shape boards.)

At startup, we will initialize all four sets of our sequences such that they can be looked up in a map by "up", "down", "left", and "right." As so:

var sequences = {
    'left': makeSequences(width, height, true,
                          function() { return []; },
                          function(c, v) {c.push(v);},
                          function(w, h, r, c) {return r * w + c;}),
    'right': makeSequences(width, height, true,
                           function() { return []; },
                           function(c, v) {c.unshift(v);},
                           function(w, h, r, c) {return r * w + c;}),
    'up': makeSequences(width, height, false,
                        function() { return []; },
                        function(c, v) {c.push(v);},
                        function(w, h, r, c) {return r + c * h;}),
    'down': makeSequences(width, height, false,
                          function() { return []; },
                          function(c, v) {c.unshift(v);},
                          function(w, h, r, c) {return r + c * h;})
};

Now that we have our sequences, we need our main algorithm. At a high level, for each sequence, we basically slide two pointers across it looking for either a slide, a merge, or simple advance. Things are a little interesting when we do a slide, because we could still merge the tile that was slid. If we do a merge, we won't consider the tile again. Also, there is no need to look at all pairs, as soon as the right focus reaches the end, we are done.

So, our overall algorithm is:

1. [initialize] \(l \gets 0\)
2. [reset r] \(r \gets l\)
3. [advance r] \(r \gets r + 1\), if \(r > w\) terminate
4. [test r] if \(b[r]\) is empty goto 3
5. [slide?] if \(b[l] is\) empty, b[l] <- b[r], b[r] <- empty, goto 3
6. [merge?] if b[l] = b[r], b[l] <- b[l] + b[r]
7. [advance l] l = l + 1, goto 2.

In javascript, this is the rather interesting looking code below. The only modification we really need is a flag to indicate that we are checking for moves and not actually performing any. That is, if the game is unable to place random pieces, we need to know if the user is able to make any more moves.

function collapseBySequence(b, s) {
    var l = 0,
        r = 0;
    for (r = 1; r < s.length; r++) {
        if (b[s[r]] === 0) {
            continue;
        }
        if (b[s[l]] === 0) {
            b[s[l]] = b[s[r]];
            b[s[r]] = 0;
            continue;
        }
        if (b[s[l]] === b[s[r]]) {
            b[s[l]] = b[s[l]] + b[s[r]];
            b[s[r]] = 0;
        }
        l = l + 1;
        r = l;
    }
}

We do not always want to perform a collapse when inspecting the game board. In particular, when we are checking for "game over." Originally, I just tacked on some extra lines in the collapse method, however, that is getting rather heavy and I'd rather keep things simpler.

So, we have this modification of that method to simply return whether or not there are possible moves for a sequence. As can be seen, it is the same code, just without the modifications to the underlying board state.

function checkForMoves(b, s) {
    var l = 0,
        r = 0;
    for (r = 1; r < s.length; r++) {
        if (b[s[l]] === 0) {
            return true
        }
        if (b[s[l]] === b[s[r]]) {
            return true;
        }
        l = l + 1;
        r = l;
    }
    return false;
}

We will also go ahead and make our method that checks for any moves. This is simply chaining the above method with all of the sequences.

function checkSequencesForMoves() {
    for (var d in sequences) {
        for (var s in sequences[d])
            if (checkForMoves(board, sequences[d][s]))
                return true;
    }
    return false;
}

After that, the only real "algorithmic" part I need is a way to place random values. I'm not going to claim that random values are a strong point, so I'm tacking "ish" to this. Basic idea is find all indexes that have a zero and then randomly pick two.

function placeRandomIsh(board, allowedValues, sequences) {
    var i, c = [];
    for (var i = 0; i < board.length; i++) {
        if (board[i] === 0) {
            c.push(i);
        }
    }
    if (c.length === 0) {
        return checkSequencesForMoves();
    } else {
        var x = Math.floor(Math.random() * c.length);
        board[c[x]] = allowedValues[Math.floor(Math.random() * allowedValues.length)];
    }
    return true;
}