I seem to have solved it a bit differently. And when I finally did, yeah, there was mathematical solution: turns out that the number of paths for subsequences corresponded to something called the tribonacci sequence.
@jonathanhwchan has joined the channel
Nice write up!
@jlw has joined the channel
Adding -O3 to gcc dropped the C version from 0.59 to 0.47 seconds.
And a bit of tweaking to Julia dropped from 0.43 to 0.41 seconds.
Really interesting puzzle; I solved it in terms of reducing equations of the form field number in {set of fields}. link (SML, not racket, but the general algorithm should be visible): https://github.com/benknoble/advent2020/blob/574f858b72a03e28440b6da469865ac962e76471/day16/solution.sml#L98
@me1890 as others have said, helper functions can be good. I also get a lot of mileage out of (require threading). I know the “Racket way” is to prefer define over let, but I greatly prefer let personally. I haven’t looked at your solution closely enough to know how similar mine is, but for reference I think <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2020/day16.rkt|I managed rightward-drift nicely> w/o resorting to defines. I purposely sacrificed readability/testability for conciseness today, so I kind of did the opposite of good practice - I collapsed variables that were only used once, and didn’t use as many helpers as I normally would, so certainly not a good example of style :)
@haskal I’ll have to look over your solution in more detail later - looks interesting! The graph module has popped up a few times for AoC, and I’m not at all familiar with it, so I should probably rectify that.
raco pkg install graph is using quite a bit of CPU!
@haskal are you using the graph module on Racket CS or Racket BC?
BC, i don’t trust CS enough yet especially after that hash bug
I can understand that. I only installed CS the other day, but I should probably be testing on it more to make sure my apps don’t have any issues.
@haskal what prompted you to consider maximum-bipartite-matching? When I was looking at the puzzle “graph algorithm” didn’t really jump out for me.
@haskal can’t you use for/list instead of for*/list on line 24? The only reason I mention it is I got confused following the code using the for* semantics - I think you can just scan through idx and cand-note in parallel vs. the cartesian product.
Just in case anyone else is curious about @haskal’s solution, here’s the code for the sample data: #lang racket
(require graph)
(define g (undirected-graph '((2 class) (3 class) (1 row) (2 row) (3 row) (3 seat))))
(maximum-bipartite-matching g)
;; => '((1 row) (2 class) (3 seat)) The edges are pairs of (list index field) where all nearby tickets have a value at that index that’s valid for the field. Very cool solution :)
That might be the best thing I learned via AoC thus far. I can see applications for this.
After browsing through some of my algorithms books, I can see it’s well suited for this - matching two disjoint sets e.g. fields w/ field values, jobs w/ applicants, etc.
Never mind about my for*/list vs. for/list comment above. I misunderstood the code.
@badkins on for*: yeah it necessary because i compare every rule to every index to generate the list of valid combinations (the edges)
what prompted me to consider this: my original solution was the i think common one where you iteratively pick one index which only has one candidate rule, remove that rule from every other index where it’s a candidate, and do that again until it’s 1:1. which took a lot of code and is a pretty basic algorithm. i kind of realized this is actually a matching problem after submitting the solution using that version, and rewrote it with matching. bipartite matching is obviously useful for many situations where you have to pair up one set of things with another set of things, and it’s still kind of fresh in my mind from my undergrad algo class, even though that was a few semesters ago now