https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2024 day 19> (spoilers) :thread:
# advent-of-code
a
b
seems like last several days my code has worked for the sample but not my input
r
Today was nice and easy again 😄 Part 1 - plain old recursion with a .any() Part 2 - used sumOf, added memoization. Could easily test the algorithm on part 1 by changing the sumOf to a Count with > 0
👍 1
m
I was debugging my part 2 which worked on the example but not on the real input way too long before realizing the answer overflows an int... Classic 😄
b
i did the same thing, but i'm still getting wrong answer with long 😕
i'm doing the exact same thing as @Renette Ros, so i must have a bug somewhere
😢 1
r
@bj0 Do you get the right answer for part 1 when using the part 2 algorithm? Basically changing part 1 to this:
Copy code
return designs.count { possibleCount(patterns, it, mutableMapOf()) > 0 }
realizing the answer overflows an int...
Had this same issue. But my final answer was negative so I knew immediately 😄
b
odd, used my p2 algo on p1 and its off by 1
🤨 1
i mean its basically identical to yours so im very confused
😮 1
??
image.png
r
Yeah that looks pretty much the same... Did you run the sample input through this same code? I once had an issue where the sample input messed up my cache and it returned the wrong result 🤔
b
they're run in separate scopes
but i'll try anything at this point
😂 1
wow, that was it,
❤️ 1
same 1
j
A bit of caching and both parts are good, part 2 was a bit problematic, that I counted it as 1 solution if I found the whole rest pattern in my available patterns https://github.com/bulldog98/advent-of-code/blob/main/advent2024/src/main/kotlin/year2024/Day19.kt
b
ah, right, it's an object, it's properties persist between runs
👍 1
thats what i get for trying to code after coming home from the cocktail bar 😄
😅 1
r
My caches area always method params now 😂 Got burnt by this once, took me forever to debug. Never again 😄
➕ 1
b
good call
m
Part 2
j
P1 caching was actually a minor performance hit for me, since I was short-circuiting anyway, so there were almost only cache-misses 😁
But for P2 the DP was the way to go
m
Spent way to long on part 1 because I saw strings and taking the start so my immediate thought was: "I gotta do prefixmaps" (completely forgetting memoization) So anyways, here is my Day 19 with a prefixmap and memoization. It clocks in at a total of 3.3ms. Sadly that kind of optimization wasn't needed for today so I overengineered and wasted time...
Day 19 Michael.cpp
k
P1 was a breeze. I already guessed how P2 was gonna turn out, and I still somehow went blank when I saw it. Finally realized I was overthinking my recursion again. Cleaned up solution
e
Day19.kt I initially cheesed part 1 with regex which didn't help part 2 at all 😛
(you won't find the regex solution in my repo, it's literally me typing
Copy code
perl -E'chomp($_=<>);s/, /|/g;$re=qr/^(?:$_)*$/;$a+=/./&&/$re/ while chomp($_=<>);say$a'
at my terminal)
d
Another easy one… BFS with memoization. Took me a minute to see the need for memoization, then when it gave me the wrong answer for part A I printed my cache and saw it overflowed (good thing I made 
> 0
the new condition for A
For part 1 plain old BFS worked fine
Although given the branching factor I’m not really sure why that is (haven’t looked hard at the input)
OK for the most part they’re unable to find even a single prefix match with the towel set — seems intentionally designed to not require memoization for part A
e
Is there any hidden trick with the patterns and the designs? I'm doing the exact same recursive approach but for some reason there is a design which goes to an infinite loop
d
are you memoizing?
👆 1
👌 1
my very first pattern has 
124653528325
different ways to make it
a
managed both parts, now I wish I woke up on time for today
cleaning up code and struggling between (a) the clarity of these 3 lines
Copy code
if (newStrings.isEmpty())
    return false
return newStrings.any { it.isPossible() }
versus (b) the coolness of one
Copy code
return newStrings.isNotEmpty() && newStrings.any { it.isPossible() }
🙃
d
Ah I like the applying drop to the recursive input, it’s cleaner
p
A nice quick day - regex for part1, cached recursion for part2.
Day19.kt
pattern.removePrefix(it)
is clearer than 
pattern.drop(it.length)
K
👍 1
d
removePrefix does have the “if it doesn’t match you get the same string back” which could lead to infinite recursion if you weren’t checking the startsWith condition properly
also, make sure you don’t call unqualified 
return
inside 
getOrPut
… that’s burned me on more than one occasion
m
return@getOrPut
is your friend
d
“memoization why u no work”
a
I have tunnel-vision on regex today. used 
"^$it"
instead of 
startsWith(it)
lol
am I missing an add-to-cache opportunity on the line 
done.count() + todo.sumOf { it.possibleWays() }
?
Untitled.cpp
h
So, I'm guessing my naive iterative approach is not going to work on the input in a reasonable amount of time (although it works perfectly fine on the sample) due to the sheer number of combinations... and that something called "memoization" is required. Any good references on this topic?
d
this is a tie for “shortest solution” for me with days 1 and 2
h
Thank you kindly
d
(first link uses Python)
a
"memoization" is also known-as "caching" (except "caching" can have other related meanings or contexts. like caching content, images, web pages, etc.)
d
generally in Kotlin you can use a pattern like this to do memoization
h
Ahhh... so if I'm correct, the idea (in this context) is that I basically generate a lookup table of previous "designs" (partial designs), so I don't have to do it every time... the idea being that if I get a "design" (or partial design), that I've seen before, I don't have to try breaking it down all over again, I can basically just get the "count" of combinations that that particular partial design represents?
✅ 3
d
Copy code
val cache = mutableMapOf<CacheKey, U>()
fun myFun(args): U = cache.getOrPut(make CacheKey from args) {
  // fn logic
}
for a single arg fun it’s just
Copy code
val cache = mutableMapOf<T, U>()
fn myFun(arg: T): U = cache.getOrPut(arg) {
  // logic
}
for multi arg you have to wrap them in a data class or similar since 
getOrPut
takes one arg
j
definitily use a data class and make sure that all arguments have a proper equals implementation, otherwise the map cannot know that the key is the same
💯 1
h
Thanks... I better get reading... the clock is ticking!
d
for 2 args 
Pair
also works
j
It can’t be this simple right? Yes, yes it can be!
K 1
m
decided to remove my whole prefixmap thingy and cleaned up. Can't believe I missed this simple of a solution this morning
Day 19 Michael.cpp
🤯 1
j
Pretty much the same as my code. I considered implementing part2 when I implemented part 1, but I didn’t think part 2 would be so obvious. It was, so I had some copy-paste to do.
Copy code
data class Day19(val towelTypes: List<String>, val designs: List<String>) {
    private constructor(st: String, sd: String) : this(st.split(",").map { it.trim() }, sd.lines())
    private constructor(input: List<String>) : this(input[0], input[1])
    constructor(input: String) : this(input.paragraphs())

    fun part1(): Int = designs.count { hasArrangement(it, mutableMapOf("" to true)) }
    fun hasArrangement(design: String, memory: MutableMap<String, Boolean>): Boolean =
        memory.getOrPut(design) {
            towelTypes.filter { design.startsWith(it) }.any { hasArrangement(design.drop(it.length), memory) }
        }

    fun part2() = designs.sumOf { countArrangements(it, mutableMapOf("" to 1L)) }
    fun countArrangements(design: String, memory: MutableMap<String, Long>): Long =
        memory.getOrPut(design) {
            towelTypes.filter { design.startsWith(it) }.sumOf { countArrangements(design.drop(it.length), memory) }
        }
}
a
if anyone would like to see today's 🎄take a look at the memo (and the code-map/overview on the side, if your IDE has it)
n
My solution does not use any recursion, but instead has 2 nested loops: iterate over all the indices of a design, count how many towels could start at the index, and increase the number of counts for the index+towel.length by the count of the current index. Then the count[design.length+1] is the number of combinations (and thus answer for part 2).
🤯 1
m
This turned out nicely! Cannot think of a way to simplify the code any further 🙂 https://github.com/MikeEnRegalia/advent-of-code/blob/master/src/main/kotlin/aoc2024/day19.kt
👍 1
h
Ok, so I tried a basic "factorial" example with a cache... and that was working fine... the cache was being populated, and it correctly "shortcut" factorial(6), when factorial(5) had already been run. my AoC code, the cache was not getting populated. Then I realised, I wasn't supposed to be using "return count"... I was just supposed to say "count"... 🤦‍♂️
And then my Part 2, was magically solved in the blink of an eye... instead of "not before the heat death of the universe" 😁
💯 2
r
Screenshot 2024-12-19 at 2.24.05 PM.png
o
Back tracking + cache
d
Now I’m golfing, 12 LOC
👀 1
😲 1
initialize the cache, no need for a base case
a
@Dan Fingal-Surma minor nitpick for 
val (towels, patterns) = lines...
the top line of the input is towel patterns and the rest are designs but you used the top-line word for both parts 😛
🧠 1
d
I never learned how to read
🙃 1
Copy code
val (patterns, designs) = lines[0].split(", ") to lines.drop(2)
nailed it
K 1
🎉 2
j
About as short as I can get it:
Copy code
fun main() {
    val input = java.io.File("src/Day19.txt").readLines()
    input.drop(2).map { design ->
        design.indices.drop(1).map(design::take).fold(listOf(1L)) { sums, part ->
            sums + input[0].split(", ").filter(part::endsWith).sumOf { sums[sums.size - it.length] }
        }.last()
    }.run { println("${count { it > 0 }}\n${sum()}") }
}
m
Golfed part 1:
Copy code
fun main() {
    val lines = generateSequence(::readLine).toList()
    val cache = mutableMapOf("" to false)

    fun String.match(): Boolean = cache.getOrPut(this) {
        lines[0].split(", ").filter(::startsWith).any { equals(it) || removePrefix(it).match() }
    }

    println(lines.drop(2).count(String::match))
}
🙌 1
And golfed part 2:
Copy code
fun main() {
    val lines = generateSequence(::readLine).toList()
    val cache = mutableMapOf("" to 0L)

    fun String.countCombinations(): Long = cache.getOrPut(this) {
        lines[0].split(", ").filter(::startsWith).sumOf { if (this == it) 1 else removePrefix(it).countCombinations() }
    }

    println(lines.drop(2).sumOf(String::countCombinations))
}
... and golfed both parts combined:
Copy code
fun main() {
    val (towels, designs) = with(generateSequence(::readLine).toList()) { first().split(", ") to drop(2) }
    val cache = mutableMapOf("" to 0L)

    fun String.countCombinations(): Long = cache.getOrPut(this) {
        towels.filter(::startsWith).sumOf { if (this == it) 1 else removePrefix(it).countCombinations() }
    }

    with(designs.map(String::countCombinations)) { listOf(count { it > 0 }, sum()).forEach(::println) }
}
👍 1
p
20 Views
Open in Slack
PreviousNext
Powered by