This is the thread for discussions of Advent of Code 2023. I will be posting my solutions here, and anyone else is free to do the same (or to link to their posts elsewhere, such as on GitHub, but please include a little discussion rather than just a simple link.)
As usual, again this year I will be working in Java. For ālife happensā reasons, I missed participating in day 1 and day 2 when the opend up. I did them in the two hours before day 3 opened, and then continued on to do day 3. To prevent having one massive post, I will still post my days separately. Before the start of each day, I copy in a āblankā framework that I use for each day. It has all the necessary boiler plate to allow me to get started quickly, and sets up JUnit for my unit tests that I use, at minimum, to make sure I can reproduce the provided examples.
Hereās some of the code from my template:
public final class AdventOfCode2023Day01Main
{
final static String DAY01_INPUT =
"""
/// I copy my personal input from the AoC site into a text block
""";
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));
}
}
The code where the actual implementation goes, is in a class named for the day. (Day01 in this example.)
final class Day01
{
public static Long part1(final String[] day01InputLines)
{
return 0L;
}
public static Long part2(final String[] day01InputLines)
{
return 0L;
}
}
The unit tests go like this (This is my actual day 1 unit test code, with sample data removed for part 2.)
public class Day01Test
{
final static String SAMPLE_INPUT1 =
"""
1abc2
pqr3stu8vwx
a1b2c3d4e5f
treb7uchet
""";
final static String SAMPLE_INPUT2 =
"""
// Part 2 data elided to prevent spoilers
""";
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(142L, result);
}
@Test
public void part2()
{
final long result = Day01.part2(SAMPLE_INPUT_LINES2);
assertEquals(0L, result); // Actual expected value removed to prevent spoilers
}
}
Day 1, part 1, was fairly straight forward I think. It was basically treating a string like an array of characters, and looking for a single digit from the start and from the back. Part 2 had a twist, in that you also had to look for a set of specific words (the digits in word form, i.e. zero, one, twoā¦).
Part 1 demonstrates two different ways to iterate over a string:
public static Long part1(final String[] day01InputLines)
{
long sum = 0;
for (final String calibrationInput : day01InputLines)
{
sum += getCalibrationValue(calibrationInput);
}
return sum;
}
private static long getCalibrationValue(final String calibrationInput)
{
int digit1 = -1;
int digit2 = -1;
for (final char c : calibrationInput.toCharArray())
{
if (isDigit(c))
{
digit1 = c - '0';
break;
}
}
if (digit1 < 0) throw new IllegalStateException("Couldn't find the first digit: " + calibrationInput);
for (int i=calibrationInput.length()-1; i>=0; i--)
{
final char c = calibrationInput.charAt(i);
if (isDigit(c))
{
digit2 = c - '0';
break;
}
}
if (digit2 < 0) throw new IllegalStateException("Couldn't find the last digit: " + calibrationInput);
return digit1*10 + digit2;
}
private static boolean isDigit(final char c)
{
if ((c >= '0') && (c<='9')) return true;
return false;
}
Part 2 is mostly a copy and paste of part one with the addition of checking for the words.
public static Long part2(final String[] day01InputLines)
{
long sum = 0;
for (final String calibrationInput : day01InputLines)
{
sum += getCalibrationValue2(calibrationInput);
}
return sum;
}
private static long getCalibrationValue2(final String calibrationInput)
{
int digit1 = -1;
int digit2 = -1;
for (int i=0; i<calibrationInput.length(); i++)
{
final char c = calibrationInput.charAt(i);
if (isDigit(c))
{
digit1 = c - '0';
break;
}
else
{
final int digit = getWordDigitIfAny(calibrationInput.substring(i));
if (digit >=0)
{
digit1 = digit;
break;
}
}
}
if (digit1 < 0) throw new IllegalStateException("Couldn't find the first digit: " + calibrationInput);
for (int i=calibrationInput.length()-1; i>=0; i--)
{
final char c = calibrationInput.charAt(i);
if (isDigit(c))
{
digit2 = c - '0';
break;
}
else
{
final int digit = getWordDigitIfAny(calibrationInput.substring(i));
if (digit >=0)
{
digit2 = digit;
break;
}
}
}
if (digit2 < 0) throw new IllegalStateException("Couldn't find the last digit: " + calibrationInput);
return digit1*10 + digit2;
}
// Yes there is a lot of code duplication here, I could have refactored it out
// but for the sake of speed I just copied and pasted 9 times to get 10 and then
// just changed the word. (The two lower case is to preventative, I don't know if
// mixed case inputs are present.)
private static int getWordDigitIfAny(final String possibleDigitWord)
{
if (possibleDigitWord.toLowerCase().startsWith("zero")) return 0;
if (possibleDigitWord.toLowerCase().startsWith("one")) return 1;
if (possibleDigitWord.toLowerCase().startsWith("two")) return 2;
if (possibleDigitWord.toLowerCase().startsWith("three")) return 3;
if (possibleDigitWord.toLowerCase().startsWith("four")) return 4;
if (possibleDigitWord.toLowerCase().startsWith("five")) return 5;
if (possibleDigitWord.toLowerCase().startsWith("six")) return 6;
if (possibleDigitWord.toLowerCase().startsWith("seven")) return 7;
if (possibleDigitWord.toLowerCase().startsWith("eight")) return 8;
if (possibleDigitWord.toLowerCase().startsWith("nine")) return 9;
return -1;
}
Day 2 needed some extra parameters to be passed in to part one. I decided not to hard code these lest they change for part 2, but part 2 was actually very easy and required almost no changes to the part 1 code, just a slight variation in calculating the numerical answer.
I suppose I should have used named constants instead of hard coded values, but I was still trying to be a little speedy, so I didnāt take the extra time.
System.out.println("Part 1: " + Day02.part1(DAY02_INPUT_LINES, 12, 13, 14));
Part 1 uses a couple of regex matchers to make parsing the input a little easier. It also uses a Java Record (a value class) to make returning sets of values as a group easier.
record GameLine(long id, long maxRed, long maxGreen, long maxBlue) {};
public static Long part1(final String[] day02InputLines, final int maxNumberOfRedCubes, final int maxNumberOfGreenCubes, final int maxNumberOfBlueCubes)
{
long sum = 0;
for (final String gameLineString : day02InputLines)
{
final GameLine gl = parseGameLine(gameLineString);
if ( (gl.maxRed <= maxNumberOfRedCubes) &&
(gl.maxGreen <= maxNumberOfGreenCubes) &&
(gl.maxBlue <= maxNumberOfBlueCubes) )
{
sum += gl.id;
}
}
return sum;
}
// Sample Input to match with regexs: Game 1: 3 blue, 4 red; 1 red, 2 green, 6 blue; 2 green
static final Pattern linePattern = Pattern.compile("Game ([0-9]+)[:] ([ 0-9,;redgnblu]+)");
static final Pattern partPattern = Pattern.compile("([0-9]+) (red|green|blue)");
private static GameLine parseGameLine(final String gameLineString)
{
int maxRed = -1;
int maxGreen= -1;
int maxBlue = -1;
final Matcher m = linePattern.matcher(gameLineString);
if (!m.matches()) throw new IllegalStateException("Can't parse input: " + gameLineString);
final String[] parts = m.group(2).split("; ");
for (final String part : parts)
{
final String[] subParts = part.split(", ");
int numRed = -1;
int numGreen = -1;
int numBlue = -1;
for (final String subPart : subParts)
{
final Matcher m2 = partPattern.matcher(subPart);
if (!m2.matches()) throw new IllegalStateException("Can't parse part: " + subPart);
if (m2.group(2).startsWith("r"))
{
numRed = Integer.parseInt(m2.group(1));
}
else if (m2.group(2).startsWith("g"))
{
numGreen = Integer.parseInt(m2.group(1));
}
else if (m2.group(2).startsWith("b"))
{
numBlue = Integer.parseInt(m2.group(1));
}
else
{
throw new IllegalStateException("Part wasn't r,g,b: " + subPart);
}
}
if (numRed > maxRed) maxRed = numRed;
if (numGreen > maxGreen) maxGreen = numGreen;
if (numBlue > maxBlue) maxBlue = numBlue;
}
return new GameLine(Long.parseLong(m.group(1)), maxRed, maxGreen, maxBlue);
}
Part 2 didnāt really add a lot of new code, and at least for my implementation was kind of a gift.
public static Long part2(final String[] day02InputLines)
{
long sum = 0;
for (final String gameLineString : day02InputLines)
{
final GameLine gl = parseGameLine(gameLineString);
sum += gl.maxRed*gl.maxGreen*gl.maxBlue;
}
return sum;
}
Day 3 is a common variation on problems for AoC. Here we use a grid of long strings (or a matrix of chars if you prefer) to represent some sort of a map (like a chart, not like the data structure.) A common way to address these sorts of inputs is a matrix. Another approach is to use a hashmap based on the x and y indexes of each character and potentially the reverse, a map of each type of character to its x and y co-ordinates. I need to remember to use the latter approach more often, as white it may lead to a little more Java code to implement it up front, it often makes the solution a lot easier to code. I did use this approach, after a fashion, for part 2.
Part 1 treats the input as a array of lines and as a matrix, variously. Accordingly there are extra checks for edge conditions. It would maybe have been faster to doctor the input to have a border of ā.ā chars. Another way to avoid these edge checks is to use the second approach I mentioned before, because itās always okay to query a hashmap and expect a āmissā where thatās not allowed for arrays.
final class Day03
{
public static Long part1(final String[] day03InputLines)
{
final Long[] partNumbers = getAllPartNumbers(day03InputLines);
long sum = 0;
for (final Long partNumber : partNumbers)
{
sum += partNumber;
}
return sum;
}
private static Long[] getAllPartNumbers(final String[] inputGridLines)
{
final List<Long> partNumbers = new ArrayList<>();
int y=0;
for (final String gridLine : inputGridLines)
{
for (int x=0; x<gridLine.length(); x++)
{
char c = gridLine.charAt(x);
if (isDigit(c))
{
final String possiblePartNumber = getPossiblePartNumber(gridLine, x);
if (isPartNumber(possiblePartNumber.length(), y, x, inputGridLines))
{
partNumbers.add(Long.parseLong(possiblePartNumber));
}
x+=possiblePartNumber.length();
}
}
y++;
}
return partNumbers.toArray(new Long[0]);
}
private static boolean isPartNumber(final int possiblePartNumberLength, int initialY, int initialX, final String[] inputGridLines)
{
final int y = initialY;
if (y>0)
{
for (int x=initialX-1; x<=initialX+possiblePartNumberLength; x++)
{
if ((x>=0) && (x<inputGridLines[y-1].length()))
{
if (isPartNumberIndicationChar(inputGridLines[y-1].charAt(x))) return true;
}
}
}
// A block, just to have a local x variable that won't interfere with future blocks
{
int x = initialX-1;
if (x>=0)
{
if (isPartNumberIndicationChar(inputGridLines[y].charAt(x))) return true;
}
x = initialX+possiblePartNumberLength;
if (x<inputGridLines[y].length())
{
if (isPartNumberIndicationChar(inputGridLines[y].charAt(x))) return true;
}
}
if (y<inputGridLines.length-1)
{
for (int x=initialX-1; x<=initialX+possiblePartNumberLength; x++)
{
if ((x>=0) && (x<inputGridLines[y+1].length()))
{
if (isPartNumberIndicationChar(inputGridLines[y+1].charAt(x))) return true;
}
}
}
return false;
}
private static boolean isPartNumberIndicationChar(final char c)
{
if (c=='.') return false;
return true;
}
private static String getPossiblePartNumber(final String gridLine, final int initialX)
{
final StringBuilder sb = new StringBuilder();
int x = initialX;
char c = gridLine.charAt(x);
while (isDigit(c))
{
sb.append(c);
x++;
if (x>=gridLine.length()) break;
c = gridLine.charAt(x);
}
return sb.toString();
}
private static boolean isDigit(final char c)
{
if ((c>='0') && (c<='9')) return true;
return false;
}
Part 2 uses a couple of Java Records as value classes to allow them to easily be used with HashMap and List. It is a copy and paste of part 1 with a few tweaks to meet the conditions for part 2 and to store the location of the gear symbol ā*ā of any gear part numbers so that when the same location is seen again you know youāve found a pair of the type you were looking for.
record GearCombo(long gear1, long gear2) {}
public static Long part2(final String[] day03InputLines)
{
final GearCombo[] gearCombos = getAllGearCombos(day03InputLines);
long sum = 0;
for (final GearCombo gearCombo : gearCombos)
{
sum += gearCombo.gear1 * gearCombo.gear2;
}
return sum;
}
record GearSymbolLocation(int x, int y) {}
static final GearSymbolLocation INVALID_GEAR_SYMBOL_LOCATION = new GearSymbolLocation(-1,-1);
private static GearCombo[] getAllGearCombos(final String[] inputGridLines)
{
final Map<GearSymbolLocation,GearCombo> gearCombos = new HashMap<>();
final List<GearCombo> validGearCombos = new ArrayList<>();
int y=0;
for (final String gridLine : inputGridLines)
{
for (int x=0; x<gridLine.length(); x++)
{
char c = gridLine.charAt(x);
if (isDigit(c))
{
final String possiblePartNumber = getPossiblePartNumber(gridLine, x);
final GearSymbolLocation gsl = isGearPartNumber(possiblePartNumber.length(), y, x, inputGridLines);
if (!gsl.equals(INVALID_GEAR_SYMBOL_LOCATION))
{
if (gearCombos.containsKey(gsl))
{
final GearCombo gc = gearCombos.get(gsl);
if (gc.gear2>=0) throw new IllegalStateException("Attempting to add a 3rd value to GearCombo at " + x + ", " + y);
final GearCombo newGearCombo = new GearCombo(gc.gear1, Long.parseLong(possiblePartNumber));
gearCombos.put(gsl, newGearCombo);
validGearCombos.add(newGearCombo);
}
else
{
gearCombos.put(gsl, new GearCombo(Long.parseLong(possiblePartNumber), -1));
}
}
x+=possiblePartNumber.length();
}
}
y++;
}
return validGearCombos.toArray(new GearCombo[0]);
}
private static GearSymbolLocation isGearPartNumber(final int possiblePartNumberLength, int initialY, int initialX, final String[] inputGridLines)
{
final int y = initialY;
if (y>0)
{
for (int x=initialX-1; x<=initialX+possiblePartNumberLength; x++)
{
if ((x>=0) && (x<inputGridLines[y-1].length()))
{
if (isGearPartNumberIndicationChar(inputGridLines[y-1].charAt(x))) return new GearSymbolLocation(x, y-1);
}
}
}
// A block to allow local variables (x) that don't collide with any subsequent blocks
{
int x = initialX-1;
if (x>=0)
{
if (isGearPartNumberIndicationChar(inputGridLines[y].charAt(x))) return new GearSymbolLocation(x, y);
}
x = initialX+possiblePartNumberLength;
if (x<inputGridLines[y].length())
{
if (isGearPartNumberIndicationChar(inputGridLines[y].charAt(x))) return new GearSymbolLocation(x, y);
}
}
if (y<inputGridLines.length-1)
{
for (int x=initialX-1; x<=initialX+possiblePartNumberLength; x++)
{
if ((x>=0) && (x<inputGridLines[y+1].length()))
{
if (isGearPartNumberIndicationChar(inputGridLines[y+1].charAt(x))) return new GearSymbolLocation(x, y+1);
}
}
}
return INVALID_GEAR_SYMBOL_LOCATION;
}
private static boolean isGearPartNumberIndicationChar(final char c)
{
if (c=='*') return true;
return false;
}
Day 4 is lottery ticket number matching (more or less.) Itās not strictly necessary to do a special approach to matching one set of numbers in a list of other numbers, but there are at least two different way to do it more efficiently that checking all n*m matches (where n and m are the size of the arrays.) If you enter the winning numbers in a hashmap then looking them up is more efficient. Another approach is to sort both arrays and use the balance line algorithm (from the batch/offline mainframe bank account processing days.) I used the balance line approach for some practice.
For part 1 I used a regex to help breaking up the parts.
public static Long part1(final String[] day04InputLines)
{
long sum = 0;
for (final String card : day04InputLines)
{
sum += calculateWorthOfCardPart1(card);
}
return sum;
}
private static long calculateWorthOfCardPart1(final String card)
{
final int numberOfMatches = calculateNumberOfMatches(card);
if (numberOfMatches == 0) return 0;
return 1<<numberOfMatches-1;
}
// Input format: Card 1: 41 48 83 86 17 | 83 86 6 31 17 9 48 53
private static final Pattern cardPattern = Pattern.compile("Card +([0-9]+): ([ 0-9]+) [|] ([ 0-9]+)");
private static int calculateNumberOfMatches(final String card)
{
final Matcher m = cardPattern.matcher(card);
if (!m.matches()) throw new IllegalStateException("Card not matching format: " + card);
final int[] winningNumbers = getNumbersSorted(m.group(2));
final int[] numbersToCheck = getNumbersSorted(m.group(3));
return calculateNumberOfMatches(winningNumbers, numbersToCheck);
}
private static int calculateNumberOfMatches(final int[] winningNumbers, final int[] numbersToCheck)
{
int winPos=0;
int checkPos=0;
int points = 0;
while ((winPos < winningNumbers.length) && (checkPos < numbersToCheck.length))
{
// This is the balance line algorithm
if (numbersToCheck[checkPos] == winningNumbers[winPos])
{
points++;
// I used the commented out code in part 1, but removed it in part 2 during my refactoring
/*
if (points == 0)
points++;
else
points=points*2;
*/
checkPos++;
winPos++;
}
else
{
if (numbersToCheck[checkPos] < winningNumbers[winPos])
{
checkPos++;
}
else
{
winPos++;
}
}
}
return points;
}
private static int[] getNumbersSorted(final String inputNumberString)
{
final String[] numbersString = inputNumberString.trim().split("[ ]+");
final int[] numbers = new int[numbersString.length];
for (int i=0; i<numbersString.length; i++)
{
numbers[i] = Integer.parseInt(numbersString[i]);
}
Arrays.sort(numbers);
return numbers;
}
Part 2 required a little refactoring of part 1 because I need to extract the points calculation based on the number of matches in part 1, but just needed the number of matches for part 2. Also, to do the approach I took, I needed to know the total number of cards, which I then passed in. The approach for part 2 is to make an array of the count of the number of each card. Initialize it to all 1ās. Then as you process each card, increase the number by the number of matches times the number of cards that you have for that card number.
System.out.println("Part 2: " + Day04.part2(DAY04_INPUT_LINES, 189)); // My input had 189 cards
public static Long part2(final String[] day04InputLines, final int numberOfCards)
{
final long[] numberOfEachCard = new long[numberOfCards];
Arrays.fill(numberOfEachCard, 1);
int cardNumber = 0;
for (final String card : day04InputLines)
{
final int numberOfMatches = calculateNumberOfMatches(card);
if (numberOfMatches > 0)
{
for (int i=1; i<= numberOfMatches; i++)
{
numberOfEachCard[cardNumber+i] += numberOfEachCard[cardNumber];
}
}
cardNumber++;
}
long sum = 0;
for (int i =0; i<numberOfEachCard.length; i++)
{
sum += numberOfEachCard[i];
}
return sum;
}
Day 5, oy vey! I made a couple of false starts on this one. First was to not consider that the sample input used very small numbers but that the actual input would be using very large longs. This led to me writing code that worked for the sample input, by adding all the entries to the maps for the mappings, but of course the number of mappings was huge and that wasnāt going to be efficient for the actual input (or it would have ran forever.) I changed it to just store the mappings as triplets of (source, dest, range) and that solved that issue, as there werenāt really huge numbers of mappings. Then for the second part, I assumed that brute forcing was going to be too slow, so I went and added caching, figuring it couldnāt but help, but that led to my PC running out of RAM for the caches. I reverted back to my version without the caching and it turns out just brute forcing it was fast enough, though still slow, it took under 5 minutes or so.
I created a new class to wrap the manipulations on the data:
final class Day5Conditions
{
record Mapping(long source, long dest, long range)
{
public boolean isInRange(final long valueToMap)
{
if ((valueToMap >= source) && (valueToMap < source + range)) return true;
return false;
}
public long mapValue(final long valueToMap)
{
return dest + (valueToMap - source);
}
};
private final List<Long> seeds;
private final List<Mapping> seedToSoilMap = new ArrayList<>();
private final List<Mapping> soilToFertilizerMap = new ArrayList<>();
private final List<Mapping> fertilizerToWaterMap = new ArrayList<>();
private final List<Mapping> waterToLightMap = new ArrayList<>();
private final List<Mapping> lightToTemperatureMap = new ArrayList<>();
private final List<Mapping> temperatureToHumidityMap = new ArrayList<>();
private final List<Mapping> humidityToLocationMap = new ArrayList<>();
public Day5Conditions(final String[] day05InputLines)
{
seeds = extractNumberList(day05InputLines[0].substring(7));
putRangesInMap("seed-to-soil map", seedToSoilMap, day05InputLines);
putRangesInMap("soil-to-fertilizer map", soilToFertilizerMap, day05InputLines);
putRangesInMap("fertilizer-to-water map", fertilizerToWaterMap, day05InputLines);
putRangesInMap("water-to-light map", waterToLightMap, day05InputLines);
putRangesInMap("light-to-temperature map", lightToTemperatureMap, day05InputLines);
putRangesInMap("temperature-to-humidity map", temperatureToHumidityMap, day05InputLines);
putRangesInMap("humidity-to-location map", humidityToLocationMap, day05InputLines);
}
private void putRangesInMap(final String locator, final List<Mapping> theMapToPopulate, final String[] inputLines)
{
int index =0;
while (!inputLines[index].contains(locator)) index++;
index++;
while (!inputLines[index].isBlank())
{
final List<Long> mappingList = extractNumberList(inputLines[index]);
if (mappingList.size() != 3) throw new IllegalStateException("Mapping does not contain 3 values: " + inputLines[index]);
long dest = mappingList.get(0);
long source = mappingList.get(1);
long mappingLength = mappingList.get(2);
final Mapping mapping = new Mapping(source, dest, mappingLength);
theMapToPopulate.add(mapping);
index++;
}
}
private List<Long> extractNumberList(final String stringOfNumbers)
{
final String[] parts = stringOfNumbers.trim().split(" +");
final List<Long> result = new ArrayList(parts.length);
for (final String part : parts)
{
result.add(Long.parseLong(part));
}
return result;
}
public long[] getInitialSeeds()
{
final long[] result = new long[seeds.size()];
int index = 0;
for (final Long seedNum : seeds)
{
result[index++] = seedNum;
}
return result;
}
public long getLocationForSeed(final long seedNum)
{
final long soil = getSoilForSeed(seedNum);
final long fertilizer = getFertilizerForSoil(soil);
final long water = getWaterForFertilizer(fertilizer);
final long light = getLightForWater(water);
final long temp = getTempForLight(light);
final long humidity = getHumidityForTemp(temp);
final long location = getLocationForHumidity(humidity);
return location;
}
private long getSoilForSeed(final long seedNum)
{
return getMapping(seedToSoilMap, seedNum);
}
private long getMapping(final List<Mapping> mapToUse, final long valueToMap)
{
for (final Mapping mapping : mapToUse)
{
if (mapping.isInRange(valueToMap))
{
return mapping.mapValue(valueToMap);
}
}
return valueToMap;
}
private long getFertilizerForSoil(final long soil)
{
return getMapping(soilToFertilizerMap, soil);
}
private long getWaterForFertilizer(final long fertilizer)
{
return getMapping(fertilizerToWaterMap, fertilizer);
}
private long getLightForWater(final long water)
{
return getMapping(waterToLightMap, water);
}
private long getTempForLight(final long light)
{
return getMapping(lightToTemperatureMap, light);
}
private long getHumidityForTemp(final long temp)
{
return getMapping(temperatureToHumidityMap, temp);
}
private long getLocationForHumidity(final long humidity)
{
return getMapping(humidityToLocationMap, humidity);
}
}
This made the actual solvers in the Day5 class very short and sweet.
Part 1:
public static Long part1(final String[] day05InputLines)
{
final Day5Conditions d5c = new Day5Conditions(day05InputLines);
final long[] initialSeeds = d5c.getInitialSeeds();
long minLocation = Long.MAX_VALUE;
for (final long seed : initialSeeds)
{
final long location = d5c.getLocationForSeed(seed);
if (location < minLocation) minLocation = location;
}
return minLocation;
}
Part 2 is pretty similar just with the necessary changes to reinterpret the input:
public static Long part2(final String[] day05InputLines)
{
final Day5Conditions2 d5c = new Day5Conditions2(day05InputLines);
final long[] initialSeeds = d5c.getInitialSeeds();
long minLocation = Long.MAX_VALUE;
for (int i=0; i<initialSeeds.length; i+=2)
{
for (long index=0; index<initialSeeds[i+1]; index++)
{
// Occasionally produce some output so we know we're making progress
if (index%10_000_000==0) System.out.println("" + i + ":" + (initialSeeds[i]+index) + " minSoFar= " + minLocation);
final long location = d5c.getLocationForSeed(initialSeeds[i]+index);
if (location < minLocation) minLocation = location;
}
}
return minLocation;
}
I think Day 6 is very straightforward. I donāt think thereās really much to say about an approach. Perhaps there is some linear equation (almost certain there probably is,) but I found it easier to just code a loop and get it done quickly.
I manually reformatted the input into a Java record:
public record BoatParams(long time, long distance) {};
final BoatParams[] exampleInput = {
new BoatParams(7,9),
new BoatParams(15,40),
new BoatParams(30,200)
};
and passed the array of values to the part1 and part2 methods.
public static Long part1(final BoatParams[] boatParams)
{
long result = 1;
for (final BoatParams bp : boatParams)
{
result *= calculateNumberOfWinningConditions(bp);
}
return result;
}
private static long calculateNumberOfWinningConditions(final BoatParams bp)
{
int result = 0;
for (long initialButtonTime=0; initialButtonTime<=bp.time; initialButtonTime++)
{
final long boatSpeed = initialButtonTime;
final long timeLeft = bp.time - initialButtonTime;
final long totalDistance = timeLeft * boatSpeed;
if (totalDistance > bp.distance) result++;
}
return result;
}
Since part 2 was just a reformatting of the input, I did that manually too, and there was almost no code to write:
public static Long part2(final BoatParams[] boatParams)
{
return calculateNumberOfWinningConditions(boatParams[0]);
}
I should use classes more often in JavaScript. At least the classic Object object (Argh, why you do this to me!), if not the ārecentlyā added class feature.
For Day 5, for the conversions, I used the following format [amount to change, start range, end range] (My code had the range in a sub array, but for high-level purposes, it doesnāt really matter)
Part 1 had nothing special, just took me a while to do the actual code (Also, first day this year I used BigInt, and god they need to add some stuff to the standard library to handle thoseā¦)
Part 2, I was just comparing ranges to ranges. If the seed range was inside the conversion range, I just converted, and moved on. If the start of the seed range was outside the conversion range, I would make a new range with all the seeds I didnāt need to convert and add it to the queue to be processed, then set the start of the range I was working on to match the start of the conversion range. If the seed range was bigger than the conversion range, I would split it and add the two ranges to the queue, so the first part would be fully within the conversion range, and the other outside. Nothing would happen if they were outside the conversion range.
Iām sure thereās a cleaner way to code what I did, however, but a 17ms run time is not bad for part 2.
Havenāt look at Day 6 yet
Interpreted Python is much slower than compiled C++ so my brute force solution (like yours) for Day 5 part 2 was hopeless. I thought Iād try working backwards by starting with location 0 and incrementing until it produced a seed number in the given seed ranges. I didnāt time it, but leaving it and coming back some time later I was surprised to see it had finished - even producing the right answer.
I decided the proper approach was to work with ranges instead of individual numbers - basically the same idea as @miquelfire. For each map I arranged all the starting and ending points in a list which I sorted low to high. I processed the input ranges one at a time, first restricting the list to just the ranges needed to cover the input. The output was an array of ranges to feed into the next map.
This worked great on the sample, but I got an execution error with the puzzle data because of a missing starting number for a range. Because of the ridiculously large numbers, I couldnāt debug it. I ended up re-writing sections of the code to make them easier to understand. Eventually the error went away and it produced the right result very quickly. But if you include the time I spent getting it to work, I think the original hopelessly slow brute force method would have beaten me.
For Day 6, the expected solution might have been to solve the quadratic and adjust the roots to get the integers at the start and end of the winning range of hold times. What I did was use the derivative which has a maximum at time/2. Stepping up and down from that worked well enough. After struggling with Day 5, I wasnāt interested in spending any more time on Day 6.
Day 7 is time to score and sort poker hands. Hopefully you didnāt make the mistake I did and initially forget to use a lookup on the char characters. The numbers sorted fine, but of course T, J, Q, K, A donāt sort right unless you [donāt forget] to make them 
As it happened, I tweaked my sort by letter into the reverse thinking I was mistaken about it, still not thinking about the letters, and it fixed it for the example, but it led to the wrong answer for the actual data. I created a class to show some stats about the hands, and when I saw the best and second best hand and the worst and second worst, my error popped right out.
Because of the ātwistā in part 2, I refactored my code, and it really wonāt be able to show part 1 without giving away part2.
I created a bunch of helper classes, one to represent the poker hand, another to manage sorting and a final one to do the scoring. (I also created the one for the stats I used in debugging.)
The method I used to determine the best hand for part 2 is far from optimal. It noticeably slows down the processing in part 2. I went for expediency in coding rather than trying to come up with the ācorrectā approach to solving the problem (assuming a way that isnāt brute force exists.)
Hereās the major class, the poker hand class:
final class CamelPokerHand implements Comparable<CamelPokerHand>
{
public enum CamelPokerHandType
{
HIGH_CARD(1),
ONE_PAIR(2),
TWO_PAIR(3),
THREE_OF_A_KIND(4),
FULL_HOUSE(5),
FOUR_OF_A_KIND(6),
FIVE_OF_A_KIND(7);
CamelPokerHandType(final int rankToSet)
{
rank = rankToSet;
}
private int rank;
int getRank()
{
return rank;
}
}
private final CamelPokerHandType handType;
private final String handString;
private final int precomputedHashCode;
private final long bid;
private final boolean isJokerWild; // For part 2
public CamelPokerHand(final String handString, final long bid, final boolean isJokerWild)
{
this.isJokerWild = isJokerWild;
this.bid = bid;
this.handString = handString;
final char[] handChars = handString.toCharArray();
Arrays.sort(handChars);
precomputedHashCode = handChars[0]<<20 | handChars[1] <<15 | handChars[2] << 10 | handChars[3] << 5 | handChars[4];
if (isJokerWild && handString.contains("J"))
handType = calculateHandTypeWithJokers(handChars);
else
handType = calculateHandType(handChars);
}
public CamelPokerHand(final String handString, final long bid)
{
this(handString, bid, false); // For part 1
}
// This is not the most efficient way to do this, but it may be the most expedient from
// a coding quickly perspective
private static final char[] SUBSTITUES_FOR_JOKERS = {'A','K','Q','T','9','8','7','6','5','4','3','2'};
private CamelPokerHandType calculateHandTypeWithJokers(final char[] handChars)
{
final boolean isC1aJ = (handChars[0]=='J');
final boolean isC2aJ = (handChars[1]=='J');
final boolean isC3aJ = (handChars[2]=='J');
final boolean isC4aJ = (handChars[3]=='J');
final boolean isC5aJ = (handChars[4]=='J');
final List<CamelPokerHand> allHands = new ArrayList<>();
for(int i1=0; i1<SUBSTITUES_FOR_JOKERS.length; i1++)
{
if (isC1aJ) handChars[0]=SUBSTITUES_FOR_JOKERS[i1];
for(int i2=0; i2<SUBSTITUES_FOR_JOKERS.length; i2++)
{
if (isC2aJ) handChars[1]=SUBSTITUES_FOR_JOKERS[i2];
for(int i3=0; i3<SUBSTITUES_FOR_JOKERS.length; i3++)
{
if (isC3aJ) handChars[2]=SUBSTITUES_FOR_JOKERS[i3];
for(int i4=0; i4<SUBSTITUES_FOR_JOKERS.length; i4++)
{
if (isC4aJ) handChars[3]=SUBSTITUES_FOR_JOKERS[i4];
for(int i5=0; i5<SUBSTITUES_FOR_JOKERS.length; i5++)
{
if (isC5aJ) handChars[4]=SUBSTITUES_FOR_JOKERS[i5];
final CamelPokerHand cph = new CamelPokerHand("" + handChars[0] + handChars[1] + handChars[2] + handChars[3] + handChars[4], 0);
allHands.add(cph);
}
}
}
}
}
final CamelPokerHand[] sortHands = allHands.toArray(new CamelPokerHand[0]);
Arrays.sort(sortHands);
return sortHands[sortHands.length-1].getHandType();
}
private CamelPokerHandType calculateHandType(final char[] handChars)
{
if ( (handChars[0] == handChars[1]) &&
(handChars[0] == handChars[2]) &&
(handChars[0] == handChars[3]) &&
(handChars[0] == handChars[4]) )
{
return CamelPokerHandType.FIVE_OF_A_KIND;
}
if ( ( (handChars[0] == handChars[1]) &&
(handChars[0] == handChars[2]) &&
(handChars[0] == handChars[3]) ) ||
( (handChars[1] == handChars[2]) &&
(handChars[1] == handChars[3]) &&
(handChars[1] == handChars[4]) ) )
{
return CamelPokerHandType.FOUR_OF_A_KIND;
}
if ( ( (handChars[0] == handChars[1]) &&
(handChars[0] == handChars[2]) &&
(handChars[3] == handChars[4]) ) ||
( (handChars[2] == handChars[3]) &&
(handChars[2] == handChars[4]) &&
(handChars[0] == handChars[1]) ) )
{
return CamelPokerHandType.FULL_HOUSE;
}
if ( ( (handChars[0] == handChars[1]) &&
(handChars[0] == handChars[2]) ) ||
( (handChars[1] == handChars[2]) &&
(handChars[1] == handChars[3]) ) ||
( (handChars[2] == handChars[3]) &&
(handChars[2] == handChars[4]) ) )
{
return CamelPokerHandType.THREE_OF_A_KIND;
}
if ( ( (handChars[0] == handChars[1]) &&
(handChars[2] == handChars[3]) ) ||
( (handChars[0] == handChars[1]) &&
(handChars[3] == handChars[4]) ) ||
( (handChars[1] == handChars[2]) &&
(handChars[3] == handChars[4]) ) )
{
return CamelPokerHandType.TWO_PAIR;
}
if ( (handChars[0] == handChars[1]) ||
(handChars[1] == handChars[2]) ||
(handChars[2] == handChars[3]) ||
(handChars[3] == handChars[4]) )
{
return CamelPokerHandType.ONE_PAIR;
}
return CamelPokerHandType.HIGH_CARD;
}
public CamelPokerHandType getHandType()
{
return handType;
}
public long getBid()
{
return bid;
}
@Override
public int compareTo(final @Nullable CamelPokerHand other)
{
if (other == null) throw new NullPointerException();
if (this == other) return 0;
if (this.handType.getRank() == other.handType.getRank())
{
return compareOnCardOrder(this.handString.toCharArray(), other.handString.toCharArray());
}
if (this.handType.getRank() < other.handType.getRank()) return -1;
return 1;
}
@Override
public int hashCode()
{
return precomputedHashCode;
}
@Override
public boolean equals(final @Nullable Object other)
{
if (other == null) return false;
if (this == other) return true;
if (!other.getClass().equals(this.getClass())) return false;
final CamelPokerHand o = (CamelPokerHand)other;
if (this.handString.equals(o.handString)) return true;
if (this.handType.getRank() != o.handType.getRank()) return false;
return allCardsEqual(this.handString.toCharArray(), o.handString.toCharArray());
}
private boolean allCardsEqual(final char[] hand1, final char[] hand2)
{
Arrays.sort(hand1);
Arrays.sort(hand2);
for(int i=0; i<5; i++)
{
if (hand1[i] != hand2[i]) return false;
}
return true;
}
private int compareOnCardOrder(final char[] hand1, final char[] hand2)
{
for (int i=0; i<5; i++)
{
if (hand1[i] == hand2[i]) continue;
if (cardVal(hand1[i]) < cardVal(hand2[i])) return -1;
return 1;
}
return 0;
}
private int cardVal(final char cardChar)
{
if (isJokerWild && (cardChar == 'J')) return 1;
return switch (cardChar)
{
case 'A' -> 14;
case 'K' -> 13;
case 'Q' -> 12;
case 'J' -> 11;
case 'T' -> 10;
case '9' -> 9;
case '8' -> 8;
case '7' -> 7;
case '6' -> 6;
case '5' -> 5;
case '4' -> 4;
case '3' -> 3;
case '2' -> 2;
default -> throw new IllegalStateException("Unexpected card char: " + cardChar);
};
}
@Override
public String toString()
{
return "[" + handString + ", " + handType + "]";
}
}
This is the sorting class, which really isnāt needed, it just collects the poker hands and makes it easy to pass them to the scoring class (or to the debugging stats class.)
final class CamelPokerHandSorter
{
private final List<CamelPokerHand> hands = new ArrayList<>();
public void add(final CamelPokerHand camelPokerHandToAdd)
{
hands.add(camelPokerHandToAdd);
}
public CamelPokerHand[] getSortedHands()
{
final CamelPokerHand[] handsForSorting = hands.toArray(new CamelPokerHand[0]);
Arrays.sort(handsForSorting);
return handsForSorting;
}
}
This is the scoring class:
final class CamelPokerScorer
{
public static Long scoreHands(final CamelPokerHandSorter cphs)
{
final CamelPokerHand[] hands = cphs.getSortedHands();
long result = 0;
for (int i=hands.length-1; i>=0; i--)
{
final int rank = i+1;
result += (rank * hands[i].getBid());
}
return result;
}
}
For good measure, hereās the debugging stats class:
public static void showStats(final CamelPokerHandSorter cphs)
{
final CamelPokerHand[] hands = cphs.getSortedHands();
System.out.println("" + hands.length + " hands");
int numDupes = 0;
for (int i=0; i<hands.length-1; i++)
{
if (hands[i].equals(hands[i+1]))
{
numDupes++;
System.out.println("Dupes: " + hands[i] + ", " + hands[i+1]);
}
}
if (numDupes == 0)
System.out.println("no dupes");
else
System.out.println("" + numDupes + " dupes");
System.out.println("Best Hand: " + hands[hands.length-1]);
System.out.println("Second Best Hand: " + hands[hands.length-2]);
System.out.println("Worst Hand: " + hands[0]);
System.out.println("Second Worst Hand: " + hands[1]);
}
}
Hereās a sample output from the debugging stats class from my actual data:
1000 hands
no dupes
Best Hand: [JJJJJ, FIVE_OF_A_KIND]
Second Best Hand: [AAAAK, FOUR_OF_A_KIND]
Worst Hand: [237AK, HIGH_CARD]
Second Worst Hand: [256JT, HIGH_CARD]
and hereās that output for part 2:
1000 hands
no dupes
Best Hand: [AAAAJ, FIVE_OF_A_KIND]
Second Best Hand: [KKKKJ, FIVE_OF_A_KIND]
Worst Hand: [237AK, HIGH_CARD]
Second Worst Hand: [257K3, HIGH_CARD]
And hereās the part 1 method, and the refactored out method it shares with part 2:
public static Long part1(final String[] day07InputLines)
{
return calculateScore(day07InputLines, false);
}
private static Long calculateScore(final String[] day07InputLines, final boolean isJokerWild)
{
final CamelPokerHandSorter cphs = new CamelPokerHandSorter();
for (final String handAndBidString: day07InputLines)
{
final String handString = handAndBidString.substring(0, 5);
final long bid = Long.parseLong(handAndBidString.substring(6));
final CamelPokerHand cph = new CamelPokerHand(handString, bid, isJokerWild);
cphs.add(cph);
}
CamelPokerStats.showStats(cphs);
return CamelPokerScorer.scoreHands(cphs);
}
And part 2 is just one line:
public static Long part2(final String[] day07InputLines)
{
return calculateScore(day07InputLines, true);
}
In discussing Day 7 part 2 on the TWiT Discord, I realized I really over-thought part 2. All you really need to do is assume that a joker (or jokers) are the same card as whatever you have the most of. I think I will code that up later, and post the update here.
EDIT: So the new approach works, and also works to make evaluating the hands for part one easier as well. Hereās the changed code:
private CamelPokerHandType calculateHandTypeWithJokers(final char[] handChars)
{
final int[] cardCounts = countEachTypeOfCard(handChars);
final int numberOfJokers = cardCounts[cardVal('J')];
if (numberOfJokers >= 4) return CamelPokerHandType.FIVE_OF_A_KIND;
cardCounts[cardVal('J')] = 0; // Don't count jokers any more
final int ofAKindSize = highestNumberOfSameCards(cardCounts) + numberOfJokers;
if (ofAKindSize == 3) // Special case for Full House
{
if (countNumberOfTimesForSameCards(cardCounts, 2) == 2)
{
return CamelPokerHandType.FULL_HOUSE;
}
}
return switch(ofAKindSize)
{
case 2 -> CamelPokerHandType.ONE_PAIR;
case 3 -> CamelPokerHandType.THREE_OF_A_KIND;
case 4 -> CamelPokerHandType.FOUR_OF_A_KIND;
case 5 -> CamelPokerHandType.FIVE_OF_A_KIND;
default -> throw new IllegalArgumentException("Unexpected value: " + ofAKindSize);
};
}
private int highestNumberOfSameCards(final int[] cardCounts)
{
int max = 0;
for (int i=1; i<15; i++)
{
if (cardCounts[i] > max) max = cardCounts[i];
}
return max;
}
private int[] countEachTypeOfCard(char[] handChars)
{
final int[] result = new int[15];
for (int i=0; i<5; i++)
{
result[cardVal(handChars[i])]++;
}
return result;
}
private int countNumberOfTimesForSameCards(final int[] cardCounts, final int countToCount)
{
int result= 0;
for (int i=1; i<15; i++)
{
if (cardCounts[i] == countToCount) result++;
}
return result;
}
private CamelPokerHandType calculateHandType(final char[] handChars)
{
final int[] cardCounts = countEachTypeOfCard(handChars);
final int highestNumberOfSameCard = highestNumberOfSameCards(cardCounts);
if (highestNumberOfSameCard == 5) return CamelPokerHandType.FIVE_OF_A_KIND;
if (highestNumberOfSameCard == 4) return CamelPokerHandType.FOUR_OF_A_KIND;
if (highestNumberOfSameCard == 3)
{
if (countNumberOfTimesForSameCards(cardCounts, 2) == 1)
{
return CamelPokerHandType.FULL_HOUSE;
}
return CamelPokerHandType.THREE_OF_A_KIND;
}
if (highestNumberOfSameCard == 2)
{
if (countNumberOfTimesForSameCards(cardCounts, 2) == 2)
{
return CamelPokerHandType.TWO_PAIR;
}
return CamelPokerHandType.ONE_PAIR;
}
return CamelPokerHandType.HIGH_CARD;
}
Day 8 part 1 is fairly straight-forward. You could potentially build an actual tree data structure, but I just made a node to hold a left and a right string and threw them all into a hashmap indexed by the node name. You then set a current node name and look up itās left and right value and then using the provided instructions chose the left or right to be the current node. Iterate until done.
Day 8 part 2 will not be possible to brute force. You kind of have to know this going in, but even if you donāt it would quickly become obvious if you wrote the obvious code. I knew it was highly likely that brute forcing would fail, but I still wrote the code for the heck of it. I then made a guess at how to get the information I needed to solve the problem by hand. (This problem is similar to one from last year, so I already knew it was going to be a least common multiples situation.) Basically I found out what a cycle for each starting value would be and when I looked at the output, I felt that was looking reasonable. I then factored the numbers, and found they all had a common factor and a prime. I then just computed the multiplication of the primes and the common factor and that was the expected answer.
I created a class to manage the āmap dataā called RLMap, and the portion below is what I needed to solve part 1. I also reused part of it for part 2 and marked lines I added for that purpose.
final class RLMap
{
private record RLMapEntry(String leftEntry, String rightEntry) {}
private final Map<String,RLMapEntry> mapEntries = new HashMap<>();
private final List<String> allNodesEndingInA = new ArrayList<>(); // part 2
private final List<String> allNodesEndingInZ = new ArrayList<>(); // part 2
// Example input: AAA = (BBB, BBB)
private static final Pattern MAP_ENTRY_PATTERN = Pattern.compile("(...) [=] [(](...)[,][ ](...)[)]");
public void add(final String mapEntry)
{
final Matcher m = MAP_ENTRY_PATTERN.matcher(mapEntry);
if (!m.matches()) throw new IllegalStateException("Unparsable input: " + mapEntry);
final String mapEntryName = m.group(1);
final String leftEntryName = m.group(2);
final String rightEntryName = m.group(3);
final RLMapEntry rlMapEntry = new RLMapEntry(leftEntryName, rightEntryName);
mapEntries.put(mapEntryName, rlMapEntry);
if (mapEntryName.charAt(2)=='A') allNodesEndingInA.add(mapEntryName); // part 2
if (mapEntryName.charAt(2)=='Z') allNodesEndingInZ.add(mapEntryName); // part 2
}
public Long numberOfStepsToGetFromTo(final String from, final String to, final String rlInstructions)
{
String current = from;
int index = 0;
long result = 0;
while (!current.equals(to))
{
final RLMapEntry currentMapEntry = mapEntries.get(current);
switch (rlInstructions.charAt(index))
{
case 'L':
{
current = currentMapEntry.leftEntry;
}
break;
case 'R':
{
current = currentMapEntry.rightEntry;
}
break;
default: throw new IllegalStateException("Unexpected LR instruction: " + rlInstructions.charAt(index));
}
index++;
if (index >= rlInstructions.length()) index = 0;
result++;
if (result > 50_000) return 0L; // part 2
}
return result;
}
The part 1 method was only a few lines, but most of those were shared with part 2 so got refactored out:
public static Long part1(final String[] day08InputLines)
{
final String rlInstructions = day08InputLines[0];
final RLMap rlmap = setupRLMap(day08InputLines);
return rlmap.numberOfStepsToGetFromTo("AAA", "ZZZ", rlInstructions);
}
private static RLMap setupRLMap(final String[] day08InputLines)
{
final RLMap rlmap = new RLMap();
for (int i=2; i<day08InputLines.length; i++)
{
rlmap.add(day08InputLines[i]);
}
return rlmap;
}
Then for part 2, I tried to brute force the solution, so added this code to the RLMap class:
public Long numberOfStepsPart2a(final String rlInstructions)
{
long result = 0;
int index = 0;
List<String> nodeList = List.copyOf(allNodesEndingInA);
while (!allNodesEndingInZ(nodeList))
{
if (result % 10_000_000 == 0) System.out.println(result); // give progress indication
final List<String> newNodeList = new ArrayList<>();
final char rlInstruction = rlInstructions.charAt(index);
for (final String node: nodeList)
{
final RLMapEntry currentMapEntry = mapEntries.get(node);
switch (rlInstruction)
{
case 'L':
{
newNodeList.add(currentMapEntry.leftEntry);
}
break;
case 'R':
{
newNodeList.add(currentMapEntry.rightEntry);
}
break;
default: throw new IllegalStateException("Unexpected LR instruction: " + rlInstructions.charAt(index));
}
}
nodeList = newNodeList;
index++;
if (index >= rlInstructions.length()) index = 0;
result++;
}
return result;
}
private boolean allNodesEndingInZ(final List<String> nodeList)
{
for (final String node: nodeList)
{
if (node.charAt(2) != 'Z') return false;
}
return true;
}
of course I quickly realized that wasnāt going to work, so then I added this to RLMap:
public Long numberOfStepsPart2(final String rlInstructions)
{
for (final String aNode: allNodesEndingInA)
{
for (final String zNode: allNodesEndingInZ)
{
System.out.println("Steps to go from " + aNode + " to " + zNode + " : " + numberOfStepsToGetFromTo(aNode,zNode,rlInstructions));
}
}
return 0L; // I replaced this line with the math once I determined the lowest common multiples
}
This produced the numbers I needed to get the factors of and find lowest common multiplesā¦ I then changed the one line to produce the result. Calling the method was about as straight forward as youād expect:
public static Long part2(final String[] day08InputLines)
{
final String rlInstructions = day08InputLines[0];
final RLMap rlmap = setupRLMap(day08InputLines);
return rlmap.numberOfStepsPart2(rlInstructions);
}
Day 9 wasnāt really much of a challenge, I donāt think. Itās more a matter of understanding the rules that are provided than anything else.
I made a class to wrap up the data management and extrapolation, and called it OasisReport:
final class OasisReport
{
private final Map<Integer,Long> firstValueOnLine = new HashMap<>(); // For part 2
private final Map<Integer,Long> lastValueOnLine = new HashMap<>();
public OasisReport(final String oasisReportLine)
{
final String[] valueStrings = oasisReportLine.split(" +");
List<Long> values = new ArrayList<>();
for (final String valStr : valueStrings) values.add(Long.parseLong(valStr));
int lineNum = 0;
while (true)
{
final List<Long> newVals = new ArrayList<>();
firstValueOnLine.put(lineNum, values.getFirst()); // Part 2
lastValueOnLine.put(lineNum, values.getLast());
boolean allDifferencesWereZero = true;
for (int i=1; i<values.size(); i++)
{
final long diff = values.get(i) - values.get(i-1);
if (diff != 0) allDifferencesWereZero = false;
newVals.add(diff);
}
values = newVals;
lineNum++;
if (allDifferencesWereZero) break;
}
firstValueOnLine.put(lineNum, 0L); // Part 2
lastValueOnLine.put(lineNum, 0L);
}
public long extrapolateForward()
{
for (int i=lastValueOnLine.size()-2; i>=0; i--)
{
long newVal = lastValueOnLine.get(i+1) + lastValueOnLine.get(i);
lastValueOnLine.put(i, newVal);
}
return lastValueOnLine.get(0);
}
The part 1 method just exercises this class in the obvious way:
public static Long part1(final String[] day09InputLines)
{
long result = 0;
for (final String OasisReportLine : day09InputLines)
{
final OasisReport or = new OasisReport(OasisReportLine);
result += or.extrapolateForward();
}
return result;
}
For part 2, I added one method to the OasisReport class:
public long extrapolateBackward()
{
for (int i=firstValueOnLine.size()-2; i>=0; i--)
{
long newVal = firstValueOnLine.get(i) - firstValueOnLine.get(i+1);
firstValueOnLine.put(i, newVal);
}
return firstValueOnLine.get(0);
}
And the copy and pasted the part 1 method to part 2 and made one obvious change:
public static Long part2(final String[] day09InputLines)
{
long result = 0;
for (final String OasisReportLine : day09InputLines)
{
final OasisReport or = new OasisReport(OasisReportLine);
result += or.extrapolateBackward();
}
return result;
}
For Day 9 Part 2 I added one line to the Part 1 algorithm to reverse the order of the input sequence.
It was mentioned on the TWiT Discord that Day 9 is a good problem for recursion, and although I never thought of it that way when considering the solution, I can certainly see that point after the fact.
Way behind you guys. I am just getting started. Day 1 and 2 done. Doing it in Common Lisp again.
Day 10 is a pretty good challengeā¦ it should start to āseparate the men from the boysā (as the phrase goes, or I suppose, āthe women from girls,ā if that is a phrase too (and why shouldnāt it be?)
In any case, part 1 wasnāt too bad, although I think there are different things that could have tripped you up. (In my case, I got one the character mappings coded wrong initially, causing me a weird infinite loop and a bit of debugging.)
I initially chose to walk the loop in both directions at once until I met at the answer. Unfortunately, with my bug, that didnāt go well. It caused me to switch to walking the whole loop once, and then dividing the answer by 2.
For part 2, the ā.5 widthā gaps were an obvious headache. I scratched my head for a few minutes on how to proceed. While I let the problem fester in my subconscious, I coded a flood fill routine because I knew that was the approach I wanted to use, and I knew I had a test case to test with it. When I got that working, then it dawned on me I could multiply the size of the map and that would increase the size of the .5 gap to be bigger and the flood fill should work. Turns out to have worked great.
I created a PipeMaze class to manage the representation of the problem:
final class PipeMaze
{
record PipeSegment(boolean connectsN, boolean connectsE, boolean connectsS, boolean connectsW) {}
private static final PipeSegment OUTSIDE_PIPE_SEGMENT = new PipeSegment(false, false, false, false);
record MazeCoordinate(int x, int y) {}
private static final MazeCoordinate INVALID_MAZE_COORDINATE = new MazeCoordinate(-1, -1);
private final Map<MazeCoordinate, PipeSegment> maze;
private final int width;
private final int height;
private MazeCoordinate startCoordinate = INVALID_MAZE_COORDINATE;
public PipeMaze(final int width, final int height, final MazeCoordinate startCoordinate, final Map<MazeCoordinate, PipeSegment> maze)
{
this.width = width;
this.height = height;
this.startCoordinate = startCoordinate;
this.maze = maze;
}
public PipeMaze(final String[] day10InputLines)
{
maze = new HashMap<>();
width = day10InputLines[0].length();
height = day10InputLines.length;
for (int y=0; y<height; y++)
{
for (int x=0; x<width; x++)
{
final MazeCoordinate mc = new MazeCoordinate(x, y);
final char c = day10InputLines[y].charAt(x);
switch (c)
{
case 'S':
{
startCoordinate = mc;
}
break;
case '|':
{
maze.put(mc, new PipeSegment(true, false, true, false));
}
break;
case '-':
{
maze.put(mc, new PipeSegment(false, true, false, true));
}
break;
case 'L':
{
maze.put(mc, new PipeSegment(true, true, false, false));
}
break;
case 'J':
{
maze.put(mc, new PipeSegment(true, false, false, true));
}
break;
case '7':
{
maze.put(mc, new PipeSegment(false, false, true, true));
}
break;
case 'F':
{
maze.put(mc, new PipeSegment(false, true, true, false));
}
break;
case '.':
{
// empty ground, do nothing
}
break;
default:
{
throw new IllegalStateException("Unexpected character: " + c);
}
}
}
}
connectStart();
}
private void connectStart()
{
boolean n = false;
boolean e = false;
boolean s = false;
boolean w = false;
if (pipeConnectsSouth(startCoordinate.x, startCoordinate.y-1)) n = true;
if (pipeConnectsWest(startCoordinate.x+1, startCoordinate.y)) e = true;
if (pipeConnectsNorth(startCoordinate.x, startCoordinate.y+1)) s = true;
if (pipeConnectsEast(startCoordinate.x-1, startCoordinate.y)) w = true;
maze.put(startCoordinate, new PipeSegment(n, e, s, w));
}
private boolean pipeConnectsSouth(final int x, final int y)
{
final MazeCoordinate mc = new MazeCoordinate(x, y);
if (maze.containsKey(mc))
{
final PipeSegment ps = maze.get(mc);
if (ps.connectsS) return true;
}
return false;
}
private boolean pipeConnectsNorth(final int x, final int y)
{
final MazeCoordinate mc = new MazeCoordinate(x, y);
if (maze.containsKey(mc))
{
final PipeSegment ps = maze.get(mc);
if (ps.connectsN) return true;
}
return false;
}
private boolean pipeConnectsEast(final int x, final int y)
{
final MazeCoordinate mc = new MazeCoordinate(x, y);
if (maze.containsKey(mc))
{
final PipeSegment ps = maze.get(mc);
if (ps.connectsE) return true;
}
return false;
}
private boolean pipeConnectsWest(final int x, final int y)
{
final MazeCoordinate mc = new MazeCoordinate(x, y);
if (maze.containsKey(mc))
{
final PipeSegment ps = maze.get(mc);
if (ps.connectsW) return true;
}
return false;
}
// I originally wrote this to walk two different paths until they met. I had a bug that was allowing that
// to get into an infinite loop. Instead I decided to code it to walk the whole loop and then cut the distance
// of the whole loop in half. I left the other code present but commented out for posterity.
public Long findLengthToMidpoint()
{
MazeCoordinate path1 = INVALID_MAZE_COORDINATE;
MazeCoordinate path2 = INVALID_MAZE_COORDINATE;
if (pipeConnectsNorth(startCoordinate.x, startCoordinate.y))
{
path1 = new MazeCoordinate(startCoordinate.x, startCoordinate.y-1);
if (pipeConnectsEast(startCoordinate.x, startCoordinate.y)) path2 = new MazeCoordinate(startCoordinate.x+1, startCoordinate.y);
if (pipeConnectsSouth(startCoordinate.x, startCoordinate.y)) path2 = new MazeCoordinate(startCoordinate.x, startCoordinate.y+1);
if (pipeConnectsWest(startCoordinate.x, startCoordinate.y)) path2 = new MazeCoordinate(startCoordinate.x-1, startCoordinate.y);
}
else
{
if (pipeConnectsEast(startCoordinate.x, startCoordinate.y))
{
path1 = new MazeCoordinate(startCoordinate.x+1, startCoordinate.y);
if (pipeConnectsSouth(startCoordinate.x, startCoordinate.y)) path2 = new MazeCoordinate(startCoordinate.x, startCoordinate.y+1);
if (pipeConnectsWest(startCoordinate.x, startCoordinate.y)) path2 = new MazeCoordinate(startCoordinate.x-1, startCoordinate.y);
}
else
{
path1 = new MazeCoordinate(startCoordinate.x, startCoordinate.y+1);
path2 = new MazeCoordinate(startCoordinate.x-1, startCoordinate.y);
}
}
MazeCoordinate path1prev = startCoordinate;
MazeCoordinate path2prev = startCoordinate;
long result = 1;
while (!path1.equals(startCoordinate))
{
// System.out.println("" + result + " " + path1.toString() + " " + path2.toString());
final MazeCoordinate path1New = navigateOneStep(path1, path1prev);
// final MazeCoordinate path2New = navigateOneStep(path2, path2prev);
path1prev = path1;
// path2prev = path2;
path1 = path1New;
// path2 = path2New;
result++;
}
return (result+1)/2;
}
private MazeCoordinate navigateOneStep(final MazeCoordinate curCoord, final MazeCoordinate prevCoord)
{
if (prevCoord.y == curCoord.y)
{
if (prevCoord.x+1 == curCoord.x)
{
if (pipeConnectsNorth(curCoord.x, curCoord.y)) return new MazeCoordinate(curCoord.x, curCoord.y-1);
if (pipeConnectsEast(curCoord.x, curCoord.y)) return new MazeCoordinate(curCoord.x+1, curCoord.y);
if (pipeConnectsSouth(curCoord.x, curCoord.y)) return new MazeCoordinate(curCoord.x, curCoord.y+1);
}
if (pipeConnectsNorth(curCoord.x, curCoord.y)) return new MazeCoordinate(curCoord.x, curCoord.y-1);
if (pipeConnectsSouth(curCoord.x, curCoord.y)) return new MazeCoordinate(curCoord.x, curCoord.y+1);
if (pipeConnectsWest(curCoord.x, curCoord.y)) return new MazeCoordinate(curCoord.x-1, curCoord.y);
}
if (prevCoord.y+1 == curCoord.y)
{
if (pipeConnectsEast(curCoord.x, curCoord.y)) return new MazeCoordinate(curCoord.x+1, curCoord.y);
if (pipeConnectsSouth(curCoord.x, curCoord.y)) return new MazeCoordinate(curCoord.x, curCoord.y+1);
if (pipeConnectsWest(curCoord.x, curCoord.y)) return new MazeCoordinate(curCoord.x-1, curCoord.y);
}
if (pipeConnectsNorth(curCoord.x, curCoord.y)) return new MazeCoordinate(curCoord.x, curCoord.y-1);
if (pipeConnectsEast(curCoord.x, curCoord.y)) return new MazeCoordinate(curCoord.x+1, curCoord.y);
if (pipeConnectsWest(curCoord.x, curCoord.y)) return new MazeCoordinate(curCoord.x-1, curCoord.y);
throw new IllegalStateException("Couldn't determine direction at: " + curCoord + " coming from " + prevCoord);
}
Then for the part 1 method, itās just orchestrating the PipeMaze class:
public static Long part1(final String[] day10InputLines)
{
final PipeMaze pm = new PipeMaze(day10InputLines);
return pm.findLengthToMidpoint();
}
For part 2, I added a bunch of additional code to the PipeMaze class:
public PipeMaze eliminateAllButPipeLoop()
{
final Map<MazeCoordinate, PipeSegment> newMaze = new HashMap<>();
MazeCoordinate path1 = INVALID_MAZE_COORDINATE;
if (pipeConnectsNorth(startCoordinate.x, startCoordinate.y))
{
path1 = new MazeCoordinate(startCoordinate.x, startCoordinate.y-1);
}
else
{
if (pipeConnectsEast(startCoordinate.x, startCoordinate.y))
{
path1 = new MazeCoordinate(startCoordinate.x+1, startCoordinate.y);
}
else
{
path1 = new MazeCoordinate(startCoordinate.x, startCoordinate.y+1);
}
}
MazeCoordinate path1prev = startCoordinate;
newMaze.put(startCoordinate, maze.get(startCoordinate));
while (!path1.equals(startCoordinate))
{
newMaze.put(path1, maze.get(path1));
final MazeCoordinate path1New = navigateOneStep(path1, path1prev);
path1prev = path1;
path1 = path1New;
}
return new PipeMaze(width, height, startCoordinate, newMaze);
}
public void FillOutsideLocations()
{
for (int x=0; x<width; x++)
{
if (coordinateIsUnfilled(x,0)) floodFill(x,0);
if (coordinateIsUnfilled(x,height-1)) floodFill(x,height-1);
}
for (int y=0; y<height; y++)
{
if (coordinateIsUnfilled(0,y)) floodFill(0,y);
if (coordinateIsUnfilled(width-1,y)) floodFill(width-1,y);
}
}
public Long CountInsideLocations()
{
long count = 0;
for (int y=0; y<height; y++)
{
for (int x=0; x<width-1; x++)
{
if (coordinateIsUnfilled(x,y)) count++;
}
}
return count;
}
private final Deque<MazeCoordinate> stack = new ArrayDeque<>();
private void floodFill(final int xIn, final int yIn)
{
stack.push(new MazeCoordinate(xIn, yIn));
while (!stack.isEmpty())
{
final MazeCoordinate curCoord = stack.pop();
maze.put(curCoord, OUTSIDE_PIPE_SEGMENT);
final int x = curCoord.x;
final int y = curCoord.y;
if (coordinateIsUnfilled(x-1,y)) stack.push(new MazeCoordinate(x-1, y));
if (coordinateIsUnfilled(x+1,y)) stack.push(new MazeCoordinate(x+1, y));
if (coordinateIsUnfilled(x,y-1)) stack.push(new MazeCoordinate(x, y-1));
if (coordinateIsUnfilled(x,y+1)) stack.push(new MazeCoordinate(x, y+1));
}
}
private boolean coordinateIsUnfilled(final int x, final int y)
{
if ( (x<0) || (x>=width) || (y<0) || (y>height-1)) return false;
final MazeCoordinate mc = new MazeCoordinate(x, y);
if (maze.containsKey(mc))
{
final PipeSegment ps = maze.get(mc);
if (ps == OUTSIDE_PIPE_SEGMENT) return false;
if (ps.connectsN || ps.connectsE || ps.connectsS || ps.connectsW) return false;
}
return true;
}
public PipeMaze doubleInSize()
{
final Map<MazeCoordinate, PipeSegment> newMaze = new HashMap<>();
for (int y=0; y<height; y++)
{
for (int x=0; x<width; x++)
{
final MazeCoordinate origMC = new MazeCoordinate(x, y);
if (maze.containsKey(origMC))
{
final PipeSegment ps = maze.get(origMC);
final MazeCoordinate mc = new MazeCoordinate(x*2, y*2);
newMaze.put(mc, ps);
if (ps.connectsE)
{
newMaze.put(new MazeCoordinate(mc.x+1, mc.y), new PipeSegment(false, true, false, true));
}
if (ps.connectsS)
{
newMaze.put(new MazeCoordinate(mc.x, mc.y+1), new PipeSegment(true, false, true, false));
}
}
}
}
final MazeCoordinate newStartCoordinate = new MazeCoordinate(startCoordinate.x*2, startCoordinate.y*2);
return new PipeMaze(width*2, height*2, newStartCoordinate, newMaze);
}
public PipeMaze halveInSize()
{
final Map<MazeCoordinate, PipeSegment> newMaze = new HashMap<>();
for (int y=0; y<height; y+=2)
{
for (int x=0; x<width; x+=2)
{
final MazeCoordinate origMC = new MazeCoordinate(x, y);
if (maze.containsKey(origMC))
{
final PipeSegment ps = maze.get(origMC);
final MazeCoordinate mc = new MazeCoordinate(x/2, y/2);
newMaze.put(mc, ps);
}
}
}
final MazeCoordinate newStartCoordinate = new MazeCoordinate(startCoordinate.x/2, startCoordinate.y/2);
return new PipeMaze(width/2, height/2, newStartCoordinate, newMaze);
}
I think the part 2 method makes the approach fairly clear:
public static Long part2(final String[] day10InputLines)
{
final PipeMaze pm = new PipeMaze(day10InputLines);
final PipeMaze pm2 = pm.eliminateAllButPipeLoop();
final PipeMaze pm3 = pm2.doubleInSize();
pm3.FillOutsideLocations();
final PipeMaze pm4 = pm3.halveInSize();
return pm4.CountInsideLocations();
}