I also went with a sparse map initally, but then converted to a dense fxvector to squeeze out more speed (part 2 went from about 95ms to 10ms).

https://github.com/Bogdanp/aoc2021/blob/master/day05.rkt

I almost initially went down the intersect road, but then figured the # of lines of real data would be large enough that the exponential nature would be killer w/o something like a quad tree

Just curious if your timing includes parsing time?

Mine takes ~70ms, but that includes parsing. And my re package (self-rolled) is definitely not as fast as cl-ppcre

No, it doesn’t include parsing time, but I just tested it and parsing’s under 1ms.

I’m using lists and values—200ms/400ms for part1/part2. (This is after starting with rebellion’s transducers and multisets—turns out they are really slow (6+s). You can see the optimization history in the commits: https://github.com/benknoble/advent2021/commits/main/day5)

Day 6 spoilers :thread:

This year really seems to be the year of sparse representations, huh. Or is there a math-y solution here?

(mine: https://github.com/Bogdanp/aoc2021/blob/master/day06.rkt)

Nice and clean!

Thanks!

Frustrated with todays. I spent quite a while wracking my brain, because I’m fairly confident this is a simple summation equation/population growth.

I spent time refreshing myself with https://en.wikipedia.org/wiki/Triangular_number, but at 1am, I don’t think I was going to make a breakthrough, and just went for memoization. :wink:

FWIW the definitions in racket/math are: (: triangle-number : Natural -> Natural) (define (triangle-number n) (quotient (* n (+ n 1)) 2)) (: triangle-number? : Natural -> Boolean) (define (triangle-number? n) (not (null? (quadratic-natural-solutions 1/2 1/2 (- n)))))