summaryrefslogtreecommitdiff
path: root/2021/rust
diff options
context:
space:
mode:
Diffstat (limited to '2021/rust')
-rw-r--r--2021/rust/Cargo.toml2
-rw-r--r--2021/rust/day14/Cargo.toml10
-rw-r--r--2021/rust/day14/src/main.rs234
3 files changed, 245 insertions, 1 deletions
diff --git a/2021/rust/Cargo.toml b/2021/rust/Cargo.toml
index 8c18a33..068961e 100644
--- a/2021/rust/Cargo.toml
+++ b/2021/rust/Cargo.toml
@@ -13,7 +13,7 @@ members = [
"day11",
"day12",
"day13",
-# "day14",
+ "day14",
# "day15",
# "day16",
# "day17",
diff --git a/2021/rust/day14/Cargo.toml b/2021/rust/day14/Cargo.toml
new file mode 100644
index 0000000..ce7a90b
--- /dev/null
+++ b/2021/rust/day14/Cargo.toml
@@ -0,0 +1,10 @@
+[package]
+name = "day14"
+version = "0.1.0"
+authors = ["cos <cos>"]
+edition = "2021"
+
+[dependencies]
+aoc = { path = "../../../common/rust/aoc" }
+anyhow = "1.0"
+regex = "1.5"
diff --git a/2021/rust/day14/src/main.rs b/2021/rust/day14/src/main.rs
new file mode 100644
index 0000000..a3b1e40
--- /dev/null
+++ b/2021/rust/day14/src/main.rs
@@ -0,0 +1,234 @@
+use {
+ anyhow::{
+ anyhow,
+ Context,
+ Result,
+ },
+ regex::Regex,
+ std::{
+ collections::HashMap,
+ env::args,
+ fs::File,
+ io::{
+ BufRead,
+ BufReader,
+ },
+ path::Path,
+ },
+};
+
+#[derive(Debug)]
+struct InsertionRule {
+ pair: String,
+ element: String,
+}
+
+impl InsertionRule {
+ fn new(pair: &str, element: &str) -> Result<Self> {
+ Ok(Self{
+ pair: pair.into(),
+ element: element.into(),
+ })
+ }
+
+ fn new_apply(&self, input: &str) -> Result<String> {
+ let mut iter = input.chars().take(2);
+ let (left, right) = (
+ iter.next().ok_or_else(|| anyhow!("Failure on pair: {}", input))?,
+ iter.next().ok_or_else(|| anyhow!("Failure on pair: {}", input))?,
+ );
+ let mut output = format!("{}", left);
+
+ if input.starts_with(&self.pair) {
+ output += &format!("{}", self.element.chars().next()
+ .ok_or_else(|| anyhow!("Failure with element for: {}", input))?);
+ }
+ output += &format!("{}", right);
+ Ok(output)
+ }
+}
+
+#[derive(Debug)]
+struct Polymer {
+ inner: String,
+}
+
+type CharCount = HashMap<char, usize>;
+type CacheMap = HashMap<String, CharCount>;
+
+impl Polymer {
+ fn new(template: impl ToString) -> Self {
+ Self {
+ inner: template.to_string(),
+ }
+ }
+
+ fn len(&self) -> usize {
+ self.inner.len()
+ }
+
+ fn first(&self) -> Result<char> {
+ self.inner.chars().next().ok_or_else(|| anyhow!("Could not get first character"))
+ }
+
+ fn transform<'a, I>(&self, rules: I) -> Result<Self>
+ where I: Copy + IntoIterator<Item = &'a InsertionRule>
+ {
+ let first = if let Some(c) = self.inner.chars().next() {
+ c.to_string()
+ } else {
+ String::from("")
+ };
+ let inner = format!("{}{}", first,
+ self.inner.chars().zip(self.inner.chars().skip(1)).map(|(left, right)| {
+ let input = format!("{}{}", left, right);
+ for rule in rules {
+ let output = rule.new_apply(&input)?;
+ if input != output {
+ return Ok(output[1..].to_string());
+ }
+ }
+ Ok(input[1..].to_string())
+ }).collect::<Result<String>>()?);
+ Ok(Self {
+ inner
+ })
+ }
+
+ fn elements(&self) -> HashMap<char, usize> {
+ let mut elements = HashMap::new();
+
+ for c in self.inner.chars() {
+ let entry = elements.entry(c).or_insert(0);
+ *entry += 1;
+ }
+
+ elements
+ }
+
+ fn str_to_char_count(s: &str) -> HashMap<char, usize> {
+ let mut elements = HashMap::new();
+ for c in s.chars() {
+ let entry = elements.entry(c).or_insert(0);
+ *entry += 1;
+ }
+
+ elements
+ }
+
+ fn evaluate<'a, I>(&self, rules: I, depth: usize, skip_first: bool, cache: &mut CacheMap)
+ -> Result<CharCount>
+ where I: Copy + IntoIterator<Item = &'a InsertionRule>
+ {
+ if depth == 0 {
+ let interesting = if skip_first {
+ &self.inner[1..]
+ } else {
+ &self.inner
+ };
+ return Ok(Self::str_to_char_count(interesting));
+ }
+ let mut char_count = CharCount::new();
+ if !skip_first {
+ char_count.insert(self.first()?, 1);
+ }
+
+ for index in 0..=(self.len() - 2) {
+ let sub_key = self.inner[index..index+2].to_string();
+ let cache_key = &format!("{}-{}-{:?}", sub_key, depth, skip_first);
+ if let Some(cached) = cache.get(cache_key) {
+ for (key, value) in cached.iter() {
+ let entry = char_count.entry(*key).or_insert(0);
+ *entry += value;
+ }
+ } else {
+ let sub_polymer = Polymer::new(&sub_key);
+ let transformed = sub_polymer.transform(rules)?;
+
+ let polymer_chars = &transformed.evaluate(rules, depth - 1, true, cache)?;
+ cache.insert(cache_key.to_string(), polymer_chars.clone());
+ for (key, value) in polymer_chars.iter() {
+ let entry = char_count.entry(*key).or_insert(0);
+ *entry += value;
+ }
+ }
+ }
+ Ok(char_count)
+ }
+}
+
+fn read_input<T: AsRef<Path>>(filename: T) -> Result<(Polymer, Vec<InsertionRule>)> {
+ let reader = BufReader::new(File::open(filename)?);
+ let mut polymer = None;
+ let mut rules = vec![];
+
+ let re = Regex::new(r#"(?x)
+ ^(?P<template>[A-Z]+)$
+ |
+ ^(?P<pair>[A-Z]{2})\ ->\ (?P<element>[A-Z])$
+ "#).map_err(|err| anyhow!("Failed to compile regex: {}", err))?;
+
+ for row in reader.lines() {
+ let string = row?;
+ if string.is_empty() {
+ continue;
+ }
+
+ let caps = re.captures(&string).ok_or_else(|| anyhow!("Could not parse: {}", string))?;
+ match (caps.name("template"), caps.name("pair"), caps.name("element")) {
+ (Some(template), None, None) => polymer = Some(Polymer::new(template.as_str())),
+ (None, Some(pair), Some(element)) =>
+ rules.push(InsertionRule::new(pair.as_str(), element.as_str())?),
+ _ => return Err(anyhow!("Could not parse: {}", string)),
+ }
+ }
+
+ if let Some(p) = polymer {
+ Ok((p, rules))
+ } else {
+ Err(anyhow!("Missing polymer template in indata"))
+ }
+}
+
+fn part1<'a, I>(polymer: &Polymer, rules: I) -> Result<usize>
+ where I: Copy + IntoIterator<Item = &'a InsertionRule>
+{
+ let mut p = polymer;
+ let mut build;
+
+ for _ in 0..10 {
+ build = p.transform(rules)?;
+ p = &build;
+ }
+ let elements = p.elements();
+ let min = elements.values().min().ok_or_else(|| anyhow!("Could not find min"))?;
+ let max = elements.values().max().ok_or_else(|| anyhow!("Could not find max"))?;
+ Ok(max - min)
+}
+
+fn part2<'a, I>(polymer: &Polymer, rules: I) -> Result<usize>
+ where I: Copy + IntoIterator<Item = &'a InsertionRule>
+{
+ let mut cache = HashMap::new();
+ let elements = polymer.evaluate(rules, 40, false, &mut cache)?;
+
+ let min = elements.values().min().ok_or_else(|| anyhow!("Could not find min"))?;
+ let max = elements.values().max().ok_or_else(|| anyhow!("Could not find max"))?;
+ Ok(max - min)
+}
+
+fn main() -> Result<()> {
+ let ( do_part_1, do_part_2 ) = aoc::do_parts();
+
+ let filename = args().nth(1).ok_or(anyhow!("Missing input filename"))?;
+ let (polymer, rules) = read_input(filename).context("Could not read input")?;
+ if do_part_1 {
+ let solution = part1(&polymer, &rules).context("No solution for part 1")?;
+ println!("Part1, solution found to be: {}", solution);
+ }
+ if do_part_2 {
+ let solution = part2(&polymer, &rules).context("No solution for part 2")?;
+ println!("Part2, solution found to be: {}", solution);
+ }
+ Ok(())
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-22 12:46:54 +0000