diff options
| -rw-r--r-- | archer.py | 4 | ||||
| -rw-r--r-- | buckets.py | 53 |
2 files changed, 32 insertions, 25 deletions
@@ -33,8 +33,8 @@ def tile_to_coords(tile, cols=13): def build_tile_graph(grid, cost_map): rows, cols = len(grid), len(grid[0]) g = defaultdict(list) - directions_even = [(-1,0),(-1,1),(0,-1),(0,1),(1,0),(1,1)] - directions_odd = [(-1,-1),(-1,0),(0,-1),(0,1),(1,-1),(1,0)] + directions_even = [(-1,-1),(-1,0),(0,-1),(0,1),(1,-1),(1,0)] + directions_odd = [(-1,0),(-1,1),(0,-1),(0,1),(1,0),(1,1)] for i in range(rows): for j in range(cols): @@ -2,34 +2,41 @@ import sys from collections import deque -def measure_one(x, y): - #perform bfs - start = (0, 0) - queue = deque([(start, [])]) - visited = {start} - - while queue: - (a, b), path = queue.popleft() - # check if goal was reached - if a == 1 or b == 1: - return path + [(a, b)] +def build_jug_graph(cap1, cap2): + from collections import defaultdict + G = defaultdict(list) - # all possible moves from (a,b) + for a in range(cap1+1): + for b in range(cap2+1): ops = [ - ((x, b), 'fill left'), - ((a, y), 'fill right'), - ((0, b), 'empty left'), - ((a, 0), 'empty right'), - ((max(0, a - (y - b)), min(y, a + b)), 'pour left to right'), - ((min(x, a + b), max(0, b - (x - a))), 'pour right to left'), + ((cap1, b), 'fill left'), + ((a, cap2), 'fill right'), + ((0, b), 'empty left'), + ((a, 0), 'empty right'), + ((max(0, a - (cap2-b)), min(cap2, a+b)), 'transfer left to right'), + ((min(cap1, a + b), max(0, b-(cap1-a))), 'transfer right to left'), ] + G[(a,b)] = ops + + return G + +def measure_one(cap1, cap2): + G = build_jug_graph(cap1, cap2) + start = (0,0) + q = deque([ (start, []) ]) + seen = {start} + + while q: + (a,b), path = q.popleft() + if a == 1 or b == 1: + return path + [(a,b)] - for state, op in ops: - if state not in visited: - visited.add(state) - queue.append((state, path + [(a, b, op)])) + for (nxt, op) in G[(a,b)]: + if nxt not in seen: + seen.add(nxt) + q.append((nxt, path + [(a, b, op)])) - return None # no solution + return None if __name__ == "__main__": # parse command line arguments |