Advent of Code 2023 - Day 23
I placed 47th on part 1; 167th on part 2; still 5th overall.
Longest path in a graph is an NP-hard problem! I wasn't sure if there was some trick to get a provably fast algorithm, but it seems like the trick was just to compress the graph down (eliminating all those long hallways) so you could exhaustively search all paths. I spent way too long submitting partial answers from my slow solutions instead of just buckling down and coding that - which turned out to be not too bad to do.
I think part 1 is "longest path in a DAG", which actually does have an linear-time solution, but even my slow brute force was fast enough to solve it.
Problem: https://adventofcode.com/2023/day/23
Solution: https://github.com/jonathanpaulson/Ad...