4 votes

Day 19: Linen Layout

Automatically posted

Today's problem description: https://adventofcode.com/2024/day/19

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace python with any of the "short names" listed in this page of supported languages):

<details>
<summary>Part 1</summary>

```python
Your code here.
```

</details>

3 comments

  1. lily
    Link
    Still in the cooldown period, I see. Didn't mind the easier puzzle, though. The only "trick" to this was using memoization so it could finish in a reasonable time. Solution (Jai) /* Advent of Code...

    Still in the cooldown period, I see. Didn't mind the easier puzzle, though. The only "trick" to this was using memoization so it could finish in a reasonable time.

    Solution (Jai) 
    /* Advent of Code 2024
 * Day 19: Linen Layout
 */

#import "Basic";
#import "File";
#import "Hash_Table";
#import "String";

get_solution :: (
    design: string,
    towels: [] string,
    known_solutions: *Table(string, int)
) -> int {
    known_solution, success := table_find(known_solutions, design);
    if success {
        return known_solution;
    }

    solution := 0;
    for towels {
        if design == it {
            solution += 1;
        } else if begins_with(design, it) {
            solution += get_solution(
                slice(design, it.count, design.count - it.count),
                towels,
                known_solutions
            );
        }
    }

    table_add(known_solutions, design, solution);
    return solution;
}

main :: () {
    input, success := read_entire_file("inputs/day_19.txt");
    assert(success);

    lines := split(input, "\n");
    defer array_free(lines);

    towels := split(lines[0], ", ");
    defer array_free(towels);

    designs := array_view(lines, 2, lines.count - 3);

    // I didn't want this to be global, so I'm passing a pointer to it into the
    // get_solutions() procedure.
    known_solutions: Table(string, int);
    deinit(*known_solutions);

    possible_designs := 0;
    total_solutions := 0;

    for designs {
        solutions := get_solution(it, towels, *known_solutions);

        if solutions > 0 {
            possible_designs += 1;
        }

        total_solutions += solutions;
    }

    print("Part 1: %\nPart 2: %\n", possible_designs, total_solutions);
}
    2 votes
  2. scarecrw
    (edited )
    Link
    Hard to complain, but this felt far easier than previous day 19s. I think I might just be biased having done enough coding puzzles in the past that I've probably done something similar a half...

    Hard to complain, but this felt far easier than previous day 19s. I think I might just be biased having done enough coding puzzles in the past that I've probably done something similar a half dozen times.

    Nothing special about the solution, just recursively solving each string by testing all the prefixes, caching results for part 2.

    Smalltalk Solution 
    Class {
	#name : 'Day19Solver',
	#superclass : 'AoCSolver',
	#instVars : [ 'patterns', 'designs', 'cache' ],
	#category : 'AoCDay19',
	#package : 'AoCDay19'
}

Day19Solver >> canBuild: design [ 
	design ifEmpty: [ ^ true ].
	^ (patterns select: [ :pattern | design beginsWith: pattern ])
		  anySatisfy: [ :pattern | self canBuild: (design allButFirst: pattern size) ]
]

Day19Solver >> countBuilds: aString [
	| options ans |
	(cache includesKey: aString) ifTrue: [ ^ cache at: aString ].
	aString isEmpty ifTrue: [ ^ 1 ].
	options := patterns select: [ :pattern | aString beginsWith: pattern ].
	ans := (options collect: [ :option | self countBuilds: (design allButFirst: option size) ]) sumNumbers.
	cache at: aString put: ans.
	^ ans
]

Day19Solver >> initialize [
	cache := Dictionary new.
]

Day19Solver >> parseRawData [
	patterns := rawData lines first splitOn: ', '.
	designs := rawData lines allButFirst: 2.
]

Day19Solver >> solvePart1 [
	^ designs count: [ :design | self canBuild: design ]
]

Day19Solver >> solvePart2 [
	^ (designs collect: [ :design | self countBuilds: design ]) sum
]
    1 vote
  3. DataWraith
    Link
    Very nice and relaxing puzzle. Part 1 (Rust) pub fn part1(input: &PuzzleInput) -> String { possible_patterns(input).len().to_string() } pub fn possible_patterns(input: &PuzzleInput) ->...

    Very nice and relaxing puzzle.

    Part 1 (Rust) 
    pub fn part1(input: &PuzzleInput) -> String {
    possible_patterns(input).len().to_string()
}

pub fn possible_patterns(input: &PuzzleInput) -> HashSet<String> {
    let mut q = BTreeSet::new();
    let mut c = HashSet::new();

    for (i, design) in input.desired_designs.iter().enumerate() {
        q.insert((i, design.as_str()));
    }

    while let Some(design) = q.pop_first() {
        for pattern in input.patterns.iter() {
            if design.1.starts_with(pattern) {
                if design.1.len() == pattern.len() {
                    c.insert(input.desired_designs[design.0].clone());
                    q.retain(|d| d.0 != design.0);
                } else {
                    q.insert((design.0, &design.1[pattern.len()..]));
                }
            }
        }
    }

    c
}
    Part 2 (Rust) 
    pub fn part2(input: &PuzzleInput) -> String {
    let possible = possible_patterns(input);

    let mut c = 0;

    for design in possible.iter() {
        c += count_possibilities(input, design);
    }

    c.to_string()
}

pub fn count_possibilities(input: &PuzzleInput, design: &str) -> usize {
    let mut c = 0;

    let mut q = BTreeMap::new();
    q.insert(design, 1);

    while let Some((design, paths)) = q.pop_first() {
        if design.len() == 0 {
            c += paths;
            continue;
        }

        for pattern in input.patterns.iter() {
            if design.starts_with(pattern) {
                q.entry(&design[pattern.len()..])
                    .and_modify(|p| *p += paths)
                    .or_insert(paths);
            }
        }
    }

    c
}
    1 vote