Day 15 was a challenge for me. Graph type algorithms are not something I have a lot of experience with. I created three different versions of solvers before I got to one that made sense to me, and ran in reasonable time and of course got the correct answers. What finally worked for me was realizing I could do a flood fill type algorithm where I only used moves to the right or down. Then that gave the correct answers for the sample input and the first part of the challenge input but not for the second part of the challenge input. I then realized that I had calculated a value that could be the best but that there might be better. I added an optimization pass and that got m all the way.
I created a class called RiskResolver to do the majority of the work:
final class RiskResolver
{
@org.eclipse.jdt.annotation.NonNullByDefault({})
record MapLocation(int x, int y) {}
private final int[][] riskMap;
private final int[][] riskFill;
private final int width;
private final int height;
private final int tileWidth;
private final int tileHeight;
public RiskResolver(final String[] inputRiskMap)
{
width = inputRiskMap[0].length();
height = inputRiskMap.length;
tileWidth=width;
tileHeight=height;
riskMap = new int[width][height];
riskFill = new int[width][height];
for (int y=0; y<height; y++)
{
for (int x=0; x<width; x++)
{
riskMap[x][y] = inputRiskMap[y].charAt(x)-'0';
}
}
}
public RiskResolver(final String[] inputRiskMap, int sizeMultiplier)
{
tileWidth = inputRiskMap[0].length();
tileHeight = inputRiskMap.length;
width = inputRiskMap[0].length() * sizeMultiplier;
height = inputRiskMap.length * sizeMultiplier;
riskMap = new int[width][height];
riskFill = new int[width][height];
for (int y=0; y<tileHeight; y++)
{
for (int x=0; x<tileWidth; x++)
{
riskMap[x][y] = inputRiskMap[y].charAt(x)-'0';
}
}
for (int i=1; i<sizeMultiplier; i++)
{
for (int y=0; y<tileHeight; y++)
{
for (int x=0; x<tileWidth; x++)
{
final int tileX = tileWidth*i + x;
final int tileY = y;
int tileValue = riskMap[x][y] + i;
if (tileValue > 9) tileValue -= 9;
riskMap[tileX][tileY] = tileValue;
}
}
}
for (int i=1; i<sizeMultiplier; i++)
{
for (int j=0; j<sizeMultiplier; j++)
{
for (int y=0; y<tileHeight; y++)
{
for (int x=0; x<tileWidth; x++)
{
final int tileX = tileWidth*j + x;
final int tileY = tileHeight*i + y;
int tileValue = riskMap[tileX][tileY-tileHeight] + 1;
if (tileValue > 9) tileValue -= 9;
riskMap[tileX][tileY] = tileValue;
}
}
}
}
}
long getLowestRiskPath()
{
fillMap();
optimizeMap();
return riskFill[width-1][height-1];
}
private void fillMap()
{
riskFill[0][0] = 0;
riskFill[0][1] = riskMap[0][1];
riskFill[1][0] = riskMap[1][0];
riskFill[1][1] = riskMap[1][1] + Math.min(riskFill[0][1], riskFill[1][0]);
int l=2;
while (l<width)
{
riskFill[l][0] = riskFill[l-1][0] + riskMap[l][0];
riskFill[0][l] = riskFill[0][l-1] + riskMap[0][l];
for (int i=1; i<=l; i++)
{
riskFill[i][l] = riskMap[i][l] + Math.min(riskFill[i-1][l], riskFill[i][l-1]);
riskFill[l][i] = riskMap[l][i] + Math.min(riskFill[l-1][i], riskFill[l][i-1]);
}
l++;
}
}
private void optimizeMap()
{
boolean madeChange = true;
while (madeChange)
{
madeChange = false;
for (int y=0; y<height; y++)
{
for (int x=0; x<width; x++)
{
int min=riskFill[x][y];
final Set<MapLocation> neighbours = getNeightbours(x,y);
for (final MapLocation neighbour : neighbours)
{
if (riskFill[neighbour.x][neighbour.y] + riskMap[x][y] < min)
{
riskFill[x][y] = riskFill[neighbour.x][neighbour.y] + riskMap[x][y];
min = riskFill[x][y];
madeChange = true;
}
}
}
}
}
}
private Set<MapLocation> getNeightbours(final int x, final int y)
{
final Set<MapLocation> neighbours = new HashSet<>();
if (x>0) neighbours.add(new MapLocation(x-1, y));
if (x<width-1) neighbours.add(new MapLocation(x+1, y));
if (y>0) neighbours.add(new MapLocation(x, y-1));
if (y<height-1) neighbours.add(new MapLocation(x, y+1));
return neighbours;
}
}
The two parts just call into the RiskResolver class, in the second part I call a different constructor to handle the changes to the map:
public static long getPart1Answer(final String day15Input, final String[] day15InputLines)
{
final RiskResolver rr = new RiskResolver(day15InputLines);
return rr.getLowestRiskPath();
}
public static long getPart2Answer(final String day15Input, final String[] day15InputLines)
{
final RiskResolver rr = new RiskResolver(day15InputLines, 5);
return rr.getLowestRiskPath();
}