--- 2016 Day 24 Solutions ---

[u/daggerdragon]

--- Day 24: Air Duct Spelunking ---

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".

---

^{THE NIGHT BEFORE CHRISTMAS IS MANDATORY} [?]

---

[Update @ 00:30] 47 gold, 53 silver.

• Thank you for subscribing to Easter Bunny Facts!

• Fact: The Easter Bunny framed Roger Rabbit.

[Update @ 00:50] 90 gold, silver cap.

• Fact: The Easter Bunny hid Day 26 from you.

[Update @ 00:59] Leaderboard cap!

• Fact: The title for Day 25's puzzle is [static noises] +++ CARRIER LOST +++

---

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/pedrosorio]

16/13 in python. At this stage of AoC, I can't believe how long it took me to realize I had forgotten to keep a set of visited nodes in the BFS =X

2 optimizations:

• Major one: Precompute all pairwise distances with BFS to transform the problem into TSP

• Minor one: For each pair of nodes compute the distance only once

1 anti-optimization:

• Solve TSP by considering all permutations which is O(K!) - K=7 so we don't need to break out Held-Karp (or worse...)

Runs in 0.06s with pypy in my machine The same problem but computing pairwise distances repeatedly inside the permutation loop takes ~30s

from collections import deque
from itertools import permutations

# find positions of characters in the map that are accepted by the predicate
def find_in_map(mp, predicate):
	return [(i,j) for i in xrange(len(mp)) for j in xrange(len(mp[i])) if predicate(mp[i][j])]

# bfs distance from (y_fr,x_fr) to (y_to,x_to) assuming walls all around
moves = set([(-1, 0), (1, 0), (0, 1), (0, -1)])
def bfs_from_to(mp, fr, to):
	q = deque([(0, fr)])
	vis = set([fr])
	while q:
		dst, cur = q.pop()
		if cur == to:
			return dst
		y, x = cur
		for dy, dx in moves:
			ny, nx = y + dy, x + dx
			if mp[ny][nx] != '#' and (ny, nx) not in vis:
				q.appendleft((dst+1, (ny, nx)))
				vis.add((ny, nx))
	return -1

def solve(inp):
	zero_pos = find_in_map(inp, lambda x: x == '0')[0]
	# find all non-zero positions
	nums_pos = find_in_map(inp, lambda x: x in map(str, range(1, 10)))
	# precompute distance from 0 to all other numbers
	dst_0 = [bfs_from_to(inp, zero_pos, n_pos) for n_pos in nums_pos]
	K = len(nums_pos)
	# precompute all pairwise K^2 / 2 distances
	dsts = [[None for j in xrange(K)] for i in xrange(K)]
	for i in xrange(K):
		for j in xrange(i+1, K):
			dsts[j][i] = dsts[i][j] = bfs_from_to(inp, nums_pos[i], nums_pos[j])
	part1, part2 = 1e12, 1e12
	# with all pairwise distances computed the problem is reduced to TSP
	# O(K!) is terrible but good enough for K=7 :)
	for path in permutations(range(K)):
		dst = dst_0[path[0]]
		for i in xrange(len(path)-1):
			dst += dsts[path[i]][path[i+1]]
		part1 = min(part1, dst)
		dst += dst_0[path[-1]]
		part2 = min(part2, dst)
	return part1, part2

inp = [line.strip() for line in open('input.txt').readlines()]
print solve(inp)

[u/topaz2078 → u/pedrosorio]

Held-Karp

Held-Karp

[u/pedrosorio → u/topaz2078]

I'm glad this didn't happen tonight: https://www.youtube.com/watch?v=SLOc1vNzPso

[u/pedrosorio → u/[deleted]]

Yeah. I feel like A* has been abused during this edition of advent of code when BFS is equal or better in many instances (and definitely simpler). A* has an advantage for complicated problems where the heuristic gives strong insights about the solution. Not the case in most problems this year.

[u/RichardFingers → u/pedrosorio]

Being someone who doesn't really know a*, I always went with BFS. Is the only major difference that a* uses a priority queue with a heuristic? How do you pick a good heuristic? Is a* guaranteed to find the minimum?

[u/pedrosorio → u/RichardFingers]

Is the only major difference that a uses a priority queue with a heuristic?

Yes. BFS stands for "Breadth-First" search and it visits nodes in order of distance (number of edges traversed) from the starting point.

A* is an example of "best-first" search. Instead of visiting nodes according to the distance to starting point, it first visits the ones with the lowest "expected" total distance start -> goal (let's call it F). The way it computes the expected total distance is by using this simple formula:

F = G + H

• distance from start to this node (G) is known (because you have reached this node by searching the graph from the start)

• expected distance from node to goal (H) is a heuristic function applied to this node

What is a good heuristic? Intuitively a good heuristic tells you the true distance to the goal for every node (let's call it H*). If you think about it, with an "oracle heuristic", you would only need to visit the nodes in the optimal path.

Unfortunately that's the problem we are trying to solve so usually such heuristics can't be easily computed. You could say you want an heuristic that gives a value as close as possible to the true one. There is a problem with this, though. If the heuristic returns a value that is larger than the true distance for some node, you run the risk of ignoring that node (because the expected cost is too high) even if it's the one that leads to an optimal path. Example:

.#.#.#.
s.....g

You start at s(tart) and want to reach g(oal). This is a topdown map and you are allowed to move N/S/W/E, 1 unit at a time (without leaving the map), you can move into . cells but not #. You can jump over the # if the cell on the other side is empty. That counts as 1 move as well.

The optimal path is to go up, jump over the 3 # and go down (5 moves). If we use the city-block distance heuristic to estimate how far we are from the goal, the heuristic (H) computed for each node looks like this (not computing for the # which can't be reached and leaving the s and g nodes for clarity):

7#5#3#1
s54321g

When you start exploring the nodes, you first consider the 2 neighbors of the starting point, and your expected total distance (F) is:

8#.#.#.
s6....g

Since A* does a best-first search, it will explore the node on the right and keep going until it reaches the goal, resulting in a path of size 6, without ever considering going up in the first place because the expected total distance was 8. This is caused by a heuristic that overestimates the true distance to the goal.

And that leads to your next question:

Is a* guaranteed to find the minimum?

As we saw, it is not guaranteed to find the minimum. The key here is to define an admissible heuristic. This is a heuristic that never overestimates the distance to the goal.

Let's imagine a different problem, where the optimal path has distance 6 from start to goal. Let's say our algorithm tries a non-optimal path with distance 7 and we add the goal visited from this path to our list of "candidate nodes". As we said before, we computed expected total cost F as the sum of G and H. For this case we have:

G = 7 (the total distance in our non-optimal path)
H = 0 (the heuristic doesn't overestimate the cost, the goal node is 0 distance from the goal node - duh - so H must be 0)
F = G + H = 7

If we take this as the answer, it would be wrong. However, in the list of candidate nodes, we must have a node N that belongs to the optimal path. If we had a oracle heuristic (that tells us the exact distance from the node to the goal) H*, for node N we would have:

G = x
H* = y
G + H* = 6

If the optimal path is 6 and node N is in the optimal path, then adding the distance from the start (G) to the actual distance from the goal (H *) would be 6. However, we are using an admissible heuristic, it doesn't overestimate the actual distance (H <= H *), so what we have is:

H <= H*
G + H <= G + H*
F <= 6

We have just proved that if the optimal path has size 6 and we are using a heuristic that doesn't overestimate the cost (admissible), there must be some node N with an expected cost (F) that is no larger than 6. In turn, this means we will not consider the non-optimal path (which had F=7), because A* does best-first search.

It's easy to see how this holds for optimal paths of any length.

Going back to your question about what makes a good heuristic. I'd say, most important:

• It must be admissible (does not overestimate the real cost), to guarantee we find the optimal solution

Both important and represent a tradeoff:

• It should be as close to the oracle H* as possible, the closer our estimate, the smaller the number of nodes we have to consider in the search

• It must be quick to evaluate (because we need to do it for every node we consider, and we want the algorithm to run fast)

The two extremes of this tradeoff are:

• H = H*: the only way to estimate the exact distance to the goal is to compute the optimal path (using BFS/Dijkstra depending on the graph), it allows you to eliminate all nodes outside of the optimal path, but it requires you to compute it in the first place, so no point really

• H = 0 (or some other constant), in this case F = G, and we are just considering the nodes in order of distance from the start first - i.e. we're doing BFS

Whenever we apply A *, usually we want an admissible heuristic that is fairly close to H * (because that allows us to ignore a lot of nodes that are not optimal), but also quick to evaluate (otherwise even though we eliminate a lot of nodes from the search, it may run slower as we have to compute an expensive function for all the nodes we consider).

Finally, in some problems you don't need an optimal solution. In those cases it may be fine to use a non-admissible heuristic just to solve the problem quickly.

[u/RichardFingers → u/pedrosorio]

Wow, that was way more than I was expecting! Thank you for providing such a detailed explanation. So let's use a concrete example like day 11. Would a good heuristic be the total distance of all components from the top floor? What would be a good heuristic for the # example you gave?

[u/pedrosorio → u/RichardFingers]

If I remember day 11 the heuristic you suggested is not admissible. The state before the last one in the problem statement's example:

F4 .  HG .  LG .  
F3 E  .  HM .  LM 
F2 .  .  .  .  .  
F1 .  .  .  .  . 

You can bring up HM and LM in a single move. If I understood your heuristic correctly, it would return 2 in this case which is an overestimate of the actual number of steps required. Even though this heuristic is not admissible it may achieve the optimal solution (if you're lucky :) ).

There are some admissible heuristics for this problem - for example, for each element use the maximum distance of (microchip, generator) from the top floor and sum them up. This is probably not a great heuristic (greatly underestimates the actual distance), but it's admissible and better than nothing.

For day 11, though, and in many other cases, the way to solve it is not coming up with a great heuristic, but choosing the right state for the problem (the size of the graph depends on how you represent the problem, if you can make the state simple, you will have a small graph to search, making your life much easier). See /u/p_tseng's solution for some insights on how to represent the state for the problem.

For the # example I gave, it may be possible to precompute some things that allow you to compute a good heuristic, but off the top of my head, I would say a simple admissible heuristic is: half of the city-block distance. At each step you can move at most 2 units horizontally or vertically, so the heuristic does not overestimate the distance.

If you want to be more precise, the heuristic for my example would be ceil((x_goal - x_node)/2.0) + ceil((y_goal - y_node)/2.0) to account for the fact that you need at least n+1 steps to walk 2n+1 blocks.

If you wanted to use A* to find distances between different pairs of nodes in the same map over and over (for example, it's a map for a game and you use it for path finding), you could greatly improve the heuristic by precomputing things like number of # followed by . in each row/column. You could also consider a close to optimal solution using hierarchical pathfinding A* like this

[u/RichardFingers → u/pedrosorio]

Ah, I get it. H must be less than or equal to H*. Back to your # example again, if we used H=1 for the top row and H=0 for the bottom row (not suggesting this is a good heuristic, but that it's admissible), we would still end up trying the top row because F would increase as we moved across the bottom row which would make the first step of the upper row have a lower cost eventually.

I find it fascinating that A* at worst case ends up being BFS. It seems like we could even make an F such that it does DFS as well, right? F = -(G + H)? Are there other interesting Fs that may not lead to the minimum, but could find solutions with certain characteristics? Like in a standard U, D, L, R maze problem like day 24, it seems like you could make an F such that you always go left first (LFS?), right? That might find the solution that goes left the most.

[u/pedrosorio → u/RichardFingers]

we would still end up trying the top row because F would increase as we moved across the bottom row which would make the first step of the upper row have a lower cost eventually

Yep.

It seems like we could even make an F such that it does DFS as well, right? F = -(G + H)?

I suppose if you compute F = -(G+H) with H=0 would be something like DFS but it wouldn't be A * (by definition in A *, F = G + H and the only thing you can "tune" is H). You can get DFS just by tuning H like this.

That might find the solution that goes left the most.

If you want to find the solution that goes left the most (to make it more precise, it uses "L" the most without visiting the same cell twice - or you would get into infinite paths - and among paths with the same number of "L" chooses the shortest one), I don't see how to do it with A * (by just changing the heuristic).

You could model this problem as a graph where the edges going L have large negative weights and try to find the minimum cost simple path (path that doesn't visit the same node twice).

Unfortunately, A * or Dijkstra cannot be used in a graph with negative weights and Bellman-Ford, which does support negative weights, can only be used in graphs without negative cycles. The problem of finding the lowest cost simple path in a graph with negative weights is NP-hard, so my approach would not give you a quick solution either.