Day 17 feels familiar to a puzzle from 2021… day 15. Advent of Code 2021 - #48 by PHolder I struggled with that one, and I struggled again with this one. I looked at some other people’s Python solutions to get a hint about how to proceed. The approach I came up with uses a Heap (or a PriorityQueue in Java.)
I created a helper class HeatLossCalculator. It starts out solving by putting the start position on the heap twice, once for each possible departure (right or down.) Then as it pulls entries of the heap, it checks if it should keep going in the current direction, or check one of the other two. (Note how it gets the other two directions by flipping DX and DY and negates one of each.) As the values get higher, the heap presents them in lowest value first, and a minimizing (best fit) approach keeps track of the best values we’ve seen as we go.
final class HeatLossCalculator
{
private record Coordinates(int x, int y) {}
private final int height;
private final int width;
private final Map<Coordinates, Integer> heatLossValues = new HashMap<>();
private final Coordinates goalCoordinates;
public HeatLossCalculator(final int height, final int width)
{
this.height = height;
this.width = width;
goalCoordinates = new Coordinates(width-1, height-1);
}
public void loadHeatLossValues(final String[] day17InputLines)
{
for (int y=0; y<height; y++)
{
for (int x=0; x<width; x++)
{
final Coordinates c = new Coordinates(x, y);
heatLossValues.put(c, day17InputLines[y].charAt(x)-'0');
}
}
}
private record Dir(int dx, int dy) {}
private record Node(Coordinates coordinates, int numInDir, Dir dir) {}
private record NodeAndHeatLoss(int heatLoss, Node node) {}
public long findLowestHeatLoss(final int minInDirection, final int maxInDirection)
{
final PriorityQueue<NodeAndHeatLoss> heap = new PriorityQueue<>(new Comparator<NodeAndHeatLoss>()
{
@Override
public int compare(final NodeAndHeatLoss o1, final NodeAndHeatLoss o2)
{
return o1.heatLoss - o2.heatLoss;
}
});
final Coordinates startCoordinates = new Coordinates(0, 0);
final Set<Node> visited = new HashSet<>();
Node reachedTarget = new Node(new Coordinates(-1,-1), -1, new Dir(0,0));
final Node start1 = new Node(startCoordinates, 0, new Dir(1,0));
final Node start2 = new Node(startCoordinates, 0, new Dir(0,1));
heap.add(new NodeAndHeatLoss(0, start1));
heap.add(new NodeAndHeatLoss(0, start2));
final Map<Node, Integer> minHeatLoss = new HashMap<>();
minHeatLoss.put(start1, 0);
minHeatLoss.put(start2, 0);
while (!heap.isEmpty())
{
final NodeAndHeatLoss nodeAndHeatloss = heap.remove();
final Node node = nodeAndHeatloss.node;
if (visited.contains(node)) continue;
visited.add(node);
if (node.coordinates.equals(goalCoordinates) && (node.numInDir() > minInDirection-1))
{
reachedTarget = node;
break;
}
final NodeAndHeatLoss[] paths = probeNeighbours(node, minInDirection, maxInDirection);
for (final NodeAndHeatLoss pathNode : paths)
{
if (visited.contains(pathNode.node)) continue;
final int newHeatLoss = minHeatLoss.get(node) + pathNode.heatLoss;
if (!minHeatLoss.containsKey(pathNode.node) || (newHeatLoss < minHeatLoss.get(pathNode.node)))
{
minHeatLoss.put(pathNode.node, newHeatLoss);
heap.add(new NodeAndHeatLoss(newHeatLoss, pathNode.node));
}
}
}
if (reachedTarget.numInDir < 0) throw new IllegalStateException("Did not resolve an answer");
return minHeatLoss.get(reachedTarget);
}
private NodeAndHeatLoss[] probeNeighbours(final Node node, final int minInDirection, final int maxInDirection)
{
final List<NodeAndHeatLoss> result = new ArrayList<>();
final int x = node.coordinates.x;
final int y = node.coordinates.y;
final Dir dir = node.dir;
final int numInDir = node.numInDir;
final int dx = dir.dx;
final int dy = dir.dy;
final Dir dir1 = new Dir(-dy, dx);
final Dir dir2 = new Dir(dy, -dx);
if ((numInDir < maxInDirection) && onGrid(x+dx, y+dy))
{
final Coordinates newCoordinates = new Coordinates(x+dx, y+dy);
final Node newNode = new Node(newCoordinates, numInDir+1, dir);
result.add(new NodeAndHeatLoss(heatLossValues.get(newCoordinates), newNode));
}
if (numInDir > minInDirection-1)
{
if (onGrid(x+dir1.dx, y+dir1.dy))
{
final Coordinates newCoordinates = new Coordinates(x+dir1.dx, y+dir1.dy);
final Node newNode = new Node(newCoordinates, 1, dir1);
result.add(new NodeAndHeatLoss(heatLossValues.get(newCoordinates), newNode));
}
if (onGrid(x+dir2.dx, y+dir2.dy))
{
final Coordinates newCoordinates = new Coordinates(x+dir2.dx, y+dir2.dy);
final Node newNode = new Node(newCoordinates, 1, dir2);
result.add(new NodeAndHeatLoss(heatLossValues.get(newCoordinates), newNode));
}
}
return result.toArray(new NodeAndHeatLoss[0]);
}
private boolean onGrid(final int x, final int y)
{
if (x<0) return false;
if (y<0) return false;
if (x>width-1) return false;
if (y>height-1) return false;
return true;
}
}
Which made the part 1 and part 2 methods very easy to write, especially since I had the foresight to include minimum and maximum values:
public static Long part1(final String[] day17InputLines)
{
final HeatLossCalculator hlc = new HeatLossCalculator(day17InputLines.length, day17InputLines[0].length());
hlc.loadHeatLossValues(day17InputLines);
return hlc.findLowestHeatLoss(0, 3);
}
public static Long part2(final String[] day17InputLines)
{
final HeatLossCalculator hlc = new HeatLossCalculator(day17InputLines.length, day17InputLines[0].length());
hlc.loadHeatLossValues(day17InputLines);
return hlc.findLowestHeatLoss(4, 10);
}