So, I did the brute force at first with part 2, and it seems the numbers got too big for JavaScript’s BigInt type.
[edit] I just remember something. Because I used BigInt in part 2 to brute force, when I figured out a way to solve it, the method I used still required BigInt. JavaScript has a safe max integer size of 2^53 - 1, and when I briefly switched away from BigInt, my total was off. Of all the days I have done so far, I think this is the first year I was required to use BigInt.
What to say about Day 12. Ascending hills that become mountains, I guess. This is a cutesy question that, like Day 15 of 2021, is just a wrapper around a graph problem and the Dijkstra least path (BFS) algorithm.
I spent way too long on this. I didn’t recognize what I should have (see spoiler above) until way to late in the effort. Accordingly, I coded a brute force solution that worked great for the tiny example input, but went exponential for the large actual input. I am leaving both parts of the code in place for my post, so that maybe someone can learn from my folly.
In an effort to assist understanding what I wrote, I’m presenting the code in an order different from how I actually coded it. So the first thing is the 2nd solver, that I referred to as “Optimized” versus the “BruteForce” one. I used a second class for the breadth first search, in hopes, when I see it again in the future, I can easily rework the code. I called this class MapDistanceSolver. The MapHandler class at the bottom more logically belongs as an Interface and instantiated in the caller, but I left it here to make future reuse possibly easier (moving one file instead of one and parts from another. optimizeMap() is really the method doing most of the work implement the BFS.
final class MapDistanceSolver
{
private static final int INFINITE_DISTANCE = 10_000;
private final MapHandler mapHandler;
private final int[][] distanceFill;
private final int width;
private final int height;
private final Coordinates startCoordinates;
private final Coordinates endCoordinates;
public MapDistanceSolver(final MapHandler mapHandler)
{
this.mapHandler = mapHandler;
this.width = mapHandler.getWidth();
this.height = mapHandler.getHeight();
distanceFill = new int[width][height];
startCoordinates = mapHandler.getStartCoordinates();
endCoordinates = mapHandler.getEndCoordinates();
}
long getShortestPath()
{
fillMap();
optimizeMap();
return distanceFill[endCoordinates.getX()][endCoordinates.getY()];
}
private void fillMap()
{
for (int y=0; y<height; y++)
for (int x=0; x<width; x++)
distanceFill[x][y] = INFINITE_DISTANCE;
distanceFill[startCoordinates.getX()][startCoordinates.getY()] = 0;
}
private void optimizeMap()
{
final Deque<Coordinates> coordsYetToProcess = new ArrayDeque<>();
final Set<Coordinates> coordsAlreadyProcessed = new HashSet<>();
coordsYetToProcess.addLast(startCoordinates);
while (!coordsYetToProcess.isEmpty())
{
final Coordinates curCoord = coordsYetToProcess.removeFirst();
if (coordsAlreadyProcessed.contains(curCoord)) continue;
coordsAlreadyProcessed.add(curCoord);
int curDist = distanceFill[curCoord.getX()][curCoord.getY()];
final Set<Coordinates> neighbours = mapHandler.getNeighbours(curCoord);
for (final Coordinates neighbour : neighbours)
{
final int neighbourDist = distanceFill[neighbour.getX()][neighbour.getY()];
if (neighbourDist == INFINITE_DISTANCE)
{
distanceFill[neighbour.getX()][neighbour.getY()] = curDist+1;
coordsYetToProcess.addLast(neighbour);
}
}
}
}
public static final class MapHandler
{
private final int[][] map;
private final int width;
private final int height;
final Coordinates startCoordinates;
final Coordinates endCoordinates;
public MapHandler(final int[][] map, final int width, final int height, final Coordinates startCoordinates, final Coordinates endCoordinates)
{
this.map = map;
this.width = width;
this.height = height;
this.startCoordinates = startCoordinates;
this.endCoordinates = endCoordinates;
}
public Coordinates getEndCoordinates()
{
return endCoordinates;
}
public int getWidth()
{
return width;
}
public int getHeight()
{
return height;
}
public Coordinates getStartCoordinates()
{
return startCoordinates;
}
private Set<Coordinates> getNeighbours(final Coordinates coordinatesToGetNeighboursOf)
{
final Set<Coordinates> neighbours = new HashSet<>();
final int x = coordinatesToGetNeighboursOf.getX();
final int y = coordinatesToGetNeighboursOf.getY();
final int heightAt = map[x][y];
if (x>0)
{
final int westHeight = map[x-1][y];
if (westHeight <= heightAt+1)
{
neighbours.add(new Coordinates(x-1, y));
}
}
if (x<width-1)
{
final int eastHeight = map[x+1][y];
if (eastHeight <= heightAt+1)
{
neighbours.add(new Coordinates(x+1, y));
}
}
if (y>0)
{
final int northHeight = map[x][y-1];
if (northHeight <= heightAt+1)
{
neighbours.add(new Coordinates(x, y-1));
}
}
if (y<height-1)
{
final int southHeight = map[x][y+1];
if (southHeight <= heightAt+1)
{
neighbours.add(new Coordinates(x, y+1));
}
}
return neighbours;
}
}
}
This class HeightMap was my first attempt to solve the problem. In its current state it contains the “BruteForce” solution, and calls out to the MapDistanceSolver above to solve the “Optimized” way. I even tried converting the map[][] to an actual graph in convertMapToGraph(). Some members and methods are marked with comments that they’re for part 2. Since part2 is really just finding a minimum over multiple iterations of part 1, I am not going to call it out separately beyond these comments.
final class HeightMap
{
private final int width;
private final int height;
private final int heights[][];
private final Coordinates startCoordinates;
private final Coordinates endCoordinates;
private Node startNode = Node.INVALID_NODE;
private final Set<Coordinates> allLowestCoordinates = new HashSet<>(); // For part 2
public HeightMap(final String[] day12InputLines)
{
width = day12InputLines[0].length();
height = day12InputLines.length;
heights = new int[width][height];
Coordinates startCoordinates = Coordinates.INVALID_COORDINATES;
Coordinates endCoordinates = Coordinates.INVALID_COORDINATES;;
for(int y=0; y<height; y++)
{
for (int x=0; x<width; x++)
{
char c = day12InputLines[y].charAt(x);
if (c == 'S')
{
startCoordinates = new Coordinates(x,y);
startNode = new Node(startCoordinates);
c='a';
}
else if (c == 'E')
{
endCoordinates = new Coordinates(x,y);
c='z';
}
if (c == 'a') // for part 2
{
allLowestCoordinates.add(new Coordinates(x,y));
}
heights[x][y] = c -'a' + 1;
}
}
if (startCoordinates == Coordinates.INVALID_COORDINATES)
throw new IllegalStateException("No start coordinates found.");
if (endCoordinates == Coordinates.INVALID_COORDINATES)
throw new IllegalStateException("No end coordinates found.");
this.startCoordinates = startCoordinates;
this.endCoordinates = endCoordinates;
convertMapToGraph();
}
// For part 2
public Set<Coordinates> getAllLowestCoordinates()
{
return allLowestCoordinates;
}
private void convertMapToGraph()
{
final Map<Coordinates, Node> nodeCoordinates = new HashMap<>();
nodeCoordinates.put(startNode.getCoordinates(), startNode);
for(int y=0; y<height; y++)
{
for (int x=0; x<width; x++)
{
final Coordinates coord = new Coordinates(x,y);
if (!coord.equals(startCoordinates))
{
final Node node = new Node(coord);
if (coord.equals(endCoordinates))
{
node.setNodeAsTerminal();
}
nodeCoordinates.put(coord, node);
}
}
}
for(int y=0; y<height; y++)
{
for (int x=0; x<width; x++)
{
final Coordinates coord = new Coordinates(x,y);
final Node node = nodeCoordinates.get(coord);
final int heightHere = heights[x][y];
final Coordinates northCoordinates = coord.clone(); northCoordinates.moveUp();
if (nodeCoordinates.containsKey(northCoordinates))
{
final int northHeight = getHeightAt(northCoordinates);
if ((northHeight == heightHere) || (northHeight == heightHere+1))
{
final Node northNode = nodeCoordinates.get(northCoordinates);
node.setNorthNode(northNode);
}
}
final Coordinates eastCoordinates = coord.clone(); eastCoordinates.moveRight();
if (nodeCoordinates.containsKey(eastCoordinates))
{
final int eastHeight = getHeightAt(eastCoordinates);
if ((eastHeight == heightHere) || (eastHeight == heightHere+1))
{
final Node eastNode = nodeCoordinates.get(eastCoordinates);
node.setEastNode(eastNode);
}
}
final Coordinates southCoordinates = coord.clone(); southCoordinates.moveDown();
if (nodeCoordinates.containsKey(southCoordinates))
{
final int southHeight = getHeightAt(southCoordinates);
if ((southHeight == heightHere) || (southHeight == heightHere+1))
{
final Node southNode = nodeCoordinates.get(southCoordinates);
node.setSouthNode(southNode);
}
}
final Coordinates westCoordinates = coord.clone(); westCoordinates.moveLeft();
if (nodeCoordinates.containsKey(westCoordinates))
{
final int westHeight = getHeightAt(westCoordinates);
if ((westHeight == heightHere) || (westHeight == heightHere+1))
{
final Node westNode = nodeCoordinates.get(westCoordinates);
node.setWestNode(westNode);
}
}
}
}
}
private int getHeightAt(final Coordinates coordinates)
{
final int x = coordinates.getX();
final int y = coordinates.getY();
if ((x<0) || (x>=width)) return 10_000;
if ((y<0) || (y>=height)) return 10_000;
return heights[x][y];
}
// The "Optimized" approach that uses MapDistanceSolver
public long findShortestPathFromStartToEndOptimized()
{
final MapDistanceSolver mds = new MapDistanceSolver(new MapHandler(heights, width, height, startCoordinates, endCoordinates));
return mds.getShortestPath();
}
// for part 2
public long findShortestPathFromALowToEnd(final Coordinates lowCoordinates)
{
final MapDistanceSolver mds = new MapDistanceSolver(new MapHandler(heights, width, height, lowCoordinates, endCoordinates));
return mds.getShortestPath();
}
// The "BruteForce" solution using recursion that goes expontential for large inputs
public long findShortestPathFromStartToEndBruteForce()
{
tryAllDirectionsFromNode(startNode, new HashSet<Node>());
return startNode.getBestDistanceFromThisNode();
}
private int tryAllDirectionsFromNode(final Node node, final Set<Node> nodesAlreadyVisited)
{
// System.out.println(node.getCoordinates());
if (nodesAlreadyVisited.contains(node)) throw new IllegalStateException("looping");
final Set<Node> newNodesAlreadyVisited = new HashSet<>();
newNodesAlreadyVisited.addAll(nodesAlreadyVisited);
newNodesAlreadyVisited.add(node);
if (node.hasNorthNode())
{
final Node northNode = node.getNorthNode();
if (!nodesAlreadyVisited.contains(northNode))
{
final int northDistance = getDistanceFromNode(northNode, newNodesAlreadyVisited);
if (northDistance < node.getBestDistanceFromThisNode())
{
node.setBestDistanceFromThisNode(northDistance);
}
}
}
if (node.hasEastNode())
{
final Node eastNode = node.getEastNode();
if (!nodesAlreadyVisited.contains(eastNode))
{
final int eastDistance = getDistanceFromNode(eastNode, newNodesAlreadyVisited);
if (eastDistance < node.getBestDistanceFromThisNode())
{
node.setBestDistanceFromThisNode(eastDistance);
}
}
}
if (node.hasSouthNode())
{
final Node southNode = node.getSouthNode();
if (!nodesAlreadyVisited.contains(southNode))
{
final int southDistance = getDistanceFromNode(southNode, newNodesAlreadyVisited);
if (southDistance < node.getBestDistanceFromThisNode())
{
node.setBestDistanceFromThisNode(southDistance);
}
}
}
if (node.hasWestNode())
{
final Node westNode = node.getWestNode();
if (!nodesAlreadyVisited.contains(westNode))
{
final int westDistance = getDistanceFromNode(westNode, newNodesAlreadyVisited);
if (westDistance < node.getBestDistanceFromThisNode())
{
node.setBestDistanceFromThisNode(westDistance);
}
}
}
return node.getBestDistanceFromThisNode();
}
private int getDistanceFromNode(final Node node, final Set<Node> nodesAlreadyVisited)
{
final int distanceToThisPoint = nodesAlreadyVisited.size();
if (node.isTerminal())
{
return distanceToThisPoint;
}
final int nodeBest = node.getBestDistanceFromThisNode();
if (nodeBest < 10_000) return nodeBest;
return tryAllDirectionsFromNode(node, nodesAlreadyVisited);
}
// ========================================================================
private static final class Node
{
private static final Node INVALID_NODE = new Node(Coordinates.INVALID_COORDINATES);
private Node northNode;
private Node eastNode;
private Node southNode;
private Node westNode;
private final Coordinates nodeCoordinates;
private boolean isTerminalNode;
private int bestDistanceFromThisNode = 10_000;
private Node(final Coordinates nodeCoordinates)
{
northNode = INVALID_NODE;
eastNode = INVALID_NODE;
southNode = INVALID_NODE;
westNode = INVALID_NODE;
this.nodeCoordinates = nodeCoordinates;
}
public Coordinates getCoordinates()
{
return nodeCoordinates;
}
public boolean hasCoordinates(final int x, final int y)
{
if ((nodeCoordinates.getX() == x) && (nodeCoordinates.getY() == y)) return true;
return false;
}
public Node setNodeAsTerminal()
{
isTerminalNode = true;
return this;
}
public Node setNorthNode(final Node northNodeToSet)
{
northNode = northNodeToSet;
return this;
}
public Node setEastNode(final Node eastNodeToSet)
{
eastNode = eastNodeToSet;
return this;
}
public Node setSouthNode(final Node southNodeToSet)
{
southNode = southNodeToSet;
return this;
}
public Node setWestNode(final Node westNodeToSet)
{
westNode = westNodeToSet;
return this;
}
public int getBestDistanceFromThisNode()
{
return bestDistanceFromThisNode;
}
public void setBestDistanceFromThisNode(final int newDistanceToSet)
{
bestDistanceFromThisNode = newDistanceToSet;
}
public boolean isTerminal()
{
return isTerminalNode;
}
public boolean hasNorthNode()
{
return northNode != INVALID_NODE;
}
public boolean hasEastNode()
{
return eastNode != INVALID_NODE;
}
public boolean hasSouthNode()
{
return southNode != INVALID_NODE;
}
public boolean hasWestNode()
{
return westNode != INVALID_NODE;
}
public Node getNorthNode()
{
return northNode;
}
public Node getEastNode()
{
return eastNode;
}
public Node getSouthNode()
{
return southNode;
}
public Node getWestNode()
{
return westNode;
}
}
}
The driver for day 12, if I wasn’t trying to show both approaches at once, I probably could have factored out the HeightMap class completely.
final class Day12
{
public static long part1(final String[] day12InputLines)
{
final HeightMap hm = new HeightMap(day12InputLines);
// return hm.findShortestPathFromStartToEndBruteForce();
return hm.findShortestPathFromStartToEndOptimized();
}
public static long part2(final String[] day12InputLines)
{
final HeightMap hm = new HeightMap(day12InputLines);
final Set<Coordinates> allLowestCoordinates = hm.getAllLowestCoordinates();
long minDist = 10_000;
for (final Coordinates coord : allLowestCoordinates)
{
final long dist = hm.findShortestPathFromALowToEnd(coord);
if (dist < minDist) minDist = dist;
}
return minDist;
}
}
Thanks to lack of sleep, I missed one important detail, and it seems many people on Reddit missed it as well. In case you’re like me and others on Reddit, you can fall to any height! Just one meme image was enough of a hint to figure out why my input appeared invalid.
My main issue with like 90% of the pathfinding libraries (at least for JavaScript) is that the nodes are just a boolean value of if you can walk or not. This puzzle is a case of the nodes are rooms, and you might have doors going North, South, West and East. Oh, and it’s only when you go up you need to worry about the difference in height, so some doors are one way! As a result of this, I learned how to make a BFS algorithm myself. I was lucky to find a page explaining each step. Basically, it went the way of making a basic pathfinding algorithm, then added bits to upgrade all the way up to A*. Somehow, I didn’t need to use Dijkstra with how I handled the nodes.
The way I wrote everything, I have a bfs function. It takes three arrays, startXY[] for where you start, endXY[] for where you want to end up, and grid[][] which is basically a height map from the input (in numbers, not letters)
I convert the start and end nodes from an array of numbers to a string (X-Y) was for putting into a Set but was changed to a Map (page used Python for code, and it seems it’s a dict instead of map)
I have an array called queue, with the start node as the starting value, and a map called came_from, which I add the start node to with a value of null: came_from.set(startNode, null);
Then I enter a while loop for the queue (basically, while there’s something in the queue)
I remove the first value to use the current check node, and break out the loop if this is the end node (for the speed, though not by much)
Then I check in the four directions, so if we’re not on the edge of the grid, and the difference between the new node and the current is less than 2 (new height - old height), and it hasn’t been added to came_from yet, I add it to the queue and the came_from (eventually used to backtrack to get the best path: came_from.set(newNode, currentNode);)
Once I hit a point where there are no objects in the queue, I’ll pick the end node from came_from and back track to the start. Because of part 2 I had to add a check to see if we’re stuck somewhere as not all possible start locations can reach the end. Since the return of this function is the length of the path from start to end, if you get stuck, it just returns the grid’s height times width. If we can backtrack to the start, we’ll return the length of the path array.
Like PHolder, I have drivers because I made this function. They start by just creating the grid (and getting the start and end nodes)
For each cell, I convert the letters to a number
data.forEach((row, y) => {
const gridRow = [];
for (let x = 0; x < row.length; x++) {
// This two if statement is from Part 2
if (row[x] == 'S') {
row[x] = 'a';
}
if (row[x] == 'a') {
startXY.push([x, y]);
}
// This if statement is part 1
if (row[x] == 'S') {
row[x] = 'a';
startXY.push(x);
startXY.push(y);
}
// Shared between the parts below this
if (row[x] == 'E') {
row[x] = 'z';
endXY.push(x);
endXY.push(y);
}
const h = row[x].charCodeAt(0) - 97;
gridRow.push(h);
}
grid.push(gridRow);
});
Part 1 just returns the value of bfs on the grid with the start value
Part 2 loops through the start nodes and run bfs for each, keeping track of the shortest path.
Day lucky number 13 is a packet decoding exercise that reminds me a bit of sailfish number math from 2021.
Packets are made of lists and lists can contain integers or other lists. This already sounds recursive. I started out by making a class to represent a packet.
final class Packet
{
private final String packetString;
private final List<String> packetParts = new ArrayList<>();
public Packet(final String packetString)
{
this.packetString = packetString;
parsePacketParts(1); // ignore first square bracket
}
private void parsePacketParts(final int incomingIndex)
{
if (incomingIndex >= packetString.length()-1) return; // ignore final square bracket
int index = incomingIndex;
char c = packetString.charAt(index);
if (c == ',')
{
index++;
c = packetString.charAt(index);
}
if (c=='[')
{
index = getSubPacket(index);
}
else
{
index = getInt(index);
}
parsePacketParts(index);
}
private int getInt(final int incomingIndex)
{
int index = incomingIndex;
char c = packetString.charAt(index);
while (c>='0' && c<='9')
{
index++;
c = packetString.charAt(index);
}
final String intStr = packetString.substring(incomingIndex, index);
final int intVal = Integer.parseInt(intStr); // just a check to make sure it parses
packetParts.add(intStr);
return index+1;
}
private int getSubPacket(final int incomingIndex)
{
int index = incomingIndex+1;
int nestLevel = 1;
while (nestLevel>0)
{
final char c = packetString.charAt(index);
if (c == '[') nestLevel++;
if (c == ']') nestLevel--;
index++;
}
final String subPacketStr = packetString.substring(incomingIndex, index);
packetParts.add(subPacketStr);
return index+1;
}
public boolean hasPartNumber(final int packetPartNumber)
{
if (packetPartNumber < packetParts.size()) return true;
return false;
}
public String getPartNumber(final int packetPartNumber)
{
return packetParts.get(packetPartNumber);
}
}
Then I need to compare the left and right packets, so I created a PacketComparator.
final class PacketComparator
{
public static boolean comparePackets(final String left, final String right)
{
final Packet leftPacket = new Packet(left);
final Packet rightPacket = new Packet(right);
int compareResult = comparePackets(leftPacket, rightPacket);
if (compareResult < 0) return false;
return true;
}
private static int comparePackets(final Packet leftPacket, final Packet rightPacket)
{
int packetPartNumber = 0;
while (leftPacket.hasPartNumber(packetPartNumber))
{
final String leftPacketPart = leftPacket.getPartNumber(packetPartNumber);
if (!rightPacket.hasPartNumber(packetPartNumber)) return -1;
final String rightPacketPart = rightPacket.getPartNumber(packetPartNumber);
final int compareResult = comparePacketParts(leftPacketPart, rightPacketPart);
if (compareResult == 0)
packetPartNumber++;
else
return compareResult;
}
if (rightPacket.hasPartNumber(packetPartNumber)) return 1;
return 0;
}
private static int comparePacketParts(final String leftPacketPart, final String rightPacketPart)
{
if (leftPacketPart.isEmpty())
{
if (rightPacketPart.isEmpty()) return 0;
return 1;
}
else
{
if (rightPacketPart.isEmpty()) return -1;
}
if (leftPacketPart.startsWith("["))
{
if (rightPacketPart.startsWith("["))
return compareLists(leftPacketPart.substring(1,leftPacketPart.length()-1),
rightPacketPart.substring(1,rightPacketPart.length()-1) );
return compareLists(leftPacketPart.substring(1,leftPacketPart.length()-1),
rightPacketPart);
}
else
{
if (rightPacketPart.startsWith("["))
return compareLists(leftPacketPart,
rightPacketPart.substring(1,rightPacketPart.length()-1) );
}
return compareTwoNumbers(leftPacketPart, rightPacketPart);
}
private static int compareTwoNumbers(final String leftPacketPart, final String rightPacketPart)
{
final int leftVal = Integer.parseInt(leftPacketPart);
final int rightVal = Integer.parseInt(rightPacketPart);
if (leftVal < rightVal) return 1;
if (leftVal > rightVal) return -1;
return 0;
}
private static int compareLists(final String leftList, final String rightList)
{
final Packet leftPacket = new Packet("[" + leftList + "]");
final Packet rightPacket = new Packet("[" + rightList + "]");
return comparePackets(leftPacket, rightPacket);
}
}
Then the driver for part 1 was about getting the inputs grouped left and right.
final class Day13
{
public static long part1(final String[] day13InputLines)
{
boolean moreInput = true;
int packetIndex = 0;
int inputIndex = 0;
int sum=0;
while (moreInput)
{
packetIndex++;
final String left = day13InputLines[inputIndex];
final String right = day13InputLines[inputIndex + 1];
inputIndex += 3;
if (inputIndex >= day13InputLines.length) moreInput = false;
if (PacketComparator.comparePackets(left, right))
{
sum += packetIndex;
}
}
return sum;
}
For part 2 I needed to add a method to the PacketComparator class to be able to do the sort.
// Part 2
public static int comparePacketsForSort(final String left, final String right)
{
final Packet leftPacket = new Packet(left);
final Packet rightPacket = new Packet(right);
return comparePackets(leftPacket, rightPacket);
}
And then the part 2 driver was pretty straightforward, just add the new inputs and sort and then find the indexes of the new inputs. Also add a comparator class (PacketComparatorForSort) for the Java collections sort().
public static long part2(final String[] day13InputLines)
{
final List<String> inputs = new ArrayList<>();
inputs.add("[[2]]");
inputs.add("[[6]]");
for (final String input : day13InputLines)
{
if (!input.isEmpty()) inputs.add(input);
}
inputs.sort(new PacketComparatorForSort());
int pos1=-1;
int pos2=-1;
for (int i=0; i<inputs.size(); i++)
{
final String s = inputs.get(i);
if (s.equals("[[2]]"))
{
pos1 = i+1;
}
if (s.equals("[[6]]"))
{
pos2 = i+1;
}
}
return pos1 * pos2;
}
private static final class PacketComparatorForSort implements Comparator<String>
{
@Override
public int compare(final String right, final String left)
{
return PacketComparator.comparePacketsForSort(left, right);
}
}
I’m enjoying Day 10 so much I don’t want to finish it. I’m really dreading how hard it’s going to get!!
See you guys later. I’ll be in the back sweeping up.
The last few days have been quite good. For Day 12 I had forgotten that I had used Python’s networkx package last year until @PHolder mentioned the puzzle on Day 15. Anyway, for this puzzle I wrote something that did a depth first type of search, and refined it enough that it did parts 1 and 2 in about 3-4 minutes. As I watched it run, the path lengths started at around 1500 steps and gradually worked their way down to the 500 range. Encourage by @miquelfire’s comments I looked at how the breadth first algorithm worked. It turned out to be much easier to code and came up with the solutions almost instantly. What’s really clever about it is that as soon as you reach the destination you know you have the shortest path. For part 2 I just ran the search backwards starting at ‘E’ and stopping when it reached any ‘a’. I’m not sure how you would use a packaged BFS function with a variable end point.
Day 14 is simulating sand falling onto rocks. Maybe it will make you feel like you’re inside of a virtual hourglass.
I reused my Coordinates class, which I also used in a couple of past days this year. My first class was SandSim. It is where the representation of the “world” exists, and handles drawing lines of rock, and simulating sand falling and pooling in hills (according to the rules.) For part 2 I only had to add a couple of extra lines, so I will mark them here.
final class SandSim
{
private final int width;
private final int height;
private final char[][] sandSim;
private Coordinates sandStartCoordinates = Coordinates.INVALID_COORDINATES;
private int highestYValueOfRock = -1; // for Part 2
public SandSim(final int width, final int height)
{
this.width = width;
this.height = height;
sandSim = new char[width][height];
fillSpaces();
fillBorder();
}
// for part 2
public void putRockFloor()
{
addRockLine(new Coordinates(0, highestYValueOfRock+2),new Coordinates(width-1, highestYValueOfRock+2));
}
private void fillSpaces()
{
for(int y=0; y<height; y++)
for(int x=0; x<width; x++)
sandSim[x][y] = ' ';
}
private void fillBorder()
{
for(int x=0; x<width; x++)
{
// No top needed, sand falls down, and it might get in the way for part 2
sandSim[x][height-1] = '~';
}
for(int y=0; y<height; y++)
{
sandSim[0][y] = '~';
sandSim[width-1][y] = '~';
}
}
public void addRockString(final String rockString)
{
final String parts[] = rockString.split(" -> ");
for (int i=1; i<parts.length; i++)
{
final Coordinates from = new Coordinates(parts[i-1]);
final Coordinates to = new Coordinates(parts[i]);
addRockLine(from, to);
}
}
private void addRockLine(final Coordinates from, final Coordinates to)
{
if (from.getX() == to.getX())
{
// vertical line
int x = from.getX();
int y1 = from.getY();
int y2 = to.getY();
int yStart;
int yEnd;
if (y1 <= y2)
{
yStart = from.getY();
yEnd = to.getY();
}
else
{
yStart = to.getY();
yEnd = from.getY();
}
for (int y=yStart; y<=yEnd; y++)
{
putRock(x, y);
}
}
else
{
// horizonal line
int y = from.getY();
int x1 = from.getX();
int x2 = to.getX();
int xStart;
int xEnd;
if (x1 <= x2)
{
xStart = from.getX();
xEnd = to.getX();
}
else
{
xStart = to.getX();
xEnd = from.getX();
}
for (int x=xStart; x<=xEnd; x++)
{
putRock(x, y);
}
}
}
private void putRock(int x, int y)
{
if (y>highestYValueOfRock) highestYValueOfRock=y; // for part 2
sandSim[x][y] = '#';
}
public void setSandStartLocation(final int x, final int y)
{
sandStartCoordinates = new Coordinates(x, y);
}
public long getMaxSand()
{
int numSandGrains = 0;
boolean moreSandCanFit = true;
while (moreSandCanFit)
{
if (simulateSandGrain())
{
numSandGrains++;
}
else
{
moreSandCanFit = false;
}
}
return numSandGrains;
}
private boolean simulateSandGrain()
{
Coordinates sandGrain = sandStartCoordinates.clone();
if (sandSim[sandGrain.getX()][sandGrain.getY()] == 'O') return false; // Full, Part 2
boolean sandStillFalling = true;
while (sandStillFalling)
{
// dump(sandGrain);
final char cDown = sandSim[sandGrain.getX()][sandGrain.getY()+1];
final char cLeft = sandSim[sandGrain.getX()-1][sandGrain.getY()+1];
final char cRight = sandSim[sandGrain.getX()+1][sandGrain.getY()+1];
if (cDown == '~') return false;
if ( ((cDown == '#') || (cDown == 'O')) && ((cLeft == 'O') || (cLeft == '#')) && ((cRight == 'O') ||(cRight == '#')) )
{
sandSim[sandGrain.getX()][sandGrain.getY()] = 'O';
sandStillFalling = false;
continue;
}
if (cDown == ' ')
{
sandGrain.moveDown();
continue;
}
if ((cDown == '#') || (cDown == 'O'))
{
if (cLeft == '~') return false;
if (cLeft == ' ')
{
sandGrain.moveDown();
sandGrain.moveLeft();
continue;
}
}
if ((cLeft == 'O') || (cLeft == '#'))
{
if (cRight == '~') return false;
if (cRight == ' ')
{
sandGrain.moveDown();
sandGrain.moveRight();
continue;
}
}
// problem
System.out.println("Problem");
throw new IllegalStateException("Sand grain got stuck");
}
return true;
}
private void dump(final Coordinates sandGrain)
{
for (int y=0; y<20; y++)
{
for (int x=490; x<510; x++)
{
if ((sandGrain.getX()==x) && (sandGrain.getY()==y))
{
System.out.print('.');
}
else
{
final char c = sandSim[x][y];
if (c == ' ')
System.out.print(' ');
else
System.out.print(c);
}
}
System.out.println();
}
System.out.println("============================");
}
}
The driver is very straight forward: create the simulation, populate the rock lines, put the floor in for part 2, and then count how many sand grains can meet the rules.
final class Day14
{
public static long part1(final String[] day14InputLines)
{
final SandSim ss = new SandSim(1000,1000);
for(final String rockString : day14InputLines)
{
ss.addRockString(rockString);
}
ss.setSandStartLocation(500,0);
return ss.getMaxSand();
}
public static long part2(final String[] day14InputLines)
{
final SandSim ss = new SandSim(1000,1000);
for(final String rockString : day14InputLines)
{
ss.addRockString(rockString);
}
ss.setSandStartLocation(500,0);
ss.putRockFloor(); // new for part 2
return ss.getMaxSand();
}
}
Day 14: I don’t remember what year it was, but I got into the habit of just a Set when I have to deal with a grid of unknown size, so that’s what I did.
Fun Fact: If you look at my code, you’ll see a data.forEach(...) section. It used to be a .map(...) that chained off the rest of the input handling, but since it didn’t return anything, the data variable would be an array of undefined the size of the input. Even though I would not use it afterward, I hated seeing that in my debugger.
My inability to guess what changes part 2 would have, when I copy and pasted the code into part 2, the flag that sets if the code can keep running still talks about falling into the void.
Day 15 is going to be a challenge for anyone who doesn’t know the math or how Manhattan distances work. You’re given some sensors and some beacons they can sense. You need to figure out where a gap in the coverage is.
I started off with a class BeaconSensorRowTracker1 which is not the best name maybe, but it was a good description for what I would be doing for part 1. The only trick for part one was to make sure you noted that the beacon on the line of interest was not counted for the example answer given.
final class BeaconSensorRowTracker1
{
private final int rowOfInterest;
private final Set<Integer> beaconsOnRowOfInterest = new HashSet<>();
private final Set<Integer> occupiedSpotsOnRowOfInterest = new HashSet<>();
public BeaconSensorRowTracker1(final int rowOfInterest)
{
this.rowOfInterest = rowOfInterest;
}
private static final Pattern INPUT_PATTERN = Pattern.compile("Sensor at x=([-0-9]+), y=([-0-9]+): closest beacon is at x=([-0-9]+), y=([-0-9]+)");
public void submitBeaconSensorInfo(final String inputLine)
{
final Matcher m = INPUT_PATTERN.matcher(inputLine);
if (!m.matches()) throw new IllegalStateException("Invalid input: " + inputLine);
final int sensorX = Integer.parseInt(m.group(1));
final int sensorY = Integer.parseInt(m.group(2));
final int beaconX = Integer.parseInt(m.group(3));
final int beaconY = Integer.parseInt(m.group(4));
if (beaconY == rowOfInterest) beaconsOnRowOfInterest.add(beaconX);
processSensorAndBeacon(sensorX,sensorY, beaconX, beaconY);
}
private void processSensorAndBeacon(final int sensorX, final int sensorY, final int beaconX, final int beaconY)
{
final int manhattanDistanceBetweenSensorAndBeacon = Math.abs(sensorX-beaconX) + Math.abs(sensorY-beaconY);
final int deltaYBetweenSensorAndRowOfInterest = Math.abs(sensorY-rowOfInterest);
if (deltaYBetweenSensorAndRowOfInterest < manhattanDistanceBetweenSensorAndBeacon)
{
final int startX = sensorX - (manhattanDistanceBetweenSensorAndBeacon-deltaYBetweenSensorAndRowOfInterest);
final int endX = sensorX + (manhattanDistanceBetweenSensorAndBeacon-deltaYBetweenSensorAndRowOfInterest);
for (int x=startX; x<=endX; x++)
{
occupiedSpotsOnRowOfInterest.add(x);
}
}
}
public int getNumPlaces()
{
return occupiedSpotsOnRowOfInterest.size() - beaconsOnRowOfInterest.size();
}
public void dumpPlaces()
{
final List<Integer> all = new ArrayList<>(occupiedSpotsOnRowOfInterest.size());
all.addAll(occupiedSpotsOnRowOfInterest);
Collections.sort(all);
for (final int i : all)
{
System.out.println(i);
}
}
}
And then the driver for part 1 is so straight forward that it isn’t worth spoiler protecting. The rowOfInterest changes with the example and the actual input, so I made that a parameter passed from the unit test or the input supplier.
final class Day15
{
public static long part1(final String[] day15InputLines, final int rowOfInterest)
{
final BeaconSensorRowTracker1 bsrt = new BeaconSensorRowTracker1(rowOfInterest);
for (final String inputLine : day15InputLines)
{
bsrt.submitBeaconSensorInfo(inputLine);
}
// bsrt.dumpPlaces();
return bsrt.getNumPlaces();
}
Part 2 is impossible to brute force using the method you used in part 1, not that I didn’t spend some time trying. Eventually I realized there was another way to tackle the problem, and that was so fast it only took seconds for my input. The basic premise is that you know the one spot you’re interested in has to be JUST outside the range of one of the sensors. So you go through each sensor, increase its Manhattan distance by one, get all the points on the path, then pass them in to a function that sees if any of the other sensors can see it. If no other sensor can see it, then you have the spot you want.
final class BeaconSensorRowTracker2
{
private int rowOfInterest;
private final Set<Integer> occupiedSpotsOnRowOfInterest = new HashSet<>();
private final List<Coordinates> sensorCoordinates = new ArrayList<>();
private final List<Coordinates> beaconCoordinates = new ArrayList<>();
private final int maxXorY;
public BeaconSensorRowTracker2(final int maxXorY)
{
this.maxXorY = maxXorY;
}
private static final Pattern INPUT_PATTERN = Pattern.compile("Sensor at x=([-0-9]+), y=([-0-9]+): closest beacon is at x=([-0-9]+), y=([-0-9]+)");
public void submitBeaconSensorInfo(final String inputLine)
{
final Matcher m = INPUT_PATTERN.matcher(inputLine);
if (!m.matches()) throw new IllegalStateException("Invalid input: " + inputLine);
final int sensorX = Integer.parseInt(m.group(1));
final int sensorY = Integer.parseInt(m.group(2));
sensorCoordinates.add(new Coordinates(sensorX, sensorY));
final int beaconX = Integer.parseInt(m.group(3));
final int beaconY = Integer.parseInt(m.group(4));
beaconCoordinates.add(new Coordinates(beaconX, beaconY));
}
public long lookForPlace()
{
for (int i=0; i<sensorCoordinates.size(); i++)
{
final Coordinates sensor = sensorCoordinates.get(i);
final Coordinates beacon = beaconCoordinates.get(i);
final int sensorX = sensor.getX();
final int sensorY = sensor.getY();
final int beaconX = beacon.getX();
final int beaconY = beacon.getY();
final int manhattanDistance = Math.abs(sensorX-beaconX) + Math.abs(sensorY-beaconY) + 1;
for (int y=0; y<=manhattanDistance; y++)
{
final int x=manhattanDistance-y;
final int checkX1 = sensorX-x;
final int checkY1 = sensorY-y;
final long result1 = checkPoint(checkX1, checkY1);
if (result1 > 0) return result1;
final int checkX2 = sensorX+x;
final int checkY2 = sensorY-y;
final long result2 = checkPoint(checkX2, checkY2);
if (result2 > 0) return result2;
final int checkX3 = sensorX-x;
final int checkY3 = sensorY+y;
final long result3 = checkPoint(checkX3, checkY3);
if (result3 > 0) return result3;
final int checkX4 = sensorX+x;
final int checkY4 = sensorY+y;
final long result4 = checkPoint(checkX4, checkY4);
if (result4 > 0) return result4;
}
}
return 0;
}
private long checkPoint(final int x, final int y)
{
if (x<0) return 0;
if (y<0) return 0;
if (x>maxXorY) return 0;
if (y>maxXorY) return 0;
for (int i=0; i<sensorCoordinates.size(); i++)
{
final Coordinates sensor = sensorCoordinates.get(i);
final Coordinates beacon = beaconCoordinates.get(i);
final int sensorX = sensor.getX();
final int sensorY = sensor.getY();
final int beaconX = beacon.getX();
final int beaconY = beacon.getY();
final int manhattanDistanceOfSensor = Math.abs(sensorX-beaconX) + Math.abs(sensorY-beaconY);
final int manhattanDistanceToPoint = Math.abs(sensorX-x) + Math.abs(sensorY-y);
if (manhattanDistanceToPoint <= manhattanDistanceOfSensor) return 0;
}
System.out.println("x="+x + ", y="+y);
return x*4000000L + y;
}
}
and the addition to the driver looks pretty similar, again passing in the max value for X/Y (20 for example, 4M for the input.)
public static long part2(final String[] day15InputLines, final int maxXorY)
{
final BeaconSensorRowTracker2 bsrt = new BeaconSensorRowTracker2(maxXorY);
for (final String inputLine : day15InputLines)
{
bsrt.submitBeaconSensorInfo(inputLine);
}
return bsrt.lookForPlace();
}
Day 16 is pretty challenging. I didn’t find an optimal answer for part 2, it would probably run for hours, but I had it outputting its current best guess as it changed, and eventually it settled down so on a lark I used it, and it worked. Far from a great way to “solve” a problem, but I have high confidence my code will yield a correct solution, it will just take a very long time.
I called my solver ValveMap. Both part 1 and 2 are present. I don’t really consider part 2 much of a spoiler because it isn’t an optimal solution, so I will present it all at once.
final class ValveMap
{
record Room(String roomName, int valveRate, String[] otherRooms) {};
private final Map<String, Room> roomNameToRoomMapping = new HashMap<>();
private final Map<String, Set<String>> allRoomsLeadingFromRoom = new HashMap<>();
private final Set<String> allRoomNames = new HashSet<>();
private final Map<String, Integer> pathLengthsBetweenRooms = new HashMap<>();
private final Map<String, Integer> valveFlowRates = new HashMap<>();
private int optimalRelease;
public ValveMap(){}
private static final Pattern ROOM_DEFINITION_PATTERN = Pattern.compile("Valve ([A-Z]+) has flow rate=([0-9]+); (?:tunnel leads to valve ([A-Z]+)|tunnels lead to valves ((?:[A-Z]+)(?:, [A-Z]+)*))");
public void addRoomDefinition(final String roomDefinitionString)
{
final Matcher m = ROOM_DEFINITION_PATTERN.matcher(roomDefinitionString);
if (!m.matches())
throw new IllegalStateException("Couldn't match room definition: " + roomDefinitionString);
final String[] rooms;
if (m.group(4)==null)
{
rooms = new String[1];
rooms[0] = m.group(3);
}
else
{
rooms = m.group(4).split(", ");
}
final int valveRate = Integer.parseInt(m.group(2));
final String roomName = m.group(1);
final Room newRoom = new Room(roomName, valveRate, rooms);
roomNameToRoomMapping.put(roomName, newRoom);
valveFlowRates.put(roomName, valveRate);
allRoomNames.add(roomName);
for (final String otherRoomName : rooms)
{
addBidirectionalRoomConnection(roomName, otherRoomName);
}
}
private void addBidirectionalRoomConnection(final String room1, final String room2)
{
if (!allRoomsLeadingFromRoom.containsKey(room1))
{
allRoomsLeadingFromRoom.put(room1, new HashSet<>());
}
if (!allRoomsLeadingFromRoom.containsKey(room2))
{
allRoomsLeadingFromRoom.put(room2, new HashSet<>());
}
allRoomsLeadingFromRoom.get(room1).add(room2);
allRoomsLeadingFromRoom.get(room2).add(room1);
}
public int findOptimalRelease()
{
getAllPathLengths();
final Set<String> openedValves = new HashSet<>();
for (final String roomName : allRoomNames)
{
if (valveFlowRates.get(roomName) == 0)
{
openedValves.add(roomName);
}
}
optimalRelease = 0;
findOptimalRelease("AA", openedValves, 30, 0);
return optimalRelease;
}
public int findOptimalRelease2()
{
getAllPathLengths();
final Set<String> openedValves = new HashSet<>();
for (final String roomName : allRoomNames)
{
if (valveFlowRates.get(roomName) == 0)
{
openedValves.add(roomName);
}
}
optimalRelease = 0;
findOptimalRelease2("AA", "AA", openedValves, 26, 26, 0);
return optimalRelease;
}
private void getAllPathLengths()
{
for(final String fromRoomName: allRoomNames)
{
for(final String toRoomName: allRoomNames)
{
if (fromRoomName.equals(toRoomName))
{
pathLengthsBetweenRooms.put(fromRoomName+toRoomName, 0);
}
else
{
pathLengthsBetweenRooms.put(fromRoomName+toRoomName, getPathLengthFromRoomToRoom(fromRoomName, toRoomName));
}
}
}
}
private void findOptimalRelease(final String currentRoom, final Set<String> incomingOpenedValves, final int minutesLeft, final int totalRelease)
{
if (minutesLeft < 2)
{
if (totalRelease > optimalRelease)
{
System.out.println("A: " + totalRelease);
optimalRelease = totalRelease;
}
return;
}
final String[] allRoomsNotYetVisited = getAllRoomsNotYetVisited(incomingOpenedValves);
if (allRoomsNotYetVisited.length == 0)
{
if (totalRelease > optimalRelease)
{
System.out.println("B: " + totalRelease);
optimalRelease = totalRelease;
}
return;
}
for (final String nextRoomName : allRoomsNotYetVisited)
{
final int pathLengthToNextRoom = pathLengthsBetweenRooms.get(currentRoom+nextRoomName);
if (pathLengthToNextRoom>0)
{
final Room nextRoom = roomNameToRoomMapping.get(nextRoomName);
final Set<String> openedValves = new HashSet<>();
openedValves.addAll(incomingOpenedValves);
openedValves.add(nextRoomName);
final int newMinutesLeft = minutesLeft-pathLengthToNextRoom-1;
if (newMinutesLeft > 0)
{
findOptimalRelease(nextRoomName, openedValves, newMinutesLeft, totalRelease + newMinutesLeft * nextRoom.valveRate);
}
}
}
if (totalRelease > optimalRelease)
{
System.out.println("C: " + totalRelease);
optimalRelease = totalRelease;
}
return;
}
private void findOptimalRelease2(final String humanCurrentRoom, final String elephantCurrentRoom, final Set<String> incomingOpenedValves, final int humanMinutesLeft, final int elephantMinutesLeft, final int totalRelease)
{
if ((humanMinutesLeft < 2) && (elephantMinutesLeft < 2))
{
if (totalRelease > optimalRelease)
{
System.out.println("A: " + totalRelease);
optimalRelease = totalRelease;
}
return;
}
final String[] allRoomsNotYetVisited = getAllRoomsNotYetVisited(incomingOpenedValves);
if (allRoomsNotYetVisited.length == 0)
{
if (totalRelease > optimalRelease)
{
System.out.println("B: " + totalRelease);
optimalRelease = totalRelease;
}
return;
}
for (final String nextHumanRoomName : allRoomsNotYetVisited)
{
for (final String nextElephantRoomName : allRoomsNotYetVisited)
{
if (nextHumanRoomName.equals(nextElephantRoomName)) continue;
final Set<String> openedValves = new HashSet<>();
openedValves.addAll(incomingOpenedValves);
int totRelease = totalRelease;
int newHumanMinutesLeft = humanMinutesLeft;
final int pathLengthToNextHumanRoom = pathLengthsBetweenRooms.get(humanCurrentRoom+nextHumanRoomName);
if (pathLengthToNextHumanRoom>0)
{
final Room nextHumanRoom = roomNameToRoomMapping.get(nextHumanRoomName);
newHumanMinutesLeft = humanMinutesLeft-pathLengthToNextHumanRoom-1;
if (newHumanMinutesLeft > 0)
{
openedValves.add(nextHumanRoomName);
totRelease = totRelease + (newHumanMinutesLeft * nextHumanRoom.valveRate);
}
}
int newElephantMinutesLeft = elephantMinutesLeft;
final int pathLengthToNextElephantRoom = pathLengthsBetweenRooms.get(elephantCurrentRoom+nextElephantRoomName);
if (pathLengthToNextElephantRoom>0)
{
final Room nextElephantRoom = roomNameToRoomMapping.get(nextElephantRoomName);
newElephantMinutesLeft = elephantMinutesLeft-pathLengthToNextElephantRoom-1;
if (newElephantMinutesLeft > 0)
{
openedValves.add(nextElephantRoomName);
totRelease = totRelease + (newElephantMinutesLeft * nextElephantRoom.valveRate);
}
}
findOptimalRelease2(nextHumanRoomName, nextElephantRoomName, openedValves, newHumanMinutesLeft, newElephantMinutesLeft, totRelease);
}
}
if (totalRelease > optimalRelease)
{
System.out.println("C: " + totalRelease);
optimalRelease = totalRelease;
}
return;
}
private int getPathLengthFromRoomToRoom(final String fromRoomName, final String toRoomName)
{
final Set<String> roomsInPath = new HashSet();
roomsInPath.add(fromRoomName);
return bestPathLength(fromRoomName, toRoomName, 0, 10_000, roomsInPath);
}
private int bestPathLength(final String fromRoomName, final String toRoomName, final int curLen, final int bestLenSoFar, final Set<String> roomsInPath)
{
if (fromRoomName.equals(toRoomName))
{
if (curLen < bestLenSoFar) return curLen;
return bestLenSoFar;
}
int newBest = bestLenSoFar;
if (curLen > newBest) return newBest;
final String[] allRoomsLeadingFromRoom = getAllRoomsLeadingFromRoom(fromRoomName);
for (final String nextRoomName : allRoomsLeadingFromRoom)
{
if (!roomsInPath.contains(nextRoomName))
{
final Set<String> newRoomsInPath = new HashSet<>();
newRoomsInPath.addAll(roomsInPath);
newRoomsInPath.add(nextRoomName);
int len = bestPathLength(nextRoomName, toRoomName, curLen+1, newBest, newRoomsInPath);
if (len < newBest) newBest = len;
}
}
return newBest;
}
private String[] getAllRoomsNotYetVisited(final Set<String> alreadyVisitedRooms)
{
final Set<String> unvisitedRooms = new HashSet<>();
for (final String roomName : allRoomNames)
{
if (!alreadyVisitedRooms.contains(roomName))
{
unvisitedRooms.add(roomName);
}
}
final String[] result = new String[unvisitedRooms.size()];
int i=0;
for (final String roomName: unvisitedRooms)
{
result[i++] = roomName;
}
return result;
}
private String[] getAllRoomsLeadingFromRoom(final String roomName)
{
final Set<String> otherRooms = allRoomsLeadingFromRoom.get(roomName);
final String[] result = new String[otherRooms.size()];
int i=0;
for (final String otherRoom : otherRooms)
{
result[i++] = otherRoom;
}
return result;
}
}
The drivers are virtually identical except for calling the different solver:
final class Day16
{
public static long part1(final String[] day16InputLines)
{
final ValveMap vm = new ValveMap();
for (final String s: day16InputLines)
{
vm.addRoomDefinition(s);
}
return vm.findOptimalRelease();
}
public static long part2(final String[] day16InputLines)
{
final ValveMap vm = new ValveMap();
for (final String s: day16InputLines)
{
vm.addRoomDefinition(s);
}
return vm.findOptimalRelease2();
}
}
(The spoiler didn’t work on the deleted post)
I eventually found a similar approach for Part 2: I figured that the point you are looking for must be surrounded by two pairs of adjacent sensor region boundaries separated by diagonal gap lines exactly one grid dot apart and with opposite slopes so they intersect.
I checked all combinations of sensors for those that were the right distance apart, found end points of the gap lines and then checked pairs of lines with opposite slopes until I found two that intersect (at the location of the distress beacon). In my puzzle input there were only two lines to compare.
I think it prefers block spoilers to have the final tag on a line by itself… or is otherwise picky.
I had put an empty line within the spoiler like this:[spoiler] the following empty line
cancels the spoiler tags [/spoiler].
I could have edited the post but I didn’t discover the reason it wasn’t working until after I deleted it. It’s hard to experiment when it’s live and you don’t know what you’re doing. 
Oh boy day 17 was rough. I spent too many hours getting his weird Tetris rules to apply properly, so many weird bugs or corner cases. For quite some time I couldn’t get the first “rock” to land where he said it should. Then when I finally had something that made the first rock work right, the second one would be off by one. It turned out my wind checking wasn’t quite right… among other things.
Another of my big bugs was not properly unit testing my culling. It wasn’t actually scrolling down like it should have been because I donno what kind of drugs I must have (or maybe should have been) on when I coded it.
According to my personal stats, it was 03:56:06 (so almost 4am) before I had part one properly debugged at working, and I was already feeling exhausted. I will say, when I drew out a picture of the first 10 rocks and it exactly matched the example, there was much celebration in my head (and I earned myself a drink.) Here’s a relevant picture:
| ##### |
| # |
| # |
| # |
| # |
| ## # |
| ## # |
| ### |
| # |
| ### |
| # |
| #### |
| ##|
| ##|
| #|
| #|
| ####|
| ### |
| # |
|# ####|
|# # |
|# # |
|# ## |
|## ## |
|###### |
| ### |
| # |
| #### |
| ## |
| ## |
| # |
| # # |
| # # |
|##### |
| ### |
| # |
| #### |
-------
Another problem I had was that my playfield size wasn’t big enough because there is the possibility of a really deep hole. In the example input, the deepest hole is 32, and in my provided input the deepest hole was 59. This means that I needed to make sure my culled playfield had at least enough room for 60 lines, which it didn’t have at first, and that was causing the answer to be off.
For part 2, I tried different things, and read some of Reddit for hints. I couldn’t get it to work right initially. Someone on Reddit did give me a cryptic hint, and eventually I worked out that there must be a cycle I needed to find. Here’s a picture of how I eventually thought about it.
I eventually got desperate to know the correct answer to help with my debugging/math, and I tried running a half dozen other peoples listed code: 4 Python and 2 Java. None of the 4 Python either worked or gave the correct answer. The first Java didn’t either. The second Java took a LOT of rework, because he had all his own utility classes and one of them clashed with my Coordinates class. (He was also using a method deprecated in more recent Java that I had to work around.)
In the end, for part 2, I wrote code that outputs a table of numbers so I could find the cycle. I had it look at the top 90 lines of the rocks and look for when it would see that pattern repeat later. (I didn’t know the size of the deepest whole at that time, but I figured I needed a good amount.) The outputs for the example input looked like this:
The columns are: currentRock#, numberOfLinesOccupied, theRock#ItsARepeatOf
So you can see that 107-72 = 35, the cycle size
And if you look ahead at 107+35 = 142 you'll see the lines
used there is 222 and subtracting the 169 at 107 gives
you 222-169 = 53, so there are 53 lines used per cycle.
107, 169, 72
108, 170, 73
109, 172, 74
110, 172, 75
111, 173, 76
112, 175, 77
113, 176, 78
114, 178, 79
115, 178, 80
116, 179, 81
117, 182, 82
118, 184, 83
119, 184, 84
120, 184, 85
121, 185, 86
122, 188, 87
123, 191, 88
124, 195, 89
125, 195, 90
126, 196, 91
127, 198, 92
128, 201, 93
129, 201, 94
130, 202, 95
131, 203, 96
132, 206, 97
133, 208, 98
134, 210, 99
135, 210, 100
136, 210, 101
137, 212, 102
138, 215, 103
139, 219, 104
140, 219, 105
141, 220, 106
142, 222, 107
143, 223, 108
144, 225, 109
145, 225, 110
146, 226, 111
147, 228, 112
...
So in the end I printed enough tabular info to be able to do the math like so:
// cycle is 35, 53 rocks per cycle
final long cycleSize = 35;
final long rocksPerCycle = 53;
final long cycleStartRock = 107;
final long numLinesAtCycleStart = 169;
final long numberOfCycles = (1_000_000_000_000L - cycleStartRock) / cycleSize;
final long numberOfAdditionalRocks = 1_000_000_000_000L - numberOfCycles * cycleSize - cycleStartRock; // 13 additional rocks
final long cycleLookupAt13 = 15;
final long result = numberOfCycles * rocksPerCycle + numLinesAtCycleStart + cycleLookupAt13;
So here’s my class for RockTetris. I left in lots of debugging stuff including commented out values that I changed for different purposes, to give you a sense of how it changed as I tried things. The method findPeriod() was what I used to print the table above.
final class RockTetris
{
private final static String[] rock1 =
"""
####
""".split("\n");
private final static String[] rock2 =
"""
#
###
#
""".split("\n");
private final static String[] rock3 =
"""
#
#
###
""".split("\n");
private final static String[] rock4 =
"""
#
#
#
#
""".split("\n");
private final static String[] rock5 =
"""
##
##
""".split("\n");
private static final Rock[] rocks = {new Rock(rock1), new Rock(rock2), new Rock(rock3), new Rock(rock4), new Rock(rock5)};
private final char[][] playfield;
private final static int PLAYFIELD_WIDTH = 7;
private final static int PLAYFIELD_HEIGHT = 8000;
//private final static int PLAYFIELD_HEIGHT = 4000;
// private final static int PLAYFIELD_HEIGHT = 20;
// private final static int PLAYFIELD_HEIGHT = 60;
private final static int HEIGHT_MARGIN = 60;
private final char[] windMovements;
private int currentWindMovementIndex = 0;
private int highestRockPosition = 0;
private long numberOfLinesEverUsed = 0;
private int currentRockShapeIndex = 0;
private Rock currentRockShape = rocks[currentRockShapeIndex];
private int deepestHole = 0;
public RockTetris(final String windMovements)
{
this.windMovements = windMovements.toCharArray();
playfield = new char[PLAYFIELD_WIDTH][PLAYFIELD_HEIGHT];
clearPlayfield();
highestRockPosition = PLAYFIELD_HEIGHT;
}
public void playRounds(final long numberOfRocks)
{
for (int i=0; i<numberOfRocks; i++)
//for (int i=0; i<10; i++)
{
playNextRock();
final int[] holeDepths = getHoleDepths();
for (int x=0; x<PLAYFIELD_WIDTH; x++)
{
if (holeDepths[x] > deepestHole) deepestHole = holeDepths[x];
}
}
System.out.println("Deepest hole: " + deepestHole);
// dumpPlayfield();
}
private int[] getHoleDepths()
{
final int[] result = new int[PLAYFIELD_WIDTH];
for (int x=0; x<PLAYFIELD_WIDTH; x++)
{
result[x] = getHoleDepthAt(x);
}
return result;
}
private int getHoleDepthAt(final int x)
{
for (int y=highestRockPosition; y<PLAYFIELD_HEIGHT; y++)
{
if (playfield[x][y] != ' ') return y-highestRockPosition;
}
return PLAYFIELD_HEIGHT - highestRockPosition;
}
public long getNumberOfLinesEverUsed()
{
return numberOfLinesEverUsed + (PLAYFIELD_HEIGHT-highestRockPosition);
}
private void playNextRock()
{
//dumpPlayfield();
if (highestRockPosition <= HEIGHT_MARGIN)
{
scrollPlayFieldDown(HEIGHT_MARGIN);
highestRockPosition +=HEIGHT_MARGIN;
numberOfLinesEverUsed +=HEIGHT_MARGIN;
}
final Coordinates CoordinatesOfCurrentRock = new Coordinates(2, highestRockPosition-4);
setCurrentRockShape();
// dumpPlayfieldWithCurrentRock(CoordinatesOfCurrentRock);
while (true)
{
applyWind(CoordinatesOfCurrentRock);
//dumpPlayfieldWithCurrentRock(CoordinatesOfCurrentRock);
if (rockHasSomethingBelow(CoordinatesOfCurrentRock))
{
break;
}
else
{
applyGravity(CoordinatesOfCurrentRock);
//dumpPlayfieldWithCurrentRock(CoordinatesOfCurrentRock);
}
}
putRockInPlayfield(CoordinatesOfCurrentRock);
// dumpPlayfield();
}
private boolean isSomethingInTheWayOfWind(Coordinates coordinatesOfCurrentRock)
{
final int windXDelta;
if (windMovements[currentWindMovementIndex] == '<')
{
windXDelta = -1;
}
else
{
windXDelta = 1;
}
final int numRockPieces = currentRockShape.getNumberOfRockPieces();
for (int i=0; i<numRockPieces; i++)
{
final Coordinates rockPieceCoordinates = currentRockShape.getRockPiece(i, coordinatesOfCurrentRock);
final Coordinates adjacentPieceCoordinates = rockPieceCoordinates.clone();
if (windXDelta<0)
adjacentPieceCoordinates.moveLeft();
else
adjacentPieceCoordinates.moveRight();
final int adjX = adjacentPieceCoordinates.getX();
final int adjY = adjacentPieceCoordinates.getY();
if ((adjX<0) || (adjX>=PLAYFIELD_WIDTH)) return true;
final char whatsThere = playfield[adjX][adjY];
if (whatsThere != ' ') return true;
}
return false;
}
private void putRockInPlayfield(final Coordinates coordinatesOfCurrentRock)
{
placeRockInto(playfield, coordinatesOfCurrentRock, '#', true);
}
private void placeRockInto(final char[][] playfieldForRock, final Coordinates coordinatesOfCurrentRock, final char rockChar, final boolean shouldUpdateHeight)
{
final int numRockPieces = currentRockShape.getNumberOfRockPieces();
for (int i=0; i<numRockPieces; i++)
{
final Coordinates rockPieceCoordinates = currentRockShape.getRockPiece(i, coordinatesOfCurrentRock);
final int rockPieceX = rockPieceCoordinates.getX();
final int rockPieceY = rockPieceCoordinates.getY();
if (shouldUpdateHeight && (rockPieceY < highestRockPosition)) highestRockPosition = rockPieceY;
playfieldForRock[rockPieceX][rockPieceY] = rockChar;
}
}
private void applyGravity(final Coordinates coordinatesOfCurrentRock)
{
coordinatesOfCurrentRock.moveDown();
}
private void applyWind(final Coordinates coordinatesOfCurrentRock)
{
final int windXDelta;
if (windMovements[currentWindMovementIndex] == '<')
{
//System.out.println("Left Wind");
windXDelta = -1;
}
else
{
//System.out.println("Right Wind");
windXDelta = 1;
}
if (!isSomethingInTheWayOfWind(coordinatesOfCurrentRock))
{
if (windXDelta<0)
coordinatesOfCurrentRock.moveLeft();
else
coordinatesOfCurrentRock.moveRight();
}
currentWindMovementIndex++;
if (currentWindMovementIndex >= windMovements.length) currentWindMovementIndex = 0;
}
private boolean rockHasSomethingBelow(final Coordinates coordinatesOfCurrentRock)
{
if (coordinatesOfCurrentRock.getY() >= PLAYFIELD_HEIGHT-1) return true;
final int numRockPieces = currentRockShape.getNumberOfRockPieces();
for (int i=0; i<numRockPieces; i++)
{
final Coordinates rockPieceCoordinates = currentRockShape.getRockPiece(i, coordinatesOfCurrentRock);
final Coordinates belowPieceCoordinates = rockPieceCoordinates.clone();
belowPieceCoordinates.moveDown();
final char whatsThere = playfield[belowPieceCoordinates.getX()][belowPieceCoordinates.getY()];
if (whatsThere != ' ') return true;
}
return false;
}
private void setCurrentRockShape()
{
currentRockShape = rocks[currentRockShapeIndex];
currentRockShapeIndex++;
if (currentRockShapeIndex >= rocks.length) currentRockShapeIndex = 0;
}
private void scrollPlayFieldDown(final int numLinesToRemove)
{
for (int y=PLAYFIELD_HEIGHT-numLinesToRemove-1; y>=0; y--)
{
for (int x=0; x<PLAYFIELD_WIDTH; x++)
{
playfield[x][y+numLinesToRemove] = playfield[x][y];
}
}
for (int y=numLinesToRemove-1; y>=0; y--)
{
for (int x=0; x<PLAYFIELD_WIDTH; x++)
{
playfield[x][y] = ' ';
}
}
}
private void clearPlayfield()
{
for (int y=0; y<PLAYFIELD_HEIGHT; y++)
{
for (int x=0; x<PLAYFIELD_WIDTH; x++)
{
playfield[x][y] = ' ';
}
}
}
private void dumpPlayfield()
{
dumpSpecificPlayfield(playfield);
}
private void dumpSpecificPlayfield(final char[][] specificPlayfield)
{
System.out.println(" -------");
for (int y=0; y<PLAYFIELD_HEIGHT; y++)
{
if (y == highestRockPosition)
System.out.print('+');
else
System.out.print('|');
for (int x=0; x<PLAYFIELD_WIDTH; x++)
{
System.out.print(specificPlayfield[x][y]);
}
if (y == highestRockPosition)
System.out.print('+');
else
System.out.print('|');
System.out.println();
}
System.out.println(" -------");
}
private void dumpPlayfieldWithCurrentRock(final Coordinates coordinatesOfCurrentRock)
{
final char[][] tempPlayfield = new char[PLAYFIELD_WIDTH][PLAYFIELD_HEIGHT];
for (int y=0; y<PLAYFIELD_HEIGHT; y++)
{
for (int x=0; x<PLAYFIELD_WIDTH; x++)
{
tempPlayfield[x][y] = playfield[x][y];
}
}
placeRockInto(tempPlayfield, coordinatesOfCurrentRock, '@', false);
dumpSpecificPlayfield(tempPlayfield);
}
// Trying using hole depths
@org.eclipse.jdt.annotation.NonNullByDefault({})
record State(int rockIndex, int windIndex, long topOfPile1, long topOfPile2, long topOfPile3, long topOfPile4, long topOfPile5, long topOfPile6, long topOfPile7, long topOfPile8, long topOfPile9, long topOfPile10) {};
private Set<State> knownStates = new HashSet<>();
private Map<State, Long> prevIndex= new HashMap<>();
public void findPeriod()
{
long rockNumber = 0;
while(rockNumber <= 4000)
{
rockNumber++;
final int rockIndex = currentRockShapeIndex;
final int windIndex = currentWindMovementIndex;
playNextRock();
long top1 = 0;
long p2=1;
if (highestRockPosition >= PLAYFIELD_HEIGHT-90) continue;
for (int y=highestRockPosition; y<highestRockPosition+9; y++)
{
for(int x=0; x<PLAYFIELD_WIDTH; x++)
{
if (playfield[x][y]=='#')
{
top1+= p2;
}
p2*=2;
}
}
long top2 = 0;
p2=1;
for (int y=highestRockPosition+9; y<highestRockPosition+18; y++)
{
for(int x=0; x<PLAYFIELD_WIDTH; x++)
{
if (playfield[x][y]=='#')
{
top2+= p2;
}
p2*=2;
}
}
long top3 = 0;
p2=1;
for (int y=highestRockPosition+18; y<highestRockPosition+27; y++)
{
for(int x=0; x<PLAYFIELD_WIDTH; x++)
{
if (playfield[x][y]=='#')
{
top3+= p2;
}
p2*=2;
}
}
long top4 = 0;
p2=1;
for (int y=highestRockPosition+27; y<highestRockPosition+36; y++)
{
for(int x=0; x<PLAYFIELD_WIDTH; x++)
{
if (playfield[x][y]=='#')
{
top4+= p2;
}
p2*=2;
}
}
long top5 = 0;
p2=1;
for (int y=highestRockPosition+36; y<highestRockPosition+45; y++)
{
for(int x=0; x<PLAYFIELD_WIDTH; x++)
{
if (playfield[x][y]=='#')
{
top5+= p2;
}
p2*=2;
}
}
long top6 = 0;
p2=1;
for (int y=highestRockPosition+45; y<highestRockPosition+54; y++)
{
for(int x=0; x<PLAYFIELD_WIDTH; x++)
{
if (playfield[x][y]=='#')
{
top6+= p2;
}
p2*=2;
}
}
long top7 = 0;
p2=1;
for (int y=highestRockPosition+54; y<highestRockPosition+63; y++)
{
for(int x=0; x<PLAYFIELD_WIDTH; x++)
{
if (playfield[x][y]=='#')
{
top7+= p2;
}
p2*=2;
}
}
long top8 = 0;
p2=1;
for (int y=highestRockPosition+63; y<highestRockPosition+72; y++)
{
for(int x=0; x<PLAYFIELD_WIDTH; x++)
{
if (playfield[x][y]=='#')
{
top8+= p2;
}
p2*=2;
}
}
long top9 = 0;
p2=1;
for (int y=highestRockPosition+72; y<highestRockPosition+81; y++)
{
for(int x=0; x<PLAYFIELD_WIDTH; x++)
{
if (playfield[x][y]=='#')
{
top9+= p2;
}
p2*=2;
}
}
long top10 = 0;
p2=1;
for (int y=highestRockPosition+81; y<highestRockPosition+90; y++)
{
for(int x=0; x<PLAYFIELD_WIDTH; x++)
{
if (playfield[x][y]=='#')
{
top10+= p2;
}
p2*=2;
}
}
final State state = new State(rockIndex, windIndex, top1, top2, top3, top4, top5, top6, top7, top8, top9, top10);
if (knownStates.contains(state))
{
System.out.println(rockNumber + ", " + (numberOfLinesEverUsed + (long)(PLAYFIELD_HEIGHT-highestRockPosition)) + ", " + prevIndex.get(state));
//break;
}
knownStates.add(state);
prevIndex.put(state, rockNumber);
}
}
}
The driver is pretty predictable. You can see my commenting out and whatnot as I did stuff in part 2 by hand and when I was trying other people’s Java code.
final class Day17
{
public static long part1(final String day17InputLine, final int numberOfRocks)
{
final RockTetris rt = new RockTetris(day17InputLine);
rt.playRounds(numberOfRocks);
return rt.getNumberOfLinesEverUsed();
//return new OtherCode2().part1(day17InputLine);
}
public static long part2(final String day17InputLine, final long numberOfRocks)
{
final RockTetris rt = new RockTetris(day17InputLine);
//rt.playRounds(numberOfRocks);
rt.findPeriod();
return 0;//rt.getNumberOfLinesEverUsed();
/*
final OtherCode2 oc = new OtherCode2();
oc.part1(day17InputLine);
return oc.part2(day17InputLine);
*/
}
}
Day 18 was refreshingly easier (for me) than day 17. It’s basically a test of 3D geometry. A cube has six sides, and the question asks you to input a bunch of cubes, then determine how many of them have sides that are not adjacent to other cubes. The trick I used with part 2 was to code a flood fill and then use locations that didn’t flood fill to find the interior holes, and fill them, then use the part 1 algorithm. One other trick I used was to determine the max X,Y and Z and thus set a reasonable size for my cube, so that the flood fill would be faster and wouldn’t chance blowing my stack.
I created a ThreeDimensionalLava class to contain my work and just used a 3D array of booleans.
final class ThreeDimensionalLava
{
private final boolean[][][] positions;
private final boolean[][][] floodFill;
private final int maxDimension;
private int maxX;
private int maxY;
private int maxZ;
public ThreeDimensionalLava(final int maxDimension)
{
this.maxDimension = maxDimension;
positions = new boolean[maxDimension][maxDimension][maxDimension];
floodFill = new boolean[maxDimension][maxDimension][maxDimension];
}
public void addPoint(final int x, final int y, final int z)
{
positions[x][y][z] = true;
if (x > maxX) maxX = x;
if (y > maxY) maxY = y;
if (z > maxZ) maxZ = z;
}
public long getSurfaceArea2()
{
floodFill(maxDimension-1,maxDimension-1,maxDimension-1);
// Fill all the interior holes
for (int x=0; x<maxDimension; x++)
for (int y=0; y<maxDimension; y++)
for (int z=0; z<maxDimension; z++)
{
if (!floodFill[x][y][z] && !positions[x][y][z])
{
positions[x][y][z] = true;
// System.out.println(x + "," + y + "," + z);
}
}
return getSurfaceArea();
}
private void floodFill(final int x, final int y, final int z)
{
if (x<0) return;
if (y<0) return;
if (z<0) return;
if (x>=maxDimension) return;
if (y>=maxDimension) return;
if (z>=maxDimension) return;
floodFill[x][y][z] = true;
final boolean[] hasNeighbour = getNeighbours(positions, x, y, z);
final boolean[] hasFloodFillNeighbour = getNeighbours(floodFill, x, y, z);
if (!hasFloodFillNeighbour[0] && !hasNeighbour[0]) floodFill(x-1, y, z);
if (!hasFloodFillNeighbour[1] && !hasNeighbour[1]) floodFill(x+1, y, z);
if (!hasFloodFillNeighbour[2] && !hasNeighbour[2]) floodFill(x, y-1, z);
if (!hasFloodFillNeighbour[3] && !hasNeighbour[3]) floodFill(x, y+1, z);
if (!hasFloodFillNeighbour[4] && !hasNeighbour[4]) floodFill(x, y, z-1);
if (!hasFloodFillNeighbour[5] && !hasNeighbour[5]) floodFill(x, y, z+1);
}
public long getSurfaceArea()
{
int sum = 0;
for (int x=0; x<maxDimension; x++)
for (int y=0; y<maxDimension; y++)
for (int z=0; z<maxDimension; z++)
sum += getSurfaceAreaAt(x,y,z);
//System.out.println("Max X: " + maxX);
//System.out.println("Max Y: " + maxY);
//System.out.println("Max Z: " + maxZ);
return sum;
}
private int getSurfaceAreaAt(int x, int y, int z)
{
if (x<0) return 0;
if (y<0) return 0;
if (z<0) return 0;
if (x>=maxDimension) return 0;
if (y>=maxDimension) return 0;
if (z>=maxDimension) return 0;
if (!positions[x][y][z]) return 0;
final boolean[] hasNeighbour = getNeighbours(positions, x, y, z);
int sum=0;
for(int i=0; i<6; i++)
if (hasNeighbour[i]) sum++;
return 6-sum;
}
private boolean[] getNeighbours(final boolean[][][] positionsArray, final int x, final int y, final int z)
{
boolean[] hasNeighbour = new boolean[6];
hasNeighbour[0] = isPositionOccupied(positionsArray, x-1, y, z);
hasNeighbour[1] = isPositionOccupied(positionsArray, x+1, y, z);
hasNeighbour[2] = isPositionOccupied(positionsArray, x, y-1, z);
hasNeighbour[3] = isPositionOccupied(positionsArray, x, y+1, z);
hasNeighbour[4] = isPositionOccupied(positionsArray, x, y, z-1);
hasNeighbour[5] = isPositionOccupied(positionsArray, x, y, z+1);
return hasNeighbour;
}
private boolean isPositionOccupied(final boolean[][][] positionsArray, final int x, final int y, final int z)
{
if (x<0) return false;
if (y<0) return false;
if (z<0) return false;
if (x>=maxDimension) return false;
if (y>=maxDimension) return false;
if (z>=maxDimension) return false;
boolean result = positionsArray[x][y][z];
return result;
}
}
The driver isn’t anything amazing:
final class Day18
{
public static long part1(final String[] day18InputLines, final int maxDimension)
{
final ThreeDimensionalLava tdl = new ThreeDimensionalLava(maxDimension);
parseAndSubmitData(day18InputLines, tdl);
return tdl.getSurfaceArea();
}
private static void parseAndSubmitData(final String[] day18InputLines, final ThreeDimensionalLava tdl)
{
for (final String input: day18InputLines)
{
final String[] parts = input.split(",");
final int x = Integer.parseInt(parts[0]);
final int y = Integer.parseInt(parts[1]);
final int z = Integer.parseInt(parts[2]);
tdl.addPoint(x, y, z);
}
}
public static long part2(final String[] day18InputLines, final int maxDimension)
{
final ThreeDimensionalLava tdl = new ThreeDimensionalLava(maxDimension);
parseAndSubmitData(day18InputLines, tdl);
return tdl.getSurfaceArea2();
}
}
I had to admit defeat on Day 16, at least temporarily. The brute force traversing of all paths became unwieldy and I didn’t want to fall behind too many days.
I liked Day 17 (probably because I was able to solve it ).
At least I could understand what to do in Part 1 even though it was a bit tricky positioning the rocks and keeping track of the height. It was entertaining to watch the rocks moving and settling in the chamber.
I knew what to look for in Part 2 but finding it was a chore. I also checked other programmers’ solutions and found they did not work with my puzzle data. The issue is to recognize that there must be a repeating pattern of some sort that adds the same height to the rock tower on each cycle.
.
My first attempt worked with the sample data but not the puzzle data. I decided to print (to the screen with wrap around) the difference in the height after each rock was added and look for a pattern. This was what I found by using the smallest font size and adjusting the console window width:
Well, it took some doing, but I finally got the speed I wanted out of Day 19 and thus code I am willing to post and discuss. Day 19 was a real bear of a challenge, if you ask me. My mistake was to generalize the code too much, rather that just doing the bare minimum I needed to, with lots of hard codes. The only solution I found that worked was a highly recursive one, and if you can’t find ways to short circuit some paths, it’s going to be too slow and take too long (as it did the night of the challenge.)
I created a number of classes along the way, and an interface to handle the fact I was trying different versions of one of the classes until I got one I liked. I created Blueprint, RobotFactory and BlueprintRunner(s) based on a BlueprintRunner interface.
Here’s the overly generic Blueprint class, that is basically responsible for understanding the incoming blueprint text (costs of robots):
final class Blueprint
{
public enum RobotType
{
ORE_ROBOT(ResourceType.ORE),
CLAY_ROBOT(ResourceType.CLAY),
OBSIDIAN_ROBOT(ResourceType.OBSIDIAN),
GEODE_ROBOT(ResourceType.GEODE);
private final ResourceType resourceProduced;
RobotType(final ResourceType resourceProduced)
{
this.resourceProduced = resourceProduced;
}
static RobotType fromText(final String text)
{
return switch(text)
{
case "ore" -> ORE_ROBOT;
case "clay" -> CLAY_ROBOT;
case "obsidian" -> OBSIDIAN_ROBOT;
case "geode" -> GEODE_ROBOT;
default -> throw new IllegalStateException("RobotType fromText was passed: " + text);
};
}
ResourceType getResourceProduced()
{
return resourceProduced;
}
}
public enum ResourceType
{
ORE,
CLAY,
OBSIDIAN,
GEODE;
static ResourceType fromText(final String text)
{
return switch(text)
{
case "ore" -> ORE;
case "clay" -> CLAY;
case "obsidian" -> OBSIDIAN;
case "geode" -> GEODE;
default -> throw new IllegalStateException("ResourceType fromText was passed: " + text);
};
}
}
public record ResourceCost(ResourceType resourceType, int numberOfResource) {}
public record RobotCosts(RobotType robotType, ResourceCost[] resourceCosts) {}
private final int id;
private final RobotCosts[] robotCosts;
public Blueprint(final String blueprintInstructions)
{
final String parts[] = blueprintInstructions.split(":");
id = getID(parts[0]);
final String[] robotRuleInstructions = breakBlueprintInstructionsDownIntoRobotRuleInstructions(parts[1]);
robotCosts = new RobotCosts[robotRuleInstructions.length];
int robotRuleIndex = 0;
for (final String robotRuleString : robotRuleInstructions)
{
robotCosts[robotRuleIndex++] = parseRobotRule(robotRuleString);
}
}
private static final Pattern ROBOT_RULE_PATTERN = Pattern.compile("Each ([a-z]+) robot costs ([0-9]+) ([a-z]+)(?: and ([0-9]+) ([a-z]+))?");
private RobotCosts parseRobotRule(final String robotRuleString)
{
final Matcher m = ROBOT_RULE_PATTERN.matcher(robotRuleString);
if (!m.matches())
throw new IllegalStateException("Could not parse robot rule: " + robotRuleString);
final ResourceCost[] resourceCosts;
final RobotType robotType = RobotType.fromText(m.group(1));
final int resoureType1Amount = Integer.parseInt(m.group(2));
final ResourceType resourceType1 = ResourceType.fromText(m.group(3));
if (m.group(4)==null)
{
resourceCosts = new ResourceCost[1];
}
else
{
resourceCosts = new ResourceCost[2];
final int resoureType2Amount = Integer.parseInt(m.group(4));
final ResourceType resourceType2 = ResourceType.fromText(m.group(5));
resourceCosts[1] = new ResourceCost(resourceType2, resoureType2Amount);
}
resourceCosts[0] = new ResourceCost(resourceType1, resoureType1Amount);
return new RobotCosts(robotType, resourceCosts);
}
private int getID(final String idString)
{
final String[] parts = idString.split(" ");
return Integer.parseInt(parts[1]);
}
private String[] breakBlueprintInstructionsDownIntoRobotRuleInstructions(final String robotString)
{
final String[] parts = robotString.split("[.]");
final String[] result = new String[parts.length];
for (int i=0; i < parts.length; i++)
{
result[i] = parts[i].trim();
}
return result;
}
public ResourceCost[] getCostsForRobotType(final RobotType robotType)
{
for (final RobotCosts costs : robotCosts)
{
if (costs.robotType == robotType)
{
return costs.resourceCosts;
}
}
throw new IllegalStateException("Could getCostsForRobotType(): " + robotType);
}
public int getID()
{
return id;
}
}
Here’s the RobotFactory class:
final class RobotFactory
{
private List<BlueprintRunner> blueprintRunners = new ArrayList<>();
public void addBluePrint(final Blueprint blueprintToAdd)
{
final BlueprintRunner bpr = new BlueprintRunner3(blueprintToAdd);
blueprintRunners.add(bpr);
}
public void runAllBlueprints(final int numberOfMinutes)
{
for (final BlueprintRunner bpr: blueprintRunners)
{
bpr.runBlueprint(numberOfMinutes);
}
}
public long getTotalBlueprintCost()
{
int sum = 0;
for (final BlueprintRunner bpr: blueprintRunners)
{
sum += bpr.getID() * bpr.getNumberOfGeodes();
}
return sum;
}
public long getBlueprintCostForThree()
{
int mult = 1;
for (final BlueprintRunner bpr: blueprintRunners)
{
mult *= bpr.getNumberOfGeodes();
}
return mult;
}
}
I had other very slow and more generic BlueprintRunner1 and BlueprintRunner2 classes I will not be discussing, but BlueprintRunner3 was my fast enough one. There are probably additional ways to further speed this up, but once it got fast enough, I didn’t feel worth spending more time on it, it’s already been 2 days. There is a notable thing in that I used a long to cache my state (by assuming each value will fit in a single byte, and just shifting them around.) It also implements some clamps based on the specific rules of the blueprint, which cuts down on a lot of unnecessary extra branching in the recursion.
final class BlueprintRunner3 implements BlueprintRunner
{
private record RobotList(int numOreRobots, int numClayRobots, int numObsidianRobots, int numGeodeRobots) {};
private record ResourceList(int numOre, int numClay, int numObsidian, int numGeode) {};
private final Set<Long> cachedResults = new HashSet<>();
private final Blueprint blueprint;
private int bestNumGeodes;
private int geodeRobotOreCost;
private int geodeRobotClayCost;
private int geodeRobotObsidianCost;
private int oreClamp;
private int clayClamp;
public BlueprintRunner3(final Blueprint blueprintToRun)
{
blueprint = blueprintToRun;
}
@Override
public void runBlueprint(final int numberOfMinutes)
{
cachedResults.clear();
bestNumGeodes = 0;
setCostsForGeodeRobots();
setResourceClamps();
runBlueprint(1, numberOfMinutes, new RobotList(1,0,0,0), new ResourceList(0,0,0,0), 0);
}
// assuming you can only buy one robot per minute, then you never need to produce
// more of a resource than it will take to buy the most expensive robot
private void setResourceClamps()
{
final List<ResourceCost> allCosts = new ArrayList<>();
final ResourceCost[] oreRobotResourceCosts = blueprint.getCostsForRobotType(RobotType.ORE_ROBOT);
final ResourceCost[] clayRobotResourceCosts = blueprint.getCostsForRobotType(RobotType.CLAY_ROBOT);
final ResourceCost[] obsidianRobotResourceCosts = blueprint.getCostsForRobotType(RobotType.OBSIDIAN_ROBOT);
final ResourceCost[] geodeRobotResourceCosts = blueprint.getCostsForRobotType(RobotType.GEODE_ROBOT);
allCosts.add(oreRobotResourceCosts[0]);
if (oreRobotResourceCosts.length > 1) allCosts.add(oreRobotResourceCosts[1]);
allCosts.add(clayRobotResourceCosts[0]);
if (clayRobotResourceCosts.length > 1) allCosts.add(clayRobotResourceCosts[1]);
allCosts.add(obsidianRobotResourceCosts[0]);
if (obsidianRobotResourceCosts.length > 1) allCosts.add(obsidianRobotResourceCosts[1]);
allCosts.add(geodeRobotResourceCosts[0]);
if (geodeRobotResourceCosts.length > 1) allCosts.add(geodeRobotResourceCosts[1]);
oreClamp = 0;
clayClamp = 0;
for (final ResourceCost rc : allCosts)
{
switch (rc.resourceType())
{
case ORE:
{
if (rc.numberOfResource() > oreClamp) oreClamp = rc.numberOfResource();
}
break;
case CLAY:
{
if (rc.numberOfResource() > clayClamp) clayClamp = rc.numberOfResource();
}
break;
default: break;
}
}
}
private void setCostsForGeodeRobots()
{
final ResourceCost[] resourceCosts = blueprint.getCostsForRobotType(RobotType.GEODE_ROBOT);
int oreCost = 0;
int clayCost = 0;
int obsidianCost = 0;
for (final ResourceCost rc : resourceCosts)
{
switch (rc.resourceType())
{
case ORE: oreCost = rc.numberOfResource(); break;
case CLAY: clayCost = rc.numberOfResource(); break;
case OBSIDIAN: obsidianCost = rc.numberOfResource(); break;
default: throw new IllegalStateException();
}
}
geodeRobotOreCost = oreCost;
geodeRobotClayCost = clayCost;
geodeRobotObsidianCost = obsidianCost;
}
private void runBlueprint(final int minuteNumber, final int stopMinuteNumber, final RobotList incomingRobotList, final ResourceList incomingResourceList, final int incomingRobotVal)
{
RobotList robotList = incomingRobotList;
ResourceList resourceList = incomingResourceList;
if (minuteNumber >= stopMinuteNumber)
{
// Not going to buy any more robots, because they won't be active in time
resourceList = getResourceProduction(robotList, resourceList);
if (resourceList.numGeode() > bestNumGeodes)
{
bestNumGeodes = resourceList.numGeode();
}
return;
}
int robotVal = incomingRobotVal;
boolean boughtOreRobot = false;
boolean boughtClayRobot = false;
boolean boughtObsidianRobot = false;
boolean boughtGeodeRobot = false;
// Always buy Geode Robot if we can afford it
if ((robotVal < 4) && (canAffordGeodeRobot(resourceList)))
{
robotVal = 5;
resourceList = buyGeodeRobot(resourceList);
boughtGeodeRobot = true;
}
if ((robotVal < 1) && (canAffordObsidianRobot(resourceList)) )
{
robotVal = 1;
callIfNotCached(minuteNumber, stopMinuteNumber, robotList, resourceList, robotVal);
if (robotList.numObsidianRobots() < geodeRobotObsidianCost)
{
robotVal = 5;
resourceList = buyObsidianRobot(resourceList);
boughtObsidianRobot = true;
}
}
if ((robotVal < 2) && (canAffordOreRobot(resourceList)) )
{
robotVal = 2;
callIfNotCached(minuteNumber, stopMinuteNumber, robotList, resourceList, robotVal);
if (robotList.numOreRobots() < oreClamp)
{
robotVal = 5;
resourceList = buyOreRobot(resourceList);
boughtOreRobot = true;
}
}
if ((robotVal < 3) && (canAffordClayRobot(resourceList)) )
{
robotVal = 3;
callIfNotCached(minuteNumber, stopMinuteNumber, robotList, resourceList, robotVal);
if (robotList.numClayRobots() < clayClamp)
{
robotVal = 5;
resourceList = buyClayRobot(resourceList);
boughtClayRobot = true;
}
}
resourceList = getResourceProduction(robotList, resourceList);
if (boughtOreRobot) robotList = putOreRobotIntoProduction(robotList);
if (boughtClayRobot) robotList = putClayRobotIntoProduction(robotList);
if (boughtObsidianRobot) robotList = putObsidianRobotIntoProduction(robotList);
if (boughtGeodeRobot) robotList = putGeodeRobotIntoProduction(robotList);
callIfNotCached(minuteNumber+1, stopMinuteNumber, robotList, resourceList, 0);
return;
}
private void callIfNotCached(final int minuteNumber, final int stopMinuteNumber, final RobotList robotList, final ResourceList resourceList, final int robotVal)
{
final long robotCacheVal =
(((byte)robotList.numGeodeRobots()) << 24) |
(((byte)Math.min(robotList.numObsidianRobots(), geodeRobotObsidianCost)) << 16) |
(((byte)Math.min(robotList.numClayRobots(), clayClamp)) << 8) |
(((byte)Math.min(robotList.numOreRobots(), oreClamp)) );
final long resourceCacheVal =
(((byte)resourceList.numGeode()) << 24) |
(((byte)Math.min(resourceList.numObsidian(), 40)) << 16) |
(((byte)Math.min(resourceList.numOre(), 40)) << 8) |
(((byte)Math.min(resourceList.numClay(), 40)) );
final long cacheVal = (robotCacheVal << 40) | (resourceCacheVal << 8) | minuteNumber;
if (cachedResults.contains(cacheVal)) return;
runBlueprint(minuteNumber, stopMinuteNumber, robotList, resourceList, robotVal);
cachedResults.add(cacheVal);
}
private RobotList putOreRobotIntoProduction(final RobotList robotList)
{
return new RobotList(
robotList.numOreRobots() + 1,
robotList.numClayRobots(),
robotList.numObsidianRobots(),
robotList.numGeodeRobots()
);
}
private RobotList putClayRobotIntoProduction(final RobotList robotList)
{
return new RobotList(
robotList.numOreRobots(),
robotList.numClayRobots() + 1,
robotList.numObsidianRobots(),
robotList.numGeodeRobots()
);
}
private RobotList putObsidianRobotIntoProduction(final RobotList robotList)
{
return new RobotList(
robotList.numOreRobots(),
robotList.numClayRobots(),
robotList.numObsidianRobots() + 1,
robotList.numGeodeRobots()
);
}
private RobotList putGeodeRobotIntoProduction(final RobotList robotList)
{
return new RobotList(
robotList.numOreRobots(),
robotList.numClayRobots(),
robotList.numObsidianRobots(),
robotList.numGeodeRobots() + 1
);
}
private ResourceList getResourceProduction(final RobotList robotList, final ResourceList resourceList)
{
return new ResourceList(
resourceList.numOre() + robotList.numOreRobots(),
resourceList.numClay() + robotList.numClayRobots(),
resourceList.numObsidian() + robotList.numObsidianRobots(),
resourceList.numGeode() + robotList.numGeodeRobots()
);
}
private boolean canAffordOreRobot(final ResourceList resourceList)
{
final ResourceCost[] resourceCosts = blueprint.getCostsForRobotType(RobotType.ORE_ROBOT);
return canAffordResources(resourceList, resourceCosts);
}
private boolean canAffordClayRobot(final ResourceList resourceList)
{
final ResourceCost[] resourceCosts = blueprint.getCostsForRobotType(RobotType.CLAY_ROBOT);
return canAffordResources(resourceList, resourceCosts);
}
private boolean canAffordObsidianRobot(final ResourceList resourceList)
{
final ResourceCost[] resourceCosts = blueprint.getCostsForRobotType(RobotType.OBSIDIAN_ROBOT);
return canAffordResources(resourceList, resourceCosts);
}
private boolean canAffordGeodeRobot(final ResourceList resourceList)
{
final ResourceCost[] resourceCosts = blueprint.getCostsForRobotType(RobotType.GEODE_ROBOT);
return canAffordResources(resourceList, resourceCosts);
}
private ResourceList buyOreRobot(final ResourceList resourceList)
{
final ResourceCost[] resourceCosts = blueprint.getCostsForRobotType(RobotType.ORE_ROBOT);
return spendResources(resourceList, resourceCosts);
}
private ResourceList buyClayRobot(final ResourceList resourceList)
{
final ResourceCost[] resourceCosts = blueprint.getCostsForRobotType(RobotType.CLAY_ROBOT);
return spendResources(resourceList, resourceCosts);
}
private ResourceList buyObsidianRobot(final ResourceList resourceList)
{
final ResourceCost[] resourceCosts = blueprint.getCostsForRobotType(RobotType.OBSIDIAN_ROBOT);
return spendResources(resourceList, resourceCosts);
}
private ResourceList buyGeodeRobot(final ResourceList resourceList)
{
final ResourceCost[] resourceCosts = blueprint.getCostsForRobotType(RobotType.GEODE_ROBOT);
return spendResources(resourceList, resourceCosts);
}
private ResourceList spendResources(final ResourceList resourceList, final ResourceCost[] resourceCosts)
{
int numOreToSpend = 0;
int numClayToSpend = 0;
int numObsidianToSpend = 0;
for (final ResourceCost resourceCost : resourceCosts)
{
switch (resourceCost.resourceType())
{
case ORE: numOreToSpend += resourceCost.numberOfResource(); break;
case CLAY: numClayToSpend += resourceCost.numberOfResource(); break;
case OBSIDIAN: numObsidianToSpend += resourceCost.numberOfResource(); break;
default: break;
}
}
return new ResourceList(
resourceList.numOre()-numOreToSpend,
resourceList.numClay()-numClayToSpend,
resourceList.numObsidian()-numObsidianToSpend,
resourceList.numGeode()
);
}
private boolean canAffordResources(final ResourceList resourceList, final ResourceCost[] resourceCosts)
{
for (final ResourceCost resourceCost : resourceCosts)
{
switch (resourceCost.resourceType())
{
case ORE: if (resourceCost.numberOfResource() > resourceList.numOre()) return false; break;
case CLAY: if (resourceCost.numberOfResource() > resourceList.numClay()) return false; break;
case OBSIDIAN: if (resourceCost.numberOfResource() > resourceList.numObsidian()) return false; break;
default: return false;
}
}
return true;
}
@Override
public int getNumberOfGeodes()
{
return bestNumGeodes;
}
@Override
public int getID()
{
return blueprint.getID();
}
}
Finally the driver is pretty predictable but part 2 does give away information about the second part, so I will spoiler it:
final class Day19
{
public static long part1(final String[] day19InputLines)
{
final RobotFactory f = new RobotFactory();
for (final String blueprintString : day19InputLines)
{
final Blueprint bp = new Blueprint(blueprintString);
f.addBluePrint(bp);
}
f.runAllBlueprints(24);
return f.getTotalBlueprintCost();
}
public static long part2(final String[] day19InputLines)
{
final RobotFactory f = new RobotFactory();
int i=0;
for (final String blueprintString : day19InputLines)
{
i++;
final Blueprint bp = new Blueprint(blueprintString);
f.addBluePrint(bp);
if (i >= 3) break;
}
f.runAllBlueprints(32);
return f.getBlueprintCostForThree();
}
}
Time to post my day 20 now that I posted day 19 almost 2 days late. It was a challenge to come up with an approach that worked well, I tried a couple related to try to find patterns, but then I had the idea to mark the inputs with their input position at the start so I could find them again after they got shuffled. Once I had that idea, the rest was fairly straightforward. I created a class NumberShuffler to do the work.
The use of final long multiplier is a spoiler for part 2, I guess.
final class NumberShuffler
{
record NumberEntry(long value, int orginalIndex) {};
private List<NumberEntry> numbers = new ArrayList<>();
private final int numberOfInputNumbers;
public NumberShuffler(final String[] day20InputLines, final long multiplier)
{
numberOfInputNumbers = day20InputLines.length;
for (int i=0; i<numberOfInputNumbers; i++)
{
numbers.add(new NumberEntry(Integer.parseInt(day20InputLines[i]) * multiplier, i));
}
}
public void shuffle()
{
// When you pull an item out to relocate it, you have one less number for the
// modular arithmetic
final int numOfNumbersWhenOneRemoved = numberOfInputNumbers - 1;
for (int i=0; i<numberOfInputNumbers; i++)
{
final int startIndex = findNumberAtOriginalIndex(i);
final NumberEntry entryBeingRelocated = numbers.get(startIndex);
final long amountToMove = entryBeingRelocated.value();
if (amountToMove == 0)
{
continue;
}
numbers.remove(startIndex);
final int moveAmount = (int) (amountToMove % numOfNumbersWhenOneRemoved);
final int newInsertionPoint = ((startIndex + moveAmount) % numOfNumbersWhenOneRemoved + numOfNumbersWhenOneRemoved) % numOfNumbersWhenOneRemoved;
numbers.add(newInsertionPoint, entryBeingRelocated);
}
}
private int findNumberAtOriginalIndex(final int originalIndex)
{
for (int i=0; i<numberOfInputNumbers; i++)
{
if (numbers.get(i).orginalIndex() == originalIndex) return i;
}
throw new IllegalStateException("findNumberAtOriginalIndex() failed for: " + originalIndex);
}
private int findIndexOfValue(final int valueToFind)
{
for (int i=0; i<numberOfInputNumbers; i++)
{
if (numbers.get(i).value() == valueToFind) return i;
}
throw new IllegalStateException("findIndexOfValue() failed for: " + valueToFind);
}
private void dump()
{
for (final NumberEntry numEntry: numbers)
{
System.out.print(" " + numEntry.value());
}
System.out.println();
}
public long getPart1Result()
{
final int zeroIndex = findIndexOfValue(0);
return numbers.get((zeroIndex + 1000) % numberOfInputNumbers).value() +
numbers.get((zeroIndex + 2000) % numberOfInputNumbers).value() +
numbers.get((zeroIndex + 3000) % numberOfInputNumbers).value();
}
public long getValueAtIndex(final int index)
{
return numbers.get(index).value();
}
}
And the driver is again straightforward, but has part 2 spoilers:
final class Day20
{
public static long part1(final String[] day20InputLines)
{
final NumberShuffler ns = new NumberShuffler(day20InputLines, 1);
ns.shuffle();
return ns.getPart1Result();
}
public static long part2(final String[] day20InputLines)
{
final NumberShuffler ns = new NumberShuffler(day20InputLines, 811589153);
for (int i=0; i<10; i++)
{
ns.shuffle();
}
return ns.getPart1Result();
}
}
Day 21 was an expression evaluation challenge. Given named functions or values, you have to recursively look up the name and any names it references, and so on, until you calculate the requested value. I created a class named MonkeyMather and then copied it and named it MonkeyMather2 for part2 then added a few tweaks.
final class MonkeyMather
{
private record MonkeyEquation(int value, char operation, String lhs, String rhs) {};
final Map<String, MonkeyEquation> monkeyEquations = new HashMap<>();
public MonkeyMather(final String[] monkeyEquationStrings)
{
for (final String s : monkeyEquationStrings)
{
final String[] parts = s.split(": ");
final String monkeyName = parts[0].trim();
final String equationSide = parts[1];
if (!equationSide.contains(" "))
{
monkeyEquations.put(monkeyName, new MonkeyEquation(Integer.parseInt(equationSide), ' ', "",""));
}
else
{
if (equationSide.contains("+"))
{
final String[] parts2 = equationSide.split("[+]");
monkeyEquations.put(monkeyName, new MonkeyEquation(0, '+', parts2[0].trim(), parts2[1].trim()));
}
else if (equationSide.contains("-"))
{
final String[] parts2 = equationSide.split("[-]");
monkeyEquations.put(monkeyName, new MonkeyEquation(0, '-', parts2[0].trim(), parts2[1].trim()));
}
else if (equationSide.contains("*"))
{
final String[] parts2 = equationSide.split("[*]");
monkeyEquations.put(monkeyName, new MonkeyEquation(0, '*', parts2[0].trim(), parts2[1].trim()));
}
else if (equationSide.contains("/"))
{
final String[] parts2 = equationSide.split("[/]");
monkeyEquations.put(monkeyName, new MonkeyEquation(0, '/', parts2[0].trim(), parts2[1].trim()));
}
else
{
throw new IllegalStateException();
}
}
}
}
public long getValueFor(final String monkeyName)
{
return evaluate(monkeyName);
}
private long evaluate(final String monkeyName)
{
if (!monkeyEquations.containsKey(monkeyName)) throw new IllegalStateException("Can't find money: '" + monkeyName + "'");
final MonkeyEquation me = monkeyEquations.get(monkeyName);
switch (me.operation)
{
case ' ': return me.value;
case '+': return evaluate(me.lhs) + evaluate(me.rhs);
case '-': return evaluate(me.lhs) - evaluate(me.rhs);
case '*': return evaluate(me.lhs) * evaluate(me.rhs);
case '/': return evaluate(me.lhs) / evaluate(me.rhs);
}
return 0;
}
}
Which was called by the driver:
final class Day21
{
public static long part1(final String[] day21InputLines)
{
final MonkeyMather mm = new MonkeyMather(day21InputLines);
return mm.getValueFor("root");
}
Then for part 2 I made the change to get root and break it into lhs and rhs and add the return value for humn. I was worried that the humn value would be on both side or used more than once. In any case, I printed out the values at humn = 0 and then did some rough math by hand to get close and then let the computer finish. Other people working in Python did some sort of a thing involving polynomials that could just solve for the answer.
final class MonkeyMather2
{
private record MonkeyEquation(int value, char operation, String lhs, String rhs) {};
private final Map<String, MonkeyEquation> monkeyEquations = new HashMap<>();
private long humanVal;
public MonkeyMather2(final String[] monkeyEquationStrings)
{
for (final String s : monkeyEquationStrings)
{
final String[] parts = s.split(": ");
final String monkeyName = parts[0].trim();
final String equationSide = parts[1];
if (!equationSide.contains(" "))
{
monkeyEquations.put(monkeyName, new MonkeyEquation(Integer.parseInt(equationSide), ' ', "",""));
}
else
{
if (equationSide.contains("+"))
{
final String[] parts2 = equationSide.split("[+]");
monkeyEquations.put(monkeyName, new MonkeyEquation(0, '+', parts2[0].trim(), parts2[1].trim()));
}
else if (equationSide.contains("-"))
{
final String[] parts2 = equationSide.split("[-]");
monkeyEquations.put(monkeyName, new MonkeyEquation(0, '-', parts2[0].trim(), parts2[1].trim()));
}
else if (equationSide.contains("*"))
{
final String[] parts2 = equationSide.split("[*]");
monkeyEquations.put(monkeyName, new MonkeyEquation(0, '*', parts2[0].trim(), parts2[1].trim()));
}
else if (equationSide.contains("/"))
{
final String[] parts2 = equationSide.split("[/]");
monkeyEquations.put(monkeyName, new MonkeyEquation(0, '/', parts2[0].trim(), parts2[1].trim()));
}
else
{
throw new IllegalStateException();
}
}
}
}
public long getValueFor()
{
final MonkeyEquation me = monkeyEquations.get("root");
final String lhs = me.lhs;
final String rhs = me.rhs;
// humanVal = 301; // for unit test
for (long h = 3_617_613_950_000L; ; h++) // got close by hand
{
humanVal = h;
final long lhsVal = evaluate(lhs);
final long rhsVal = evaluate(rhs);
if (lhsVal == rhsVal)
{
return humanVal;
}
}
}
private long evaluate(final String monkeyName)
{
if (monkeyName.equals("humn")) return humanVal;
if (!monkeyEquations.containsKey(monkeyName)) throw new IllegalStateException("Can't find money: '" + monkeyName + "'");
final MonkeyEquation me = monkeyEquations.get(monkeyName);
switch (me.operation)
{
case ' ': return me.value;
case '+': return evaluate(me.lhs) + evaluate(me.rhs);
case '-': return evaluate(me.lhs) - evaluate(me.rhs);
case '*': return evaluate(me.lhs) * evaluate(me.rhs);
case '/': return evaluate(me.lhs) / evaluate(me.rhs);
}
return 0;
}
}
And the part2 driver is pretty obvious:
public static long part2(final String[] day21InputLines)
{
final MonkeyMather2 mm = new MonkeyMather2(day21InputLines);
return mm.getValueFor();
}