In [1]:

    

# python imports
import re
import numpy as np
import math
import urllib.request

from collections import Counter, defaultdict, namedtuple, deque
from functools import lru_cache
from itertools import permutations, combinations, chain, cycle, product, islice
from heapq import heappop, heappush

def Input(day):
    """Open this day's input file."""
    filename = 'advent2016/input{}.txt'.format(day)
    try:
        return open(filename)
    except FileNotFoundError:
        return urllib.request.urlopen("http://norvig.com/ipython/" + filename)
    
def transpose(matrix):
    return zip(*matrix)

def first(iterable):
    return next(iter(iterable))

def nth(iterable, n, default=None):
    """Returns the nth item of iterable, or a default value"""
    return next(islice(iterable, n, None), default)

cat = "".join
Ø   = frozenset() # Empty set
inf = float('inf')
BIG = 10 ** 999


    

In [2]:

    

def grep(pattern, lines):
    """Print lines that match pattern."""
    for line in lines:
        if re.search(pattern, line):
            print(line)

            
def groupby(iterable, key=lambda it: it):
    """Return a dic whose keys are key(it) and whose values are all the elements of iterable with that key."""
    dic = defaultdict(list)
    for it in iterable:
        dic[key(it)].append(it)
    return dic


def powerset(iterable):
    """Yield all subsets of items."""
    items = list(iterable)
    for r in range(len(items)+1):
        for c in combinations(items, r):
            yield c
            

# 2-D points implemented using (x, y) tuples
def X(point): return point[0]
def Y(point): return point[1]

def neighbors4(point): 
    "The four neighbors (without diagonals)."
    x, y = point
    return ((x+1, y), (x-1, y), (x, y+1), (x, y-1))

def neighbors8(point): 
    "The eight neighbors (with diagonals)."
    x, y = point 
    return ((x+1, y), (x-1, y), (x, y+1), (x, y-1),
            (X+1, y+1), (x-1, y-1), (x+1, y-1), (x-1, y+1))

def cityblock_distance(p, q=(0, 0)): 
    "City block distance between two points."
    return abs(X(p) - X(q)) + abs(Y(p) - Y(q))

def euclidean_distance(p, q=(0, 0)): 
    "Euclidean (hypotenuse) distance between two points."
    return math.hypot(X(p) - X(q), Y(p) - Y(q))

def trace1(f):
    "Print a trace of the input and output of a function on one line."
    def traced_f(*args):
        result = f(*args)
        print('{}({}) = {}'.format(f.__name__, ', '.join(map(str, args)), result))
        return result
    return traced_f

def astar_search(start, h_func, moves_func):
    "Find a shortest sequence of states from start to a goal state (a state s with h_func(s) == 0)."
    frontier  = [(h_func(start), start)] # A priority queue, ordered by path length, f = g + h
    previous  = {start: None}  # start state has no previous state; other states will
    path_cost = {start: 0}     # The cost of the best path to a state.
    while frontier:
        (f, s) = heappop(frontier)
        if h_func(s) == 0:
            return Path(previous, s)
        for s2 in moves_func(s):
            new_cost = path_cost[s] + 1
            if s2 not in path_cost or new_cost < path_cost[s2]:
                heappush(frontier, (new_cost + h_func(s2), s2))
                path_cost[s2] = new_cost
                previous[s2] = s
    return dict(fail=True, front=len(frontier), prev=len(previous))
                
def Path(previous, s): 
    "Return a list of states that lead to state s, according to the previous dict."
    return ([] if (s is None) else Path(previous, previous[s]) + [s])


    

In [4]:

    

assert tuple(transpose(((1, 2, 3), (4, 5, 6)))) == ((1, 4), (2, 5), (3, 6))
assert first('abc') == first(['a', 'b', 'c']) == 'a'
assert cat(['a', 'b', 'c']) == 'abc'
assert (groupby(['test', 'one', 'two', 'three', 'four'], key=len) 
        == {3: ['one', 'two'], 4: ['test', 'four'], 5: ['three']})


    

In [8]:

    

print(list(powerset(['a', 'b', 'c', 'd'])))


    

    




[(), ('a',), ('b',), ('c',), ('d',), ('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd'), ('a', 'b', 'c'), ('a', 'b', 'd'), ('a', 'c', 'd'), ('b', 'c', 'd'), ('a', 'b', 'c', 'd')]

In [ ]: