search

jeremylt / advent2020

Advent of Code 2020
https://jeremylt.github.io/advent2020/
BSD 2-Clause "Simplified" License
7 stars 1 forks source link

Day 10 Part 2 #1

Closed Knight-Ops closed 3 years ago

Knight-Ops commented 3 years ago

I have been looking through some Day 10 part 2 solutions and yours struck me as extremely interesting. I understand how this specific solution works, but was looking for some more information on why it works, specifically if the approach/algorithm has a name for how it generally applies to variable path exploration instead of specifically Advent of Code.

Knight-Ops commented 3 years ago

After a bit more trolling through Reddit discussion and google. I have discovered this is a tabulation bottom-up dynamic programming approach compared to the memoziation approach of top-down recursive solutions. Feel free to drop any good references on the topic, but I will close the issue.

jeremylt commented 3 years ago

I don't actually have much formal training in Comp Sci, so the dynamic programming terminology is new to me. My experience is in high performance computing. We design our algorithms to pass through the data as few times as possible, as memory access can be a serious bottleneck, and this is the approach I took to this problem. I could solve the problem by walking through the data once in reverse instead of jumping around in the data many times with recursion, so that's the approach I took.

John McCalpin has some good talks on how memory bandwidth vs FLOPs are relevant to supercomputers: https://sites.utexas.edu/jdm4372/2016/11/22/sc16-invited-talk-memory-bandwidth-and-system-balance-in-hpc-systems/