mstepniowski · January 20, 2013 00:32 · Jan 20, 2013
diff --git a/adventure.py b/adventure.py
@@ -0,0 +1,190 @@
+#########
+# 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