My little Python helper for http://adventure.cueup.com/

adventure.py

#########
# LEVEL 1
#########

RANDOM_SEQ = [6, 19, 16]


def vax_mth_random(seed):
    """VAX's MTH$RANDOM is a linear congruential generator. 

    It's form is: x_{n+1} = (a x_n + c) \mod m
    where a = 69069, c = 1, m = 2^32
    
    See:
     - http://en.wikipedia.org/wiki/Linear_congruential_generator
     - gsl_rng_vax from http://www.gnu.org/software/gsl/manual/html_node/Other-random-number-generators.html
    """
    n = seed
    while True:
        n = (69069 * n + 1) % 2**32
        yield n

# First three numbers from seed = 6 turned out to match the RANDOM_SEQ 


#########
# LEVEL 2
#########

### Parens
        
PARENS = """{{[{{{{}}{{}}}[]}[][{}][({[((
{{[][()()]}}{[{{{}}}]}))][()]
{[[{((()))({}(())[][])}][]()]
}{()[()]}]})][]]}{{}[]}}""".replace('\n', '')

PAREN_PAIRS = {'}': '{', ')': '(', ']': '['}


def find_error(parens):
    """Finds the index of the first error in paren sequence."""
    s = []

    for idx, paren in enumerate(parens):
        if paren in PAREN_PAIRS.values():
            s.append(paren)
        else:
            last_open_paren = s.pop()
            if last_open_paren != PAREN_PAIRS[paren]:
                return idx


### Map

MAP = """8 8 4 4 ^
         4 9 6 4 8
         8 6 4 1 2
         4 8 2 6 3
         * 6 8 8 4""".replace(' ', '').split('\n')


DIRECTIONS = {(0, 1): 'e',
              (0, -1): 'w',
              (1, 0): 's',
              (-1, 0): 'n'}


def find_char(map, char):
    for x, row in enumerate(map):
        for y, c in enumerate(row):
            if c == char:
                return x, y


def find_neighbours(map, x, y, money, t):
    result = []
    for i, j in DIRECTIONS.keys():
        if x + i < 0 or y + j < 0:
            continue
        try:
            map[x + i][y + j]
        except IndexError:
            pass
        else:
            if money >= get_cost(map, x + i, y + j, t):
                result.append((x + i, y + j, money - get_cost(map, x + i, y + j, t), t + 1)) 
    return result


def get_cost(map, x, y, t):
    if map[x][y] == '^':
        return 5
    elif map[x][y] == '*':
        return 0
    else:
        # Here t should be added only for bonus round calculations.
        # For non-bonus rounds, remove t.
        return int(map[x][y]) + t


def find_route(m, money):
    """Finds the route through the map m with cost equal to money.

    Returns transition table of moves searched through. To get only
    the moves leading to the goal, use follow_transitions.
    """
    start = find_char(m, '*')
    end = find_char(m, '^')

    visited = set([(start[0], start[1], 35, 0)])
    moves = find_neighbours(m, start[0], start[1], money, 0)
    transitions = {}
    
    while len(moves) > 0:
        x, y, money, t = moves.pop()
        if (x, y) == end and money == 0:
            # Reached goal
            return transitions
        else:
            visited.add((x, y, money, t))
            possible_moves = [move for move in find_neighbours(m, x, y, money, t)
                              if move not in visited]
            for move in possible_moves:
                transitions[move] = (x, y, money, t)
            moves.extend(possible_moves)


def follow_transitions(t, dest):
    result = [dest]
    while True:
        if t.get(result[-1]):
            result.append(t.get(result[-1]))
        else:
            return list(reversed(result))


from itertools import tee, izip

def pairwise(iterable):
    """pairwise([1, 2, 3, 4]) -> ([1, 2], [2, 3], [3, 4])"""
    a, b = tee(iterable)
    next(b, None)
    return izip(a, b)


def directions(moves):
    for m1, m2 in pairwise(moves):
        yield DIRECTIONS[(m2[0] - m1[0], m2[1] - m1[1])]


#############
# BONUS LEVEL
#############

### VAX's MTH$RANDOM

LONG_RANDOM_SEQ = [34, 27, 16, 1, 34, 31, 24, 17, 34, 35, 16, 13] 

# Brute force!

def next_three():
    random = vax_mth_random(6)
    results = []
    while results[-12:] != LONG_RANDOM_SEQ:
        results.append(next(random) % 36)
        if len(results) > 10000:
            results = results[-12:]
    return [next(random) for x in range(3)]

# Solution: [26, 19, 4]


### Map

LARGE_MAP = """* 8 1 7 8 8 5 2 9 5 9 5
               8 5 1 1 5 6 9 4 4 5 2 1
               7 2 3 5 2 9 2 6 9 3 9 4
               9 2 5 9 8 9 5 7 7 5 9 6
               2 4 6 7 1 4 2 6 6 2 5 8
               2 8 1 5 3 8 4 9 7 5 2 3
               2 9 3 5 6 7 2 4 9 4 2 5
               6 3 1 7 8 2 3 3 6 7 9 3
               2 5 7 4 2 7 8 5 5 3 5 8
               5 2 9 8 3 6 1 4 9 5 6 3
               4 6 9 8 5 4 9 7 6 4 6 8
               2 7 7 1 9 9 7 3 7 2 2 ^""".replace(' ', '').split('\n')

# Same algorithm as in the smaller case. Just add turn number to move cost.
#
# Solution: eeeeeeeeeeeweswssssessssss