This is a Jupyter Notebook for the Advent of Code 2023 challenge.
It is written in .NET7 using the Polyglot NoteBook extension for the dotnet-interactive kernel in VS Code.
Code cells are isolated by day and part, and can be run individually or all at once. No code is shared between cells.
AdventOfCode2023.ipynb file from the repository in VS Code, input directories must be relative to the notebook file--- Trebuchet?! ---
Something is wrong with global snow production, and you've been selected to take a look. The Elves have even given you a map; on it, they've used stars to mark the top fifty locations that are likely to be having problems.
You've been doing this long enough to know that to restore snow operations, you need to check all fifty stars by December 25th.
Collect stars by solving puzzles. Two puzzles will be made available on each day in the Advent calendar; the second puzzle is unlocked when you complete the first. Each puzzle grants one star. Good luck!
You try to ask why they can't just use a weather machine ("not powerful enough") and where they're even sending you ("the sky") and why your map looks mostly blank ("you sure ask a lot of questions") and hang on did you just say the sky ("of course, where do you think snow comes from") when you realize that the Elves are already loading you into a trebuchet ("please hold still, we need to strap you in").
As they're making the final adjustments, they discover that their calibration document (your puzzle input) has been amended by a very young Elf who was apparently just excited to show off her art skills. Consequently, the Elves are having trouble reading the values on the document.
The newly-improved calibration document consists of lines of text; each line originally contained a specific calibration value that the Elves now need to recover. On each line, the calibration value can be found by combining the first digit and the last digit (in that order) to form a single two-digit number.
For example:
1abc2
pqr3stu8vwx
a1b2c3d4e5f
treb7uchet
In this example, the calibration values of these four lines are 12, 38, 15, and 77. Adding these together produces 142.
Consider your entire calibration document. What is the sum of all of the calibration values?
using System;
using System.IO;
string filePath = "1/input.txt";
string[] input;
input = File.ReadAllLines(filePath);
int finalSum = 0;
foreach (string line in input)
{
int calibrationValue = ExtractCalibrationValue(line);
AddToFinalSum(finalSum, calibrationValue);
}
Console.WriteLine($"Final Sum: {finalSum}");
int ExtractCalibrationValue(string line)
{
int firstDigit = -1;
int lastDigit = -1;
// Find the first digit
for (int i = 0; i < line.Length; i++)
{
if (char.IsDigit(line[i]))
{
firstDigit = line[i] - '0';
break;
}
}
// Find the last digit
for (int i = line.Length - 1; i >= 0; i--)
{
if (char.IsDigit(line[i]))
{
lastDigit = line[i] - '0';
break;
}
}
// Combine the digits to form the calibration value
int calibrationValue = firstDigit * 10 + lastDigit;
return calibrationValue;
}
void AddToFinalSum(int sum, int value)
{
finalSum += value;
}
--- Part Two ---
Your calculation isn't quite right. It looks like some of the digits are actually spelled out with letters: one, two, three, four, five, six, seven, eight, and nine also count as valid "digits".
Equipped with this new information, you now need to find the real first and last digit on each line. For example:
two1nine eightwothree abcone2threexyz xtwone3four 4nineeightseven2 zoneight234 7pqrstsixteen
In this example, the calibration values are 29, 83, 13, 24, 42, 14, and 76. Adding these together produces 281.
What is the sum of all of the calibration values?
using System.IO;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
var input = File.ReadAllLines("1/input.txt");
var pattern = @"(?=(one|two|three|four|five|six|seven|eight|nine|\d))";
var sum = 0;
var transform = new Dictionary<string, string>
{
{ "one", "1" },
{ "two", "2" },
{ "three", "3" },
{ "four", "4" },
{ "five", "5" },
{ "six", "6" },
{ "seven", "7" },
{ "eight", "8" },
{ "nine", "9" },
{ "1", "1" },
{ "2", "2" },
{ "3", "3" },
{ "4", "4" },
{ "5", "5" },
{ "6", "6" },
{ "7", "7" },
{ "8", "8" },
{ "9", "9" }
};
foreach (var line in input)
{
var matches = Regex.Matches(line, pattern);
var firstNumber = transform[matches.First().Groups[1].Value];
var secondNumber = transform[matches.Last().Groups[1].Value];
var combined = firstNumber + secondNumber;
sum += int.Parse(combined);
}
Console.WriteLine($"Final Sum: {sum}");
--- Cube Conundrum ---
You're launched high into the atmosphere! The apex of your trajectory just barely reaches the surface of a large island floating in the sky. You gently land in a fluffy pile of leaves. It's quite cold, but you don't see much snow. An Elf runs over to greet you.
The Elf explains that you've arrived at Snow Island and apologizes for the lack of snow. He'll be happy to explain the situation, but it's a bit of a walk, so you have some time. They don't get many visitors up here; would you like to play a game in the meantime?
As you walk, the Elf shows you a small bag and some cubes which are either red, green, or blue. Each time you play this game, he will hide a secret number of cubes of each color in the bag, and your goal is to figure out information about the number of cubes.
To get information, once a bag has been loaded with cubes, the Elf will reach into the bag, grab a handful of random cubes, show them to you, and then put them back in the bag. He'll do this a few times per game.
You play several games and record the information from each game (your puzzle input). Each game is listed with its ID number (like the 11 in Game 11: ...) followed by a semicolon-separated list of subsets of cubes that were revealed from the bag (like 3 red, 5 green, 4 blue).
For example, the record of a few games might look like this:
Game 1: 3 blue, 4 red; 1 red, 2 green, 6 blue; 2 green
Game 2: 1 blue, 2 green; 3 green, 4 blue, 1 red; 1 green, 1 blue
Game 3: 8 green, 6 blue, 20 red; 5 blue, 4 red, 13 green; 5 green, 1 red
Game 4: 1 green, 3 red, 6 blue; 3 green, 6 red; 3 green, 15 blue, 14 red
Game 5: 6 red, 1 blue, 3 green; 2 blue, 1 red, 2 green
In game 1, three sets of cubes are revealed from the bag (and then put back again). The first set is 3 blue cubes and 4 red cubes; the second set is 1 red cube, 2 green cubes, and 6 blue cubes; the third set is only 2 green cubes.
The Elf would first like to know which games would have been possible if the bag contained only 12 red cubes, 13 green cubes, and 14 blue cubes?
In the example above, games 1, 2, and 5 would have been possible if the bag had been loaded with that configuration. However, game 3 would have been impossible because at one point the Elf showed you 20 red cubes at once; similarly, game 4 would also have been impossible because the Elf showed you 15 blue cubes at once. If you add up the IDs of the games that would have been possible, you get 8.
Determine which games would have been possible if the bag had been loaded with only 12 red cubes, 13 green cubes, and 14 blue cubes. What is the sum of the IDs of those games?
using System.IO;
var input = File.ReadAllLines("2/input.txt");
var desiredRed = 12;
var desiredGreen = 13;
var desiredBlue = 14;
var possibleGames = new List<int>();
foreach (var line in input)
{
var gameIdIndex = line.IndexOf("Game ") + 5;
var gameId = int.Parse(line.Substring(gameIdIndex, line.IndexOf(":") - gameIdIndex).Trim());
var gameData = line.Split(new[] { ": " }, StringSplitOptions.RemoveEmptyEntries)[1];
var rounds = gameData.Split(new[] { "; " }, StringSplitOptions.RemoveEmptyEntries);
bool gamePossible = true;
foreach (var round in rounds)
{
var colorValues = round.Split(new[] { ' ', ',' }, StringSplitOptions.RemoveEmptyEntries);
for (int i = 0; i < colorValues.Length; i += 2)
{
int quantity = int.Parse(colorValues[i]);
string color = colorValues[i + 1];
switch (color)
{
case "red":
if (quantity > desiredRed)
{
gamePossible = false;
}
break;
case "green":
if (quantity > desiredGreen)
{
gamePossible = false;
}
break;
case "blue":
if (quantity > desiredBlue)
{
gamePossible = false;
}
break;
}
}
}
if (gamePossible)
{
possibleGames.Add(gameId);
}
}
int sumOfPossibleGameIDs = possibleGames.Sum();
Console.WriteLine($"Sum of IDs of possible games: {sumOfPossibleGameIDs}");
--- Part Two ---
The Elf says they've stopped producing snow because they aren't getting any water! He isn't sure why the water stopped; however, he can show you how to get to the water source to check it out for yourself. It's just up ahead!
As you continue your walk, the Elf poses a second question: in each game you played, what is the fewest number of cubes of each color that could have been in the bag to make the game possible?
Again consider the example games from earlier:
Game 1: 3 blue, 4 red; 1 red, 2 green, 6 blue; 2 green
Game 2: 1 blue, 2 green; 3 green, 4 blue, 1 red; 1 green, 1 blue
Game 3: 8 green, 6 blue, 20 red; 5 blue, 4 red, 13 green; 5 green, 1 red
Game 4: 1 green, 3 red, 6 blue; 3 green, 6 red; 3 green, 15 blue, 14 red
Game 5: 6 red, 1 blue, 3 green; 2 blue, 1 red, 2 green
In game 1, the game could have been played with as few as 4 red, 2 green, and 6 blue cubes. If any color had even one fewer cube, the game would have been impossible.
Game 2 could have been played with a minimum of 1 red, 3 green, and 4 blue cubes.
Game 3 must have been played with at least 20 red, 13 green, and 6 blue cubes.
Game 4 required at least 14 red, 3 green, and 15 blue cubes.
Game 5 needed no fewer than 6 red, 3 green, and 2 blue cubes in the bag.
The power of a set of cubes is equal to the numbers of red, green, and blue cubes multiplied together. The power of the minimum set of cubes in game 1 is 48. In games 2-5 it was 12, 1560, 630, and 36, respectively. Adding up these five powers produces the sum 2286.
For each game, find the minimum set of cubes that must have been present. What is the sum of the power of these sets?
using System.IO;
using System;
using System.Collections.Generic;
using System.Linq;
var input = File.ReadAllLines("2/input.txt");
List<int> gamePowers = new List<int>();
foreach (var line in input)
{
var gameIdIndex = line.IndexOf("Game ") + 5;
var gameId = line.Substring(gameIdIndex, line.IndexOf(":") - gameIdIndex).Trim();
var gameData = line.Split(new[] { ": " }, StringSplitOptions.RemoveEmptyEntries)[1];
var rounds = gameData.Split(new[] { "; " }, StringSplitOptions.RemoveEmptyEntries);
Dictionary<string, int> maxCounts = new Dictionary<string, int>
{
{"red", int.MinValue},
{"green", int.MinValue},
{"blue", int.MinValue}
};
foreach (var round in rounds)
{
var colorValues = round.Split(new[] { ' ', ',' }, StringSplitOptions.RemoveEmptyEntries);
for (int i = 0; i < colorValues.Length; i += 2)
{
int quantity = int.Parse(colorValues[i]);
string color = colorValues[i + 1];
maxCounts[color] = Math.Max(maxCounts[color], quantity);
}
}
var totalPower = maxCounts["red"] * maxCounts["green"] * maxCounts["blue"];
gamePowers.Add(totalPower);
// Console.WriteLine($"Game {gameId} - MinRed: {maxCounts["red"]}, MinGreen: {maxCounts["green"]}, MinBlue: {maxCounts["blue"]}");
}
Console.WriteLine($"Sum of game powers: {gamePowers.Sum()}");
--- Gear Ratios ---
You and the Elf eventually reach a gondola lift station; he says the gondola lift will take you up to the water source, but this is as far as he can bring you. You go inside.
It doesn't take long to find the gondolas, but there seems to be a problem: they're not moving.
"Aaah!"
You turn around to see a slightly-greasy Elf with a wrench and a look of surprise. "Sorry, I wasn't expecting anyone! The gondola lift isn't working right now; it'll still be a while before I can fix it." You offer to help.
The engineer explains that an engine part seems to be missing from the engine, but nobody can figure out which one. If you can add up all the part numbers in the engine schematic, it should be easy to work out which part is missing.
The engine schematic (your puzzle input) consists of a visual representation of the engine. There are lots of numbers and symbols you don't really understand, but apparently any number adjacent to a symbol, even diagonally, is a "part number" and should be included in your sum. (Periods (.) do not count as a symbol.)
Here is an example engine schematic:
467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..
In this schematic, two numbers are not part numbers because they are not adjacent to a symbol: 114 (top right) and 58 (middle right). Every other number is adjacent to a symbol and so is a part number; their sum is 4361.
Of course, the actual engine schematic is much larger. What is the sum of all of the part numbers in the engine schematic?
using System.IO;
using System.Linq;
using System.Collections.Generic;
using System.Text.RegularExpressions;
/*
Credit to objectwizard (https://github.com/objectwizard/AdventOfCode2023)
for the idea of processing rows entirely with Regex.
*/
// Read the input file
var engineSchematic = File.ReadAllLines("3/input.txt");
// Define the regular expression pattern for numbers
private const string numberMatch = @"\d+";
// Initialize variables
int totalNumberSum = 0;
List<string> validNumbers = new List<string>();
// Function to get symbol matches in a line
private static Dictionary<int, char> GetAllSymbolMatches(string line)
{
Dictionary<int, char> matches = new Dictionary<int, char>();
for (int i = 0; i < line.Length; i++)
{
if (!char.IsDigit(line[i]) && line[i] != '.')
{
matches.Add(i, line[i]);
}
}
return matches;
}
// Loop over each row in the schematic
for (int y = 0; y < engineSchematic.Length; y++)
{
// Get the current row
string row = engineSchematic[y];
// Get all symbol matches in the current row
Dictionary<int, char> symbolMatchesCurrentRow = GetAllSymbolMatches(row);
// Loop over each number match in the current row
foreach (Match numberMatch in Regex.Matches(row, numberMatch))
{
int indexMin = numberMatch.Index;
int indexMax = indexMin + numberMatch.Length - 1;
// Check for adjacent symbols in the current row
if (symbolMatchesCurrentRow.Keys.Any(si => indexMin - 1 <= si && indexMax + 1 >= si))
{
// Add the value of the number to the total sum
totalNumberSum += int.Parse(numberMatch.Value);
validNumbers.Add(numberMatch.Value);
}
// Check for adjacent symbols in the row above
if (y > 0)
{
Dictionary<int, char> symbolMatchesPreviousRow = GetAllSymbolMatches(engineSchematic[y - 1]);
if (symbolMatchesPreviousRow.Keys.Any(si => indexMin - 1 <= si && indexMax + 1 >= si))
{
// Add the value of the number to the total sum
totalNumberSum += int.Parse(numberMatch.Value);
validNumbers.Add(numberMatch.Value);
}
}
// Check for adjacent symbols in the row below
if (y < engineSchematic.Length - 1)
{
Dictionary<int, char> symbolMatchesNextRow = GetAllSymbolMatches(engineSchematic[y + 1]);
if (symbolMatchesNextRow.Keys.Any(si => indexMin - 1 <= si && indexMax + 1 >= si))
{
// Add the value of the number to the total sum
totalNumberSum += int.Parse(numberMatch.Value);
validNumbers.Add(numberMatch.Value);
}
}
}
}
Console.WriteLine($"The sum of all part numbers in the engine schematic is: {totalNumberSum}");
--- Part Two ---
The engineer finds the missing part and installs it in the engine! As the engine springs to life, you jump in the closest gondola, finally ready to ascend to the water source.
You don't seem to be going very fast, though. Maybe something is still wrong? Fortunately, the gondola has a phone labeled "help", so you pick it up and the engineer answers.
Before you can explain the situation, she suggests that you look out the window. There stands the engineer, holding a phone in one hand and waving with the other. You're going so slowly that you haven't even left the station. You exit the gondola.
The missing part wasn't the only issue - one of the gears in the engine is wrong. A gear is any * symbol that is adjacent to exactly two part numbers. Its gear ratio is the result of multiplying those two numbers together.
This time, you need to find the gear ratio of every gear and add them all up so that the engineer can figure out which gear needs to be replaced.
Consider the same engine schematic again:
467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..
In this schematic, there are two gears. The first is in the top left; it has part numbers 467 and 35, so its gear ratio is 16345. The second gear is in the lower right; its gear ratio is 451490. (The * adjacent to 617 is not a gear because it is only adjacent to one part number.) Adding up all of the gear ratios produces 467835.
What is the sum of all of the gear ratios in your engine schematic?
using System.IO;
using System.Linq;
using System.Collections.Generic;
var input = File.ReadAllText("3/input.txt");
IEnumerable<int> GetNeighboringCells(int currentIndex, int gridWidth) {
int upIndex = currentIndex - gridWidth;
int downIndex = currentIndex + gridWidth;
// Check if there are valid neighbors in the up direction
if (upIndex >= 0) {
// Check and yield the left neighbor in the up direction
if (upIndex - 1 is var leftUp && leftUp / gridWidth == upIndex / gridWidth) {
yield return leftUp;
}
// Yield the neighbor in the up direction
yield return upIndex;
// Check and yield the right neighbor in the up direction
if (upIndex + 1 is var rightUp && rightUp / gridWidth == upIndex / gridWidth) {
yield return rightUp;
}
}
// Check and yield the left and right neighbors
if (currentIndex - 1 is var left && left / gridWidth == currentIndex / gridWidth) {
yield return left;
}
if (currentIndex + 1 is var right && right / gridWidth == currentIndex / gridWidth) {
yield return right;
}
// Check if there are valid neighbors in the down direction
if (downIndex < input.Length) {
// Check and yield the left neighbor in the down direction
if (downIndex - 1 is var leftDown && leftDown / gridWidth == downIndex / gridWidth) {
yield return leftDown;
}
// Yield the neighbor in the down direction
yield return downIndex;
// Check and yield the right neighbor in the down direction
if (downIndex + 1 is var rightDown && rightDown / gridWidth == downIndex / gridWidth) {
yield return rightDown;
}
}
}
int CalculateGearRatio(List<int> neighboringNumbers) {
return neighboringNumbers[0] * neighboringNumbers[1];
}
int ParseNumber(ReadOnlySpan<char> input, HashSet<int> visitedIndices, int currentIndex, int gridWidth) {
if (visitedIndices.Contains(currentIndex))
return 0;
List<char> numberChars = new() { input[currentIndex] };
visitedIndices.Add(currentIndex);
int firstIndexOfRow = (currentIndex / gridWidth) * gridWidth;
int lastIndexOfRow = firstIndexOfRow + gridWidth;
// Traverse to the left of the current index to form the complete number
for (int leftIndex = currentIndex - 1; leftIndex >= firstIndexOfRow; leftIndex--) {
if (input[leftIndex] is var digitChar && char.IsDigit(digitChar)) {
// Insert the digit at the beginning of the list
numberChars.Insert(0, digitChar);
if (!visitedIndices.Add(leftIndex))
return 0;
} else {
break;
}
}
// Traverse to the right of the current index to form the complete number
for (int rightIndex = currentIndex + 1; rightIndex < lastIndexOfRow; rightIndex++) {
if (input[rightIndex] is var digitChar && char.IsDigit(digitChar)) {
numberChars.Add(digitChar);
if (!visitedIndices.Add(rightIndex))
return 0;
} else {
break;
}
}
return int.Parse(new string(numberChars.ToArray()));
}
HashSet<int> visitedIndices = new();
int totalGearRatio = 0;
int currentIndex = 0;
int gridWidth = input.IndexOf("\n") + 1;
string symbols = "!@#$%^&*()-+=/";
string whitespaceChars = "\r\n.";
while (currentIndex < input.Length) {
char currentChar = input[currentIndex];
if (whitespaceChars.Contains(currentChar) || char.IsDigit(currentChar)) {
currentIndex++;
continue;
}
if (symbols.Contains(currentChar)) {
List<int> neighboringNumbers = new();
foreach (var neighborIndex in GetNeighboringCells(currentIndex, gridWidth)) {
if (char.IsDigit(input[neighborIndex])) {
var number = ParseNumber(input, visitedIndices, neighborIndex, gridWidth);
if (number > 0) {
neighboringNumbers.Add(number);
}
}
}
if (currentChar == '*' && neighboringNumbers.Count == 2) {
// Calculate and update the total gear ratio
totalGearRatio += neighboringNumbers[0] * neighboringNumbers[1];
}
currentIndex++;
}
}
Console.WriteLine($"Total Gear Ratio: {totalGearRatio}");
--- Scratchcards ---
The gondola takes you up. Strangely, though, the ground doesn't seem to be coming with you; you're not climbing a mountain. As the circle of Snow Island recedes below you, an entire new landmass suddenly appears above you! The gondola carries you to the surface of the new island and lurches into the station.
As you exit the gondola, the first thing you notice is that the air here is much warmer than it was on Snow Island. It's also quite humid. Is this where the water source is?
The next thing you notice is an Elf sitting on the floor across the station in what seems to be a pile of colorful square cards.
"Oh! Hello!" The Elf excitedly runs over to you. "How may I be of service?" You ask about water sources.
"I'm not sure; I just operate the gondola lift. That does sound like something we'd have, though - this is Island Island, after all! I bet the gardener would know. He's on a different island, though - er, the small kind surrounded by water, not the floating kind. We really need to come up with a better naming scheme. Tell you what: if you can help me with something quick, I'll let you borrow my boat and you can go visit the gardener. I got all these scratchcards as a gift, but I can't figure out what I've won."
The Elf leads you over to the pile of colorful cards. There, you discover dozens of scratchcards, all with their opaque covering already scratched off. Picking one up, it looks like each card has two lists of numbers separated by a vertical bar (|): a list of winning numbers and then a list of numbers you have. You organize the information into a table (your puzzle input).
As far as the Elf has been able to figure out, you have to figure out which of the numbers you have appear in the list of winning numbers. The first match makes the card worth one point and each match after the first doubles the point value of that card.
For example:
Card 1: 41 48 83 86 17 | 83 86 6 31 17 9 48 53
Card 2: 13 32 20 16 61 | 61 30 68 82 17 32 24 19
Card 3: 1 21 53 59 44 | 69 82 63 72 16 21 14 1
Card 4: 41 92 73 84 69 | 59 84 76 51 58 5 54 83
Card 5: 87 83 26 28 32 | 88 30 70 12 93 22 82 36
Card 6: 31 18 13 56 72 | 74 77 10 23 35 67 36 11
In the above example, card 1 has five winning numbers (41, 48, 83, 86, and 17) and eight numbers you have (83, 86, 6, 31, 17, 9, 48, and 53). Of the numbers you have, four of them (48, 83, 17, and 86) are winning numbers! That means card 1 is worth 8 points (1 for the first match, then doubled three times for each of the three matches after the first).
So, in this example, the Elf's pile of scratchcards is worth 13 points.
Take a seat in the large pile of colorful cards. How many points are they worth in total?
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
var input = File.ReadAllLines("4/input.txt");
int totalPoints = 0;
Dictionary<int, int> gameRecord = new();
foreach(var line in input) {
List<int> winningNumbers = new();
List<int> gameNumbers = new();
int gameId = int.Parse(line.Substring(5, line.IndexOf(":") - 5).Trim());
var winningNumbersString = line.Substring(line.IndexOf(":") + 2).Split("|")[0].Trim();
var gameNumbersString = line.Substring(line.IndexOf(":") + 2).Split("|")[1].Trim();
foreach(var number in winningNumbersString.Split(" ", StringSplitOptions.RemoveEmptyEntries)) {
winningNumbers.Add(int.Parse(number));
}
foreach(var number in gameNumbersString.Split(" ", StringSplitOptions.RemoveEmptyEntries)) {
gameNumbers.Add(int.Parse(number));
}
var matches = gameNumbers.Where(x => winningNumbers.Contains(x)).ToList();
if(matches.Count > 0) {
// If more than one match, double game points per match and add to total points
int points = 1; // Start with 1 point for the first match
foreach (var match in matches.Skip(1)) {
points *= 2; // Double the points for each subsequent match
}
totalPoints += points;
gameRecord.Add(gameId, points);
}
}
Console.WriteLine($"Total points: {totalPoints}");
--- Part Two ---
Just as you're about to report your findings to the Elf, one of you realizes that the rules have actually been printed on the back of every card this whole time.
There's no such thing as "points". Instead, scratchcards only cause you to win more scratchcards equal to the number of winning numbers you have.
Specifically, you win copies of the scratchcards below the winning card equal to the number of matches. So, if card 10 were to have 5 matching numbers, you would win one copy each of cards 11, 12, 13, 14, and 15.
Copies of scratchcards are scored like normal scratchcards and have the same card number as the card they copied. So, if you win a copy of card 10 and it has 5 matching numbers, it would then win a copy of the same cards that the original card 10 won: cards 11, 12, 13, 14, and 15. This process repeats until none of the copies cause you to win any more cards. (Cards will never make you copy a card past the end of the table.)
This time, the above example goes differently:
Card 1: 41 48 83 86 17 | 83 86 6 31 17 9 48 53
Card 2: 13 32 20 16 61 | 61 30 68 82 17 32 24 19
Card 3: 1 21 53 59 44 | 69 82 63 72 16 21 14 1
Card 4: 41 92 73 84 69 | 59 84 76 51 58 5 54 83
Card 5: 87 83 26 28 32 | 88 30 70 12 93 22 82 36
Card 6: 31 18 13 56 72 | 74 77 10 23 35 67 36 11
Once all of the originals and copies have been processed, you end up with 1 instance of card 1, 2 instances of card 2, 4 instances of card 3, 8 instances of card 4, 14 instances of card 5, and 1 instance of card 6. In total, this example pile of scratchcards causes you to ultimately have 30 scratchcards!
Process all of the original and copied scratchcards until no more scratchcards are won. Including the original set of scratchcards, how many total scratchcards do you end up with?
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
var input = File.ReadAllLines("4/input.txt");
Dictionary<int, int> gameRecord = new();
foreach(var line in input) {
List<int> winningNumbers = new();
List<int> gameNumbers = new();
int gameId = int.Parse(line.Substring(5, line.IndexOf(":") - 5).Trim());
var winningNumbersString = line.Substring(line.IndexOf(":") + 2).Split("|")[0].Trim();
var gameNumbersString = line.Substring(line.IndexOf(":") + 2).Split("|")[1].Trim();
foreach(var number in winningNumbersString.Split(" ", StringSplitOptions.RemoveEmptyEntries)) {
winningNumbers.Add(int.Parse(number));
}
foreach(var number in gameNumbersString.Split(" ", StringSplitOptions.RemoveEmptyEntries)) {
gameNumbers.Add(int.Parse(number));
}
// Check for matches in game and winning numbers
var matches = gameNumbers.Where(x => winningNumbers.Contains(x)).ToList();
gameRecord.Add(gameId, matches.Count);
}
// Dictionary to track the count of cards won for each game
Dictionary<int, int> finalCardCount = new Dictionary<int, int>();
foreach(var game in gameRecord) {
finalCardCount.Add(game.Key, 1);
}
// Loop through each game
foreach (var game in gameRecord) {
// take each id after the current game per match on this game
foreach (var nextGame in gameRecord.Where(x => x.Key > game.Key && x.Key <= game.Key + game.Value))
{
// add the card count to the current game
finalCardCount[nextGame.Key] += finalCardCount[game.Key];
}
}
int scratchCardTotal = finalCardCount.Sum(x => x.Value);
Console.WriteLine($"Scratch Card Total: {scratchCardTotal}");
--- Day 5: If You Give A Seed A Fertilizer ---
You take the boat and find the gardener right where you were told he would be: managing a giant "garden" that looks more to you like a farm.
"A water source? Island Island is the water source!" You point out that Snow Island isn't receiving any water.
"Oh, we had to stop the water because we ran out of sand to filter it with! Can't make snow with dirty water. Don't worry, I'm sure we'll get more sand soon; we only turned off the water a few days... weeks... oh no." His face sinks into a look of horrified realization.
"I've been so busy making sure everyone here has food that I completely forgot to check why we stopped getting more sand! There's a ferry leaving soon that is headed over in that direction - it's much faster than your boat. Could you please go check it out?"
You barely have time to agree to this request when he brings up another. "While you wait for the ferry, maybe you can help us with our food production problem. The latest Island Island Almanac just arrived and we're having trouble making sense of it."
The almanac (your puzzle input) lists all of the seeds that need to be planted. It also lists what type of soil to use with each kind of seed, what type of fertilizer to use with each kind of soil, what type of water to use with each kind of fertilizer, and so on. Every type of seed, soil, fertilizer and so on is identified with a number, but numbers are reused by each category - that is, soil 123 and fertilizer 123 aren't necessarily related to each other.
For example:
seeds: 79 14 55 13
seed-to-soil map:
50 98 2
52 50 48
soil-to-fertilizer map:
0 15 37
37 52 2
39 0 15
fertilizer-to-water map:
49 53 8
0 11 42
42 0 7
57 7 4
water-to-light map:
88 18 7
18 25 70
light-to-temperature map:
45 77 23
81 45 19
68 64 13
temperature-to-humidity map:
0 69 1
1 0 69
humidity-to-location map:
60 56 37
56 93 4
The almanac starts by listing which seeds need to be planted: seeds 79, 14, 55, and 13.
The rest of the almanac contains a list of maps which describe how to convert numbers from a source category into numbers in a destination category. That is, the section that starts with seed-to-soil map: describes how to convert a seed number (the source) to a soil number (the destination). This lets the gardener and his team know which soil to use with which seeds, which water to use with which fertilizer, and so on.
Rather than list every source number and its corresponding destination number one by one, the maps describe entire ranges of numbers that can be converted. Each line within a map contains three numbers: the destination range start, the source range start, and the range length.
Consider again the example seed-to-soil map:
50 98 2
52 50 48
The first line has a destination range start of 50, a source range start of 98, and a range length of 2. This line means that the source range starts at 98 and contains two values: 98 and 99. The destination range is the same length, but it starts at 50, so its two values are 50 and 51. With this information, you know that seed number 98 corresponds to soil number 50 and that seed number 99 corresponds to soil number 51.
The second line means that the source range starts at 50 and contains 48 values: 50, 51, ..., 96, 97. This corresponds to a destination range starting at 52 and also containing 48 values: 52, 53, ..., 98, 99. So, seed number 53 corresponds to soil number 55.
Any source numbers that aren't mapped correspond to the same destination number. So, seed number 10 corresponds to soil number 10.
So, the entire list of seed numbers and their corresponding soil numbers looks like this:
seed soil
0 0
1 1
... ...
48 48
49 49
50 52
51 53
... ...
96 98
97 99
98 50
99 51
With this map, you can look up the soil number required for each initial seed number:
Seed number 79 corresponds to soil number 81.
Seed number 14 corresponds to soil number 14.
Seed number 55 corresponds to soil number 57.
Seed number 13 corresponds to soil number 13.
The gardener and his team want to get started as soon as possible, so they'd like to know the closest location that needs a seed. Using these maps, find the lowest location number that corresponds to any of the initial seeds. To do this, you'll need to convert each seed number through other categories until you can find its corresponding location number. In this example, the corresponding types are:
Seed 79, soil 81, fertilizer 81, water 81, light 74, temperature 78, humidity 78, location 82.
Seed 14, soil 14, fertilizer 53, water 49, light 42, temperature 42, humidity 43, location 43.
Seed 55, soil 57, fertilizer 57, water 53, light 46, temperature 82, humidity 82, location 86.
Seed 13, soil 13, fertilizer 52, water 41, light 34, temperature 34, humidity 35, location 35.
So, the lowest location number in this example is 35.
What is the lowest location number that corresponds to any of the initial seed numbers?
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
var filePath = "5/input.txt";
using (var reader = new StreamReader(filePath))
{
var seeds = GetSeeds(reader);
Console.WriteLine($"Seeds: {string.Join(", ", seeds)}");
var seedToSoilMap = GetMap(reader, "seed-to-soil map:");
var soilToFertilizerMap = GetMap(reader, "soil-to-fertilizer map:");
var fertilizerToWaterMap = GetMap(reader, "fertilizer-to-water map:");
var waterToLightMap = GetMap(reader, "water-to-light map:");
var lightToTemperatureMap = GetMap(reader, "light-to-temperature map:");
var temperatureToHumidityMap = GetMap(reader, "temperature-to-humidity map:");
var humidityToLocationMap = GetMap(reader, "humidity-to-location map:");
long lowestLocation = long.MaxValue;
foreach (var seed in seeds)
{
long currentSeed = seed;
currentSeed = ProcessMap(currentSeed, seedToSoilMap);
currentSeed = ProcessMap(currentSeed, soilToFertilizerMap);
currentSeed = ProcessMap(currentSeed, fertilizerToWaterMap);
currentSeed = ProcessMap(currentSeed, waterToLightMap);
currentSeed = ProcessMap(currentSeed, lightToTemperatureMap);
currentSeed = ProcessMap(currentSeed, temperatureToHumidityMap);
currentSeed = ProcessMap(currentSeed, humidityToLocationMap);
lowestLocation = Math.Min(lowestLocation, currentSeed);
}
Console.WriteLine($"The lowest location number is: {lowestLocation}");
}
long ProcessMap(long seed, List<Tuple<long, long, long>> map)
{
foreach (var mapEntry in map)
{
if (seed >= mapEntry.Item2 && seed < mapEntry.Item2 + mapEntry.Item3)
{
return mapEntry.Item1 + (seed - mapEntry.Item2);
}
}
return seed;
}
List<long> GetSeeds(StreamReader reader)
{
var seedsLine = reader.ReadLine();
if (seedsLine != null)
{
List<long> seeds = seedsLine
.Split(' ', StringSplitOptions.RemoveEmptyEntries)
.Where(s => !string.IsNullOrWhiteSpace(s))
.Select(s =>
{
bool parsed = long.TryParse(s, out long value);
return parsed ? value : -1;
})
.Where(value => value >= 0)
.ToList();
return seeds;
}
else
{
Console.WriteLine("Error: Seeds line not found or empty.");
return new List<long>();
}
}
List<Tuple<long, long, long>> GetMap(StreamReader reader, string mapIdentifier)
{
List<Tuple<long, long, long>> map = new List<Tuple<long, long, long>>();
string line;
while ((line = reader.ReadLine()) != null)
{
if (line.StartsWith(mapIdentifier))
{
break;
}
}
while ((line = reader.ReadLine()) != null && !string.IsNullOrWhiteSpace(line))
{
var parts = line.Split(' ');
if (parts.Length == 3)
{
map.Add(Tuple.Create(long.Parse(parts[0]), long.Parse(parts[1]), long.Parse(parts[2])));
}
}
return map;
}
--- Part Two ---
Everyone will starve if you only plant such a small number of seeds. Re-reading the almanac, it looks like the seeds: line actually describes ranges of seed numbers.
The values on the initial seeds: line come in pairs. Within each pair, the first value is the start of the range and the second value is the length of the range. So, in the first line of the example above:
seeds: 79 14 55 13
This line describes two ranges of seed numbers to be planted in the garden. The first range starts with seed number 79 and contains 14 values: 79, 80, ..., 91, 92. The second range starts with seed number 55 and contains 13 values: 55, 56, ..., 66, 67.
Now, rather than considering four seed numbers, you need to consider a total of 27 seed numbers.
In the above example, the lowest location number can be obtained from seed number 82, which corresponds to soil 84, fertilizer 84, water 84, light 77, temperature 45, humidity 46, and location 46. So, the lowest location number is 46.
Consider all of the initial seed numbers listed in the ranges on the first line of the almanac. What is the lowest location number that corresponds to any of the initial seed numbers?
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
var input = File.ReadAllLines("5/input.txt");
var seeds = ParseSeeds(input);
var maps = ParseMaps(input);
var ranges = GetSeedRanges(seeds);
foreach (var map in maps)
{
var orderedMap = map.OrderBy(x => x.from).ToList();
ranges = ProcessSeedRanges(ranges, orderedMap);
}
var result = ranges.Min(r => r.from);
Console.WriteLine($"Lowest Seed Location: {result}");
List<long> ParseSeeds(string[] input)
{
return input[0].Split(' ').Skip(1).Select(x => long.Parse(x)).ToList();
}
List<List<(long from, long to, long adjustment)>> ParseMaps(string[] input)
{
var maps = new List<List<(long from, long to, long adjustment)>>();
List<(long from, long to, long adjustment)>? currMap = null;
foreach (var line in input.Skip(2))
{
if (line.EndsWith(':'))
{
currMap = new List<(long from, long to, long adjustment)>();
continue;
}
else if (line.Length == 0 && currMap != null)
{
maps.Add(currMap!);
currMap = null;
continue;
}
var seedData = line.Split(' ').Select(x => long.Parse(x)).ToArray();
currMap!.Add((seedData[1], seedData[1] + seedData[2] - 1, seedData[0] - seedData[1]));
}
if (currMap != null)
maps.Add(currMap);
return maps;
}
List<(long from, long to)> GetSeedRanges(List<long> seeds)
{
var ranges = new List<(long from, long to)>();
for (int i = 0; i < seeds.Count; i += 2)
ranges.Add((from: seeds[i], to: seeds[i] + seeds[i + 1] - 1));
return ranges;
}
List<(long from, long to)> ProcessSeedRanges(
List<(long from, long to)> ranges,
List<(long from, long to, long adjustment)> map
)
{
var newRanges = new List<(long from, long to)>();
foreach (var r in ranges)
{
var range = r;
foreach (var mapping in map)
{
if (range.from < mapping.from)
{
newRanges.Add((range.from, Math.Min(range.to, mapping.from - 1)));
range.from = mapping.from;
if (range.from > range.to)
break;
}
if (range.from <= mapping.to)
{
newRanges.Add((range.from + mapping.adjustment, Math.Min(range.to, mapping.to) + mapping.adjustment));
range.from = mapping.to + 1;
if (range.from > range.to)
break;
}
}
if (range.from <= range.to)
newRanges.Add(range);
}
return newRanges;
}
--- Wait For It ---
The ferry quickly brings you across Island Island. After asking around, you discover that there is indeed normally a large pile of sand somewhere near here, but you don't see anything besides lots of water and the small island where the ferry has docked.
As you try to figure out what to do next, you notice a poster on a wall near the ferry dock. "Boat races! Open to the public! Grand prize is an all-expenses-paid trip to Desert Island!" That must be where the sand comes from! Best of all, the boat races are starting in just a few minutes.
You manage to sign up as a competitor in the boat races just in time. The organizer explains that it's not really a traditional race - instead, you will get a fixed amount of time during which your boat has to travel as far as it can, and you win if your boat goes the farthest.
As part of signing up, you get a sheet of paper (your puzzle input) that lists the time allowed for each race and also the best distance ever recorded in that race. To guarantee you win the grand prize, you need to make sure you go farther in each race than the current record holder.
The organizer brings you over to the area where the boat races are held. The boats are much smaller than you expected - they're actually toy boats, each with a big button on top. Holding down the button charges the boat, and releasing the button allows the boat to move. Boats move faster if their button was held longer, but time spent holding the button counts against the total race time. You can only hold the button at the start of the race, and boats don't move until the button is released.
For example:
Time: 7 15 30
Distance: 9 40 200
This document describes three races:
The first race lasts 7 milliseconds. The record distance in this race is 9 millimeters.
The second race lasts 15 milliseconds. The record distance in this race is 40 millimeters.
The third race lasts 30 milliseconds. The record distance in this race is 200 millimeters.
Your toy boat has a starting speed of zero millimeters per millisecond. For each whole millisecond you spend at the beginning of the race holding down the button, the boat's speed increases by one millimeter per millisecond.
So, because the first race lasts 7 milliseconds, you only have a few options:
Don't hold the button at all (that is, hold it for 0 milliseconds) at the start of the race. The boat won't move; it will have traveled 0 millimeters by the end of the race.
Hold the button for 1 millisecond at the start of the race. Then, the boat will travel at a speed of 1 millimeter per millisecond for 6 milliseconds, reaching a total distance traveled of 6 millimeters.
Hold the button for 2 milliseconds, giving the boat a speed of 2 millimeters per millisecond. It will then get 5 milliseconds to move, reaching a total distance of 10 millimeters.
Hold the button for 3 milliseconds. After its remaining 4 milliseconds of travel time, the boat will have gone 12 millimeters.
Hold the button for 4 milliseconds. After its remaining 3 milliseconds of travel time, the boat will have gone 12 millimeters.
Hold the button for 5 milliseconds, causing the boat to travel a total of 10 millimeters.
Hold the button for 6 milliseconds, causing the boat to travel a total of 6 millimeters.
Hold the button for 7 milliseconds. That's the entire duration of the race. You never let go of the button. The boat can't move until you let go of the button. Please make sure you let go of the button so the boat gets to move. 0 millimeters.
Since the current record for this race is 9 millimeters, there are actually 4 different ways you could win: you could hold the button for 2, 3, 4, or 5 milliseconds at the start of the race.
In the second race, you could hold the button for at least 4 milliseconds and at most 11 milliseconds and beat the record, a total of 8 different ways to win.
In the third race, you could hold the button for at least 11 milliseconds and no more than 19 milliseconds and still beat the record, a total of 9 ways you could win.
To see how much margin of error you have, determine the number of ways you can beat the record in each race; in this example, if you multiply these values together, you get 288 (4 * 8 * 9).
Determine the number of ways you could beat the record in each race. What do you get if you multiply these numbers together?
using System;
using System.IO;
using System.Linq;
var inputFilePath = "6/input.txt";
var lines = File.ReadAllLines(inputFilePath);
var raceTimes = lines[0]
.Split(' ', StringSplitOptions.RemoveEmptyEntries)
.Skip(1)
.Select(int.Parse)
.ToArray();
var recordDistances = lines[1]
.Split(' ', StringSplitOptions.RemoveEmptyEntries)
.Skip(1)
.Select(int.Parse)
.ToArray();
var totalWaysToWin = raceTimes
.Zip(recordDistances, (time, record) =>
{
var maxHoldTime = Math.Min(time - 1, record);
return Enumerable.Range(1, maxHoldTime)
.Count(holdTime => holdTime * (time - holdTime) > record);
})
.Aggregate(1, (acc, ways) => acc * ways);
Console.WriteLine($"Total ways to win {totalWaysToWin}");
--- Part Two ---
As the race is about to start, you realize the piece of paper with race times and record distances you got earlier actually just has very bad kerning. There's really only one race - ignore the spaces between the numbers on each line.
So, the example from before:
Time: 7 15 30
Distance: 9 40 200
...now instead means this:
Time: 71530
Distance: 940200
Now, you have to figure out how many ways there are to win this single race. In this example, the race lasts for 71530 milliseconds and the record distance you need to beat is 940200 millimeters. You could hold the button anywhere from 14 to 71516 milliseconds and beat the record, a total of 71503 ways!
How many ways can you beat the record in this one much longer race?
using System;
using System.IO;
using System.Linq;
var inputFilePath = "6/input.txt";
var lines = File.ReadAllLines(inputFilePath);
var timeAndDistance = lines.Select(line => line.Split(':')[1].Replace(" ", "")).ToArray();
long record = long.Parse(timeAndDistance[1]);
long time = long.Parse(timeAndDistance[0]);
var firstTimeToBeatRecord = 0;
for (var i = 0; i <= time; i++)
{
if ((time - i) * i > record)
{
firstTimeToBeatRecord = i;
break;
}
}
long totalWaysToWin = time - 2 * firstTimeToBeatRecord + 1;
Console.WriteLine($"Total ways to win: {totalWaysToWin}");
--- Camel Cards ---
Your all-expenses-paid trip turns out to be a one-way, five-minute ride in an airship. (At least it's a cool airship!) It drops you off at the edge of a vast desert and descends back to Island Island.
"Did you bring the parts?"
You turn around to see an Elf completely covered in white clothing, wearing goggles, and riding a large camel.
"Did you bring the parts?" she asks again, louder this time. You aren't sure what parts she's looking for; you're here to figure out why the sand stopped.
"The parts! For the sand, yes! Come with me; I will show you." She beckons you onto the camel.
After riding a bit across the sands of Desert Island, you can see what look like very large rocks covering half of the horizon. The Elf explains that the rocks are all along the part of Desert Island that is directly above Island Island, making it hard to even get there. Normally, they use big machines to move the rocks and filter the sand, but the machines have broken down because Desert Island recently stopped receiving the parts they need to fix the machines.
You've already assumed it'll be your job to figure out why the parts stopped when she asks if you can help. You agree automatically.
Because the journey will take a few days, she offers to teach you the game of Camel Cards. Camel Cards is sort of similar to poker except it's designed to be easier to play while riding a camel.
In Camel Cards, you get a list of hands, and your goal is to order them based on the strength of each hand. A hand consists of five cards labeled one of A, K, Q, J, T, 9, 8, 7, 6, 5, 4, 3, or 2. The relative strength of each card follows this order, where A is the highest and 2 is the lowest.
Every hand is exactly one type. From strongest to weakest, they are:
Five of a kind, where all five cards have the same label: AAAAA
Four of a kind, where four cards have the same label and one card has a different label: AA8AA
Full house, where three cards have the same label, and the remaining two cards share a different label: 23332
Three of a kind, where three cards have the same label, and the remaining two cards are each different from any other card in the hand: TTT98
Two pair, where two cards share one label, two other cards share a second label, and the remaining card has a third label: 23432
One pair, where two cards share one label, and the other three cards have a different label from the pair and each other: A23A4
High card, where all cards' labels are distinct: 23456
Hands are primarily ordered based on type; for example, every full house is stronger than any three of a kind.
If two hands have the same type, a second ordering rule takes effect. Start by comparing the first card in each hand. If these cards are different, the hand with the stronger first card is considered stronger. If the first card in each hand have the same label, however, then move on to considering the second card in each hand. If they differ, the hand with the higher second card wins; otherwise, continue with the third card in each hand, then the fourth, then the fifth.
So, 33332 and 2AAAA are both four of a kind hands, but 33332 is stronger because its first card is stronger. Similarly, 77888 and 77788 are both a full house, but 77888 is stronger because its third card is stronger (and both hands have the same first and second card).
To play Camel Cards, you are given a list of hands and their corresponding bid (your puzzle input). For example:
32T3K 765
T55J5 684
KK677 28
KTJJT 220
QQQJA 483
This example shows five hands; each hand is followed by its bid amount. Each hand wins an amount equal to its bid multiplied by its rank, where the weakest hand gets rank 1, the second-weakest hand gets rank 2, and so on up to the strongest hand. Because there are five hands in this example, the strongest hand will have rank 5 and its bid will be multiplied by 5.
So, the first step is to put the hands in order of strength:
32T3K is the only one pair and the other hands are all a stronger type, so it gets rank 1.
KK677 and KTJJT are both two pair. Their first cards both have the same label, but the second card of KK677 is stronger (K vs T), so KTJJT gets rank 2 and KK677 gets rank 3.
T55J5 and QQQJA are both three of a kind. QQQJA has a stronger first card, so it gets rank 5 and T55J5 gets rank 4.
Now, you can determine the total winnings of this set of hands by adding up the result of multiplying each hand's bid with its rank (765 * 1 + 220 * 2 + 28 * 3 + 684 * 4 + 483 * 5). So the total winnings in this example are 6440.
Find the rank of every hand in your set. What are the total winnings?
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
var lines = File.ReadAllLines("7/input.txt");
var input = lines.Select(line =>
{
var parts = line.Split(' ');
return (Hand: parts[0], Bid: int.Parse(parts[1]));
}).ToList();
var cardStrength = new Dictionary<char, int>
{
{'A', 14}, {'K', 13}, {'Q', 12}, {'J', 11}, {'T', 10},
{'9', 9}, {'8', 8}, {'7', 7}, {'6', 6}, {'5', 5},
{'4', 4}, {'3', 3}, {'2', 2}
};
var sortedHands = input.Select(hand => (Hand: hand.Hand, Bid: hand.Bid, Rank: GetHandRank(hand.Hand)))
.OrderByDescending(hand => hand.Rank.rank)
.ThenByDescending(hand => hand.Rank.orderedCardStrengths, new CardStrengthComparer())
.ToList();
var totalWinnings = sortedHands.Select((hand, index) => hand.Bid * (sortedHands.Count - index)).Sum();
Console.WriteLine($"Total winnings: {totalWinnings}");
(int rank, int[] orderedCardStrengths) GetHandRank(string hand)
{
var counts = hand.GroupBy(c => c)
.ToDictionary(g => g.Key, g => g.Count());
var rank = 0;
if (counts.Values.Max() == 5)
rank = 8; // Five of a kind
else if (counts.Values.Max() == 4)
rank = 7; // Four of a kind
else if (counts.Values.Count(v => v == 3) == 1 && counts.Values.Count(v => v == 2) == 1)
rank = 6; // Full house
else if (counts.Values.Count(v => v == 3) == 1)
rank = 5; // Three of a kind
else if (counts.Values.Count(v => v == 2) == 2)
rank = 4; // Two pair
else if (counts.Values.Count(v => v == 2) == 1)
rank = 3; // One pair
else
rank = 2; // High card
// Convert hand to array of card strengths while maintaining the order
var orderedCardStrengths = hand.Select(c => cardStrength[c]).ToArray();
return (rank, orderedCardStrengths);
}
class CardStrengthComparer : IComparer<int[]>
{
public int Compare(int[] x, int[] y)
{
for (int i = 0; i < Math.Min(x.Length, y.Length); i++)
{
if (x[i] != y[i])
return x[i].CompareTo(y[i]);
}
return x.Length.CompareTo(y.Length);
}
}
Total winnings: 248559379
--- Part Two ---
To make things a little more interesting, the Elf introduces one additional rule. Now, J cards are jokers - wildcards that can act like whatever card would make the hand the strongest type possible.
To balance this, J cards are now the weakest individual cards, weaker even than 2. The other cards stay in the same order: A, K, Q, T, 9, 8, 7, 6, 5, 4, 3, 2, J.
J cards can pretend to be whatever card is best for the purpose of determining hand type; for example, QJJQ2 is now considered four of a kind. However, for the purpose of breaking ties between two hands of the same type, J is always treated as J, not the card it's pretending to be: JKKK2 is weaker than QQQQ2 because J is weaker than Q.
Now, the above example goes very differently:
32T3K 765
T55J5 684
KK677 28
KTJJT 220
QQQJA 483
32T3K is still the only one pair; it doesn't contain any jokers, so its strength doesn't increase.
KK677 is now the only two pair, making it the second-weakest hand.
T55J5, KTJJT, and QQQJA are now all four of a kind! T55J5 gets rank 3, QQQJA gets rank 4, and KTJJT gets rank 5.
With the new joker rule, the total winnings in this example are 5905.
Using the new joker rule, find the rank of every hand in your set. What are the new total winnings?
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
var lines = File.ReadAllLines("7/input.txt");
var input = lines.Select(line =>
{
var parts = line.Split(' ');
return (Hand: parts[0], Bid: int.Parse(parts[1]));
}).ToList();
var cardStrength = new Dictionary<char, int>
{
{'A', 14}, {'K', 13}, {'Q', 12}, {'T', 10}, {'9', 9},
{'8', 8}, {'7', 7}, {'6', 6}, {'5', 5}, {'4', 4},
{'3', 3}, {'2', 2}, {'J', 1} // J is now the weakest
};
var sortedHands = input.Select(hand => (Hand: hand.Hand, Bid: hand.Bid, Rank: GetHandRank(hand.Hand)))
.OrderByDescending(hand => hand.Rank.rank)
.ThenByDescending(hand => hand.Rank.orderedCardStrengths, new CardStrengthComparer())
.ToList();
var totalWinnings = sortedHands.Select((hand, index) => hand.Bid * (sortedHands.Count - index)).Sum();
Console.WriteLine($"Total winnings: {totalWinnings}");
(int rank, int[] orderedCardStrengths) GetHandRank(string hand)
{
var bestHand = CalculateBestHand(hand, cardStrength);
var counts = bestHand.GroupBy(c => c)
.ToDictionary(g => g.Key, g => g.Count());
var rank = 0;
if (counts.Values.Max() == 5)
rank = 8;
else if (counts.Values.Max() == 4)
rank = 7;
else if (counts.Values.Count(v => v == 3) == 1 && counts.Values.Count(v => v == 2) == 1)
rank = 6;
else if (counts.Values.Count(v => v == 3) == 1)
rank = 5;
else if (counts.Values.Count(v => v == 2) == 2)
rank = 4;
else if (counts.Values.Count(v => v == 2) == 1)
rank = 3;
else
rank = 2;
var orderedCardStrengths = hand.Select(c => cardStrength[c]).ToArray();
return (rank, orderedCardStrengths);
}
class CardStrengthComparer : IComparer<int[]>
{
public int Compare(int[] x, int[] y)
{
for (int i = 0; i < Math.Min(x.Length, y.Length); i++)
{
if (x[i] != y[i])
return x[i].CompareTo(y[i]);
}
return x.Length.CompareTo(y.Length);
}
}
string CalculateBestHand(string hand, Dictionary<char, int> cardStrength)
{
// Replace 'J' with the best possible card to form the strongest hand
var cards = hand.ToCharArray();
var jokerCount = cards.Count(c => c == 'J');
if (jokerCount == 0)
return hand; // No jokers, return the hand as is
// Possible cards to replace 'J'
var possibleCards = cardStrength.Keys.Except(new[] { 'J' });
// Evaluate each possible replacement and choose the one that results in the best hand
var bestHand = hand;
var bestRank = 0;
var bestOrderedCardStrengths = Array.Empty<int>();
foreach (var replacement in possibleCards)
{
var replacedHand = new string(cards.Select(c => c == 'J' ? replacement : c).ToArray());
var (rank, orderedCardStrengths) = GetHandRank(replacedHand);
if (rank > bestRank || (rank == bestRank && CompareCardStrengths(orderedCardStrengths, bestOrderedCardStrengths) > 0))
{
bestHand = replacedHand;
bestRank = rank;
bestOrderedCardStrengths = orderedCardStrengths;
}
}
return bestHand;
}
int CompareCardStrengths(int[] strengths1, int[] strengths2)
{
for (int i = 0; i < Math.Min(strengths1.Length, strengths2.Length); i++)
{
if (strengths1[i] != strengths2[i])
return strengths1[i].CompareTo(strengths2[i]);
}
return strengths1.Length.CompareTo(strengths2.Length);
}
Total winnings: 249631254
--- Haunted Wasteland ---
You're still riding a camel across Desert Island when you spot a sandstorm quickly approaching. When you turn to warn the Elf, she disappears before your eyes! To be fair, she had just finished warning you about ghosts a few minutes ago.
One of the camel's pouches is labeled "maps" - sure enough, it's full of documents (your puzzle input) about how to navigate the desert. At least, you're pretty sure that's what they are; one of the documents contains a list of left/right instructions, and the rest of the documents seem to describe some kind of network of labeled nodes.
It seems like you're meant to use the left/right instructions to navigate the network. Perhaps if you have the camel follow the same instructions, you can escape the haunted wasteland!
After examining the maps for a bit, two nodes stick out: AAA and ZZZ. You feel like AAA is where you are now, and you have to follow the left/right instructions until you reach ZZZ.
This format defines each node of the network individually. For example:
RL
AAA = (BBB, CCC)
BBB = (DDD, EEE)
CCC = (ZZZ, GGG)
DDD = (DDD, DDD)
EEE = (EEE, EEE)
GGG = (GGG, GGG)
ZZZ = (ZZZ, ZZZ)
Starting with AAA, you need to look up the next element based on the next left/right instruction in your input. In this example, start with AAA and go right (R) by choosing the right element of AAA, CCC. Then, L means to choose the left element of CCC, ZZZ. By following the left/right instructions, you reach ZZZ in 2 steps.
Of course, you might not find ZZZ right away. If you run out of left/right instructions, repeat the whole sequence of instructions as necessary: RL really means RLRLRLRLRLRLRLRL... and so on. For example, here is a situation that takes 6 steps to reach ZZZ:
LLR
AAA = (BBB, BBB)
BBB = (AAA, ZZZ)
ZZZ = (ZZZ, ZZZ)
Starting at AAA, follow the left/right instructions. How many steps are required to reach ZZZ?
using System;
using System.Collections.Generic;
using System.IO;
string[] input = File.ReadAllLines("8/input.txt");
string instructions = input[0];
Dictionary<string, (string Left, string Right)> map = new Dictionary<string, (string, string)>();
for (int i = 1; i < input.Length; i++)
{
if (string.IsNullOrWhiteSpace(input[i]))
continue;
var parts = input[i].Split(" = (", StringSplitOptions.RemoveEmptyEntries);
if (parts.Length != 2)
continue;
var node = parts[0].Trim();
var edges = parts[1].Trim(')').Split(", ");
if (edges.Length != 2)
continue;
map[node] = (edges[0], edges[1]);
}
string currentNode = "AAA";
int stepCount = 0;
int instructionIndex = 0;
while (currentNode != "ZZZ")
{
if (!map.ContainsKey(currentNode))
throw new KeyNotFoundException($"Node {currentNode} not found in map.");
currentNode = instructions[instructionIndex] == 'L' ? map[currentNode].Left : map[currentNode].Right;
stepCount++;
instructionIndex = (instructionIndex + 1) % instructions.Length;
}
Console.WriteLine($"Steps to reach ZZZ: {stepCount}");
Steps to reach ZZZ: 16697
--- Part Two ---
The sandstorm is upon you and you aren't any closer to escaping the wasteland. You had the camel follow the instructions, but you've barely left your starting position. It's going to take significantly more steps to escape!
What if the map isn't for people - what if the map is for ghosts? Are ghosts even bound by the laws of spacetime? Only one way to find out.
After examining the maps a bit longer, your attention is drawn to a curious fact: the number of nodes with names ending in A is equal to the number ending in Z! If you were a ghost, you'd probably just start at every node that ends with A and follow all of the paths at the same time until they all simultaneously end up at nodes that end with Z.
For example:
LR
11A = (11B, XXX)
11B = (XXX, 11Z)
11Z = (11B, XXX)
22A = (22B, XXX)
22B = (22C, 22C)
22C = (22Z, 22Z)
22Z = (22B, 22B)
XXX = (XXX, XXX)
Here, there are two starting nodes, 11A and 22A (because they both end with A). As you follow each left/right instruction, use that instruction to simultaneously navigate away from both nodes you're currently on. Repeat this process until all of the nodes you're currently on end with Z. (If only some of the nodes you're on end with Z, they act like any other node and you continue as normal.) In this example, you would proceed as follows:
Step 0: You are at 11A and 22A.
Step 1: You choose all of the left paths, leading you to 11B and 22B.
Step 2: You choose all of the right paths, leading you to 11Z and 22C.
Step 3: You choose all of the left paths, leading you to 11B and 22Z.
Step 4: You choose all of the right paths, leading you to 11Z and 22B.
Step 5: You choose all of the left paths, leading you to 11B and 22C.
Step 6: You choose all of the right paths, leading you to 11Z and 22Z.
So, in this example, you end up entirely on nodes that end in Z after 6 steps.
Simultaneously start on every node that ends with A. How many steps does it take before you're only on nodes that end with Z?
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
static BigInteger LCM(BigInteger a, BigInteger b)
{
return (a * b) / BigInteger.GreatestCommonDivisor(a, b);
}
BigInteger CalculateCycleLength(string startNode)
{
var visited = new Dictionary<(string Node, int Index), int>();
var currentState = (Node: startNode, Index: 0);
int step = 0;
while (!visited.ContainsKey(currentState))
{
visited[currentState] = step;
currentState = instructions[currentState.Index] == 'L' ?
(map[currentState.Node].Left, (currentState.Index + 1) % instructions.Length)
: (map[currentState.Node].Right, (currentState.Index + 1) % instructions.Length);
step++;
}
return step - visited[currentState];
}
string[] input = File.ReadAllLines("8/input.txt");
string instructions = input[0];
Dictionary<string, (string Left, string Right)> map = input.Skip(2)
.Select(line => line.Split(" = (", StringSplitOptions.RemoveEmptyEntries))
.ToDictionary(
parts => parts[0].Trim(),
parts => (parts[1].Split(", ")[0], parts[1].Split(", ")[1].Trim(')')));
// Calculate Cycle Lengths and LCM
var cycleLengths = map.Keys.Where(node => node.EndsWith("A"))
.Select(node => CalculateCycleLength(node));
BigInteger resultLCM = cycleLengths.Aggregate((current, length) => LCM(current, length));
Console.WriteLine($"Steps to reach all Z-ending nodes: {resultLCM}");
Steps to reach all Z-ending nodes: 10668805667831
--- Mirage Maintenance ---
You ride the camel through the sandstorm and stop where the ghost's maps told you to stop. The sandstorm subsequently subsides, somehow seeing you standing at an oasis!
The camel goes to get some water and you stretch your neck. As you look up, you discover what must be yet another giant floating island, this one made of metal! That must be where the parts to fix the sand machines come from.
There's even a hang glider partially buried in the sand here; once the sun rises and heats up the sand, you might be able to use the glider and the hot air to get all the way up to the metal island!
While you wait for the sun to rise, you admire the oasis hidden here in the middle of Desert Island. It must have a delicate ecosystem; you might as well take some ecological readings while you wait. Maybe you can report any environmental instabilities you find to someone so the oasis can be around for the next sandstorm-worn traveler.
You pull out your handy Oasis And Sand Instability Sensor and analyze your surroundings. The OASIS produces a report of many values and how they are changing over time (your puzzle input). Each line in the report contains the history of a single value. For example:
0 3 6 9 12 15
1 3 6 10 15 21
10 13 16 21 30 45
To best protect the oasis, your environmental report should include a prediction of the next value in each history. To do this, start by making a new sequence from the difference at each step of your history. If that sequence is not all zeroes, repeat this process, using the sequence you just generated as the input sequence. Once all of the values in your latest sequence are zeroes, you can extrapolate what the next value of the original history should be.
In the above dataset, the first history is 0 3 6 9 12 15. Because the values increase by 3 each step, the first sequence of differences that you generate will be 3 3 3 3 3. Note that this sequence has one fewer value than the input sequence because at each step it considers two numbers from the input. Since these values aren't all zero, repeat the process: the values differ by 0 at each step, so the next sequence is 0 0 0 0. This means you have enough information to extrapolate the history! Visually, these sequences can be arranged like this:
0 3 6 9 12 15
3 3 3 3 3
0 0 0 0
To extrapolate, start by adding a new zero to the end of your list of zeroes; because the zeroes represent differences between the two values above them, this also means there is now a placeholder in every sequence above it:
0 3 6 9 12 15 B
3 3 3 3 3 A
0 0 0 0 0
You can then start filling in placeholders from the bottom up. A needs to be the result of increasing 3 (the value to its left) by 0 (the value below it); this means A must be 3:
0 3 6 9 12 15 B
3 3 3 3 3 3
0 0 0 0 0
Finally, you can fill in B, which needs to be the result of increasing 15 (the value to its left) by 3 (the value below it), or 18:
0 3 6 9 12 15 18
3 3 3 3 3 3
0 0 0 0 0
So, the next value of the first history is 18.
Finding all-zero differences for the second history requires an additional sequence:
1 3 6 10 15 21
2 3 4 5 6
1 1 1 1
0 0 0
Then, following the same process as before, work out the next value in each sequence from the bottom up:
1 3 6 10 15 21 28
2 3 4 5 6 7
1 1 1 1 1
0 0 0 0
So, the next value of the second history is 28.
The third history requires even more sequences, but its next value can be found the same way:
10 13 16 21 30 45 68
3 3 5 9 15 23
0 2 4 6 8
2 2 2 2
0 0 0
So, the next value of the third history is 68.
If you find the next value for each history in this example and add them together, you get 114.
Analyze your OASIS report and extrapolate the next value for each history. What is the sum of these extrapolated values?
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
int ExtrapolateNextValue(List<int> history)
{
List<int> diffs;
List<List<int>> sequences = new List<List<int>> { new List<int>(history) };
do
{
diffs = sequences.Last().Zip(sequences.Last().Skip(1), (a, b) => b - a).ToList();
sequences.Add(diffs);
}
while (diffs.Any(d => d != 0));
// Extrapolate next value from the bottom up
for (int i = sequences.Count - 2; i >= 0; i--)
{
sequences[i].Add(sequences[i].Last() + sequences[i + 1].Last());
}
return sequences[0].Last();
}
var lines = File.ReadAllLines("9/input.txt");
var sumOfExtrapolatedValues = lines.Select(line => ExtrapolateNextValue(line.Split().Select(int.Parse).ToList())).Sum();
Console.WriteLine($"Sum of extrapolated values: {sumOfExtrapolatedValues}");
Sum of extrapolated values: 2043183816
--- Part Two ---
Of course, it would be nice to have even more history included in your report. Surely it's safe to just extrapolate backwards as well, right?
For each history, repeat the process of finding differences until the sequence of differences is entirely zero. Then, rather than adding a zero to the end and filling in the next values of each previous sequence, you should instead add a zero to the beginning of your sequence of zeroes, then fill in new first values for each previous sequence.
In particular, here is what the third example history looks like when extrapolating back in time:
5 10 13 16 21 30 45
5 3 3 5 9 15
-2 0 2 4 6
2 2 2 2
0 0 0
Adding the new values on the left side of each sequence from bottom to top eventually reveals the new left-most history value: 5.
Doing this for the remaining example data above results in previous values of -3 for the first history and 0 for the second history. Adding all three new values together produces 2.
Analyze your OASIS report again, this time extrapolating the previous value for each history. What is the sum of these extrapolated values?
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
int ExtrapolatePreviousValue(List<int> history)
{
List<int> diffs;
List<List<int>> sequences = new List<List<int>> { new List<int>(history) };
do
{
diffs = sequences.Last().Zip(sequences.Last().Skip(1), (a, b) => b - a).ToList();
sequences.Add(diffs);
}
while (diffs.Any(d => d != 0));
// Extrapolate previous value from the bottom up
for (int i = sequences.Count - 2; i >= 0; i--)
{
sequences[i].Insert(0, sequences[i][0] - sequences[i + 1][0]);
}
return sequences[0].First();
}
var lines = File.ReadAllLines("9/input.txt");
var sumOfExtrapolatedPreviousValues = lines.Select(line => ExtrapolatePreviousValue(line.Split().Select(int.Parse).ToList())).Sum();
Console.WriteLine($"Sum of extrapolated previous values: {sumOfExtrapolatedPreviousValues}");
Sum of extrapolated previous values: 1118