This is the thread for discussing your efforts at participating in Advent of Code 2024. You can ask questions if you need a hint, and you can post code here too, as I will probably be doing.
Day 1 is pretty straight forward, as one would expect. It involves working with two lists of numbers of the same size.
Part 1 is to sort the two lists and then sum the differences of corresponding elements.
Part 2 doesn’t require the sort (but it wouldn’t hurt) and you need to count occurrences of each number in list1 in list2.
As usual, I have a framework I use for each day. I’ve shown it here in past years, but here it is again.
This is the main driver code… it invokes the code below twice, once for each part.
public final class AdventOfCode2024Day01Main
{
final static String DAY01_INPUT =
"""
... my supplied inputs will be pasted here
""";
final static String[] DAY01_INPUT_LINES = DAY01_INPUT.split("\n");
public static void main(final String[] args)
{
System.out.println("Part 1: " + Day01.part1(DAY01_INPUT_LINES));
System.out.println("Part 2: " + Day01.part2(DAY01_INPUT_LINES));
/*
Part 1: I memorialize my actual result (when accepted) here for
Part 2: each part, just for future reference
*/
}
}
This is a class named after the day, where I write a line or two to create the class instance to solve the problem, and then pass it in the data. This is also called directly from my unit tests so I can use the supplied examples as unit tests to check my work before I submit the larger problem dataset. For today’s problem I called the solution class NumberListDiffer which will be shown below.
final class Day01
{
public static Long part1(final String[] day01InputLines)
{
final NumberListDiffer nld = new NumberListDiffer(day01InputLines);
return nld.calcDiff();
}
public static Long part2(final String[] day01InputLines)
{
final NumberListDiffer nld = new NumberListDiffer(day01InputLines);
return nld.calcSim();
}
}
Before I show the class that actually does the work, here’s my example unit test. I won’t be showing unit tests in future posts. I set it up for two example inputs, because usually there are at least two. For day 1 there was not two different lists, so I left one unused. You can see where I placed the two provided answers for the sample below, 11 and 31.
public class Day01Test
{
final static String SAMPLE_INPUT1 =
"""
3 4
4 3
2 5
1 3
3 9
3 3
""";
final static String SAMPLE_INPUT2 =
"""
""";
final static String[] SAMPLE_INPUT_LINES1 = SAMPLE_INPUT1.split("\n");
final static String[] SAMPLE_INPUT_LINES2 = SAMPLE_INPUT2.split("\n");
@Test
public void part1()
{
final long result = Day01.part1(SAMPLE_INPUT_LINES1);
assertEquals(11L, result);
}
@Test
public void part2()
{
final long result = Day01.part2(SAMPLE_INPUT_LINES1);
assertEquals(31L, result);
}
}
And finally the class that does the actual solving of the problem. The calcDiff() method does part 1 and calcSim() does part2. The trick for part 1 is to sort both lists first and to use the Math.abs() function to prevent any negatives. (Although I didn’t actually check if that was required, I wouldn’t be surprised if it were needed because that would be a good trick to catch people up on.) I don’t think there really is much of a trick for part 2, it’s quite straight-forward.
final class NumberListDiffer
{
final List<Integer> list1 = new ArrayList<>();
final List<Integer> list2 = new ArrayList<>();
public NumberListDiffer(final String[] day01InputLines)
{
for (final String line: day01InputLines)
{
final String[] parts = line.split("[ ]+");
final int int1 = Integer.parseInt(parts[0]);
final int int2 = Integer.parseInt(parts[1]);
list1.add(int1);
list2.add(int2);
}
if (list1.size() != list2.size()) throw new IllegalStateException("Lists not the same size");
}
public Long calcDiff()
{
final Integer[] l1 = list1.toArray(new Integer[0]);
final Integer[] l2 = list2.toArray(new Integer[0]);
Arrays.sort(l1);
Arrays.sort(l2);
long sum = 0;
for (int i=0; i<l1.length; i++)
{
sum+= Math.abs(l1[i]-l2[i]);
}
return sum;
}
public Long calcSim()
{
long sum = 0;
for (int i=0; i<list1.size(); i++)
{
int count = 0;
final int val = list1.get(i);
for (int j=0; j<list2.size(); j++)
{
if (val == list2.get(j)) count++;
}
sum += (val*count);
}
return sum;
}
}
1 Like
I’ve never done one of these, but I’ve always wanted to. I’ve never liked coding as much as I always wanted to. I’m more into system administration with a side of Python/JS.
I think this year I’ll try it out during the working hours of the day. Good work Paul (and I started watching Leo’s stream a lil bit)
Day 2 is about confirming a list of numbers to make sure they’re all either strictly increasing or all strictly decreasing. with no increase or decrease greater than 3. The ones that follow the rules are considered safe, and you’re asked to count them. For part 2, you’re allowed to ignore one of the numbers in the list.
I created a class LevelReportCheck to do the checking. I retroactively modified my checker for part 2.
final class LevelReportCheck
{
final String[] inputReports;
public LevelReportCheck(final String[] day02InputLines)
{
this.inputReports = day02InputLines;
}
public long countOfSafe() // Part 1
{
int count=0;
for (final String line : inputReports)
{
final int[] series = splitLineIntoIntArray(line);
if (checkASeries(series, -1)) count++; // the -1 parameter was added for part 2, it means
// not to exclude any parameter (which is necessary in part 2)
}
return count;
}
public long countOfSafe2() // Part 2
{
int count=0;
for (final String line : inputReports)
{
final int[] series = splitLineIntoIntArray(line);
if (!checkASeries(series, -1))
{
boolean modifiedIsOk = false;
for (int i=0; i<series.length; i++)
{
// Try every variation with one element skipped
if (checkASeries(series, i))
{
modifiedIsOk = true;
break;
}
}
if (modifiedIsOk) count++;
}
else count++;
}
return count;
}
private int[] splitLineIntoIntArray(final String line)
{
final String[] parts = line.split(" +"); // separate elements on one or more spaces
final int[] series = new int[parts.length];
for (int i=0; i<parts.length; i++)
{
series[i] = Integer.parseInt(parts[i]);
}
return series;
}
// The rules require a series to be strictly increasing or decreasing and no increase
// or decrease larger than 3
// Part 2 allows the option to skip one one of the inputs
private boolean checkASeries(final int[] series, final int indexToSkip)
{
boolean isOk = true;
boolean isIncreasing = true;
int prev=0;
int p=0; // This was added for part 2 because skipping broke checking the index i
for (int i=0; i<series.length; i++)
{
if (indexToSkip == i) continue; // Added for part 2 to allow skipping an element in the list
final int cur = series[i];
if (p==0) // This was (i==0) in part 1
{
prev=cur;
p++;
continue;
}
if (cur==prev) // Must be strictly increasing
{
isOk = false;
break;
}
// Once we have two numbers we can determine increasing or decreasing
if (p==1) // This was (i==1) in part 1
{
p++;
if (cur>prev)
isIncreasing = true;
else
isIncreasing = false;
}
if (isIncreasing)
{
if ((cur <= prev) || (cur-prev > 3))
{
isOk = false;
break;
}
}
else
{
if ((cur >= prev) || (prev-cur > 3))
{
isOk = false;
break;
}
}
prev=cur;
}
return isOk;
}
}
1 Like
I’ve streamed the first two days in real time - which is pretty bold for an amateur coder like me. But it turned out ok. You can watch the streams on my YouTube. My Common Lisp code is on Github. PHolder joined me last night -with great subtle hints!
I’ll try again tonight. 9p Pacific if you want to watch and chat as I humiliate myself.
Fortunately the first two days have been fairly simple so my embarassment has been kept to a minimum. In fact, it’s been really fun!
We’ll be doing a recap with PHolder, Darren, Cyphase, and more this Thursday, December 5, at 5p Pacific/8p Eastern/0100 UTC. Streaming on YouTube, Twitch, TikTok, X, Kick, Facebook, and LinkedIn. After the fact, the recap will be available to Club TWiT members on the TWiT+ feed.
2 Likes
I found it funny for day 2, my answers just switched the last two digits. Best way to describe it:
Inputs part 1 answer
Engineers: That number seem low
Me: Sorry, dyslexic moment there.
Inputs part 2 answer
1 Like
Day 3 has us looking through a memory dump that has corruption. The goal for part one is to recognize mult() instructions that take two parameters. We’re to find all of them, do the multiplication and then sum them all. For part 2 it gets a little trickier, because we need to only process mult()'s that do not get disabled by don't() instructions until they’re re-enabled by a do() instruction. We’re to assume that we start the input enabled.
I created the class CorruptionParser and as in Day 2, I simply tweaked my part 1 code to add a new aspect of it for part 2. I did this by passing in a boolean flag to indicate if part2 processing should be enabled. The real trick to accomplishing this challenge is to use regex matching. The addition of putting things in parentheses is a little trick to make sure you learn how to escape them in the regex because they would otherwise have special meaning to regex.
final class CorruptionParser
{
final String[] inputLines;
public CorruptionParser(final String[] inputLines)
{
this.inputLines = inputLines;
}
public long sumOfMults(final boolean enablePart2Filtering) // boolean parameter added for part 2
{
long sum = 0;
// This was the simplified pattern that worked for part 1, but while it still works for part 1 it
// had two other expressions added below for part 2
// final Pattern p = Pattern.compile("(mul[(]([-+0-9]+)[,]([-+0-9]+)[)])");
final Pattern p = Pattern.compile("(do[(][)]|don't[(][)]|mul[(]([-+0-9]+)[,]([-+0-9]+)[)])");
boolean multEnabled = true; // added for part 2
for (final String line : inputLines)
{
final Matcher m = p.matcher(line);
while (m.find())
{
// System.out.println(m.group());
if (m.group().equals("do()")) // added for part 2
{
multEnabled = true;
}
else if (m.group().equals("don't()")) // added for part 2
{
multEnabled = false;
}
else if (!enablePart2Filtering || multEnabled) // the entire "if" was added for part 2
sum += (Long.parseLong(m.group(2)) * Long.parseLong(m.group(3)));
}
}
return sum;
}
}
Day 4 is a search a word problem. A grid of letters in which we have to count occurrences of XMAS. There are 8 possible directions a word could be searched, for each of the 8 compass directions. The approach for this is simply to look at every possible x,y coordinate and then in each of the eight directions from there, keeping count as we go. Part 2’s twist is that we’re now looking for an “X-shaped” pair of MAS words that overlap on the centre A. This gives one of four possibilities to look for.
I wrote a class WordSearcher to do the bulk of the work.
final class WordSearcher
{
record Coord(int x, int y) {}
private final Map<Coord, Character> wordGrid = new HashMap<>();
private final int height;
private final int width;
public WordSearcher(final String[] inputGrid)
{
height = inputGrid.length;
width = inputGrid[0].length();
for (int y=0; y<height; y++)
{
for (int x=0; x<width; x++)
{
final Coord coord = new Coord(x,y);
wordGrid.put(coord, inputGrid[y].charAt(x));
}
}
}
public long countOccurencesOf(final String wordToLookFor) // Part 1, passed in XMAS
{
long count = 0;
final char[] word = wordToLookFor.toCharArray();
for (int y=0; y<height; y++)
{
for (int x=0; x<width; x++)
{
count += countWords(new Coord(x,y), word);
}
}
return count;
}
// Look in the 8 different compass directions
private long countWords(final Coord coord, final char[] word)
{
long result = 0;
if (wordIsPresent(coord, new Coord( 0, -1), word)) result++; // N
if (wordIsPresent(coord, new Coord( 0, 1), word)) result++; // S
if (wordIsPresent(coord, new Coord(-1, 0), word)) result++; // W
if (wordIsPresent(coord, new Coord( 1, 0), word)) result++; // E
if (wordIsPresent(coord, new Coord(-1, -1), word)) result++; // NW
if (wordIsPresent(coord, new Coord(-1, 1), word)) result++; // NE
if (wordIsPresent(coord, new Coord( 1, -1), word)) result++; // SW
if (wordIsPresent(coord, new Coord( 1, 1), word)) result++; // SE
return result;
}
private boolean wordIsPresent(final Coord startCoord, final Coord delta, final char[] word)
{
for (int i=0; i<word.length; i++)
{
final Coord letterCoord = new Coord(startCoord.x()+i*delta.x(), startCoord.y()+i*delta.y());
if (!wordGrid.containsKey(letterCoord)) return false; // went off the grid
if (wordGrid.get(letterCoord) != word[i]) return false;
}
return true;
}
public long countMASOccurences() // Part 2
{
long count = 0;
final char[] word = "MAS".toCharArray();
for (int y=0; y<height; y++)
{
for (int x=0; x<width; x++)
{
count += countMAS(new Coord(x,y), word);
}
}
return count;
}
private long countMAS(final Coord coord, final char[] word)
{
long result = 0;
if (wordGrid.get(coord) != word[1]) return 0; // No middle A
if (wordIsPresent(new Coord(coord.x()-1, coord.y()-1), new Coord( 1, 1), word))
{
if (wordIsPresent(new Coord(coord.x()+1, coord.y()-1), new Coord(-1, 1), word)) result++;
if (wordIsPresent(new Coord(coord.x()-1, coord.y()+1), new Coord( 1,-1), word)) result++;
}
if (wordIsPresent(new Coord(coord.x()+1, coord.y()+1), new Coord(-1,-1), word))
{
if (wordIsPresent(new Coord(coord.x()+1, coord.y()-1), new Coord(-1, 1), word)) result++;
if (wordIsPresent(new Coord(coord.x()-1, coord.y()+1), new Coord( 1,-1), word)) result++;
}
return result;
}
}
1 Like
Day 5 is manual updates… as in updating pages in a manual… at least in pretend. Part 1 we have to find the page numbers that are in the correct order and sum the middle page number. For part 2, we have to fix the pages that are not in the correct order by putting them in the correct order, and then also sum the [new] middle page number.
I had an approach to part 2 that seemed to be working, but not quite correctly. I was using lists and trying to insert into the list based on the page order info. While I was debugging that code, I noticed that the count of the number of page pairs was unique. This led me to my final solution, which is not something I would have thought of otherwise.
I created a class ManualPager to solve this day. One other approach that theoretically would work for part 2 would be to try all possible combinations of page orders. The issue is that my longest list to re-order was 23 elements long, and 23 factorial is a REALLY big number.
final class ManualPager
{
record PageOrderPair(int first, int second) {}
private final Set<PageOrderPair> pageOrderPairs = new HashSet<>();
private final String[] updates;
public ManualPager(final String[] pageOrders, final String[] updates)
{
for (final String pageOrderLine : pageOrders)
{
final String[] parts = pageOrderLine.split("[|]");
final int part1 = Integer.parseInt(parts[0]);
final int part2 = Integer.parseInt(parts[1]);
pageOrderPairs.add(new PageOrderPair(part1, part2));
}
this.updates = updates;
}
public long getMiddleSumOfCorrectlyOrderedUpdates() // Part 1
{
long sum = 0;
for (final String update : updates)
{
final String[] parts = update.split(",");
final int[] pageNumbers = new int[parts.length];
for (int i=0; i < parts.length; i++)
{
pageNumbers[i] = Integer.parseInt(parts[i]);
}
if (arePageNumbersInOrder(pageNumbers))
{
sum += getMiddle(pageNumbers);
}
}
return sum;
}
private boolean arePageNumbersInOrder(final int[] pageNumbers)
{
if (pageNumbers.length == 1) return true;
for (int i=1; i < pageNumbers.length; i++)
{
final int num1 = pageNumbers[i-1];
final int num2 = pageNumbers[i];
if (!areNumsInOrder(num1, num2)) return false;
}
return true;
}
private boolean areNumsInOrder(final int num1, final int num2)
{
if (pageOrderPairs.contains(new PageOrderPair(num1, num2))) return true;
return false;
}
private long getMiddle(final int[] pageNumbers)
{
final int middleIndex = pageNumbers.length/2;
return pageNumbers[middleIndex];
}
public long fixIncorrectlyOrderedUpdates() // Part 2
{
long sum = 0;
for (final String update : updates)
{
final String[] parts = update.split(",");
final int[] pageNumbers = new int[parts.length];
for (int i=0; i < parts.length; i++)
{
pageNumbers[i] = Integer.parseInt(parts[i]);
}
if (!arePageNumbersInOrder(pageNumbers))
{
final int[] newOrder = fixPageOrder(pageNumbers);
sum += getMiddle(newOrder);
}
}
return sum;
}
// One of the other competitors (Hi Cyphase) mentioned that this
// problem is a topological sort. My graph skills are weak I guess
// because I don't know what that is [yet]. But as I was trying
// a different approach, I noticed that there appears to be a unique
// number coming out while I was looping through the pairs as I do
// below. This led me to try this approach. This approach is
// O(n^2) but that's okay for these small sized inputs.
private int[] fixPageOrder(final int[] pageNumbers)
{
final int[] result = new int[pageNumbers.length];
for (int i=0; i < pageNumbers.length; i++)
{
int count = 0;
final int num1 = pageNumbers[i];
for (int j = 0; j < pageNumbers.length; j++)
{
if (i == j) continue;
final int num2 = pageNumbers[j];
final PageOrderPair testPair = new PageOrderPair(num1, num2);
if (pageOrderPairs.contains(testPair))
{
count++;
}
}
result[result.length - count - 1] = num1;
}
return result;
}
}
Day 6 is a prototypical Advent of Code problem. You have a grid and you’re tracking a guard moving around in the grid, and it turns clockwise when it hits something. Your goal for part1 is to find how many squares it will traverse before going off the grid. For part 2, you need to count the number of places where you could place a new obstruction and cause the guard to go into an [infinite] loop.
I created the class GuardPathPredictor. I ran into a couple of silly initial bugs as I was unit testing. In part 1 I returned the coordinates of the collision instead of the one short and in part 2 I didn’t initially store the direction as part of my loop detector.
final class GuardPathPredictor
{
record Coord(int x, int y) {}
private static final Coord BAD_COORD = new Coord(-1,-1);
private final int height;
private final int width;
private final Set<Coord> mapItems = new HashSet<>();
private Coord startPosition = BAD_COORD;
public GuardPathPredictor(final String[] inputMap)
{
height = inputMap.length;
width = inputMap[0].length();
for (int y=0; y<height; y++)
{
for (int x=0; x<width; x++)
{
final char c = inputMap[y].charAt(x);
final Coord coord = new Coord(x,y);
if (c == '^') startPosition = coord;
if (c == '#') mapItems.add(coord);
}
}
if (startPosition.equals(BAD_COORD)) throw new IllegalStateException("No start position");
}
private enum Dir {UP, DOWN, LEFT, RIGHT};
record LoopDetection(int x, int y, Dir d) {} // part 2
public long getGuardPathSize() // part 1
{
final Set<Coord> guardsPath = new HashSet<>();
final Set<LoopDetection> loopDetector = new HashSet<>(); // part 2
guardsPath.add(startPosition);
int x = startPosition.x();
int y = startPosition.y();
Dir d = Dir.UP;
while (x >= 0 && x < width && y >= 0 && y < height)
{
final Coord curCoord = new Coord(x,y);
switch (d)
{
case UP -> {y = moveUp(guardsPath, curCoord); d = Dir.RIGHT;}
case DOWN -> {y = moveDown(guardsPath, curCoord); d = Dir.LEFT;}
case LEFT -> {x = moveLeft(guardsPath,curCoord); d = Dir.UP;}
case RIGHT -> {x = moveRight(guardsPath, curCoord); d = Dir.DOWN;}
}
final LoopDetection possibleLoop = new LoopDetection(x,y,d); // part 2
if (loopDetector.contains(possibleLoop)) return -1; // part 2
loopDetector.add(possibleLoop); // part 2
}
return guardsPath.size();
}
private int moveUp(final Set<Coord> guardsPath, final Coord fromCoord)
{
final int x = fromCoord.x();
int y = fromCoord.y();
while (y>=0)
{
final Coord curCoord = new Coord(x,y);
if (mapItems.contains(curCoord)) return y+1;
guardsPath.add(curCoord);
y--;
}
return y;
}
private int moveDown(final Set<Coord> guardsPath, final Coord fromCoord)
{
final int x = fromCoord.x();
int y = fromCoord.y();
while (y<height)
{
final Coord curCoord = new Coord(x,y);
if (mapItems.contains(curCoord)) return y-1;
guardsPath.add(curCoord);
y++;
}
return y;
}
private int moveLeft(final Set<Coord> guardsPath, final Coord fromCoord)
{
int x = fromCoord.x();
final int y = fromCoord.y();
while (x>=0)
{
final Coord curCoord = new Coord(x,y);
if (mapItems.contains(curCoord)) return x+1;
guardsPath.add(curCoord);
x--;
}
return x;
}
private int moveRight(final Set<Coord> guardsPath, final Coord fromCoord)
{
int x = fromCoord.x();
final int y = fromCoord.y();
while (x<width)
{
final Coord curCoord = new Coord(x,y);
if (mapItems.contains(curCoord)) return x-1;
guardsPath.add(curCoord);
x++;
}
return x;
}
public long loopObstructionCount() // part 2
{
final Set<Coord> mapItemsBackup = new HashSet<>(mapItems);
int count = 0;
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
final Coord blockCoord = new Coord(x,y);
if (blockCoord.equals(startPosition)) continue;
if (mapItemsBackup.contains(blockCoord)) continue;
mapItems.clear();
mapItems.addAll(mapItemsBackup);
mapItems.add(blockCoord);
if (getGuardPathSize() < 0) count ++;
}
}
return count;
}
}
Day 7 is your prototypical recursion problem. You need to evaluate a set of numbers with potential operators between them (without normal order of precedence being applied) and see if there is a combination that can generate the supplied result. If you can generate the result (potentially more than one way) then you add the result to the sum, which is the final answer. For part 1 you have plus and multiply operations. For part 2 there is an additional concatenation operation.
I created a solver class named EquationSolver. I copied and pasted part 1 to make part 2, because that seemed more efficient than adding additional parameters to differentiate the two parts. Unfortunately that led to a bug for me because I initially forgot to change the call to recursiveEvaluate to be recursiveEvaluate2.
final class EquationSolver
{
record Equation(long result, long[] inputs) {}
private List<Equation> equations = new ArrayList<>();
public EquationSolver(final String[] equationsToValidate)
{
for (final String equationLine : equationsToValidate)
{
final String[] split1 = equationLine.split("[:] ");
final long result = Long.parseLong(split1[0]);
final String[] split2 = split1[1].split(" +");
final long[] inputs = new long[split2.length];
for (int i=0; i < split2.length; i++)
{
inputs[i] = Long.parseLong(split2[i]);
}
equations.add(new Equation(result, inputs));
}
}
public long sumOfResultsOfValidEquations() // part 1
{
long sum = 0;
for (final Equation potentiallyValidEquation : equations)
{
if (canBeMadeValidEquation(potentiallyValidEquation))
{
sum += potentiallyValidEquation.result();
}
}
return sum;
}
private boolean canBeMadeValidEquation(final Equation potentiallyValidEquation)
{
return recursiveEvaluate(potentiallyValidEquation.result, potentiallyValidEquation.inputs, 1, potentiallyValidEquation.inputs[0]);
}
private boolean recursiveEvaluate(final long result, final long[] inputs, final int position, final long resultInProgress)
{
if (position >= inputs.length)
{
if (resultInProgress == result) return true;
return false;
}
final boolean result1 = recursiveEvaluate(result, inputs, position+1, resultInProgress + inputs[position]);
final boolean result2 = recursiveEvaluate(result, inputs, position+1, resultInProgress * inputs[position]);
if (result1 || result2) return true;
return false;
}
public long sumOfResultsOfValidEquations2() //part 2
{
long sum = 0;
for (final Equation potentiallyValidEquation : equations)
{
if (canBeMadeValidEquation2(potentiallyValidEquation))
{
sum += potentiallyValidEquation.result();
}
}
return sum;
}
private boolean canBeMadeValidEquation2(final Equation potentiallyValidEquation)
{
return recursiveEvaluate2(potentiallyValidEquation.result, potentiallyValidEquation.inputs, 1, potentiallyValidEquation.inputs[0]);
}
private boolean recursiveEvaluate2(final long result, final long[] inputs, final int position, final long resultInProgress)
{
if (position >= inputs.length)
{
if (resultInProgress == result) return true;
return false;
}
final boolean result1 = recursiveEvaluate2(result, inputs, position+1, resultInProgress + inputs[position]);
final boolean result2 = recursiveEvaluate2(result, inputs, position+1, resultInProgress * inputs[position]);
final boolean result3 = recursiveEvaluate2(result, inputs, position+1, Long.parseLong(""+resultInProgress+ "" + inputs[position]));
if (result1 || result2 || result3) return true;
return false;
}
}
There is a minor optimization that can be added to the solver to check if the building result is already larger than the desired result, you can stop sooner. This is because the operations (multiply, addition and concatenation in part 2) only ever grow the number.
private boolean recursiveEvaluate2(final long result, final long[] inputs, final int position, final long resultInProgress)
{
if (resultInProgress > result) return false; // minor optimization possible because the operations only grow the result
if (position >= inputs.length)
{
if (resultInProgress == result) return true;
return false;
}
...
Good job Paul. Way to make it through the week 
Day 8 is about antennas. More specifically it’s about finding locations on either side of a pair of related antennas in a set of related antennas. I found the problem description confusing in a couple of different ways, so I’m not really going to try and explain it further here. Part 2 is a minor extension to part 1, really it shouldn’t pose much of a challenge to do part 2 after you succeeded at part 1, once you understand the request.
I created a class AntennaMapper to solve day 8.
final class AntennaMapper
{
record Coord(int x, int y) {}
record AntennaCoord(Coord coord, char name) {}
private final int height;
private final int width;
private final List<AntennaCoord> antennas = new ArrayList<>();
private final Set<Character> antennaNames = new HashSet<>();
private final Set<Coord> antinodeLocations = new HashSet<>();
public AntennaMapper(final String[] antennaMap)
{
height = antennaMap.length;
width = antennaMap[0].length();
for (int y=0; y < height; y++)
{
for (int x=0; x < width; x++)
{
final char c = antennaMap[y].charAt(x);
if (c != '.')
{
antennas.add(new AntennaCoord(new Coord(x, y), c));
antennaNames.add(c);
}
}
}
}
public long countAntiNodes() // part 1
{
for (final char c : antennaNames)
{
final List<AntennaCoord> namedAntennas = getNamedAntennas(c);
final int numAnt = namedAntennas.size();
if (numAnt < 2) continue;
for (int i=0; i<numAnt-1; i++)
{
final AntennaCoord ant1 = namedAntennas.get(i);
for (int j=i+1; j<numAnt; j++)
{
final AntennaCoord ant2 = namedAntennas.get(j);
getAntinodesInScope(ant1.coord().x(), ant1.coord().y(), ant2.coord().x(), ant2.coord().y());
}
}
}
return antinodeLocations.size();
}
private void getAntinodesInScope(final int x1, final int y1, final int x2, final int y2)
{
final int dx1 = x1 - x2;
final int dy1 = y1 - y2;
final int anti1x = x1 + dx1;
final int anti1y = y1 + dy1;
final int dx2 = x2 - x1;
final int dy2 = y2 - y1;
final int anti2x = x2 + dx2;
final int anti2y = y2 + dy2;
if (isXInScope(anti1x) && isYInScope(anti1y))
antinodeLocations.add(new Coord(anti1x, anti1y));
if (isXInScope(anti2x) && isYInScope(anti2y))
antinodeLocations.add(new Coord(anti2x, anti2y));
}
private boolean isXInScope(final int xToTest)
{
if (xToTest < 0) return false;
if (xToTest >= width) return false;
return true;
}
private boolean isYInScope(final int yToTest)
{
if (yToTest < 0) return false;
if (yToTest >= height) return false;
return true;
}
private List<AntennaCoord> getNamedAntennas(final char name)
{
final List<AntennaCoord> result = new ArrayList<>();
for (final AntennaCoord c : antennas)
{
if (c.name() == name) result.add(c);
}
return result;
}
public long countAntiNodes2() // part 2
{
for (final char c : antennaNames)
{
final List<AntennaCoord> namedAntennas = getNamedAntennas(c);
final int numAnt = namedAntennas.size();
if (numAnt < 2) continue;
for (int i=0; i<numAnt-1; i++)
{
final AntennaCoord ant1 = namedAntennas.get(i);
for (int j=i+1; j<numAnt; j++)
{
final AntennaCoord ant2 = namedAntennas.get(j);
getAntinodesInScope2(ant1.coord().x(), ant1.coord().y(), ant2.coord().x(), ant2.coord().y());
}
}
}
return antinodeLocations.size();
}
private void getAntinodesInScope2(final int x1, final int y1, final int x2, final int y2)
{
antinodeLocations.add(new Coord(x1, y1));
antinodeLocations.add(new Coord(x2, y2));
final int dx1 = x1 - x2;
final int dy1 = y1 - y2;
int anti1x = x1 + dx1;
int anti1y = y1 + dy1;
while (isXInScope(anti1x) && isYInScope(anti1y))
{
antinodeLocations.add(new Coord(anti1x, anti1y));
anti1x = anti1x + dx1;
anti1y = anti1y + dy1;
}
final int dx2 = x2 - x1;
final int dy2 = y2 - y1;
int anti2x = x2 + dx2;
int anti2y = y2 + dy2;
while (isXInScope(anti2x) && isYInScope(anti2y))
{
antinodeLocations.add(new Coord(anti2x, anti2y));
anti2x = anti2x + dx2;
anti2y = anti2y + dy2;
}
}
}
OK, so I have to ask, it’s now day 8, how far behind is Leo?
I believe he’s still working on the 2nd part of Day 6.
I went back and revisited Day 6 part 2 to get some additional optimization. (At the prompting of Leo who is finding his solution too slow.) My version above looks at the entire grid, whereas this version realizes that any new obstacle has to be placed in the path calculated in part 1. It also changes from using a backup copy of the map to just placing the obstacle for a loop check and then removing it before moving to the next check.
Most of the code for part 1 is the same, but I extracted it to a method so I could get the guards path and then called that for the size for part 1.
public long getGuardPathSize() // part 1
{
return getGuardsPath().size();
}
public Set<Coord> getGuardsPath()
{
...
if (loopDetector.contains(possibleLoop)) return new HashSet<>(); // part 2
...
return guardsPath;
}
I then replaced the part 2 code with this
// Optimized version, after the realization that any added obstacle
// must be in the original path of the guard. Also this version doesn't
// make a backup of the map, it just adds a new item as a block and then
// removes it before moving on to next location
public long loopObstructionCount() // part 2
{
int count = 0;
final Set<Coord> guardsOriginalPath = getGuardsPath();
for (final Coord coordInOriginalPath : guardsOriginalPath)
{
if (coordInOriginalPath.equals(startPosition)) continue;
mapItems.add(coordInOriginalPath);
if (getGuardPathSize() <= 0) count ++;
mapItems.remove(coordInOriginalPath);
}
return count;
}
The difference this made in processing time for part 2 is:
2.2279952s (before optimization) became 0.6035976s (after optimization)
Day 9 has us pretending to be an operating system’s file system manager. I created a class DiskHandler. There’s not really a lot of discussion to be had about the process of the differences between part 1 and 2. Pretty much you have to read the problem, and re-read it, until it makes sense, and then just implement the described processes. The one thing that did slow me down doing part 1 was that I needed an extra “cleanup pass” at the end because the moved file portions left a hole behind.
final class DiskHandler
{
final String diskDescription;
public DiskHandler(final String inputDiskDescription)
{
diskDescription = inputDiskDescription + "0";
}
record FileDescription(int fileStartBlock, int fileSize, int fileNumber) {}
record FreeBlock(int startBlock, int size) {}
public long getCompactedChecksum() // part 1
{
final List<FileDescription> fileDescriptions = new ArrayList<>();
final List<FreeBlock> freeBlocks = new ArrayList<>();
// Parse the input into pairs. Track the files and the free spaces in
// separate lists
int fileBlock = 0;
int fileNumber = 0;
for (int pos=0; pos < diskDescription.length(); pos += 2)
{
final int fileSize = diskDescription.charAt(pos)-'0';
final int freeSpaceAfterFile = diskDescription.charAt(pos+1)-'0';
final FileDescription fd = new FileDescription(fileBlock, fileSize, fileNumber++);
fileDescriptions.add(fd);
fileBlock += fileSize;
freeBlocks.add(new FreeBlock(fileBlock, freeSpaceAfterFile));
fileBlock += freeSpaceAfterFile;
}
// Make an array to track all the blocks, and initialize it to minus one
// because 0 is a valid file number
final int blocks[] = new int[fileBlock];
for (int i=0; i<fileBlock; i++) blocks[i] = -1;
// Copy the file numbers into the array, we'll need that info to
// calculate the checksum later
for (final FileDescription fd : fileDescriptions)
{
for (int i=0; i < fd.fileSize; i++)
{
blocks[fd.fileStartBlock + i] = fd.fileNumber;
}
}
// Move files from the end into the tracked empty spaces
int endPos = fileBlock-1;
for (final FreeBlock fb : freeBlocks)
{
final int numBlocksToMove = fb.size;
endPos = moveBlocksFromEnd(blocks, numBlocksToMove, endPos, fb.startBlock);
}
// "Cleanup phase" to get straggler blocks at the end
int curEmptyBlock = findNextEmptyBlock(blocks, 0);
endPos = fileBlock-1;
while (endPos > curEmptyBlock)
{
if (blocks[endPos] != -1)
{
blocks[curEmptyBlock] = blocks[endPos];
blocks[endPos] = -1;
curEmptyBlock = findNextEmptyBlock(blocks, curEmptyBlock+1);
}
endPos--;
}
// Calculate the checksum... sum of block number times
// the file number occupying the block
long checksum = 0;
for (int i=0; i<fileBlock; i++)
{
if (blocks[i] != -1)
{
checksum += i*blocks[i];
}
}
return checksum;
}
private int findNextEmptyBlock(final int[] blocks, final int startSearchPoint)
{
int pos = startSearchPoint;
while (blocks[pos] != -1) pos++;
return pos;
}
private int moveBlocksFromEnd(final int[] blocks, final int numBlocksToMove, final int endPos, final int startBlock)
{
int blocksLeft = numBlocksToMove;
int searchPos = endPos;
int destBlock = startBlock;
while (blocksLeft > 0)
{
while (blocks[searchPos]==-1) searchPos--;
blocks[destBlock++] = blocks[searchPos];
blocks[searchPos--] = -1;
blocksLeft--;
}
return searchPos;
}
public long getCompactedChecksum2() // part 2
{
final List<FileDescription> fileDescriptions = new ArrayList<>();
final List<FreeBlock> freeBlocks = new ArrayList<>();
// Same parsing as in part one
int fileBlock = 0;
int fileNumber = 0;
for (int pos=0; pos < diskDescription.length(); pos += 2)
{
final int fileSize = diskDescription.charAt(pos)-'0';
final int freeSpaceAfterFile = diskDescription.charAt(pos+1)-'0';
final FileDescription fd = new FileDescription(fileBlock, fileSize, fileNumber++);
fileDescriptions.add(fd);
fileBlock += fileSize;
freeBlocks.add(new FreeBlock(fileBlock, freeSpaceAfterFile));
fileBlock += freeSpaceAfterFile;
}
// Same array as in part one
final int blocks[] = new int[fileBlock];
for (int i=0; i<fileBlock; i++) blocks[i] = -1;
for (final FileDescription fd : fileDescriptions)
{
for (int i=0; i < fd.fileSize; i++)
{
blocks[fd.fileStartBlock + i] = fd.fileNumber;
}
}
// The instructions say to make one attempt to move each file
// from the highest file number to the lowest
for (int fileNum = fileDescriptions.size()-1; fileNum > 0; fileNum--)
{
final FileDescription fd = fileDescriptions.get(fileNum);
for (int j=0; j < freeBlocks.size(); j++)
{
final FreeBlock fb = freeBlocks.get(j);
if (fb.startBlock >= fd.fileStartBlock) break;
if (fb.size >= fd.fileSize)
{
moveFile(blocks, fd.fileStartBlock, fd.fileSize, fb.startBlock);
// Since a block is rarely the same size as the [smaller] file that
// will fit there, we need to track the remainder as a free block
if (fd.fileSize != fb.size)
{
freeBlocks.add(j+1, new FreeBlock(fb.startBlock + fd.fileSize, fb.size - fd.fileSize));
}
freeBlocks.remove(j);
break;
}
}
}
// Same checksum algorithm as in part one
long checksum = 0;
for (int i=0; i<fileBlock; i++)
{
if (blocks[i] != -1)
{
checksum += i*blocks[i];
}
}
return checksum;
}
private void moveFile(final int[] blocks, final int fromStartBlock, final int numberOfBlocksToMove, final int destStartBlock)
{
for (int i=0; i<numberOfBlocksToMove; i++)
{
blocks[destStartBlock+i] = blocks[fromStartBlock+i];
blocks[fromStartBlock+i] = -1;
}
}
}
Day 10 is path finding with a twist in part 2. I implemented both parts as a sort of modified flood fill. I created a class TrailFinder. For part 1 we use a set to track places already visited so we don’t visit them more than once. For part 2 we need to allow revisits, because we’re splitting the path every time we have more than one adjacent exit from a location. In this case we use a set to track how many of the paths (by number) end up at a summit.
final class TrailFinder
{
record Coord(int x, int y) {}
private final Map<Coord, Integer> topography = new HashMap<>();
private final List<Coord> trailHeads = new ArrayList<>();
private final int height;
private final int width;
private int pathNum = 0;
public TrailFinder(final String[] topographicData)
{
height = topographicData.length;
width = topographicData[0].length();
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
final char c = topographicData[y].charAt(x);
final Coord coord = new Coord(x, y);
if (c == '0')
{
trailHeads.add(coord);
}
else
{
int height = c - '0';
topography.put(coord, height);
}
}
}
}
public long findSumOfTrailheads() // part 1
{
long sum = 0;
for (final Coord trailHead : trailHeads)
{
final long numReachable = determineNumberOfReachableSummits(trailHead);
sum += numReachable;
}
return sum;
}
private long determineNumberOfReachableSummits(final Coord trailHead)
{
final Deque<Coord> stack = new ArrayDeque<>();
final Set<Coord> alreadyVisited = new HashSet<>();
alreadyVisited.add(trailHead);
long count = 0;
pushReachablePlaces(stack, trailHead, 0, alreadyVisited);
while (!stack.isEmpty())
{
final Coord curCoord = stack.pop();
final int curHeight = topography.get(curCoord);
alreadyVisited.add(curCoord);
if (curHeight == 9)
{
count++;
}
else
{
pushReachablePlaces(stack, curCoord, curHeight, alreadyVisited);
}
}
return count;
}
private void pushReachablePlaces(final Deque<Coord> stack, final Coord coord, final int fromHeight, final Set<Coord> alreadyVisited)
{
final Coord northCoord = new Coord(coord.x(), coord.y() - 1);
final Coord southCoord = new Coord(coord.x(), coord.y() + 1);
final Coord eastCoord = new Coord(coord.x() + 1, coord.y());
final Coord westCoord = new Coord(coord.x() - 1, coord.y());
pushToStackIfHeight(stack, northCoord, fromHeight+1, alreadyVisited);
pushToStackIfHeight(stack, southCoord, fromHeight+1, alreadyVisited);
pushToStackIfHeight(stack, eastCoord, fromHeight+1, alreadyVisited);
pushToStackIfHeight(stack, westCoord, fromHeight+1, alreadyVisited);
}
private void pushToStackIfHeight(final Deque<Coord> stack, final Coord coord, final int heightToMatch, final Set<Coord> alreadyVisited)
{
if (alreadyVisited.contains(coord)) return;
if (!topography.containsKey(coord)) return;
final int targetHeight = topography.get(coord);
if (targetHeight != heightToMatch) return;
stack.push(coord);
}
public long findSumOfTrailheads2() // part 2
{
long sum = 0;
for (final Coord trailHead : trailHeads)
{
final long numReachable = determineNumberOfReachableSummits2(trailHead);
sum += numReachable;
}
return sum;
}
// For part 2, we need to track each separate path that ends up
// reaching a summit. Every time the path splits into two or more
// directions it gets a new path number
record Coord2(int x, int y, int pathNum) {}
private long determineNumberOfReachableSummits2(final Coord trailHead)
{
final Deque<Coord2> stack = new ArrayDeque<>();
final Set<Integer> pathsThatReached = new HashSet<>();
pathNum = 0;
pushReachablePlaces2(stack, new Coord2(trailHead.x(), trailHead.y(), pathNum), 0);
while (!stack.isEmpty())
{
final Coord2 curCoord2 = stack.pop();
final Coord curCoord = new Coord(curCoord2.x(), curCoord2.y());
final int curHeight = topography.get(curCoord);
if (curHeight == 9)
{
pathsThatReached.add(curCoord2.pathNum());
}
else
{
pushReachablePlaces2(stack, curCoord2, curHeight);
}
}
return pathsThatReached.size();
}
private void pushReachablePlaces2(final Deque<Coord2> stack, final Coord2 coord2, final int fromHeight)
{
final List<Coord> nearbyPlaces = new ArrayList<>();
final Coord coord = new Coord(coord2.x(), coord2.y());
final int curPathNum = coord2.pathNum();
final Coord northCoord = new Coord(coord.x(), coord.y() - 1);
final Coord southCoord = new Coord(coord.x(), coord.y() + 1);
final Coord eastCoord = new Coord(coord.x() + 1, coord.y());
final Coord westCoord = new Coord(coord.x() - 1, coord.y());
addToListIfReachable(nearbyPlaces, northCoord, fromHeight+1);
addToListIfReachable(nearbyPlaces, southCoord, fromHeight+1);
addToListIfReachable(nearbyPlaces, eastCoord, fromHeight+1);
addToListIfReachable(nearbyPlaces, westCoord, fromHeight+1);
final int numberOfReachablePlaces = nearbyPlaces.size();
if (numberOfReachablePlaces == 0) return; // dead end
// The first place keeps the existing path num
final Coord theFirstPlace = nearbyPlaces.getFirst();
stack.push(new Coord2(theFirstPlace.x(), theFirstPlace.y(), curPathNum));
if (numberOfReachablePlaces > 1)
{
// There's a split in the path, give it a new path num
final Coord theSecondPlace = nearbyPlaces.get(1);
stack.push(new Coord2(theSecondPlace.x(), theSecondPlace.y(), getNewPathNum()));
}
if (numberOfReachablePlaces > 2)
{
// There's a split in the path, give it a new path num
final Coord theThirdPlace = nearbyPlaces.get(2);
stack.push(new Coord2(theThirdPlace.x(), theThirdPlace.y(), getNewPathNum()));
}
if (numberOfReachablePlaces > 3) // should only happen at a trailhead
{
// There's a split in the path, give it a new path num
final Coord theFourthPlace = nearbyPlaces.get(3);
stack.push(new Coord2(theFourthPlace.x(), theFourthPlace.y(), getNewPathNum()));
}
if (numberOfReachablePlaces > 4) throw new IllegalStateException();
}
private int getNewPathNum()
{
return ++pathNum;
}
private void addToListIfReachable(final List<Coord> listToAddNearbyPlacesTo, final Coord coord, final int heightToMatch)
{
if (!topography.containsKey(coord)) return;
final int targetHeight = topography.get(coord);
if (targetHeight != heightToMatch) return;
listToAddNearbyPlacesTo.add(coord);
}
}
Day 11 could potentially remind you of 2021’s Day 6. The approach for solving it is similar. You can do part one by brute force, and I did it that way just to get it done. I figured, even as I was writing my part 1 code, that it would need to be done a different way for part 2… and that proved out. My answer for part 2 is approximately 240T, so there is no way to keep track and process lists of numbers that big. Accordingly I created a helper class called CountKeeper.
final class CountKeeper
{
final Map<Long, Long> counts = new HashMap<>();
public long getCountOf(final long valueToGetCountOf)
{
if (!counts.containsKey(valueToGetCountOf)) return 0;
return counts.get(valueToGetCountOf);
}
public void increaseCountOf(final long valueToIncreaseCountOf, final long amountToIncreaseBy)
{
if (!counts.containsKey(valueToIncreaseCountOf))
counts.put(valueToIncreaseCountOf, amountToIncreaseBy);
else
counts.put(valueToIncreaseCountOf, counts.get(valueToIncreaseCountOf) + amountToIncreaseBy);
}
public long[] getCountedValues()
{
final long[] result = new long[counts.size()];
int i = 0;
for (final Long val : counts.keySet())
{
result[i++] = val;
}
return result;
}
}
and then used it in part 2 of my solver class NumberBlinker. I kept my part 1 implementation intact, but ultimately I updated my part 1 code to call part 2 because it’s so much faster… See my times below.
final class NumberBlinker
{
private final long[] inputNumbers;
public NumberBlinker(final long[] inputNumbers)
{
this.inputNumbers = inputNumbers;
}
public long blinkNTimes(final int numberOfBlinks) // part 1
{
return getNumbersAfterBlinkNTimes(numberOfBlinks).length;
}
// I allowed to get the array because at one point I was outputting
// the sizes to see if there was any discernible pattern
public Long[] getNumbersAfterBlinkNTimes(final int numberOfBlinks)
{
List<Long> numbers = new ArrayList<>();
for (final long number : inputNumbers) numbers.add(number);
for (int i=0; i<numberOfBlinks; i++)
{
final List<Long> newNumbers = new ArrayList<>();
for (final long number : numbers)
{
if (number == 0)
{
newNumbers.add(1L);
continue;
}
final int n = (int) Math.log10(number) + 1; // get length of number
if (n % 2 == 0) // if length is even, split in half
{
final long left = number / (long)Math.pow(10, n/2);
final long right = number % (long)Math.pow(10, n/2);
newNumbers.add(left);
newNumbers.add(right);
continue;
}
newNumbers.add(number * 2024);
}
numbers= newNumbers;
}
return numbers.toArray(new Long[0]);
}
// The trick to doing part 2 is to realize you can't have an ever growing array,
// so you need to instead keep track of the count of each number that the
// process generates. I created a helper class called CountKeeper to help.
public long blinkNTimesByCounting(final int numberOfBlinks) // part 2
{
CountKeeper ck = new CountKeeper();
for (int i=0; i<inputNumbers.length; i++)
{
ck.increaseCountOf(inputNumbers[i], 1);
}
for (int i=0; i<numberOfBlinks; i++)
{
final CountKeeper newCK = new CountKeeper();
for (final long countedValue : ck.getCountedValues())
{
final long numOfValue = ck.getCountOf(countedValue);
if (countedValue == 0)
{
newCK.increaseCountOf(1, numOfValue);
continue;
}
final int n = (int) Math.log10(countedValue) + 1;
if (n % 2 == 0)
{
final long left = countedValue / (long)Math.pow(10, n/2);
final long right = countedValue % (long)Math.pow(10, n/2);
newCK.increaseCountOf(left, numOfValue);
newCK.increaseCountOf(right, numOfValue);
}
else
{
newCK.increaseCountOf(countedValue * 2024L, numOfValue);
}
}
ck = newCK;
}
long sum = 0;
for (final long countedValue : ck.getCountedValues())
sum += ck.getCountOf(countedValue);
return sum;
}
}
Here’s my run times:
Part 1: 0.0090087s
Part 2: 0.0360327s
Day 12 has us fencing in patches of different parts of a garden. To solve it I created two classes, first a GardenFencer class to manage the overall garden map and figure out where the patches are, and then GardenPatch to do the necessary math to determine the area, perimeter and (for part 2) the number of sides of each garden patch.
First is GardenFencer. It uses a flood fill to determine the extents of each garden patch.
final class GardenFencer
{
record Coord(int x, int y) {}
private final List<GardenPatch> gardenPatches = new ArrayList<GardenPatch>();
private final Map<Coord, GardenPatch> mappingOfCoordToGardenPatch = new HashMap<>();
private final Map<Coord, Character> gardenMap = new HashMap<>();
private final int height;
private final int width;
public GardenFencer(final String[] inputGardenMap)
{
height = inputGardenMap.length;
width = inputGardenMap[0].length();
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
final char c = inputGardenMap[y].charAt(x);
final Coord coord = new Coord(x, y);
gardenMap.put(coord, c);
}
}
// Find each patch by looking at a given coordinate and seeing
// if we've already mapped it to an existing patch, and if not
// do a flood fill from the coordinate to find all the rest
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
final Coord coord = new Coord(x, y);
if (mappingOfCoordToGardenPatch.containsKey(coord)) continue; // already in a patch
final Set<Coord> gardenPatchCoords = extractGardenPatchCoords(coord);
final GardenPatch newGardenPatch = new GardenPatch(gardenPatchCoords);
gardenPatches.add(newGardenPatch);
for (final Coord gardenPatchCoord : gardenPatchCoords)
{
mappingOfCoordToGardenPatch.put(gardenPatchCoord, newGardenPatch);
}
}
}
}
// Do a flood fill to find the extent of the garden patch
private Set<Coord> extractGardenPatchCoords(final Coord startCoord)
{
final Set<Coord> result = new HashSet<>();
final char gardenChar = getGardenMapChar(startCoord);
result.add(startCoord);
final Deque<Coord> stack = new ArrayDeque<>();
stack.push(startCoord);
while (!stack.isEmpty())
{
final Coord curCoord = stack.pop();
final Coord north = new Coord(curCoord.x(), curCoord.y() - 1);
final char northGardenChar = getGardenMapChar(north);
if (northGardenChar == gardenChar)
{
if (!result.contains(north))
{
result.add(north);
stack.push(north);
}
}
final Coord south = new Coord(curCoord.x(), curCoord.y() + 1);
final char southGardenChar = getGardenMapChar(south);
if (southGardenChar == gardenChar)
{
if (!result.contains(south))
{
result.add(south);
stack.push(south);
}
}
final Coord east = new Coord(curCoord.x() + 1, curCoord.y());
final char eastGardenChar = getGardenMapChar(east);
if (eastGardenChar == gardenChar)
{
if (!result.contains(east))
{
result.add(east);
stack.push(east);
}
}
final Coord west = new Coord(curCoord.x() - 1, curCoord.y());
final char westGardenChar = getGardenMapChar(west);
if (westGardenChar == gardenChar)
{
if (!result.contains(west))
{
result.add(west);
stack.push(west);
}
}
}
return result;
}
private char getGardenMapChar(final Coord startCoord)
{
if (!gardenMap.containsKey(startCoord)) return '#';
return gardenMap.get(startCoord);
}
public long getSumOfAllFencingNeeds() // part 1
{
long sum = 0;
for (final GardenPatch gardenPatch : gardenPatches)
{
sum += gardenPatch.getArea() * gardenPatch.getPerimeter();
}
return sum;
}
public long getSumOfAllFencingNeeds2() // part 2
{
long sum = 0;
for (final GardenPatch gardenPatch : gardenPatches)
{
sum += gardenPatch.getArea() * gardenPatch.getNumberOfSides();
}
return sum;
}
}
And here’s GardenPatch which keeps track of all the coordinates of the garden patch. This means the area is just the number of coordinates, and the perimeter can be determined by counting the number of coordinates that don’t have a neighbour coordinate in each of the four cardinal directions. Determining the number of sides for part 2 is a little trickier. Basically what it does is use an approach similar to the perimeter to separate out all the north perimeter pieces and south perimeter pieces and east perimeter pieces and west perimeter pieces. Then for each of these subsets, it iterates over them, skipping any it’s already processed, and then looking in each of the two delta directions (east/west for the north and south perimeter subsets, and north/south for the east and west perimeter subsets) to determine the extent of that side.
final class GardenPatch
{
private final Set<Coord> gardenPatchCoords;
GardenPatch(final Set<Coord> inputgardenPatchCoords)
{
gardenPatchCoords = inputgardenPatchCoords;
}
public int getArea() // part 1
{
return gardenPatchCoords.size();
}
public int getPerimeter() // part 1
{
int result = 0;
for (final Coord curCoord : gardenPatchCoords)
{
final Coord north = new Coord(curCoord.x(), curCoord.y() - 1);
final Coord south = new Coord(curCoord.x(), curCoord.y() + 1);
final Coord east = new Coord(curCoord.x() + 1, curCoord.y());
final Coord west = new Coord(curCoord.x() - 1, curCoord.y());
if (!gardenPatchCoords.contains(north)) result ++;
if (!gardenPatchCoords.contains(south)) result ++;
if (!gardenPatchCoords.contains(east)) result ++;
if (!gardenPatchCoords.contains(west)) result ++;
}
return result;
}
public int getNumberOfSides() // part 2
{
final Set<Coord> northCoords = new HashSet<>();
final Set<Coord> southCoords = new HashSet<>();
final Set<Coord> eastCoords = new HashSet<>();
final Set<Coord> westCoords = new HashSet<>();
for (final Coord curCoord : gardenPatchCoords)
{
final Coord north = new Coord(curCoord.x(), curCoord.y() - 1);
final Coord south = new Coord(curCoord.x(), curCoord.y() + 1);
final Coord east = new Coord(curCoord.x() + 1, curCoord.y());
final Coord west = new Coord(curCoord.x() - 1, curCoord.y());
if (!gardenPatchCoords.contains(north)) northCoords.add(north);
if (!gardenPatchCoords.contains(south)) southCoords.add(south);
if (!gardenPatchCoords.contains(east)) eastCoords.add(east);
if (!gardenPatchCoords.contains(west)) westCoords.add(west);
}
final int northSides = countSides(northCoords, new Coord(-1, 0), new Coord(1, 0));
final int southSides = countSides(southCoords, new Coord(-1, 0), new Coord(1, 0));
final int eastSides = countSides(eastCoords, new Coord(0, -1), new Coord(0, 1));
final int westSides = countSides(westCoords, new Coord(0, -1), new Coord(0, 1));
return northSides + southSides + eastSides + westSides;
}
private int countSides(final Set<Coord> coords, final Coord inputDeltaCoord1, final Coord inputDeltaCoord2)
{
final Set<Coord> countedCoords = new HashSet<>();
int count = 0;
for (final Coord curCoord : coords)
{
if (countedCoords.contains(curCoord)) continue;
count++;
countedCoords.add(curCoord);
Coord delta1Coord = curCoord;
Coord delta2Coord = curCoord;
// Look in first direction to continue the side
while (true)
{
delta1Coord = new Coord(delta1Coord.x() + inputDeltaCoord1.x(), delta1Coord.y() + inputDeltaCoord1.y());
if (!coords.contains(delta1Coord)) break;
countedCoords.add(delta1Coord);
}
// Look in second direction to continue the side
while (true)
{
delta2Coord = new Coord(delta2Coord.x() + inputDeltaCoord2.x(), delta2Coord.y() + inputDeltaCoord2.y());
if (!coords.contains(delta2Coord)) break;
countedCoords.add(delta2Coord);
}
}
return count;
}
}
The code runs pretty fast:
Number of patches: 640
Part 1: 0.0460449s
Part 2: 0.0170168s