or you could something simple.

yeah, I just did dynamic programming with a vector

Memoization is the cheater’s DP :stuck_out_tongue:

it is cheating :stuck_out_tongue:

can you do it in O(1) space now?

i did

I did something like that in JS, but not constant space.

Just no need. n ~ 100.

I saw on reddit, someone made an improved puzzle input that was much larger so people couldn’t cheat with memoization

I don’t know what you mean - that it’s so big that the memo would OOM?

i think the result was something like 40k digits long, and you just needed to find the last 10 digits

not necesarily that it would oom, but it would be very inefficient to use all that extra space

meh. Memoization’s not cheating in real life. It’s equivalent to DP.

true

but sometimes it’s just fun to compete for a more optimal solution

that’s all

sure

which is why my part 1 is overdone :slightly_smiling_face: There’s just no need for more than one pass, but the simple way is more concise.

more than one pass?

through the list

don’t you just sort the list then take the differences then count the ones and threes?

well, sort is one pass.

i suppose

but if you take the difference, that’s another pass through the list

and each count is another pass through the list.

They’re all linear (except I guess sorting). And it just doesn’t matter.

if you use count it is, but you can also count it while you do the subtractions

also, the sorting can be linear because you can use counting sort algo

actually, if you have a memoization macro, part 2 is basically a one-liner: (define/memo part2 (define (reachable? x) (< n x (+ n 4))) (max 1 (apply + (map part2 (filter reachable? input)))))

OMG I felt like an idiot. It wasn’t until I saw Peter Norvig’s solution that the lightbulb went off.

FYI - for everyone doing (map string->number (file->lines "input")) as I was, you can do (file->list "input") instead. Thanks to @samth for the idea.

I did not like this one :) I could sense there was an elegant solution that I wasn’t coming up with, so I just did memoization and called it a day :) I’ll have to take a look at the better solutions.

It seems like there is a mathematical solution that doesn’t require dynamic programming or memoization.

@racket192 is a Racket fan? That’s awesome :)

This <https://github.com/tckmn/polyaoc–2020/blob/master/10/jl/10.jl|Julia version> is pretty nice.

And a similarly elegant <https://github.com/tckmn/polyaoc–2020/blob/master/10/rb/10.rb|Ruby version> - I feel like a hack after viewing those!

I like (port->list read) but it’s not line delimited

port->list and read are what file->list is doing