Day 14 is pretty much Day 17 of 2022 ( Advent of Code 2022 - #75 by PHolder ) all over again. Basically you’ve got to simulate some activity (rolling rocks this year, letting tetris pieces fall last year) and report on some configuration value in part 1 and then in part 2 you’re going to be asked to simulate running a whole lot of activity. You will not be able to brute force part 2, so you need to consider if there is some other way to short circuit the problem.
The trick for part 2 is that the pattern will run for a while until it hits a configuration that is a start of a cycle. You then need to figure out how big the cycle is, and then you will be able to calculate how many full cycle repeats fit into the desired number of runs, and what the remainder will be. Then you basically tell your simulation to run the initial number until start of the cycle, and then run the remainder and you will be in the same state as having run the really big number of iterations. For example, say your cycle starts at move number 76 and the cycle is 53 moves long and your desired number of moves is 500_000. You would do (500_000-76)/53=9432 (integer division). Then you would find the remainder by doing 500_000-76-9432*53=28. So you would tell your simulation to run 76+28 times and find your result.
I created a helper class which I creatively called RockAndRoll:
final class RockAndRoll
{
private record Coordinates(int x, int y) {}
private final Set<Coordinates> rollingRockPositions = new HashSet<>();
private final Set<Coordinates> stationaryRockPositions = new HashSet<>();
private final int height;
private final int width;
public RockAndRoll(final String[] day14InputLines)
{
height = day14InputLines.length;
width = day14InputLines[0].length();
for (int y=0; y<height; y++)
{
for (int x=0; x<width; x++)
{
final char c = day14InputLines[y].charAt(x);
if (c == 'O')
{
rollingRockPositions.add(new Coordinates(x, y));
}
else if (c == '#')
{
stationaryRockPositions.add(new Coordinates(x, y));
}
}
}
}
public void rollToNorth()
{
boolean somethingMoved = false;
do
{
somethingMoved = false;
for (int y=1; y<height; y++)
{
for (int x=0; x<width; x++)
{
final Coordinates c = new Coordinates(x, y);
if (rollingRockPositions.contains(c))
{
final Coordinates potentialNewCoordiantes = new Coordinates(x, y-1);
if (isFreePosition(potentialNewCoordiantes))
{
rollingRockPositions.remove(c);
rollingRockPositions.add(potentialNewCoordiantes);
somethingMoved = true;
}
}
}
}
} while (somethingMoved);
}
public void rollToWest() // Part 2
{
boolean somethingMoved = false;
do
{
somethingMoved = false;
for (int x=1; x<width; x++)
{
for (int y=0; y<height; y++)
{
final Coordinates c = new Coordinates(x, y);
if (rollingRockPositions.contains(c))
{
final Coordinates potentialNewCoordiantes = new Coordinates(x-1, y);
if (isFreePosition(potentialNewCoordiantes))
{
rollingRockPositions.remove(c);
rollingRockPositions.add(potentialNewCoordiantes);
somethingMoved = true;
}
}
}
}
} while (somethingMoved);
}
public void rollToSouth() // Part 2
{
boolean somethingMoved = false;
do
{
somethingMoved = false;
for (int y=height-2; y>=0; y--)
{
for (int x=0; x<width; x++)
{
final Coordinates c = new Coordinates(x, y);
if (rollingRockPositions.contains(c))
{
final Coordinates potentialNewCoordiantes = new Coordinates(x, y+1);
if (isFreePosition(potentialNewCoordiantes))
{
rollingRockPositions.remove(c);
rollingRockPositions.add(potentialNewCoordiantes);
somethingMoved = true;
}
}
}
}
} while (somethingMoved);
}
public void rollToEast() // Part 2
{
boolean somethingMoved = false;
do
{
somethingMoved = false;
for (int x=width-2; x>=0; x--)
{
for (int y=0; y<height; y++)
{
final Coordinates c = new Coordinates(x, y);
if (rollingRockPositions.contains(c))
{
final Coordinates potentialNewCoordiantes = new Coordinates(x+1, y);
if (isFreePosition(potentialNewCoordiantes))
{
rollingRockPositions.remove(c);
rollingRockPositions.add(potentialNewCoordiantes);
somethingMoved = true;
}
}
}
}
} while (somethingMoved);
}
private boolean isFreePosition(final Coordinates coordiantes)
{
if (rollingRockPositions.contains(coordiantes)) return false;
if (stationaryRockPositions.contains(coordiantes)) return false;
return true;
}
public long getLoad()
{
long result = 0;
for (int y=0; y<height; y++)
{
final int loadFactor = height-y;
for (int x=0; x<width; x++)
{
final Coordinates c = new Coordinates(x, y);
if (rollingRockPositions.contains(c)) result += loadFactor;
}
}
return result;
}
// The string representation is used in Part 2 to detect when the
// cycle repeats
@Override
public String toString()
{
final StringBuilder sb = new StringBuilder();
for (int y=0; y<height; y++)
{
for (int x=0; x<width; x++)
{
final Coordinates c = new Coordinates(x, y);
if (rollingRockPositions.contains(c))
{
sb.append('O');
}
else if (stationaryRockPositions.contains(c))
{
sb.append('#');
}
else
{
sb.append('.');
}
}
sb.append("\n");
}
return sb.toString();
}
private void doOneCycle() // part 2
{
rollToNorth();
rollToWest();
rollToSouth();
rollToEast();
}
// Call once for part 2 to determine the values for the cycle length and cycle start
public long cycleUntilRepeat()
{
final Map<String, Integer> pastCycles = new HashMap<>();
int count = 0;
doOneCycle();
String config = toString();
int numCycles = 0;
int cycleStart = -1;
int cycleLength = -1;
int startOfCycle = -1;
while (numCycles < 4)
{
count++;
if (!pastCycles.containsKey(config))
{
pastCycles.put(config, count);
}
else
{
final int matchVal = pastCycles.get(config);
if (matchVal == cycleStart)
{
if (startOfCycle>0)
{
if (cycleLength < 0)
{
cycleLength = count - startOfCycle;
}
else
{
if (cycleLength != count - startOfCycle)
{
throw new IllegalStateException("Cycle length mismatch");
}
}
}
numCycles++;
startOfCycle = count;
}
if (cycleStart < 0) cycleStart = matchVal;
}
doOneCycle();
config = toString();
}
System.out.println("cycleStart = " + cycleStart);
System.out.println("cycleLength = " + cycleLength);
return count;
}
public void cycleNTimes(final int numCycles) // part 2
{
for (int i=0; i<numCycles; i++) doOneCycle();
}
}
This is the part 1 and part 2 methods. Part 2 is to be called with cycleStart and cycleLength (as well as numCyclesToRun which is 1_000_000_000.) Call it with all zeros to have it calculate those values.
public static Long part1(final String[] day14InputLines)
{
final RockAndRoll rar = new RockAndRoll(day14InputLines);
rar.rollToNorth();
return rar.getLoad();
}
public static Long part2(final String[] day14InputLines, final int cycleStart, final int cycleLength, final int numCyclesToRun)
{
final RockAndRoll rar = new RockAndRoll(day14InputLines);
// Run it one time with zero inputs to get the values for cycleStart and cycleLength
if (cycleLength == 0)
{
rar.cycleUntilRepeat();
return 0L;
}
rar.cycleNTimes(cycleStart);
final int numFullCycles = (numCyclesToRun-cycleStart)/cycleLength;
final int remainderCycles = numCyclesToRun - cycleStart - numFullCycles*cycleLength;
rar.cycleNTimes(remainderCycles);
return rar.getLoad();
}
Not shown here is how I called the part2() method with the input and three zero parameters first time to get the cycle start and length, and then replaced that call’s zeros with those new values after having determined them.