<Advent of Code 2021 day 23> :thread:

# advent-of-code

[Advent of Code 2021 day 23]

Advent of Code 2021 day 23 🧵

[Dan Fingal-Surma]

Well now I get to implement A* search

[elizarov]

Djikstra (again) FTW

[elizarov]

It is quite puzzling that going from part1 to part2 does not considerably increase the number of reachable configurations in this problem. The movement rules are very constrained and there is no much freedom.

[elizarov]

How's everyone did part1 so fast, but have not done part2? What kind of solution for part1 is easy to write, yet does not scale to solve part2?

[David Whittaker]

@elizarov - doing it by hand

[David Whittaker]

I actually managed to do part 2 by hand on my mini-whiteboard but it was tricky tracking all of the moves

[elizarov]

https://www.reddit.com/r/adventofcode/comments/rmpc5i/2021_day_23_forget_artificial_intelligence/?utm_source=share&amp;utm_medium=web2x&amp;context=3

[Dan Fingal-Surma]

Not the most efficient representation, but gets the job done: https://github.com/dfings/advent-of-code/blob/main/src/2021/problem_23.main.kts

[Dan Fingal-Surma]

To get from part 1 to part 2 I had to generalize where I’d hard-coded that there were 2 slots per room

[Dan Fingal-Surma]

A* doesn’t end up being faster with the heuristic I came up with

[Dan Fingal-Surma]

With PQ
Part 1:

Runtime: 6637ms
States explored: 68782

Part 2:

Runtime: 7168ms
States explored: 83316

[Dan Fingal-Surma]

Without PQ
Part 1:

Runtime: 22419ms
States explored: 68781

Part 2:

Runtime: 29036ms
States explored: 83316

[Dan Fingal-Surma]

Unlike problem 15, the frontier gets big

[Dan Fingal-Surma]

Part 1, 12597, part 2, 15855

[Dan Fingal-Surma]

Anyway this reminds me of my CS 221 problem sets from a very long time ago

[Dan Fingal-Surma]

Using an (hashCode sort order) sorted list instead of a set to represent the state for dedupe purposes drops part 1 to 660ms and part 2 to 1398ms

[Dan Fingal-Surma]

Cleaned up a lot, down to 451ms for part 1 and 694ms for part 2

[nkiesel]

finally found time to work on this. My code is also reasonably fast: time ./gradlew clean cleanTest test --tests Day23 runs in about 1.1 seconds (solving both the sample and the actual puzzle). What is really strange though is that the very first run of the same code takes more than 6 minutes!!! Gradle keeps the JVM running, and thus the subsequent runs benefit from the JRE optimizations of the first run. But a speedup by a factor of of more than 300? Is that normal?

[ephemient]

finally got around to solving this one in Kotlin https://github.com/ephemient/aoc2021/blob/main/kt/src/commonMain/kotlin/com/github/ephemient/aoc2021/Day23.kt
hard-coded a ton more stuff than my Haskell solution, which makes it faster even without a heuristic

[ephemient]

tbh what I'm timing is more like

./gradlew installDist && time build/install/aoc2021/bin/aoc2021

so it's not being executed inside of gradle

[ephemient]

although if I compare

$ ./gradlew installDist && time build/install/aoc2021/bin/aoc2021
real	0m1.323s
user	0m2.832s
sys	0m0.199s

with

$ ./gradlew linkReleaseExecutableLinuxX64 && time build/bin/linuxX64/releaseExecutable/aoc2021.kexe
real	0m8.332s
user	0m8.315s
sys	0m0.016s

Kotlin/Native clearly has a long way to go. Kotlin/JS performance is even worse than that…