Introduction
This book documents my solutions and the thought process that went into my advent of code solutions.
Day one
On day one, you are loaded in a trebuchet of which the calibration was done by a young artistic elf. Due to the artistry, the calibration value is difficult to read. We need to get the calibration value for the elves.
Part one
For the first part, we need to find a calibration value within a line of text, grabbing only the first and last number in that line of text. These two numbers have to be concatenated and form a two digit number together. By adding up all these numbers, you find your calibration value.
I started by just creating a simple test to check if the example input equals the example answer. With this I can check if my code is correct for the example, so I can use it on my true input. Tests are really easy to write in rust, so my test looks like this:
#[test]
fn test_part_one() {
let input_file: &str = "\
1abc2
pqr3stu8vwx
a1b2c3d4e5f
treb7uchet";
let answer: i64 = 142;
assert_eq!(answer, part_one(input_file));
}This will check if the answer is the same as the output of part one. These tests do have to be wrapped in a mod tests which is also has a #[cfg(tests)] value associated with it.
Next, I added a simple parser that splits the input into lines, so I can iterate over every line within my part_one() function. To get all the lines from some text, you can just use the text.lines() function and store this in a vec as follows.
fn parse(file: &str) -> Vec<&str> {
let lines: Vec<&str> = file.lines().collect();
lines
}Now let's start with solving the problem!
fn part_one(input: &str) -> i64 {
let lines = parse(input);
let mut answer: i64 = 0;
for line in lines {
let nums: Vec<char> = line.chars()
.filter(|c| c.is_digit(10))
.collect();
let number_string: String = [nums[0], nums[nums.len() - 1]].iter().collect();
let number: i64 = number_string.parse::<i64>().expect("Can't parse string!");
answer += number;
}
answer
}In the for loop, we first create a vector from the characters in our string that are digits. This is done by the filter() method. Fofr every character c, we check if the number is a digit within the range of 0-10. If this is true, the character is collected by the vector. So if a string is 1abc2, the associated vector will be ['1', '2'].
Next up, we create a String from the characters. We need the first and last character in the vector, so position 0 and the length of the vector -1, because the length doesn't start at 0. By collecting these characters, we can create a string, which is essentially a vector of characters.
At last, we parse the string, which always should be possible. We panic! if it isn't possible, because that means that something went wrong. The final number is added to the answer and this is repeated for every line in the file. By returning the number, we can just use println! to print the number and get our answer. This is exactly what we do in the main function.
fn main() {
let input_file = include_str!("../../inputs/day_01.txt");
let answer_one = part_one(input_file);
println!("Part one: {}\n", answer_one);
}Here we read the input file to a string and use this as input for our part_one() function. This function returns an i64, so we bind a variable to that and print the variable. If everything works correctly, you should see the correct answer here.
Part two
Part two throws us a bit for a loop, because it appears that there are also numbers hidden in our file with plain text. This looks like this: two1nine, which means the answer should be 29. This is because we need to parse the text numbers into numbers and then take the first and last part of the numbers.
Let's start by writing another test and making sure all the functions are correct. Our new test uses a different test input, so it looks a bit different.
#[test]
fn test_part_two() {
let input_file: &str = "\
two1nine
eightwothree
abcone2threexyz
xtwone3four
4nineeightseven2
zoneight234
7pqrstsixteen";
let answer: i64 = 281;
assert_eq!(answer, part_two(input_file));
}We also have created a part_two() function, which returns an i64 and added the part two output to our main() function. This looks like this.
fn main() {
let input_file = include_str!("../../inputs/day_01.txt");
let answer_one = part_one(input_file);
let answer_two = part_two(input_file);
println!("Part one: {}\nPart two: {}", answer_one, answer_two);
}
fn part_two(input: &str) -> i64 {
let lines = parse(input);
281
}We still use the same input file, but the output now also outputs the second part. I'm currently just returning the answer so my test passes. Now let's start solving the problem.
Luckily, we can use most of the code from part one. I know that repetition is bad practice, but I want to have every part work independently and be clear to read for every function. So I've copied all the code over from the first part.
fn part_one(input: &str) -> i64 {
let lines = parse(input);
let mut answer: i64 = 0;
for line in lines {
let nums: Vec<char> = line.chars()
.filter(|c| c.is_digit(10))
.collect();
let number_string: String = [nums[0], nums[nums.len() - 1]].iter().collect();
let number: i64 = number_string.parse::<i64>().expect("Can't parse string!");
answer += number;
}
answer
}This function works exactly like the one in the first part, but we need to make some modifications to the line variable before we parse it. This is quite easy, as we can just replace any occurence of a string in a line with another string with replace().
fn part_one(input: &str) -> i64 {
// snip
for line in lines {
let line = line
.replace("one", "1")
.replace("two", "2")
.replace("three", "3")
.replace("four", "4")
.replace("five", "5")
.replace("six", "6")
.replace("seven", "7")
.replace("eight", "8")
.replace("nine", "9");
//snip
}
answer
}We just replace all of the instances of a written out number with a number and the parsing works! Now let's run cargo test. Aaaaand the test fails. With this function, we get 211 as answer, but we need 281. Let's backtrack to the input.
It seems that our issue lies in the parsing of the text. In some lines the letters of the numbers overlap, like in xtwone3four. Because we convert one first, this means we get 14 instead of 24. So, we should leave certain parts of the text intact. With a new, updated function it does work!
fn part_one(input: &str) -> i64 {
// snip
for line in lines {
let line = line
.replace("one", "o1e")
.replace("two", "t2o")
.replace("three", "t3ree")
.replace("four", "f4ur")
.replace("five", "f5ve")
.replace("six", "s6x")
.replace("seven", "s7ven")
.replace("eight", "e8ght")
.replace("nine", "n9ne");
//snip
}
answer
}This does work, I've replaced every second character of the numbers with a number, so the first and last characters never interfere. The first and last are the only ones that would overlap, so this is a simple way to do it. Another way would be to convert one to one1one, which leaves the full word at the front and back intact. Now we've solved both parts for day 1, so on to day 2!
The files for this day are available here. If you want to test the full solution with the test input, check out the playground.
Day two
For day two of advent of code, we arrive at Snow Island. We walk a bit with an elf and play a game. The elf will show us some red, green and blue cubes and we have to tell which games were possible.
Part one
For the first part, we are given an example input and need to fins out which games were possible with 12 red, 13 green, and 14 blue cubes. Let's start and write a test for that.
#[test]
fn test_part_one() {
let input_file: &str = "\
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";
let answer: i64 = 8;
assert_eq!(answer, part_one(input_file));
}Make sure to wrap this in mod tests, which uses #[cfg(test)]. Now, we can start by solving the puzzle. The advent of code explanation says that you need to take a look at every draw from the bag and need to take a look what was the highest number and check if the game was possible. Because we just need to check if the largest number per color is smaller than the given colors, we can skip the whole draw part.
I've tried to compile this into a simple parser, where we're left with a vector that contains all the drawn cubes in a game.
fn parse(file: &str) -> Vec<&str> {
let lines: Vec<&str> = file.lines()
.map(|l| {
let (_, cubes) = l
.split_once(": ")
.expect("Couldn't split line!"); cubes })
.collect();
lines
}This function splits the file in lines and removes everything in front of the : , which means we only have the numbers and cubes. Now we need to check which games were possible. I'm starting by creating a loop that registers the indices of a game and maps every game to a vec of just the count and the color of the cubes.
for (id, game ) in games.iter().enumerate() {
let id = id + 1;
let draws: Vec<&str> = game
.split([',', ';'])
.map(|s| s.trim())
.collect();
}This registers every id by using .iter().enumerate(). We need to add 1 to that, because the initial id's will be the index of the game, which start at 0. The draws are splitted in every count and cube and the whitespace is trimmed. We split at two different characters, because the draws can be split by those characters (due to draws and sets being a different thing in the explanation).
For every draw, we need to check the color, the amount and if the draw is smaller than the maximum amount possible. If it isn't smaller, we need to skip the id and continue to the next game. The first part is done like so:
for draw in draws {
let (count, color) = draw
.split_once(" ")
.expect("Can't split draw!");
let count = count.parse::<i64>().expect("Can't parse count!");
let possible = match color {
"red" => count <= 12,
"green" => count <= 13,
"blue" => count <= 14,
_ => panic!("That shouldn't happen..."),
};
}We split the draw into a count and color. which are separated by a space. The count always precedes the color, as you can see in the example. After this, we parse the count so we can compare it easily and return a boolean if the value we've found is possible or not.
We now know if a draw was possible, but we still need to skip the round if the value wasn't possible. This is were the continue function comes in. We can use continue to skip the current iteration of a for loop and go to the second.
'outer: for (id, game ) in games.iter().enumerate() {
// snip
for draw in draws {
// snip
if !possible { continue 'outer; }
}
answer += id as i64;
}We use a label to specify which loop has to continue, which in this case is the outer loop. If we hadn't used this, the inner for loop would just continue at the next draw, making it so every id is added to our answer. If all draws in a game are possible, we add the id to the answer and the next game is checked. At the end of the for loop we also return the answer, giving us access to it in the main() function.
Speaking of the main() function, it is built up in the same way as day one:
fn main() {
let input_file = include_str!("../../inputs/day_02.txt");
let answer_one = part_one(input_file);
let answer_two = part_two(input_file);
println!("Part one: {}\nPart two: {}", answer_one, answer_two);
}We can now use this to print out the answer of part one, but let's add the part two function too!
Part two
For part two, we need to check the minimum amount of cubes of each color necessary to play a game. We need to multiply all the values of all colors together and add it up to come to the answer. Let's start by making another test.
#[test]
fn test_part_two() {
let input_file: &str = "\
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";
let answer: i64 = 2286;
assert_eq!(answer, part_two(input_file));
}Now we need to get the answer for part two, so let's start on that. The first part is mostly the same, so let's copy and paste that from part one. We need to change up some parts of the innermost for loop though.
let games: Vec<&str> = parse(input);
let mut answer: i64 = 0;
for game in games {
let mut red: Vec<i64> = Vec::new();
let mut green: Vec<i64> = Vec::new();
let mut blue: Vec<i64> = Vec::new();
// snip
let draws: Vec<&str> = game
.split([',', ';'])
.map(|s| s.trim())
.collect();
for draw in draws {
let (count, color) = draw
.split_once(" ")
.expect("Can't split draw!");
let count = count.parse::<i64>().expect("Can't parse count!");
// snip
match color {
"red" => red.push(count),
"green" => green.push(count),
"blue" => blue.push(count),
_ => panic!("That shouldn't happen..."),
};
}
let red = red.iter().max().expect("Couldn't find minimum value!");
let green = green.iter().max().expect("Couldn't find minimum value!");
let blue = blue.iter().max().expect("Couldn't find minimum value!");
let power: i64 = red * green * blue;
answer += power;
}
answerI've snipped out the parts that are the same as the part one solution, but you can view them in the code preview. Now let's take a look at what's happening here. First, we start by creating a few vectors which contain all the values which belong to a color. After this, we match the color and push the count to the correct vector if we match the correct color. Finally, we get the largest value out of these vectors (which is the minimum value to make a game possible) and multiply these.
To solve part two, we return the answer so we can view our output. The full project for this day is available here. If you want to try the full solution with a test input, take a look at the playground.
Day three
For day three, we need to find a certain engine part for an elf engineer so we can go up a gondola lift. We need to find this part number within an engine schematic.
Part one
For part one, we need to add up all part numbers that are adjecent to a symbol. These numbers can be adjacent horizontal, vertical or diagonal. This is what makes the challenge a bit difficult. Let's start creating a simple test for part one.
#[test]
fn test_part_one() {
let input_file: &str = "\
467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..";
let answer: i64 = 4361;
assert_eq!(answer, part_one(input_file));
}My first idea is to create a vector of every line, with every character in the line being stored in a vector. With this we can have a coordinate system, with the index in vector 1 being y and the index in vec 2 being x. This can be whipped up with a simple parser function.
fn parser(file: &str) -> Vec<Vec<char>> {
let map: Vec<Vec<char>> = file
.lines()
.map(|s| s.chars().collect())
.collect();
map
}This function splits the input into lines and maps the characters in every line to a vector of characters. This makes it so that we have a 2 dimensional vector of all the characters in the map Now we need to find out if any number is adjacent to a special character. This problem is quite difficult to solve, so let's take a look at the conditions we need to add a number.
First, we need to check if any digit of a number is adjacent to a special character. We also need to get the full number to add to our answer. Because two special characters can be adjacent to the same number, I'm going to store the numbers so I don't have to deal with duplicate numbers. Let's try to find a digit in our array of characters first.
let mut numbers: Vec<Number> = Vec::new();
let mut symbols: HashSet<(i64, i64)> = HashSet::new();
for (y, line) in map.iter().enumerate() {
for (x, &ch) in line.iter().enumerate() {
if ch.is_digit(10) {
// get number + coords
} else if ch != '.' {
// get symbol coords
} else {
continue
}
}
}In this piece of code, we iterate over each line and each character, keeping track of the indices by using enumerate(). If we find a digit, we want to get the full number and the coordinates of the cells around the number. If we find a special character (that's not a .) we want to get the coordinates of that symbol only, so we can overlay the coordinates of the number's surroundings with the coordinates of the character.
Now let's go over getting the number and coordinates if we find a digit. I'm using a struct for this, so I can easily create new numbers and coordinate blocks around it. The code I used to find the full number and the coordinates around it is as follows.
struct Number {
value: i64,
coords: HashSet<(i64, i64)>,
}
impl Number {
fn new(x: usize, y: usize, map: &Vec<Vec<char>>) -> Self {
let mut number: String = String::new();
let mut coords: HashSet<(i64, i64)> = HashSet::new();
for x in x..map.len() {
if map[y][x].is_digit(10) {
number.push(map[y][x]);
let x = x as i64;
let y = y as i64;
coords.extend(HashSet::from([
(x - 1, y - 1), (x - 1, y), (x - 1, y + 1),
(x, y - 1), (x, y + 1),
(x + 1, y - 1), (x + 1, y), (x + 1, y + 1),
]));
} else {
break;
}
}
Number {
value: number.parse::<i64>().expect("Couldn't parse number!"),
coords,
}
}
}First, we create a struct that gets a full number as an i64, and gets a coordinate cloud as a HashSet. HashSets only take unique items, so every coordinate in the HashSet will be unique. I implemented a new() function for the number, to limit the amount of code in the part_one() function.
In the new() function, we start by initializing a string (which is an array of characters) and a HashSet for the coordinates. For every location from x through the length of the map, we check if the character at that location is a digit. If this is true, we append the character to the string, forming our number. We then get the 8 locations directly around the x of the character and add those to the HashSet. By using extend(), we can add a full vector. The extend() function will check if the coordinates already exist, eliminating double entries. If we don't find any digits anymore, we break out of the loop.
After that, we return the Number struct with the parsed value and the coordinate range around the number. There is one problem with the for loop. It will return the first full number and continue returning the consecutive digits, giving us way to much numbers. This can easily be fixed by skipping the iterations over the length of the number.
let mut numbers: Vec<Number> = Vec::new();
let mut symbols: HashSet<(i64, i64)> = HashSet::new();
for (y, line) in map.iter().enumerate() {
let mut n = 0;
for (x, &ch) in line.iter().enumerate() {
if n > 0 {
n -= 1;
continue;
}
if ch.is_digit(10) {
let num = Number::new(x, y, &map);
n += (num.value.to_string()).len() - 1;
numbers.push(num);
} //snip
}
}With this, we can skip every iteration over the length of the number we've just gotten. Now that that's out of the way, we need to get the coordinates of each character in the map. We already have a hashset for the symbols, so we just need to extend() the coordinates of our symbol.
for (y, line) in map.iter().enumerate() {
let mut n = 0;
for (x, &ch) in line.iter().enumerate() {
//snip
if ch.is_digit(10) {
let num = Number::new(x, y, &map);
n += (num.value.to_string()).len() - 1;
numbers.push(num);
} else if ch != '.' {
let coords = [
(x as i64, y as i64),
];
symbols.extend(coords);
} else {
continue
}
}
}Here, we just get the current x and y values as an i64 and add them to our HashSet. Now let's just reiterate over what we've done. First, we map all the characters into a 2D vector and iterate over those characters. When we find a digit, we create a number out of it and skip the iterations over the length of the number to prevent the creation of non-existent numbers.
We get all the coordinates around a number and the coordinates of the symbols, and that's basically the point where we are now. To find which numbers we need to add up, we need to check if the coordinates around a number intersect with the coordinates of a symbol. Luckily, a HashSet has this great function called intersection(). To make the general idea a bit clearer, I've added an image. Here, the orange parts are the coordinates around our number. If we find a symbol in those coordinates (the * in this case) we want to see that as a part number.
Let's implement this in our code. Luckily, it is quite easy. We've gotten both coordinates in HashSets, so we can just intersection() them.
for number in numbers {
if number.coords.intersection(&symbols).next().is_some() {
answer += number.value;
}
}We check the if the coordinates for each number intersect with the coordinates for each symbol. If that is true, we just add our number and we get our output!
Part two
For the second part, we need to find the gear ratios within our schematic. To find these, we need to find the 'gears', or * and multiply the two numbers next to it if we find just two numbers. Note that if we find 1 or 3 numbers, the calculation doesn't count. Let's start by writing a new test.
#[test]
fn test_part_two() {
let input_file: &str = "\
467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..";
let answer: i64 = 467835;
assert_eq!(answer, part_two(input_file));
}Now, let's copy our code from part one and make a few adjustments to it.
let map = parser(input);
// snip
let mut gears: HashSet<(i64, i64)> = HashSet::new();
for (y, line) in map.iter().enumerate() {
let mut n = 0;
for (x, &ch) in line.iter().enumerate() {
// snip
if ch.is_digit(10) {
// snip
} else if ch == '*' {
let coords = [
(x as i64, y as i64),
];
gears.extend(coords);
} else {
continue
}
}
}I've cut off the last few for loops, but what I mainly did here is renamed our symbols variable to gears (because we're looking for gears) and check if the character is a *, which is a gear. Now let's go over the search loop.
for gear in gears {
let mut hits: Vec<i64> = Vec::new();
for number in &numbers {
if number.coords.contains(&gear) {
hits.push(number.value);
}
}
if hits.len() == 2 {
answer += hits[0] * hits[1];
}
}Here, we iterate over each gear in stead of each number. Within each gear, we gather the hits we got around the gear. We do this by iterating over each number and check if it's coordinates are the same as the coordinates of the gear. After we've looped over all numbers, we check if we just have 2 hits. If this is true, we multiply the two numbers we've found and add them to our answer.
Today was a bit difficult with the 2D vectors, but after preparing most work for part one, part two was significantly easier. If you want to check out the full file for day 3, take a look at the repo. To run the code with the test input, check out the playground.
Day four
On day four, we find an elf sitting in a huge pile of scratchcards. We need to help the elf figure out what he has won.
Part one
For the first part, we need to calculate the score for the scratchcards. Each card contains two rows of values, separated by a pipe (|). The first row are the winning numbers and the second are the numbers on your card. You calculate the score by taking 1 point for the first winning number and doubling this for every consecutive one. This is the same as raising the score - 1 to the power of 2.
Let's start by writing a test with the example input and throwing it in mod tests.
#[test]
fn test_part_one() {
let input_file: &str = "\
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
";
let answer: i64 = 13;
assert_eq!(answer, part_one(input_file));
}Next, we want to parse the file and throw out the Card #: . Let's write a simple parser that returns the lines and throws out that first part.
fn parse(file: &str) -> Vec<&str> {
let lines: Vec<&str> = file.lines()
.map(|l| {
let (_, cards) = l
.split_once(": ")
.expect("Couldn't split line!"); cards })
.collect();
lines
}This parser is basically the same as in day 2. Now, we need to split the winning numbers and the owned numbers and throw them in a HashSet. We can use the great intersection() function for this day again, just like in day 3. So let's map these numbers in a HashSet.
for line in lines {
let (winning, card) = line
.split_once(" | ")
.expect("Couldn't split numbers!");
let winning_numbers: HashSet<i64> = winning
.split_whitespace()
.map(|num| num.parse::<i64>().expect("Can't parse number!"))
.collect();
let card_numbers: HashSet<i64> = card
.split_whitespace()
.map(|num| num.parse::<i64>().expect("Can't parse number!"))
.collect();
}First, we split the line at the pipe, so we have two different rows of numbers. Next, we split the cards at the whitespace (because some single-digit numbers have two spaces in front of them) and parse them. After we've parsed the numbers, we map them to a HashSet. I've only shown the first variable assignment here, because they're the same. You can take a look at the second one by clicking on the eye icon.
Now, we need to count how many wins we get per card and raise that (minus one) to a power of 2.
for line in lines {
// snip
let power = winning_numbers.intersection(&card_numbers).count();
if power > 0 {
answer += 2_i64.pow((power - 1) as u32);
}
}Here, we count the amount of intersections we have per card. Next, we check if the power is greater than 0 (otherwise we're subtracting with overflow) and add the power minus one to the answer. After we've iterated over all the cards, we have our final answer! Now on to part two.
Part two
Part two makes this a whole lot more difficult. If we win on a card, we get that amount of consecutive copies on the next crads. There is a lot of text explaining this, but the gist of it is as follows: If we win 2 times on card 1, we get 1 copy of card 2 and 1 copy of card 3. Now, we need to calculate the score for the amount of cards we have for the next and the score of every copy also counts towards the amount of consecutive cards we get.
This is really difficult to understand and the solution is everything but difficult.
let mut answer: Vec<i64> = vec![1; lines.len()];
for (index, line) in lines.iter().enumerate() {
// snip
for i in index + 1..index + count + 1 {
answer[i] += answer[index];
}
}
answer.iter().sum()The for loop is almost exactly the same, we've just added a small inner loop. What this loop does is keep track of how many cards we have in total. We start by creating a vec! that contains the value one over the length of all the cards. This can be done with the vec![1; num] syntax, where num is the amount of cards, or lines.len().
After calculating the win count, we iterate over the vector we've created from the card after the current card, till the amount of wins we've gotten. We add the value of the current card to the cards at that location, essentially creating the correct amount of duplicates for that card.
If that was a bit unclear, maybe this will make it a bit more clear. If we have a vector of 3 cards, which looks like [1, 1, 1] when initialized, because we start with one card each. Then card 1 has 2 wins, giving us an extra card 2 and 3. The iterator will go from the location of card 1 and add it to card 2 and 3, creating [1, 2, 2] as a vec. Next we have card 2, which has 1 win and gives us an extra card 3. The iterator will now take the value of card 2 (which is 2, because we have one copy) and add this to card 3. This means that our final vector will be [1, 2, 3]. By summing this, we get our total amount of cards!
This day was a lot of parsing and iterating, so if you want to check out the files, take a look in the repo. If you want to test the full solution with the test input, check out the playground.
Day five
Day five gives you a list of maps and seeds, which are used to map the seeds to certain locations.
Parsing
Parsing is done by splitting the file into blocks of maps. In my first iteration I created a separate Block struct, but that is unnecessary, as you can just nest the vectors.
The first part of the parsing just replaces unnecessary text and splits of the seeds by splitting once on the first newline. This works because the seeds are separated by a newline.
Next, we parse the seeds into a vector, which makes them easier to use. After this, the maps need to be separated into vectors. This is done in the following line:
let maps: Vec<Vec<&str>> = maps.split("\n\n").map(|m| m.lines().filter(|l| l != &"").collect()).collect();This line does a lot of things, so let's split it up. First, the remaining lines (without the seeds) are splitted at every newline. Because every map block is separated by the newline we end with the map blocks. This is done by the .split("\n\n"). Next we separate the map blocks by using the .map(|m| m.lines(). We still can have some empty lines though, so we use .filter(|l| l != &""). After this, we just plug some .collect() calls to collect them into a Vec<Vec<&str>.
After this, we just iterate over every block. Within the block we have separate lines, which we need to put into a Map struct. The struct looks as follows:
#[derive(Debug)]
struct Map {
source: i64,
destination: i64,
range: i64,
}It just gives names to every part of a single map line, so we can use them more easily in the program. After this we have nested iteration to map everything:
for block in maps {
let mut map = Vec::new();
for line in block {
let categories: Vec<i64> = line.split_whitespace().map(|n| n.parse().expect("Couldn't parse maps!")).collect();
map.push(Map {
source: categories[1],
destination: categories[0],
range: categories[2],
});
}
blocks.push(map);
}We iterate over every block, after which we separate every line to create a Map. All the map values are split at the whitespace and collected into a Vec<i64>. This Map gets pushed to a Vec, which gets pushed into a blocks vec after every block. This gives us a Vec<Vec<Map>>. We can iterate over the inside part of the blocks variable to get every map value.
Part one
For the first part, we need to find the lowest location number for the seeds given. After parsing the file in a bit of a simpler data structure, we can solve for part one.
We just create a vector for the positions, in which we can find the lowest number easily.
Now we iterate over every seed and apply all the necessary transforms. This is done easily with the following code block:
for mut seed in seeds {
for block in &blocks {
for map in block {
if (map.source..map.source + map.range).contains(&seed) {
seed = seed + (map.destination - map.source);
break;
}
}
}
positions.push(seed);
}We iterate over every seed and iterate over every block of maps within the seed. After that, we iterate over all the map lines to check if the seed falls within the source range.
We can find the next seed value by using the following equation: seed = seed + (map.destination - map.source). This is what we do if a seed falls within the source range of a map line. After this we break out of the block, because the seed can be counted within the same map block, but that can't be done due to the rules.
After we've done all these transformations, we push the final location to the positions vec. After we've iterated over every seed, we can use the following to find the smallest location.
let &answer = positions
.iter()
.min()
.expect("Couldn't find minimal value!");
This iterates over every position and finds the smallest value. This is finally returned.
Part two
For part two, it seems that the seeds are actually ranges of seeds. We need to find the smallest location again.
Because iterating over every range of seeds would be insane and take too much time, we need to find a different approach. The seeds we would need to iterate over would be many millions, but the smallest seed would probably be a few million.
This means we can iterate over the final location and just reverse search for the seed. To start with this, we need to get all the seed ranges and reverse the blocks to reverse search for the seed.
let ranges: Vec<&i64> = seeds.iter().skip(1).step_by(2).collect();
let seeds: Vec<&i64> = seeds.iter().step_by(2).collect();
let seeds: Vec<(&i64, &i64)> = seeds.into_iter().zip(ranges.into_iter()).collect();
let blocks: Vec<Vec<Map>> = blocks.into_iter().rev().collect();We first split the seeds into ranges and seeds. This is done by stepping every 2 items, so we get every odd item for the ranges. This is done with the .step_by(2) function. We do the same thing for the ranges, but skip the first item and get every even item for the seeds.
Next, we create a vector of tuples with Vec<(&i64, &i64)>. Within this, the first number is the seed and the second is the range. This is done by using .zip(). The item that's used as an argument, will be the second item in the tuple. After collecting this we have a vector of tuples.
After this, we iterate over every location from 0.
for i in 0.. {
let mut seed = i;
for block in &blocks {
for map in block {
if (map.destination..map.destination + map.range).contains(&seed) {
seed = &seed - (map.destination - map.source);
break;
}
}
}
for (source, range) in &seeds {
let range = *source..&(*source + *range - 1);
if range.contains(&&seed) {
return i;
}
}
}This starts by setting a seed by using i. After this, we iterate over all the blocks and reverse the equation used for converting from a seed to a location. This is done by using seed = &seed - (map.destination - map.source) when a destination range contains the seed. After this we still need to break, to prevent converting double.
After we've gotten the final seed, we need to check if it falls within the seed sources. This is done as follows:
for (source, range) in &seeds {
let range = *source..&(*source + *range - 1);
if range.contains(&&seed) {
return i;
}
}We create a range of numbers from the source to the source and the range added up. After this we can check if the range contains our found seed and if this is true, we return i. This function can run indefinitely, but because the program needs to find an answer, this isn't as bad.
Conclusion
The most difficult part of this day was definitely the second part. The algorithm I've used also isn't the most efficient, but finds the answer in 6 seconds which is relatively good.
Parsing was a bit of a challenge this day, but after simplifying it a bit, solving the parts became a lot easier. If you'd like to mess around with the code I made, take a look at the following code block:
fn main() { let input_file = "\ 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"; let answer_one = part_one(input_file); let answer_two = part_two(input_file); println!("Part one: {}\nPart two: {}", answer_one, answer_two); } #[derive(Debug)] struct Map { source: i64, destination: i64, range: i64, } fn part_one(input: &str) -> i64 { let (seeds, blocks) = parse(input); let mut positions: Vec<i64> = Vec::new(); for mut seed in seeds { for block in &blocks { for map in block { if (map.source..map.source + map.range).contains(&seed) { seed = seed + (map.destination - map.source); break; } } } positions.push(seed); } let &answer = positions .iter() .min() .expect("Couldn't find minimal value!"); answer } fn part_two(input: &str) -> i64 { let (seeds, blocks) = parse(input); let ranges: Vec<&i64> = seeds.iter().skip(1).step_by(2).collect(); let seeds: Vec<&i64> = seeds.iter().step_by(2).collect(); let seeds: Vec<(&i64, &i64)> = seeds.into_iter().zip(ranges.into_iter()).collect(); let blocks: Vec<Vec<Map>> = blocks.into_iter().rev().collect(); for i in 0.. { let mut seed = i; for block in &blocks { for map in block { if (map.destination..map.destination + map.range).contains(&seed) { seed = &seed - (map.destination - map.source); break; } } } for (source, range) in &seeds { let range = *source..&(*source + *range - 1); if range.contains(&&seed) { return i; } } } 0 } fn parse(file: &str) -> (Vec<i64>, Vec<Vec<Map>>) { // Replace all unnecessary text let file = file .replace("seeds: ", "") .replace("seed-to-soil map:", "") .replace("soil-to-fertilizer map:", "") .replace("fertilizer-to-water map:", "") .replace("water-to-light map:", "") .replace("light-to-temperature map:", "") .replace("temperature-to-humidity map:", "") .replace("humidity-to-location map:", ""); // Seeds are separated by a newline, so splitting there will give the seed line. let (seeds, maps) = file.split_once("\n\n").expect("Couldn't split seeds!"); // The seeds get parsed, after which all the map lines are collected. let seeds: Vec<i64> = seeds.split_whitespace().map(|n| n.parse().expect("Couldn't parse seed!")).collect(); let maps: Vec<Vec<&str>> = maps.split("\n\n").map(|m| m.lines().filter(|l| l != &"").collect()).collect(); let mut blocks: Vec<Vec<Map>> = Vec::new(); // For every block, we parse every map into a Map struct and push this to the blocks vec. for block in maps { let mut map = Vec::new(); for line in block { let categories: Vec<i64> = line.split_whitespace().map(|n| n.parse().expect("Couldn't parse maps!")).collect(); map.push(Map { source: categories[1], destination: categories[0], range: categories[2], }); } blocks.push(map); } (seeds, blocks) }
Day six
On day six we start racing with boats. This is done by pressing a button and releasing it, making the boat travel at a certain speed.
Parsing
Parsing was quite easy for this day. You just have two lines you need to parse. We start by getting the lines and parsing per line. We do this as follows:
let (_, times) = lines[0].split_once(": ").unwrap();
let (_, records) = lines[1].split_once(": ").unwrap();
let times: Vec<i64> = times.split_whitespace().map(|num| num.parse().expect("Couldn't parse times!")).collect();
let records: Vec<i64> = records.split_whitespace().map(|num| num.parse().expect("Couldn't parse records!")).collect();In this, we start by dropping the first part of the line, which is separated by a colon. After this, we end up with a string of numbers separated by spaces.
We do this for both lines and parse the numbers into a vec of i64. Finally, we create the races as a vec of tuples.
for (index, time) in times.iter().enumerate() {
races.push((*time, records[index]));
}This iterates over the times and keeps track of the index with .enumerate(). After that, we just push the time and the record at the same index as a tuple to the races vector.
Part one
For part one we need to multiply all the possibilities per race. The fastest way to calculate the possibilities to break the records is to go up to the first broken record and multiplying this by 2. We also need to add one because otherwise every answer will fall 1 short.
This full calculation is done in the following loop:
for (time, record) in races {
for press in 0..time {
let distance = (time - press) * press;
if distance > record {
let possibility = (time - press * 2) + 1;
answer *= possibility;
break;
}
}
}Here we check every time from 0 to the max time. After this we calculate the distance traveled with distance = (time - press) * press. We check if the distance traveled is larger than the record, and if that is so we calculate the possibilities with (time - press * 2) + 1. After that, we multiply our current answer with the amount of possibilities and break out of the loop.
Part two
The next part is mostly a parsing challenge. We need to combine all the time numbers and the record numbers for one big race.
We can do this by iterating over evry number, converting it to a string and pushing it to a single string. This is done in the following snippet:
let mut time: String = String::new();
let mut record: String = String::new();
for (times, records) in races {
time.push_str(×.to_string());
record.push_str(&records.to_string());
}After that, we parse the time and record and just use the same algorithm as in the first part.
Conclusion
Today wasn't a really difficult challenge. The algorithm I created where you stop the calculations once you break a record was about 60% faster than testing every possible outcome, so that was a nice optimization.
Parsing also wasn't that difficult, so all things considered it was a somewhat easy day. If you want to play around with the code from day 6, take a look at this code block:
fn main() { let input_file = "\ Time: 7 15 30 Distance: 9 40 200"; let answer_one = part_one(input_file); let answer_two = part_two(input_file); println!("Part one: {}\nPart two: {}", answer_one, answer_two); } fn part_one(input: &str) -> i64 { let races = parse(input); let mut answer = 1; for (time, record) in races { for press in 0..time { let distance = (time - press) * press; if distance > record { let possibility = (time - press * 2) + 1; answer *= possibility; break; } } } answer } fn part_two(input: &str) -> i64 { let races = parse(input); let mut time: String = String::new(); let mut record: String = String::new(); for (times, records) in races { time.push_str(×.to_string()); record.push_str(&records.to_string()); } let mut possibility = 0; let time: i64 = time.parse().expect("Couldn't parse time!"); let record: i64 = record.parse().expect("Couldn't parse time!"); for press in 0..time { let distance = (time - press) * press; if distance > record { possibility = (time - press * 2) + 1; break; } } possibility } fn parse(file: &str) -> Vec<(i64, i64)> { let lines: Vec<&str> = file.lines().collect(); let (_, times) = lines[0].split_once(": ").unwrap(); let (_, records) = lines[1].split_once(": ").unwrap(); let times: Vec<i64> = times.split_whitespace().map(|num| num.parse().expect("Couldn't parse times!")).collect(); let records: Vec<i64> = records.split_whitespace().map(|num| num.parse().expect("Couldn't parse records!")).collect(); let mut races: Vec<(i64, i64)> = vec![]; for (index, time) in times.iter().enumerate() { races.push((*time, records[index])); } races }
Day seven
On day 7 we try and implement a simplified poker analyzer.
Parsing
The parser for this day isn't that complicated. It has been implemented as the following:
let hands: Vec<(&str, &str)> = file.lines().map(|l| l.split_once(" ").expect("Couldn't split line!")).collect();
let mut games: Vec<Hand> = Vec::new();At first, we get all the lines and use .map() to apply some logic to every line. We split the lines at the space once, which separated the cards and the bids. This gives us a tuple, and by collecting this we end up with a vec of tuples.
Now we need to create cards. All the cards are made up of characters, but we can't sort them easily. Because of this we've created a cards enum with an implementation that enables us to sort the cards.
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
enum Card {
Joker,
Two,
Three,
Four,
Five,
Six,
Seven,
Eight,
Nine,
Ten,
Jack,
Queen,
King,
Ace,
}
impl Card {
fn from_char(card: char, joker: bool) -> Self {
match card {
'2' => Self::Two,
'3' => Self::Three,
'4' => Self::Four,
'5' => Self::Five,
'6' => Self::Six,
'7' => Self::Seven,
'8' => Self::Eight,
'9' => Self::Nine,
'T' => Self::Ten,
'J' => if joker { Self::Joker } else { Self::Jack },
'Q' => Self::Queen,
'K' => Self::King,
'A' => Self::Ace,
_ => panic!("That shouldn't be possible!")
}
}
}This matches all the characters and assigns the correct cards to it. It aso contains a joker boolean, which we'll use in part two.
To get all the data in a better format, we created a Hand struct with the cards, score and the bid. The score will help us determining the hand rank soon.
#[derive(Debug)]
struct Hand {
cards: Vec<Card>,
score: [i64; 2],
bid: i64,
}We parse all the data in the following function:
for (cards, bid) in hands {
let bid: i64 = bid.parse().expect("Couldn't parse bid!");
let cards: Vec<Card> = cards.chars().map(|c| Card::from_char(c, joker)).collect();
games.push(Hand {
cards,
score: [0, 0],
bid,
});
}
games
}For every hand, we parse the bid to an i64, all the cards get split into .chars() and gets parsed into a Card type. After this, we push the Hand struct to the games vec. We set the score to 0 to modify later.
Part one
In part one, we just need to build a simple poker parser.