travel_agent.py

""" The problem was solved on 1 core in 543m35.913s.
The best score was: 3354674163673461017691780032809373762464467910656
The best dice was: up: 6,  down: 3,  top: 1,  bottom: 6,  left: 8,  right: 7
The dice started with 1 on top and 3 on up
The route associated with the score and the dice is:
[(1, 1), (2, 1), (2, 2), (3, 2), (3, 3), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (2, 9), (2, 10), (1, 10), (1, 11), (    2, 11), (3, 11), (4, 11), (5, 11), (6, 11), (7, 11), (8, 11), (9, 11), (9, 10), (9, 9), (9, 8), (9, 7), (9, 6), (9, 5), (8, 5), (8,     4), (7, 4), (6, 4), (6, 5), (6, 6), (6, 7), (7, 7), (7, 8), (7, 9), (6, 9), (5, 9), (4, 9), (4, 8), (4, 7), (4, 6), (3, 6), (3, 5),     (4, 5), (5, 5), (5, 4), (4, 4), (4, 3), (4, 2), (5, 2), (6, 2), (7, 2), (8, 2), (9, 2), (9, 3), (10, 3), (10, 2), (10, 1), (11, 1),     (11, 2), (11, 3), (11, 4), (10, 4), (10, 5), (11, 5), (11, 6), (11, 7), (11, 8), (11, 9), (11, 10), (11, 11), (11, 12), (12, 12)]
"""

from itertools import product
from random import shuffle

table = None


def read_table():
    global table
    data = None
    with open('table', 'r') as f:
        data = f.readlines()
    
    table = []
    for line in data:
        table.append([])
        for cell in line.split():
            if cell == "n":
                val = None
            else:
                val = int(cell)
            table[-1].append(val)

UP, DOWN, LEFT, RIGHT = range(4)


class Dice(object):
    def __init__(
            self, top, left, down, right, up, bottom):
        self.up = up
        self.down = down
        self.left = left
        self.right = right
        self.top = top
        self.bottom = bottom
        self.attrs = ["up", "down", "top", "bottom", "left", "right"]

    def roll(self, direction):
        top = self.top
        assert direction in range(4)

        if direction == LEFT:
            self.top = self.right
            self.right = self.bottom
            self.bottom = self.left
            self.left = top
        elif direction == RIGHT:
            self.top = self.left
            self.left = self.bottom
            self.bottom = self.right
            self.right = top
        elif direction == DOWN:
            self.top = self.up
            self.up = self.bottom
            self.bottom = self.down
            self.down = top
        else: # direction == UP
            self.top = self.down
            self.down = self.bottom
            self.bottom = self.up
            self.up = top

    def __str__(self):
        return " ".join(["%s: %s, " % (attr, getattr(self, attr)) for attr in self.attrs])

    def __contains__(self, key):
        return any([getattr(self, attr) == key for attr in self.attrs])


moves = [RIGHT] + [DOWN] * 10 + [RIGHT] * 9 + [DOWN] + [RIGHT]
grow, gcol = 11, 11
mrow, mcol = 11, 11


def between(val, low, high):
    return val >= low and val <= high


def make_move(row, col, direction):
    if direction == DOWN:
        return (row + 1, col)
    elif direction == RIGHT:
        return (row, col + 1)
    elif direction == LEFT:
        return (row, col - 1)
    else: # direction == UP
        return (row - 1, col)


def opposite(direction):
    if direction == LEFT:
        return RIGHT
    elif direction == RIGHT:
        return LEFT
    elif direction == UP:
        return DOWN
    else: # direction == DOWN
        return UP

greach = 0
gmax = -1


def go(dice, table, row, col, was, curr, route):
    if grow == row and gcol == col:
        global greach 
        greach += 1
        global gmax
        gmax = max(curr, gmax)
        print "dice: %s" % (dice,)
        print "Reached the end %s times and the current best score is: %s" % (greach, gmax)
        print "route: %s" % ([(x[0] + 1, x[1] + 1) for x in route],)
        return curr * table[grow][gcol]
    
    orow, ocol = row, col
    ret = -1
    for direction in xrange(4):
        od = opposite(direction)
        row, col = make_move(row, col, direction)
        if not between(row, 0, mrow) or not between(col, 0, mcol):
            row, col = orow, ocol
            continue
        dice.roll(direction)
        tval = table[row][col]
        if not was[row][col] and (tval is None or tval == dice.top):
            was[row][col] = True
            curr *= dice.top
            route.append((row, col))
            ret = max(ret, go(dice, table, row, col, was, curr, route))
            route.pop()
            was[row][col] = False
            curr /= dice.top
        dice.roll(od)
        row, col = orow, ocol 

    return ret


def fill_dict(orig, filler):
    keys = ["top", "bottom", "up", "down", "left", "right"]
    fp = 0
    ret = {key:orig[key] for key in orig.keys()}
    for key in keys:
        if key not in ret:
            ret[key] = filler[fp]
            fp += 1
    return ret


if __name__ == "__main__":
    read_table()
    rc = len(table)
    cc = len(table[0])
    best = -1
    bases = [{"top": 1, "up": 3}, {"top": 1, "left": 5}]
    fillers = list(product(*[range(1, 10) for _ in xrange(4)]))
    shuffle(fillers)
    fillers = [[6, 6, 5, 4]] + fillers
    for filler in fillers:
        for base in bases:
            fd = fill_dict(base, filler)
            dice = Dice(**fd)
            if 3 not in dice and 7 not in dice:
                continue
            print "current dice: %s" % dice
            print "fd: %s" % (fd,)
            print "filler: %s" % (filler,)
            row, col = 0, 0
            was = [[False for _2 in xrange(cc)] for _ in xrange(rc)]
            was[0][0] = True
            curr = 1
            route = [(0, 0)]
            val = go(dice, table, row, col, was, curr, route)
            if val >  best:
                best = val
                print "new best: %s" % best
                print "best dice: %s" % dice

    print "best: %s" % (best,)


""" The contents of the 'table' file is:
1 5 4 4 6 1 1 4 1 3 7 5
3 n n n n n n n n n n 1
4 n 6 4 1 8 1 4 2 1 n 3
7 n 1 n n n n n n 1 n 2
1 n 1 n 6 1 6 2 n 2 n 1
8 n 4 n 1 n n 8 n 3 n 5
4 n 2 n 5 n n 3 n 5 n 2
8 n 5 n 1 1 2 3 n 4 n 6
6 n 1 n n n n n n 3 n 6
3 n 6 3 6 5 4 3 4 5 n 1
6 n n n n n n n n n n 3
2 1 6 6 4 5 2 1 1 1 7 1
"""