{{ message }}

Switch branches/tags
Nothing to show

Cannot retrieve contributors at this time
287 lines (206 sloc) 6.54 KB
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 import re import math import hashlib import operator from functools import total_ordering LETTERS = [x for x in 'abcdefghijklmnopqrstuvwxyz'] VOWELS = {'a', 'e', 'i', 'o', 'u'} CONSONANTS = set(x for x in LETTERS if x not in VOWELS) def parse_line(regex, line): ret = [] for match in re.match(regex, line).groups(): try: ret.append(int(match)) except ValueError: ret.append(match) return ret def parse_nums(line, negatives=True): num_re = r'-?\d+' if negatives else r'\d+' return [int(n) for n in re.findall(num_re, line)] def new_table(val, width, height): return [[val for _ in range(width)] for _ in range(height)] def transposed(matrix): """Returns the transpose of the given matrix.""" return [list(r) for r in zip(*matrix)] def rotated(matrix): """Returns the given matrix rotated 90 degrees clockwise.""" return [list(r) for r in zip(*matrix[::-1])] def mul(lst): """Like sum(), but for multiplication.""" return reduce(operator.mul, lst, 1) # NOQA def chunks(l, n): """Yield successive n-sized chunks from l.""" for i in range(0, len(l), n): yield l[i:i + n] def all_unique(lst): return len(lst) == len(set(lst)) def factors(n): """Returns the factors of n.""" return sorted( x for tup in ( [i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0) for x in tup) def gcd(a,b): """Compute the greatest common divisor of a and b""" while b > 0: a, b = b, a % b return a def lcm(a, b): """Compute the lowest common multiple of a and b""" return a * b / gcd(a, b) def min_max_xy(points): if len(points) == 0: return None, None, None, None if type(points[0]) == tuple: min_x = min(p[0] for p in points) max_x = max(p[0] for p in points) min_y = min(p[1] for p in points) max_y = max(p[1] for p in points) else: min_x = min(p.x for p in points) max_x = max(p.x for p in points) min_y = min(p.y for p in points) max_y = max(p.y for p in points) return min_x, max_x, min_y, max_y def print_grid(grid, f=None): if f is None: f = lambda x: x # NOQA if type(grid) is dict: positions = grid.keys() min_x, max_x, min_y, max_y = min_max_xy(positions) if type(positions[0]) is tuple: for y in range(min_y, max_y + 1): print ''.join(f(grid.get((x, y), ' ')) for x in range(min_x, max_x + 1)) else: # (x, y) => point for y in range(min_y, max_y + 1): print ''.join(f(grid.get(Point(x, y), ' ')) for x in range(min_x, max_x + 1)) else: for y in range(len(grid)): print ''.join(f(grid[y][x]) for x in range(len(grid[0]))) def memoize(f): """Simple dictionary-based memoization decorator""" cache = {} def _mem_fn(*args): if args not in cache: cache[args] = f(*args) return cache[args] _mem_fn.cache = cache return _mem_fn def _eratosthenes(n): """http://stackoverflow.com/a/3941967/239076""" # Initialize list of primes _primes = [True] * n # Set 0 and 1 to non-prime _primes[0] = _primes[1] = False for i, is_prime in enumerate(_primes): if is_prime: yield i # Mark factors as non-prime for j in xrange(i * i, n, i): # NOQA _primes[j] = False def primes(n): """Return a list of primes from [2, n)""" return list(_eratosthenes(n)) def md5(msg): m = hashlib.md5() m.update(msg) return m.hexdigest() def sha256(msg): s = hashlib.sha256() s.update(msg) return s.hexdigest() def knot_hash(msg): lengths = [ord(x) for x in msg] + [17, 31, 73, 47, 23] sparse = range(0, 256) pos = 0 skip = 0 for _ in range(64): for l in lengths: for i in range(l // 2): x = (pos + i) % len(sparse) y = (pos + l - i - 1) % len(sparse) sparse[x], sparse[y] = sparse[y], sparse[x] pos = pos + l + skip % len(sparse) skip += 1 hash_val = 0 for i in range(16): res = 0 for j in range(0, 16): res ^= sparse[(i * 16) + j] hash_val += res << ((16 - i - 1) * 8) return '%032x' % hash_val HEX_DIRS = { 'N': (1, -1, 0), 'NE': (1, 0, -1), 'SE': (0, 1, -1), 'S': (-1, 1, 0), 'SW': (-1, 0, 1), 'NW': (0, -1, 1), } def hex_distance(x, y, z): """Returns a given hex point's distance from the origin.""" return (abs(x) + abs(y) + abs(z)) // 2 @total_ordering class Point: """Simple 2-dimensional point.""" def __init__(self, x, y): self.x = x self.y = y def __add__(self, other): return Point(self.x + other.x, self.y + other.y) def __sub__(self, other): return Point(self.x - other.x, self.y - other.y) def __mul__(self, n): return Point(self.x * n, self.y * n) def __div__(self, n): return Point(self.x / n, self.y / n) def __neg__(self): return Point(-self.x, -self.y) def __eq__(self, other): return self.x == other.x and self.y == other.y def __ne__(self, other): return not self == other def __lt__(self, other): return self.length < other.length def __str__(self): return "({}, {})".format(self.x, self.y) def __repr__(self): return "Point({}, {})".format(self.x, self.y) def __hash__(self): return hash(tuple((self.x, self.y))) def dist(self, other): return math.sqrt((self.x - other.x) ** 2 + (self.y - other.y) ** 2) def dist_manhattan(self, other): return abs(self.x - other.x) + abs(self.y - other.y) def angle(self, to=None): if to is None: return math.atan2(self.y, self.x) return math.atan2(self.y - to.y, self.x - to.x) @property def manhattan(self): return abs(self.x) + abs(self.y) @property def length(self): return math.sqrt(self.x ** 2 + self.y ** 2) def neighbours_4(self): return [self + p for p in DIRS_4] def neighbours_8(self): return [self + p for p in DIRS_8] DIRS_4 = DIRS = [ Point(0, 1), # north Point(1, 0), # east Point(0, -1), # south Point(-1, 0), # west ] DIRS_8 = [ Point(0, 1), # N Point(1, 1), # NE Point(1, 0), # E Point(1, -1), # SE Point(0, -1), # S Point(-1, -1), # SW Point(-1, 0), # W Point(-1, 1), # NW ]