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
6 points
Javascript
Behold an abomination!
const input = require('fs').readFileSync(0, 'utf-8').toString();
const towels = new Set(input.split(/\r?\n\r?\n/g)[0].split(', '));
const count = (p, t) => [...new Array(p.length).keys()].reduce((acc, i) => [...new Array(i + 1).keys()].forEach(j => acc[j] > 0n && t.has(p.substring(j, i + 1)) ? acc[i + 1] += acc[j] : null) ? acc : acc, [1n, ...new Array(p.length).fill(0n)])[p.length];
input.split(/\r?\n\r?\n/g)[1].split(/\r?\n/g).filter(p => p.length > 0).reduce((acc, p) => { let c = count(p, towels); acc[0] += c > 0 ? 1 : 0; acc[1] += c; return acc }, [0, 0n]).forEach((v, i) => console.log(`Part ${i+1}: ${v}`));
4 points
4 points
3 points
3 points
Haskell
solution
{-# LANGUAGE LambdaCase #-}
module Main where
import Control.Arrow
import Control.Monad.State
import Data.Char
import Data.List
import Data.Map qualified as M
import Data.Monoid
import Text.ParserCombinators.ReadP
parse = fst . last . readP_to_S ((,) <$> (patterns <* eol <* eol) <*> designs)
where
eol = char '\n'
patterns = sepBy word (string ", ")
designs = endBy word eol
word = munch1 isLetter
part1 patterns = length . filter (valid patterns)
part2 patterns = getSum . combinations patterns
dropPrefix = drop . length
valid :: [String] -> String -> Bool
valid patterns design = go design
where
go "" = True
go design = case filter (`isPrefixOf` design) patterns of
[] -> False
l -> any (go . (`dropPrefix` design)) l
combinations :: [String] -> [String] -> Sum Int
combinations patterns designs = evalState (fmap mconcat . mapM go $ designs) mempty
where
go "" = return $ Sum 1
go design =
gets (M.lookup design) >>= \case
Just c -> return c
Nothing -> case filter (`isPrefixOf` design) patterns of
[] -> return $ Sum 0
l -> do
res <- mconcat <$> mapM (go . (`dropPrefix` design)) l
modify (M.insert design res)
return res
main = getContents >>= print . (uncurry part1 &&& uncurry part2) . parse
2 points
C
Interestingly part 1 already defied a naive approach. It was fun thinking of a way to memoize without hash tables.
Code
#include "common.h"
static char *pats[480];
static int lens[480];
int np;
/* memoized for 's' by mem[off], 0 = unknown, >0 = value+1 */
static int64_t
recur(char *s, int off, int64_t *mem)
{
int64_t acc=0;
int i;
if (!s[off]) return 1;
if (mem[off]) return mem[off]-1;
for (i=0; i<np; i++)
if (!strncmp(s+off, pats[i], lens[i]))
acc += recur(s, off+lens[i], mem);
mem[off] = acc+1;
return acc;
}
int
main(int argc, char **argv)
{
static char patbuf[3200], design[64];
int64_t p1=0,p2=0, mem[64], n;
char *rest, *lf;
if (argc > 1)
DISCARD(freopen(argv[1], "r", stdin));
rest = fgets(patbuf, sizeof(patbuf), stdin);
for (; (pats[np] = strsep(&rest, ",")); np++) {
while (isspace(pats[np][0]))
pats[np]++; /* skip spaces */
if ((lf = strchr(pats[np], '\n')))
*lf = '\0'; /* trim trailing \n */
lens[np] = strlen(pats[np]);
assert(np+1 < (int)LEN(pats));
}
while (scanf(" %63s", design) == 1) {
memset(mem, 0, sizeof(mem));
n = recur(design, 0, mem);
p1 += n >0;
p2 += n;
}
printf("19: %"PRId64" %"PRId64"\n", p1, p2);
return 0;
}
https://codeberg.org/sjmulder/aoc/src/branch/master/2024/c/day19.c
Zee
Also a port to my cursed Dutch dialect of C, Zee:
Code
#ingesloten "zee.kop"
#ingesloten "algemeen.kop"
besloten letterverwijzing patronen[480];
besloten getal lengtes[480];
getal patroonsom;
besloten zeer groot getal
afdaling(
letterverwijzing tekst,
getal startpositie,
zeergrootgetalreeksverwijzing onthouden)
{
zeer groot getal deelsom=0;
getal sortering, teller;
tenzij (tekst[startpositie])
lever 1;
mits (onthouden[startpositie])
lever onthouden[startpositie]-1;
voor (teller=0; teller < patroonsom; teller++) {
sortering = tekstdeelvergelijking(
tekst + startpositie,
patronen[teller],
lengtes[teller]);
mits (sortering == 0) {
deelsom += afdaling(
tekst,
startpositie + lengtes[teller],
onthouden);
}
}
onthouden[startpositie] = deelsom+1;
lever deelsom;
}
getal
aanvang(
getal parametersom,
letterverwijzingsreeksverwijzing parameters)
{
blijvende letter patroonruimte[3200];
blijvende letter ontwerp[64];
zeer groot getal deel1=0, aantal;
zeer groot getal deel2=0, onthouden[64];
letterverwijzing rest;
letterverwijzing regeleinde;
mits (parametersom > 1)
VERWERP(heropen(parameters[1], "r", standaardinvoer));
rest = geefregel(patroonruimte, grootte(patroonruimte),
standaardinvoer);
voor (; ; patroonsom++) {
verzeker(patroonsom+1 < (getal)LENGTE(patronen));
patronen[patroonsom] = tekstsplitsing(naar rest, ",");
mits (patronen[patroonsom] == NIETS)
klaar;
zolang (iswitruimte(patronen[patroonsom][0]))
patronen[patroonsom]++;
mits ((regeleinde = zoekletter(patronen[patroonsom], '\n')))
volg regeleinde = '\0';
lengtes[patroonsom] = tekstlengte(patronen[patroonsom]);
}
zolang (invorm(" %63s", ontwerp) == 1) {
overschrijf(onthouden, 0, grootte(onthouden));
aantal = afdaling(ontwerp, 0, onthouden);
deel1 += aantal >0;
deel2 += aantal;
}
uitvorm("19: %"GEEFZGG" %"GEEFZGG"\n", deel1, deel2);
lever 0;
}
2 points
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
2 points
3 points
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.
2 points
*
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.
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()));
}
}
