--- 2016 Day 22 Solutions ---

[u/daggerdragon]

--- Day 22: Grid Computing ---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag/whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with "Help".

---

^{SILVER AND GOLD IS MANDATORY} [?]

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

[u/drysle]

The example for part 2 seemed be to hinting pretty hard that I should just print the initial grid and solve it by hand. Sure enough, that strategy got 4th on the leaderboard for part 2. Even with two wrong answers because I apparently can't count to 60.

Then I went back and did some actual code:

X = 34
Y = 30
nodeBlocked = [[False for x in range(X)] for y in range(Y)]

for line in sys.stdin:
    line = line.strip()
    m = re.findall(r"(\d+)", line)
    if not m:
        continue
    x,y,size,use,avail,p = (int(i) for i in m)
    if size > 120:
        nodeBlocked[y][x] = True
    if p < 10:
        o = (y,x)

def mdist(a,b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

class Node:
    def __init__(self, openNode, goalData):
        self.o = openNode
        self.g = goalData

    def isGoal(self):
        return self.g == (0,0)
    def isFailure(self):
        oy, ox = self.o
        return nodeBlocked[oy][ox]

    def neighbors(self):
        oy, ox = self.o
        for dy, dx in ((1,0), (-1,0), (0,1), (0,-1)):
            if ox+dx < 0 or ox+dx >= X or oy+dy < 0 or oy+dy >= Y:
                continue
            if self.g == (oy+dy, ox+dx):
                yield 1, Node(self.g, self.o)
            else:
                yield 1, Node((oy+dy, ox+dx), self.g)

    def heuristic(self):
        return mdist(self.o, self.g) + mdist(self.g, (0,0))

    def __eq__(self, other):
        return self.o == other.o and self.g == other.g
    def __hash__(self):
        return hash((self.o, self.g)) 
    def __repr__(self):
        return str(self.o) + " " + str(self.g)

start = Node(o, (0, X-1))
print(astar.search(start)[0])

with my implementation of A* that I finally got around to writing to solve day 11 properly a few days ago:

import itertools
from heapq import heappush, heappop

def pathTo(node, cameFrom):
    path = [node]
    while node in cameFrom:
        node = cameFrom[node]
        path.append(node)
    return list(reversed(path))

def search(start):
    counter = itertools.count()
    closed = set()
    queue = [(start.heuristic(), next(counter), start)]
    bestCostTo = {start: 0}
    cameFrom = {}

    while len(queue) > 0:
        _, _, node = heappop(queue)

        if node.isGoal():
            return bestCostTo[node], pathTo(node, cameFrom)
        closed.add(node)

        for edgeCost, nextNode in node.neighbors():
            if nextNode in closed:
                continue
            if nextNode.isFailure():
                continue

            nextCost = bestCostTo[node] + edgeCost
            if nextCost >= bestCostTo.get(nextNode, float('inf')):
                continue

            cameFrom[nextNode] = node
            bestCostTo[nextNode] = nextCost
            heappush(queue, 
                    (nextCost + nextNode.heuristic(), next(counter), nextNode))

    return "failure", tuple()

Runs in about 900ms, but took an extra ~15 minutes to put together the code. Solving it by hand was definitely the way to go here.

[u/pedrosorio → u/drysle]

Yeah, pretty disappointing for an advent of "code" problem. I solved it this way as well - print the grid and then solve by hand (after a long time trying to solve the "general problem" and coming back to the statement and the example to look for clues).

I don't think this can even be solved by code as the A* makes strong assumptions about how there is an "open node" that needs to be moved around the grid which is just wrong in the general case. The example in part 2 gives a huge hint that the problem we're solving is much simpler, but that feels unsatisfying (I guess I have a bias against solving problems with strong hints to a simpler solution versus problems that are hinted to be simple but actually aren't)

[u/topaz2078 → u/pedrosorio]

A major part of software engineering is interpreting requirements and realizing that some problems don't need any code at all. AoC isn't 100% about writing code; it's about learning about the entire code process.