The problem doesn't have a part 2. Completing the advent calendar
requires finishing all the others though. I'm missing day 23 part 2 and
the entirety of day 24.
Racket 8.3 had a performance regression that caused hashing pairs of
small numbers to take a long time. Using a vector made it substantially
faster (2 min -> 15 s).
See also [1] for upstream bug report.
[1] https://github.com/racket/racket/issues/4098
Slightly hacky solution, enabled by small input size:
- max number of recursions is arbitrary, found via testing
- bounds for x and minimal bound for y are analytic; max bound for y is
from testing
- p2.rkt: going left and up is allowed, so add these moves to graph.
This fixes our results
- p.py: correct implementation of p.rkt (that one is still broken)
- test4.txt: pre-expanded test input
Still incomplete! Results for part 2, via either p.rkt or p2.rkt, aren't
correct.
- p.rkt: solves part 1 and part 2 if fed the pre-expanded map
- p2.rkt: solves part 2 by expanding the map itself
- test1.txt and test3.txt are the sample inputs, first for part 1 and
then pre-expanded from part 2
- test2.txt is my puzzle input
This allows us to parse the input as a big integer instead of an array
of bits. The operations were few enough that the speed up is minimal,
but it's still nicer code.
Two solutions: p.rkt is the naive solution and works for part 1, but
fails hard at part 2. It was slow enough I couldn't even get to memory
exhaustion. p2.rkt uses a hash map for pairs and a hash map for
character count, both of which are updated for each iteration. This one
can probably deal with any reasonable number of iterations.
Execution time is now irrelevant.
Could probably be further simplified for just counting members when they
are present in hash table, but no need for it yet.
Érico Nogueira