Day 19 - Linen Layout
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
You are viewing a single thread.
View all comments 3 points
Rust
I figured that Part 2 would want something to do with unique paths, so I tried to generate all paths in Part 1, which took too long. So I then decided to go with dynamic programming. In Part 1, I stored a cache of whether a given state can lead to the solution. In Part 2, I updated it to store how many options are possible from a given state.
https://gitlab.com/bricka/advent-of-code-2024-rust/-/blob/main/src/days/day19.rs?ref_type=heads
The Code
use std::collections::HashMap;
use crate::solver::DaySolver;
fn parse_input(input: String) -> (Vec<String>, Vec<String>) {
let towels = input.lines().take(1).collect::<String>().split(", ").map(|s| s.to_string()).collect();
let designs = input.lines().skip(2).map(|s| s.to_string()).collect();
(towels, designs)
}
fn how_many_ways(cache: &mut HashMap<String, usize>, towels: &[String], current: String, target: &str) -> usize {
if let Some(ways) = cache.get(¤t) {
*ways
} else if current == target {
cache.insert(current.clone(), 1);
1
} else if !target.starts_with(¤t) {
cache.insert(current.clone(), 0);
0
} else {
let ways = towels.iter()
.map(|t| format!("{}{}", current, t))
.map(|next| how_many_ways(cache, towels, next, target))
.sum();
cache.insert(current, ways);
ways
}
}
pub struct Day19Solver;
impl DaySolver for Day19Solver {
fn part1(&self, input: String) -> String {
let (towels, designs) = parse_input(input);
designs.into_iter()
.filter(|d| how_many_ways(&mut HashMap::new(), &towels, "".to_string(), d) > 0)
.count()
.to_string()
}
fn part2(&self, input: String) -> String {
let (towels, designs) = parse_input(input);
designs.into_iter()
.map(|d| how_many_ways(&mut HashMap::new(), &towels, "".to_string(), &d))
.sum::<usize>()
.to_string()
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_part1() {
let input = include_str!("../../inputs/test/19");
let solver = Day19Solver {};
assert_eq!("6", solver.part1(input.to_string()));
}
#[test]
fn test_part2() {
let input = include_str!("../../inputs/test/19");
let solver = Day19Solver {};
assert_eq!("16", solver.part2(input.to_string()));
}
}
