diff options
author | Jesse Luehrs <doy@tozt.net> | 2020-12-09 00:16:34 -0500 |
---|---|---|
committer | Jesse Luehrs <doy@tozt.net> | 2020-12-09 00:16:34 -0500 |
commit | 4c943e636ec4720a4d5e54317ac5da5e52143d12 (patch) | |
tree | 1ab069a67de3bdc216b6b56d4586d665551bf543 /src/2020 | |
parent | 340c586e323d3c8838c0e5fd53870a4d07350c75 (diff) | |
download | advent-of-code-4c943e636ec4720a4d5e54317ac5da5e52143d12.tar.gz advent-of-code-4c943e636ec4720a4d5e54317ac5da5e52143d12.zip |
day 7
Diffstat (limited to 'src/2020')
-rw-r--r-- | src/2020/7/mod.rs | 101 | ||||
-rw-r--r-- | src/2020/mod.rs | 4 |
2 files changed, 105 insertions, 0 deletions
diff --git a/src/2020/7/mod.rs b/src/2020/7/mod.rs new file mode 100644 index 0000000..2bd8bea --- /dev/null +++ b/src/2020/7/mod.rs @@ -0,0 +1,101 @@ +use anyhow::Context as _; + +type Graph = std::collections::HashMap<String, Vec<(i64, String)>>; + +pub fn part1() -> anyhow::Result<i64> { + let input = crate::util::read_file_str("data/7.txt")?; + let graph = parse(&input)?; + let mut colors = 0; + for color in graph.keys() { + if bag_contains(&graph, &color, "shiny gold")? { + colors += 1; + } + } + Ok(colors) +} + +pub fn part2() -> anyhow::Result<i64> { + let input = crate::util::read_file_str("data/7.txt")?; + let graph = parse(&input)?; + // subtract 1 to not count the shiny gold bag itself + count_bags(&graph, "shiny gold").map(|i| i - 1) +} + +fn parse(input: &str) -> anyhow::Result<Graph> { + let mut graph = Graph::new(); + for line in input.lines() { + let (k, v) = parse_line(line)?; + graph.insert(k, v); + } + Ok(graph) +} + +fn parse_line(line: &str) -> anyhow::Result<(String, Vec<(i64, String)>)> { + let main_rx = regex::Regex::new(r"^(.*) bags contain (.*)\.$").unwrap(); + let contents_rx = regex::Regex::new(r"^([0-9]+) (.*) bags?").unwrap(); + + let captures = main_rx + .captures(line) + .context("line failed to match regex")?; + let color = captures.get(1).unwrap().as_str(); + let contents = captures.get(2).unwrap().as_str(); + if contents == "no other bags" { + Ok((color.to_string(), vec![])) + } else { + Ok(( + color.to_string(), + contents + .split(", ") + .map(|s| { + let captures = contents_rx + .captures(s) + .context("line failed to match regex")?; + Ok(( + captures + .get(1) + .unwrap() + .as_str() + .parse() + .context("invalid number of bags")?, + captures.get(2).unwrap().as_str().to_string(), + )) + }) + .collect::<anyhow::Result<_>>()?, + )) + } +} + +fn bag_contains( + graph: &Graph, + start: &str, + target: &str, +) -> anyhow::Result<bool> { + let mut to_check = graph + .get(&start.to_string()) + .context("failed to find starting color in graph")? + .clone(); + while let Some((_, next)) = to_check.pop() { + if next == target { + return Ok(true); + } + to_check.extend( + graph + .get(&next) + .context("failed to find next color in graph")? + .iter() + .cloned(), + ); + } + Ok(false) +} + +fn count_bags(graph: &Graph, color: &str) -> anyhow::Result<i64> { + Ok(1 + graph + .get(&color.to_string()) + .context("failed to find starting color in graph")? + .iter() + .map(|(count, child)| Ok(count * count_bags(graph, child)?)) + .collect::<anyhow::Result<Vec<_>>>()? + .iter() + .sum::<i64>()) +} diff --git a/src/2020/mod.rs b/src/2020/mod.rs index 47f5150..165d2ab 100644 --- a/src/2020/mod.rs +++ b/src/2020/mod.rs @@ -10,6 +10,8 @@ mod day4; mod day5; #[path = "6/mod.rs"] mod day6; +#[path = "7/mod.rs"] +mod day7; pub fn run(day: u8, puzzle: u8) -> anyhow::Result<i64> { match (day, puzzle) { @@ -25,6 +27,8 @@ pub fn run(day: u8, puzzle: u8) -> anyhow::Result<i64> { (5, 2) => day5::part2(), (6, 1) => day6::part1(), (6, 2) => day6::part2(), + (7, 1) => day7::part1(), + (7, 2) => day7::part2(), _ => Err(anyhow::anyhow!("unknown puzzle {}-{}", day, puzzle)), } } |