Advent of Code 2023 Day 5
Day 5: If You Give A Seed A Fertilizer
https://adventofcode.com/2023/day/5
The previous elf sent you to see a gardener elf that needs your help.
There is a problem with this year’s planting of seeds. Your input is a guide that tells you which seeds to plant.
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
An example input looks like this:
seeds: 79 14 55 13seed-to-soil map:50 98 252 50 48soil-to-fertilizer map:0 15 3737 52 239 0 15fertilizer-to-water map:49 53 80 11 4242 0 757 7 4water-to-light map:88 18 718 25 70light-to-temperature map:45 77 2381 45 1968 64 13temperature-to-humidity map:0 69 11 0 69humidity-to-location map:60 56 3756 93 4
The guide first lists which seeds should be planted.
What follows are a bunch of maps that tell you how to convert a number of a certain type to a number of a different type.
Instead of having one rule per number, the rule lines in a map apply to a range of numbers.
Each rule in a map has 3 numbers:
- The destination range start
- The source range start
- The range length
Consider again the example seed-to-soil map, it has 2 rules:
- 50 98 2
- 52 50 48
For the first rule, the three parts are:
- Destination range start: 50
- Source range start 98
- Range length 2
So that rule maps to:
- Destinations: 50, 51
- Sources: 98, 99
A source number that falls in the range, gets converted to a destination number with the same offset.
Applying that rule:
- Seed number 98 maps to soil number 50
- Seed number 99 maps to soil number 51
If a number has no rule that applies to it, it remains unchanged. So seed number 10 maps to soil number 10.
Part 1
The question asks what the lowest numbered location where a seed will be planted is.
To do this, we need to convert each seed number through every category until we end up with a 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.
Option 1: for loop
First up, parsing the input into useful data!
I want to end up with a list of seed numbers, and a list of maps.
Each map holds a list of rules.
To not confuse what’s a destination and what’s a source while coding, I created a Rule data type for this.
Now I can access a destination with rule.destination, and not rule[0] like I would have to do if I stored the rule in a list too (or was it rule[1]? I forget).
struct Rule {destination: i64,source: i64,range: i64,}
The order of the rule maps in the input is sequential, how considerate of the puzzle creator. This means I can ignore the headers of each map.
That order is:
- seed to soil
- soil to fertilizer
- fertilizer to water
- water to light
- light to temperature
- temperature to humidity
- humidity to location
let (seeds_str, maps_str) = input.split_once("\n\n").unwrap();let seeds = seeds_str.strip_prefix("seeds: ").unwrap();let seeds = seeds.split_whitespace().map(|s| s.parse::<i64>().unwrap());let mut maps = Vec::new();for block in maps_str.split("\n\n") {// ignore header of maplet (_, rules) = block.split_once("\n").unwrap();let mut map = Vec::new();for line in rules.lines() {let mut nums = line.splitn(3, " ");let destination: i64 = nums.next().unwrap().parse().unwrap();let source: i64 = nums.next().unwrap().parse().unwrap();let range: i64 = nums.next().unwrap().parse().unwrap();map.push(Rule {destination,source,range,});}maps.push(map);}
Next, the part where I calculate the location every seed is planted at.
I keep track of the minimum location and update it when a location is calculated.
some pseudocode:
let mut min = infinity;// map each seed to a locationfor seed in seeds {let mut curr = seed; // keep track of the current number, start it off as the seed number// apply every rule-map sequentially, first comes seed-to-soil, then soil-to-fertilizer, etc...for map in maps {if map_has_rule_that_applies {// apply rule, change the number in curr to the number it maps to}}// we applied all rule-maps, the number in curr is now the number of a location// update minimum locationmin = // minimum of min and curr}return min
Translated to valid Rust code:
let mut min = i64::MAX;for seed in seeds {let mut curr = seed;'maps: for map in &maps {for rule in map {let rule_applies = curr >= rule.source && curr <= rule.source + rule.range;if rule_applies {// map currlet offset = curr - rule.source;curr = rule.destination + offset;// a mapping was applied, on to the next map!continue 'maps;}// curr stays the same}}// once all maps are applied, the location is in currmin = min.min(curr);}min
Code
pub fn part_1(input: &str) -> i64 {let (seeds_str, maps_str) = input.split_once("\n\n").unwrap();let seeds = seeds_str.strip_prefix("seeds: ").unwrap();let seeds = seeds.split_whitespace().map(|s| s.parse::<i64>().unwrap());let mut maps = Vec::new();for block in maps_str.split("\n\n") {// ignore header of maplet (_, rules) = block.split_once("\n").unwrap();let mut map = Vec::new();for line in rules.lines() {let mut nums = line.splitn(3, " ");let destination: i64 = nums.next().unwrap().parse().unwrap();let source: i64 = nums.next().unwrap().parse().unwrap();let range: i64 = nums.next().unwrap().parse().unwrap();map.push(Rule {destination,source,range,});}maps.push(map);}let mut min = i64::MAX;for seed in seeds {let mut curr = seed;'maps: for map in &maps {for rule in map {let rule_applies = curr >= rule.source && curr <= rule.source + rule.range;if rule_applies {// map currlet offset = curr - rule.source;curr = rule.destination + offset;// a mapping was applied, on to the next map!continue 'maps;}// curr stays the same}}// once all maps are applied, the destination is in currmin = min.min(curr);}min}
Option 2: An iterator chain
The iterator chain has less “bookkeeping”, no more keeping track of a curr, and a min variable, the iterator adapters take care of that.
Code
pub fn part_1(input: &str) -> i64 {let (seeds_str, maps_str) = input.split_once("\n\n").unwrap();let seeds = seeds_str.strip_prefix("seeds: ").unwrap();let seeds = seeds.split_whitespace().map(|s| s.parse::<i64>().unwrap());let maps: Vec<Vec<Rule>> = maps_str.split("\n\n").map(|block| {block.lines().skip(1).map(|line| {let mut nums = line.splitn(3, " ");Rule {destination: nums.next().unwrap().parse().unwrap(),source: nums.next().unwrap().parse().unwrap(),range: nums.next().unwrap().parse().unwrap(),}}).collect()}).collect();seeds// map each seed to a location.map(|seed| {maps.iter().fold(seed, |curr, rules| {if let Some(rule) = rules.iter().find(|rule| curr >= rule.source && curr <= rule.source + rule.range){let offset = curr - rule.source;rule.destination + offset} else {curr}})}).min().unwrap()}
Part 2
Turns out we read the list of seeds wrong!
The “seeds:” line describes pairs of numbers.
- The first is the start of a range
- The second is the lengths of that range
For example: “seeds: 79 14 55 13”
Describes 2 ranges of seeds to be planted:
- Seeds numbered 79 to 92
- Seeds numbered 55 to 67
The question asks what the lowest numbered location where a seed will be planted is.
The brute-force approach would be to expand the list of seeds from part 1 to include all seeds. Then run the exact same logic as in part 1.
But that solution takes a long time to run, and takes a lot of memory to complete. I tried, but my computer was not beefy enough.
So instead of operating on single numbers, I operate on ranges of numbers in part 2.
A Range struct allows me to stay organized while I code and avoid accessing start and end numbers via an index:
#[derive(Debug, Clone)]struct Range {from: i64,to: i64,}
Code
pub fn part_2(input: &str) -> i64 {let (seeds_str, maps_str) = input.split_once("\n\n").unwrap();let seeds = seeds_str.strip_prefix("seeds: ").unwrap();let seeds = seeds.split_whitespace().map(|s| s.parse::<i64>().unwrap()).chunks(2);let seeds = seeds.into_iter().map(|mut chunk| {let from = chunk.next().unwrap();let range = chunk.next().unwrap();Range {from,to: from + range,}});let maps: Vec<Vec<Rule>> = maps_str.split("\n\n").map(|block| {block.lines().skip(1).map(|line| {let mut nums = line.splitn(3, " ");Rule {destination: nums.next().unwrap().parse().unwrap(),source: nums.next().unwrap().parse().unwrap(),range: nums.next().unwrap().parse().unwrap(),}}).sorted_by(|a, b| a.source.cmp(&b.source)).collect()}).collect();// for every range in the seed ranges, transform it to a range of the next kind, repeat until all all maps are applied, at that point all ranges are location ranges// loop1 transforms those ranges of seed to ranges of soils// loop2 transforms those ranges of soil to ranges of fertilizer// loop3 transforms those ranges of fertilizer to ranges of water// loop4 transforms those ranges of water to ranges of light// loop5 transforms those ranges of light to ranges of temperature// loop6 transforms those ranges of temperature to ranges of humidity// loop7 transforms those ranges of humidity to ranges of locationlet mut curr_ranges: Vec<Range> = seeds.collect();for map in &maps {let mut new_ranges: Vec<Range> = Vec::new();for range in &curr_ranges {let mut curr = range.clone();for rule in map {let offset = rule.destination - rule.source;let rule_applies = curr.from <= curr.to&& curr.from <= rule.source + rule.range&& curr.to >= rule.source;if rule_applies {if curr.from < rule.source {new_ranges.push(Range {from: curr.from,to: rule.source - 1,});curr.from = rule.source;if curr.to < rule.source + rule.range {new_ranges.push(Range {from: curr.from + offset,to: curr.to + offset,});curr.from = curr.to + 1;} else {new_ranges.push(Range {from: curr.from + offset,to: rule.source + rule.range - 1 + offset,});curr.from = rule.source + rule.range;}} else if curr.to < rule.source + rule.range {new_ranges.push(Range {from: curr.from + offset,to: curr.to + offset,});curr.from = curr.to + 1;} else {new_ranges.push(Range {from: curr.from + offset,to: rule.source + rule.range - 1 + offset,});curr.from = rule.source + rule.range;}}}if curr.from <= curr.to {new_ranges.push(curr);}}curr_ranges = new_ranges;}curr_ranges.iter().map(|range| range.from).min().unwrap()}
Final code
1use itertools::Itertools;23struct Rule {4 destination: i64,5 source: i64,6 range: i64,7}89#[derive(Debug, Clone)]10struct Range {11 from: i64,12 to: i64,13}1415pub fn part_1(input: &str) -> i64 {16 let (seeds_str, maps_str) = input.split_once("\n\n").unwrap();17 let seeds = seeds_str.strip_prefix("seeds: ").unwrap();18 let seeds = seeds.split_whitespace().map(|s| s.parse::<i64>().unwrap());1920 let maps: Vec<Vec<Rule>> = maps_str21 .split("\n\n")22 .map(|block| {23 block24 .lines()25 .skip(1)26 .map(|line| {27 let mut nums = line.splitn(3, " ");28 Rule {29 destination: nums.next().unwrap().parse().unwrap(),30 source: nums.next().unwrap().parse().unwrap(),31 range: nums.next().unwrap().parse().unwrap(),32 }33 })34 .collect()35 })36 .collect();3738 seeds39 .map(|seed| {40 maps.iter().fold(seed, |curr, rules| {41 if let Some(rule) = rules42 .iter()43 .find(|rule| curr >= rule.source && curr <= rule.source + rule.range)44 {45 let offset = curr - rule.source;46 rule.destination + offset47 } else {48 curr49 }50 })51 })52 .min()53 .unwrap()54}5556pub fn part_2(input: &str) -> i64 {57 let (seeds_str, maps_str) = input.split_once("\n\n").unwrap();58 let seeds = seeds_str.strip_prefix("seeds: ").unwrap();59 let seeds = seeds60 .split_whitespace()61 .map(|s| s.parse::<i64>().unwrap())62 .chunks(2);63 let seeds = seeds.into_iter().map(|mut chunk| {64 let from = chunk.next().unwrap();65 let range = chunk.next().unwrap();66 Range {67 from,68 to: from + range,69 }70 });7172 let maps: Vec<Vec<Rule>> = maps_str73 .split("\n\n")74 .map(|block| {75 block76 .lines()77 .skip(1)78 .map(|line| {79 let mut nums = line.splitn(3, " ");80 Rule {81 destination: nums.next().unwrap().parse().unwrap(),82 source: nums.next().unwrap().parse().unwrap(),83 range: nums.next().unwrap().parse().unwrap(),84 }85 })86 .sorted_by(|a, b| a.source.cmp(&b.source))87 .collect()88 })89 .collect();9091 // for every range in the seed ranges, transform it to a range of the next kind, repeat until all all maps are applied, at that point all ranges are location ranges92 // loop1 transforms those ranges of seed to ranges of soils93 // loop2 transforms those ranges of soil to ranges of fertilizer94 // loop3 transforms those ranges of fertilizer to ranges of water95 // loop4 transforms those ranges of water to ranges of light96 // loop5 transforms those ranges of light to ranges of temperature97 // loop6 transforms those ranges of temperature to ranges of humidity98 // loop7 transforms those ranges of humidity to ranges of location99 let mut curr_ranges: Vec<Range> = seeds.collect();100101 for map in &maps {102 let mut new_ranges: Vec<Range> = Vec::new();103104 for range in &curr_ranges {105 let mut curr = range.clone();106107 for rule in map {108 let offset = rule.destination - rule.source;109 let rule_applies = curr.from <= curr.to110 && curr.from <= rule.source + rule.range111 && curr.to >= rule.source;112113 if rule_applies {114 if curr.from < rule.source {115 new_ranges.push(Range {116 from: curr.from,117 to: rule.source - 1,118 });119 curr.from = rule.source;120 if curr.to < rule.source + rule.range {121 new_ranges.push(Range {122 from: curr.from + offset,123 to: curr.to + offset,124 });125 curr.from = curr.to + 1;126 } else {127 new_ranges.push(Range {128 from: curr.from + offset,129 to: rule.source + rule.range - 1 + offset,130 });131 curr.from = rule.source + rule.range;132 }133 } else if curr.to < rule.source + rule.range {134 new_ranges.push(Range {135 from: curr.from + offset,136 to: curr.to + offset,137 });138 curr.from = curr.to + 1;139 } else {140 new_ranges.push(Range {141 from: curr.from + offset,142 to: rule.source + rule.range - 1 + offset,143 });144 curr.from = rule.source + rule.range;145 }146 }147 }148 if curr.from <= curr.to {149 new_ranges.push(curr);150 }151 }152 curr_ranges = new_ranges;153 }154155 curr_ranges.iter().map(|range| range.from).min().unwrap()156}
Series navigation for: Advent of Code 2023