A script to find a solution to the 2048 puzzle.

2kb.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# License: public domain
# Author: Saravjeet 'Aman' Singh <[email protected]>

import json
import argparse
import time
import sys
import re

try:
    import curses
except ImportError:
    print >> sys.stderr, "unable to import curses, logging is diabled"

    # stub interface to curses, in case it is unavailable.
    # notice the lack of self parameter.
    class _dumdum(object):

        def dummy(*args, **kwargs):
            pass

        def wrapper(func, *args, **kwargs):
            return func(_dumdum(), *args, **kwargs)

        def __getattribute__(self, attr):
            try:
                return _dumdum.__dict__[attr]
            except KeyError:
                return _dumdum.__dict__['dummy']

    curses = _dumdum()

import selenium
import selenium.webdriver
from selenium.webdriver.common.keys import Keys
from selenium.common.exceptions import StaleElementReferenceException


class config:
    GAME_URL = 'https://quaxio.com/2048/'
    UNDO = 'z'
    TILES_PER_AXIS = 4
    TARGET = 2048


def generate_board():
    '''generate an empty board'''
    outer = []
    for i in range(config.TILES_PER_AXIS):
        inner = []
        for j in range(config.TILES_PER_AXIS):
            inner.append(0)
        outer.append(inner)
    return outer


def board_state(page):
    '''get the current board's status'''
    while True:
        # savage
        try:
            elements = page.find_elements_by_class_name('tile')
            positions = [el.get_attribute('class') for el in elements]
            break
        except StaleElementReferenceException:
            continue

    x = re.compile('tile-position-(\d+)-')
    y = re.compile('tile-position-\d+-(\d+)')
    v = re.compile('tile-(\d+)')

    positions = zip(
        # make the coordinates 0-indexed
        map(lambda v: int(v) - 1, [x.search(p).groups()[0]
            for p in positions]),
        map(lambda v: int(v) - 1, [y.search(p).groups()[0]
            for p in positions]),
        map(int, [v.search(p).groups()[0] for p in positions]))

    board = generate_board()
    for x, y, val in positions:
        board[y][x] = val

    return board


def board_changed(this, that):
    '''determine if there is a difference between two boards'''
    composite = zip(this, that)

    def compare(result, current):
        for i in range(len(current[0])):
            if current[0][i] != current[1][i]:
                return True
        return result

    return reduce(compare, composite, False)


def board_has(board, value):
    # convert the 2d matrix into a 1d matrix
    all_values = [v for val in board for v in val]
    return reduce(lambda result, v: result or v == value, all_values, False)


def game_won(board):
    ''' determines if the winning condition has been reached '''
    return board_has(board, config.TARGET)

def generate_dump(page, hist):

    send = page.find_element_by_tag_name('body').send_keys
    n = len(hist)
    result = []
    for i in range(n, 0, -1):
        state = board_state(page)
        send(config.UNDO)
        result.append({
            'step': i,
            'state': state,
            'move': hist.pop()})
    result.reverse()
    return result


def find(stdscr, page):

    moves = [Keys.ARROW_UP, Keys.ARROW_RIGHT,
             Keys.ARROW_DOWN, Keys.ARROW_LEFT]

    move_map = {
        Keys.ARROW_UP: 'up',
        Keys.ARROW_RIGHT: 'right',
        Keys.ARROW_DOWN: 'down',
        Keys.ARROW_LEFT: 'left'}

    send = page.find_element_by_tag_name('body').send_keys

    hist = []
    stack = []
    stack.append(list(moves))
    ops = 0
    start_t = time.time()

    while len(stack) != 0:

        if start_t - time.time() > 30:
            ops = 0
            start_t = time.time()

        ops += 1
        rate = 'rate: {} ops/second'.format(
            ops / (time.time() - start_t))

        stdscr.addstr(0, 0, 'running ...')
        stdscr.addstr(1, 0, '<ctrl-c to exit>')
        stdscr.addstr(2, 0, 'stats: ')
        stdscr.addstr(3, 4, 'stack depth: {}'.format(len(stack)))
        stdscr.addstr(4, 4, 'operation count: {}'.format(ops))
        stdscr.addstr(5, 4, rate)
        stdscr.refresh()

        # get the current frame
        current_frame = stack.pop()
        if len(current_frame) == 0:
            send(config.UNDO)
            hist.pop()
            continue

        move = current_frame.pop()

        # push the rest of the moves back onto stack
        stack.append(current_frame)

        # add th current move to the history
        hist.append(move_map[move])

        old_board = board_state(page)
        send(move)
        new_board = board_state(page)

        if game_won(new_board):

            stats = (
                "stats: \n"
                "    stack depth: {}\n"
                "    operation count: {}\n"
                .format(len(stack), ops))

            return stats, hist

        if board_changed(old_board, new_board):
            stack.append(list(moves))
        else:
            hist.pop()



def main():
    parser = argparse.ArgumentParser(
        description='this little program finds the solution '
                    'to the 2048 puzzle using a backtracking '
                    'algorithm. You can ask it to dump the '
                    'solution once it is done '
                    'note that this program assumes we\'re using '
                    'the original version with some kind of mod for '
                    'the undo')
    parser.add_argument('-g', '--game-url', type=str, metavar='uri',
        help='the game url')
    parser.add_argument('-t', '--target', type=int, metavar='n',
        help='the target tile')
    parser.add_argument('-o', '--out', metavar='file',
        help='save the result/solution to a file')

    args = parser.parse_args()
    if args.target:
        config.TARGET = args.target

    if args.game_url:
        config.GAME_URL = args.game_url

    page = selenium.webdriver.Firefox()
    page.get(config.GAME_URL)

    try:
        stats, hist = curses.wrapper(find, page)

        print stats

        if args.out:
            dump = generate_dump(page, hist)
            json.dump(dump, open(args.out, 'w'))

    except KeyboardInterrupt:
        print "exiting"


if __name__ == '__main__':
    main()