Skip to content

Instantly share code, notes, and snippets.

@mstepniowski
Created January 20, 2013 00:32
Show Gist options
  • Save mstepniowski/3947539c9905898c8480 to your computer and use it in GitHub Desktop.
Save mstepniowski/3947539c9905898c8480 to your computer and use it in GitHub Desktop.
My little Python helper for http://adventure.cueup.com/
#########
# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment