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
Rust
First part is solved by making a regex of the available towels, like ^(r|wr|bg|bwu|rb|gb|br)*$ for the example. If a design matches it, then it can be made. This didn’t work for the second part, which is done using recursion and memoization instead. Again, it was quite surprising to see such a high solution number. 32 bits were not enough (thanks, debug mode overflow detection).
Solution
use regex::Regex;
use rustc_hash::FxHashMap;
fn parse(input: &str) -> (Vec<&str>, Vec<&str>) {
let (towels, designs) = input.split_once("\n\n").unwrap();
(towels.split(", ").collect(), designs.lines().collect())
}
fn part1(input: String) {
let (towels, designs) = parse(&input);
let pat = format!("^({})*$", towels.join("|"));
let re = Regex::new(&pat).unwrap();
let count = designs.iter().filter(|d| re.is_match(d)).count();
println!("{count}");
}
fn n_arrangements<'a>(
design: &'a str,
towels: &[&str],
cache: &mut FxHashMap<&'a str, u64>,
) -> u64 {
if design.is_empty() {
return 1;
}
if let Some(n) = cache.get(design) {
return *n;
}
let n = towels
.iter()
.filter(|t| design.starts_with(*t))
.map(|t| n_arrangements(&design[t.len()..], towels, cache))
.sum();
cache.insert(design, n);
n
}
fn part2(input: String) {
let (towels, designs) = parse(&input);
let sum: u64 = designs
.iter()
.map(|d| n_arrangements(d, &towels, &mut FxHashMap::default()))
.sum();
println!("{sum}");
}
util::aoc_main!();
Also on github
About 3ms. A manual implementation might be a bit faster, but not by much. The regex crate is quite optimized for pretty much these problems.
Wow, that is very fast, nice. I was happy with 120ms, seems I’m leaving a lot of performance on the table.
Edit: Regex cut my total time in half, but I am measuring the whole execution, still a massive improvement.
