4 ms·
I had considered this approach but the nature of AoC means it rewards real world time to solution rather than and kind of computation time, and a naive solution
by xnorswap 4y ago
I had considered this approach but the nature of AoC means it rewards real world time to solution rather than and kind of computation time, and a naive solution still runs fast enough that it more than makes up in time spent programming it.
There's actually whole classes of problems which would be more interesting if the naive solution wasn't fast enough, for example even on day 7 (or was it 8?) naively exploring to every edge from every square would be O(N^3) but still execute just fine.
I'm a couple of days behind but so far this year hasn't yet had lanternfish style problems where the naive solution blows up completely, but hopefully they will come as they are a lot more interesting.
- n4r9 4y agoArguably day 11 part 2 is such a "lanternfish" problem, although it essentially tells you to watch out for it.
- WJW 4y agoI definitely ran into that. I read "impractically large number" and thought "well the language I'm using has arbitrary size integers so I should be fine". So, I changed the code from 20 iterations to 10000 iterations and suddenly all 16 GB of my RAM was filled with Santa's worry counters.
- dmurray 4y agoWorse, I ported my solution to use BigInt and then found that was neither necessary nor sufficient.
- nraynaud 4y agoI love the Sunday quaterbacking of AoC, more than the competition itself (I'm not even doing this year). And I agree with you that a quick reminder that some problems are "naively intractable" is a good wake up call once in a while.
- ladberg 4y agoIf you aren't already familiar with it, you might find projecteuler.net fun!
- kadoban 4y agocodeforces.com or one of those is slightly more likely to be fun for programmers. projecteuler.net is great, but it _very_ quickly becomes deep math.