<Advent of Code 2023 day 19> :thread:
# advent-of-code
a
j
Part 1 was pretty easy, part 2 I'm still developing an algorithm. I think the basic idea is to take accepting States and compute back to in which IntRanges allow these
Ok what I said was wrong the trick for part2 is to simulate from the full range and split them up. This is my code https://github.com/bulldog98/advent-of-code/blob/main/advent2023/src/main/kotlin/year2023/Day19.kt
m
Wow part 2 took me forever but was quite satisfying to solve.
same 2
m
It's day 5 all over again, I was team brute force back then... 🥲
j
@Max Thiele I thought about brute forcing, but decided it's easier to split ranges along the processing of the workflows
b
I am currently trying to split range through the workflows but i am not getting the right answer... this one is killer
j
@bj0 did you think about filtering out the ranges, that are in the rejected state, also some intersections between ranges should produce empty ranges
m
https://github.com/mdekaste/AdventOfCode2023/blob/master/src/main/kotlin/day19/Day19.kt (still cleaning up) The gist is that input is parsed to
Copy code
val workflows: Map<String, Map<Rule, Transition>>
    val parts: List<Map<String, Int>>
where Rule is sealed that is either
Copy code
data object Just : Rule
data class Check(variable, value, compare)
and Transition is sealed that is either
Copy code
data class Next(val input: String)
data class Accepted(val boolean: Boolean)
solving part 1 and 2 are both recursive functions
b
@Jonathan Kolberg i started with the full range of values, then recursively stepped through the rules applying the conditions to narrow them until i find an accept.
t
I also solved part 2 using range splitting - the solution turned out really nice 🙂 (I had to fix one off-by-one error, though)
And I just realized that the variable names
x
,
m
,
a
,
s
are an easter egg: Xmas 😄
🎄 3
e
https://github.com/ephemient/aoc2023/blob/main/kt/aoc2023-lib/src/commonMain/kotlin/com/github/ephemient/aoc2023/Day19.kt took a while to track down an off-by-one in my splitting but it was obvious once I found it
j
Pretty happy with my solution, although it’s the first one that’s over 100 lines of code. Had some small problems getting it right, but my testcases helped find the problem. https://github.com/JBeet/MyAdventOfCode2023/blob/main/src/aoc19/Day19.kt
j
@bj0 have you checked that your intersection logic is correct, I messed that up a few times until I got it right, was an off by one in the intersected ranges
plus1 1
b
im trying to clean it up so i can hopefully spot any errors
👍 1
j
I had an issue when multiple conditions in one workflow point to the same next workflow
m
Solved part2 after some more sleep. It's a bit lengthy but overall I'm quite happy with the solution: https://github.com/fabmax/aoc-2023/blob/main/src/main/kotlin/day19/Day19.kt
j
@ephemient I like the IntRange.size extension value, not sure why it's not in the standard lib, I did a
range.map { it }.size
which is way worse performance wise
b
i fixed all the problems i can find but im still too low, i guess i'll have to sleep on it
j
I have an
IntRange.length
as well, although
IntRange.count()
(which is
Iterable<T>.count()
and iterates all the values) would have been fast enough here.
b
ok i layed in bed for 15 minutes and realized what i was doing wrong
got it
my range splitting was fine, i was treating each accept as a distinct path and finding the max combos of each path, instead of OR(add)ing the results in a single workflow
basically all i had to do was change the final
maxOf
to a
sumOf
....
f
isn’t
jl{a>1466:R,s<2978:A,s<3574:A,A}
the same as
jl{a>1466:R,s<2978:A,A}
the same as
jl{a>1466:R,A}
or am i missing something?
j
@Fredrik Rødland Yes it is. But for me it wasn’t necessary to simplify the workflows, my solution was quick enough without it
👍 1
m
By the way, I did some brute-force tests and can squeeze 1.040G end-to-end part checks out of my CPU (16C/32T), so brute forcing this would only take about 2.9 Days: https://github.com/fabmax/aoc-2023/blob/main/src/main/kotlin/day19/Day19BruteForce.kt
👍 1
d
I always ended up high because of this bug (which resulted from a copy paste of part 1 where I had something similar, but with a
return
statement)
Copy code
if (rule.size == 1) {
  if (rule[0] == "A") {
    result += "A" to currentRanges
  }
  result += doWorkflowPart2(rule[0], currentRanges)
}
Which should be this 🤦‍♂️
Copy code
if (rule.size == 1) {
  if (rule[0] == "A") {
    result += "A" to currentRanges
  } else if (rule[0] != "R") {
    result += doWorkflowPart2(rule[0], currentRanges)
  }
}
Ah well… finally done: https://github.com/jpelgrim/adventofcode/blob/main/2023/aoc_2023_kotlin/src/day19/Day19.kt
r
a few off-by-one errors, combined with completely missing the line in the description saying that the values were in the range of 1-4000 led to some waste of time trying to solve part 2, but it works! Similar approach to the already mentioned one: using ranges and splitting them based on the workflow rules
p
Wow, I’m really proud of this 😊 https://github.com/PaulWoitaschek/AdventOfCode/blob/ffa4f4f2f45f6e5d0fa572e3da5266a5bf0f698a/2023/src/main/kotlin/aoc/year2023/Day19.kt Though I’m a little puzzled that it’s actually working ^^
m
So I took the brute force approach one step further and implemented it as a compute shader 😃 (still fully written in kotlin using kool!): https://github.com/fabmax/aoc-2023/blob/main/src/main/kotlin/day19/Day19Compute.kt I haven't run this completely through but it should complete in ~2 hours (on an RTX4080...)
😃 2
c
I'm not going to but how long would the brute force take for this one?
n
@Charles Flynn, @Max Thiele will tell us anon.
m
On my pretty powerful RTX4080 it would apparently take about 2 hours (it evaluates ~37G part combinations per second). That is under the assumption that the average evaluation time stays the same over the full value range. At least in the ranges I played around with that seems to be the case, however I only let it run for a couple of minutes to get a robust average time.
n
That was fun, if a bit fiddly. I wonder if I developed a flinch response from previous stack overflows and picked an overly convoluted architecture in order to avoid recursion. But I didn't get lost in my architecture. Just ~30 min of finding random bonehead bugs. https://github.com/nbanman/Play2022/blob/master/src/main/kotlin/org/gristle/adventOfCode/y2023/d19/Y2023D19.kt
@Max Thiele did it work?
m
This has been my favorite day so far. What do you think of my solution in terms of style and Kotlin idioms? https://github.com/MikeEnRegalia/advent-of-code/blob/master/src/main/kotlin/aoc2023/day19.kt
m
@Neil Banman I still haven't run the full range (don't wanna stress my electric bill and ears so much...). But I did a 10% run (x-range limited to 1 .. 400) and compared the result to my regular implementation and the number were identical (after fixing the inevitable off-by-one bug), so I'm confident that this actually does work 😅 Also switched over to Windows (usually I use Ubuntu), which gave another 25% perfoamnce boost: The 10% run finished in 568 seconds which would make ~1.5 hours for the full run.
👍 1
c
Involved getting up early but I eventually made it 🙂 Ended up being an off by one when adding the > ranges. What made it a lot easier to figure out was moving from using recursion to adding to a queue instead so I could see easier in the debugger what was happening.
m
^ I NEVER use a debugger. It’s so time-consuming. If my code does not work I’ll add debug outputs to figure out what is happening. Might seem unsophisticated, but it keeps the code cleaner (and the debug outputs can be useful even in production).
n
The IntelliJ debugger can be so helpful, especially when you don't know what to look for yet. Do you use a logger for debugging? I haven't gotten into it. I have a Boolean.println() extension function that lets me turn printing to console on and off with one global variable, but that's it.
e
sometimes real-world scenarios are challenging to get set up into the right state, and a debugger can be useful there… but I never use it for self-contained problems like this
it's so much more reproducible to just test the code directly
j
I also have to say, I seldomly use debugger, only to have a look what exactly goes wrong in a computation I tend to use it, but I always have a test, that tests my code with the example input
m
I just try to avoid stepping through the code … whenever I do I can’t help thinking of feeling the need to do it as a code smell, and usually refactoring the code solves the problem more efficiently (e.g. using a better approach gets rid of off-by-one errors). Agree with @ephemient, of course in some situations using a debugger is appropriate. I also sometimes use it in actual projects, but NEVER with AoC.
a
hi folks, straightforward solution with parsing the expressions and evaluating them ( either constant or ranges values). Ranges standard lib is surprisingly limited. Maybe there is a good third part open source library to deal with ranges (cutting and slicing, overlapping etc)? the code continues to be immutable data only but this time I used recursive functions just because that's how I'm conditioned by school when it comes to parsing/evaluationg expression trees. https://github.com/andriyo/advent-of-code-kotlin-2023/blob/main/src/Day19.kt