19 ms·
Dynamic programming is not black magic
- siddbudd 3y agohttps://archive.vn/dynNQ https://archive.vn/dynNQ (qsantos does not load for me)
- tnecniv 3y agoI think that CS classes also teach it really poorly. I did not understand it at all until I took an optimal control class and it instantly made sense
- gbacon 3y agoI like Erik Demaine’s lectures on dynamic programming. https://youtu.be/r4-cftqTcdI https://youtu.be/r4-cftqTcdI https://youtu.be/KLBCUx1is2c https://youtu.be/KLBCUx1is2c https://youtu.be/OQ5jsbhAv_M https://youtu.be/OQ5jsbhAv_M
- ctk_25 3y agoWould recommend DPV Algorithms book and Georgia Techs lectures on udacity for graduate algorithms. The way to master dynamic programming is - practice practice practice solving problems…
- 62951413 3y agoConsider https://www.amazon.com/Dynamic-Programming-Coding-Interviews-Bottom-Up/dp/1946556696 https://www.amazon.com/Dynamic-Programming-Coding-Interviews... for the most pedagogical approach I have seen.
- _v7gu 3y agoThe name "Dynamic Programming" might seem out of place because it doesn't come from programming as a discipline. In this case, it actually refers to something like optimization, similar to linear programming. Dynamic programming is basically a method you can use to solve decision problems with discrete time, i.e picking the optimal sequence {a_t} in order to maximize \sum_t u_t(a_t) (plus constraints). The "dynamic programming" is defining a value function V* where V*(t) = max_{a_t}{ u_t(a_t) + V*(t-1) } which greatly reduces the dimensionality of the optimization problem.
- glimshe 3y agoMost of the time I hear the term being used by other people (not you :) ), I feel it's for showing off and look smarter than everybody else - "Look, I used dynamic programming to solve that problem", when in fact they were just employing what I'd consider the natural and intuitive approach for solving the problem. There was nothing they actually "used", besides happening to identify that the problem could be broken into progressively smaller subproblems.
- valval 3y agoWell aren’t you cynical.
- mk89 3y ago> happening to identify that the problem could be broken into progressively smaller subproblems. Which is what dynamic programming is about. And no, not everyone is capable to do that, especially since not all problems solved at work are Leetcode. Sometimes people really have to spend hours or days to understand how to split a problem. Only then optimizations can be applied or become "obvious". Like usual, solutions are "so obvious" when someone has done a lot of heavy lifting to simplify the problem, improve the context, etc.
- bcrosby95 3y agoDo you feel similarly if someone says they used an iterative, recursive, or greedy algorithm? Dynamic programming is a whole chapter in most algorithms books. It's not about showing off, it's the name of the technique.
- throwaway2037 3y agoAs I interpret the GP, the person is peacocking or gate-keeping by (humble)bragging about using dynamic programming to solve a problem. For all we know, they Googled for an efficient algorithm and copied the result. I have done it before, and I have no shame about it. If a teammate asks me how I knew about that dynamic programming algorithm, I would reply: "Are you joking? I could never program that myself. Thank you Google." Except for a few algorithms, most are solved using iterative or recursive.
- bombela 3y agoI really like how this article exposes the problem recursively first then progressively adds caching, and finally reduces the size of the cache to only what is necessary. I have often made the mistake of trying to get to the dynamic programming solution directly, and either got stuck or had to go through heroic efforts to get it working. I think from now on, I will force myself to go through the steps in order.
- qsantos 3y agoFrom my own experience, being taught dynamic programming straight way makes it more of a puzzle. By going through the steps and explaining _why_ we are using a table, and connecting the concept to caching, I feel like it makes much more sense.
- gligorot 3y agohttps://web.archive.org/web/20240114111200/https://qsantos.fr/2024/01/04/dynamic-programming-is-not-black-magic/ https://web.archive.org/web/20240114111200/https://qsantos.f... Since it got the hug of death
- sethammons 3y agoWould it be wrong to just think "memoization" when you hear "dynamic programming"? The missing part may be intelligently breaking up the problem to use memoization?
- ecshafer 3y agoYes it would be wrong in my book. First i think a obvious counter example of memoization can be used outside of dynamic programing. Otherwise you can do most dynamic programming algorithms with storing the results in a table, and searching the table afterwards for the best answer. Memoization is basically a strategy to speed up algorithms.
- sk11001 3y ago> First i think a obvious counter example of memoization can be used outside of dynamic programing This isn't relevant, the quesion is whether there are dynamic programming solutions which do not involve memoization.
- eru 3y agoWell, dynamic programming also tells you when you can drop your 'memoization' caches.
- JohnKemeny 3y agoThat's exactly how I teach dynamic programming. First solve it recursively, then add memoization (I call that top-down). Then notice that recursion and memoization has some overhead, and construct the table from bottom-up, remove the recursive call, and voila, dynamic programming.
- throwaway2037 3y agoThis sounds like a promising teaching technique. Do you have a slide deck to share? I am sure HN crowd would be interested to read.
- akoboldfrying 3y agoIt's good that the article points out that DP algorithms are "just" clever ways to cache a recursion. Looking for a recursive solution is certainly the best way to start out looking for a DP solution, in my experience -- if you can find one, memoising it is trivial and may give a big speedup (and may even be faster than a "bottom-up" DP, since it only ever computes solutions that we definitely need). With enough practice, it's usually possible to come up with a (correct but slow) recursive solution. When turning this into a DP, it doesn't matter if there are large numbers of subproblems in the call tree -- what's important is that there are a relatively small number of distinct subproblems. (Since there's no point caching a result that's only ever needed one time.) And that's where the difficulty tends to lie: Figuring out how to partition the original problem into few enough distinct subproblems.
- da39a3ee 3y agoThis is a widespread misconception: thinking of dynamic programming as just a form of memoized recursion is not the way to learn DP because it makes it extremely difficult to understand how to do the style of DP problems that involve filling out a 2D array. For example, look at the "best time to buy and sell stock" series on leetcode: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/ https://leetcode.com/problems/best-time-to-buy-and-sell-stoc.... These are much more naturally done by filling out an array, right? I've never done them with a recursion; I can't say I've thought hard about it -- is there a natural recursive solution? (I linked to iii above but for anyone who hasn't tried them they are a great intro to DP problems; start with the first one: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/ https://leetcode.com/problems/best-time-to-buy-and-sell-stoc...)
- deleted 3y ago[deleted]
- lifthrasiir 3y agoThe point is that you don't have to exactly fill the 2D array to solve the problem in that way. The 2D array is an optimization in this view, and can be safely replaced with a cache without breaking the correctness. Of course there is also some learned techniques specific to dynamic programming, and that makes it worthy to learn at some point because otherwise you will never think of them, but at its core dynamic programming is just a specific way of doing recursion.
- hit8run 3y agoCannot establish database connection… It probably is…
- ris58h 3y ago> Dynamic Programming is not Black Magic But who said otherwise?
- mikhailfranco 3y agoThe No True Scots Straw Man?
- croes 3y ago[flagged]
- alephnan 3y agoI was using Leetcode this week and realized how terrible the software is. The login flow was broken where it kept signing me out when I tried to click “subscribe to premium”. There was no way to give them money and I was stuck in a loop.
- eru 3y agoDynamic programming doesn't automatically mean you don't have any books, or that things will be fast.
- deaddodo 3y agoThey definitely need to install a caching plugin. Wordpress taking your site down, even on some subpar shared host, should be a thing of the past by now.
- qsantos 3y agoAbsolutely. I did not bother so far, since I was mostly writing for myself. But I should have before posting here; I know what the hug of death means!
- qsantos 3y agoSorry about that. It looks like the MySQL database did not like the sudden influx of traffic. It's back up!
- bob1029 3y agoIf you are seeking black magic, dynamic optimality might be more your speed.
- wiseowise 3y agoAwaiting “but you’ll never need it at your job” crowd.
- jmull 3y agoDo people use it much in their jobs? I can't remember ever actually using it other than for puzzle-solving (like the excellent Advent of Code problems). I guess it's pretty common to use leet-code type problems for interviews, which maybe counts, but even there hopefully most employers aren't clueless enough to give people DP problems. I've done some stuff around generating puzzles/levels/challenges for games that maybe could have used it, but it seemed like problems it might be useful for never came up for me... maybe because I found that you get better, funner puzzles and can control the difficulty better if the generator sort of "thinks like" a human solver/player would. No doubt there are some edge cases, but how much are people really using DP at a job?
- nottorp 3y agoYou don't use all them algorithms explicitly. When have you last done a sort? However if you know them, you have an intuitive understanding of what your libraries do and are less likely to end up on accidentally quadratic.
- rav 3y ago> And many common algorithms are actually just the application of dynamic programming to specific problems, including omnipresent path-finding algorithms such as Dijkstra’s algorithm. Dijkstra's algorithm is an application of dynamic programming? I disagree. In dynamic programming, you tabulate the subproblems to solve, with static interdependencies between them leading to straightforward orders in which to solve the subproblems. In Dijkstra's algorithm, you need to compute the shortest path from s to each vertex, but the order in which you have to visit the vertices is only discovered along the way using a priority queue, so the subproblem interdependencies are not known ahead of time until you have actually solved the problem.
- qsantos 3y agoI totally agree in that I use the same mental model. But, if you look at it as “the shortest path must be the shortest path through one of its neighbors”, it can actually be classified as a dynamic programming algorithm! https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Dynamic_programming_perspective https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Dynamic...
- rav 3y agoIn dynamic programming, the problem can be solved by solving subproblems, and those subproblems are solved by solving subsubproblems, and there is overlap between these subproblems. This allows us to solve DP problems in two ways, either by recursion with memoization or by iterative table filling. Although the shortest path problem has some kind of "optimal substructure", the recursive memoized approach doesn't work because there's no set order in which the subproblems can be solved. Instead, you need to compute the shortest paths in order of shortest path length, and the shortest path lengths aren't given ahead of time - those are exactly what Dijkstra's algorithm computes! It's not enough to call it dynamic programming that "the shortest path must be the shortest path through one of its neighbors", because this fact doesn't immediately lead to an acyclic subproblem dependency graph. Shortest path on an acyclic graph, and longest path on an acyclic graph, are two problems that can be solved with dynamic programming - but Dijkstra's algorithms solves shortest paths on a different class of graphs that doesn't lend itself to DP.
- charlieyu1 3y agoI don't find DP that difficult to be called Black Magic. Tree algorithms on the other hand, is much harder
- qsantos 3y agoDo you mean tree rebalancing algorithms? I have to agree with this. AVL tree insertion is fine enough, but it gets hairy when you get to deletion. And Red-Black trees…
- charlieyu1 3y agoThere are more than that, even finding diameter of a tree is pretty nasty
- qsantos 3y agoAh yes, but I use Rust, I cannot go back up a tree (-:
- KRAKRISMOTT 3y agoNo graphs either :(
- n2d4 3y agoOnly nasty to find diameter of general graphs, right? If you know you have a tree, just root it at a random vertex and recursively compute `max(largest diameter of children, sum of the two biggest heights of children)`
- peterfirefly 3y agoOnce you relax the invariants a bit, it becomes much easier to delete from your reddish-blackish trees :) If you don't have to implement deletion, things are already a lot easier. And if you decide to implement a persistent red-black tree then they can be downright easy, even without relaxed invariants. Relaxed invariants: https://en.wikipedia.org/wiki/AA_tree https://en.wikipedia.org/wiki/AA_tree https://en.wikipedia.org/wiki/Left-leaning_red%E2%80%93black_tree https://en.wikipedia.org/wiki/Left-leaning_red%E2%80%93black... --- Years ago, I played around with red-black trees and I figured that I could relax the invariants and make the code a lot simpler -- and maybe get slightly worse theoretical performance and quite likely slightly better practical performance for small trees. I looked around for other people's ideas along the same lines and found AA trees, which didn't quite please me. A few years later, Sedgewick's left-leaning red-black trees came out. I would probably have found them myself (+ some other related ideas) if I had continued to play around + systematically tried different relaxations. But I didn't, so I didn't.
- Der_Einzige 3y agoAll problems solved using DP can also be solved using global optimization techniques. A much easier one to implement in an interview than most DP solutions are simple genetic algorithms. Yes, DPs really do solve any silly interview problem and even have several advantages to boot (i.e. partial solutions if stopped before they're finished). Anyone interviewing you who won't give you a pass for solving the leetcode problem the "wrong way" without strong very strong justifications is a fool who themselves shouldn't be working in tech.
- qsantos 3y agoDid you encounter practical problems where genetic algorithms work well? So far, the only serious usage I did was for CodinGame's Mars Lander optimization problem (and it works pretty well there!).
- anon291 3y agoGenetic algorithms are not deterministic, whereas a DP solution is going to be deterministic with very easily calculable bounds on execution time. Comparing the two as you do, in my opinion, shows a fundamental gap in algorithms understanding.
- nottorp 3y agoBut they didn't say 'use LLMs... in Rust' :) Points for that.
- deleted 3y ago[deleted]
- hxypqr 3y agoMost of Dynamic programming is just a method of reducing computational complexity by changing the noun objects in first-order logic (or second-order logic, advanced version) to walk through the answers of unfinished tasks using completed tasks. Only in very few cases is it necessary to extract and match the completed parts from the unfinished objects in the above process, which often involves optimizing a function f(A,B). However, most of the time, this process is futile.
- marcodiego 3y agoI had a very good algorithms professor. He studied at UCLA. His classes about dynamic programming were superb. He started with a problem for which the naive solution was simple and had exponential complexity. Then he broke the problem into smaller problems and reduced the complexity to something polynomial. Then he applied memoisation and the complexity dropped to linear. I really would like to remember the problems he used.
- Horffupolde 3y ago1. *Fibonacci Sequence*: The classic example where the naive recursive solution has exponential complexity. By storing previously computed values (memoization), the complexity can be reduced to linear. 2. *Coin Change Problem*: Given different denominations of coins and a total amount, finding the number of ways to make the change. The naive approach is exponential, but dynamic programming reduces it to polynomial complexity. 3. *Knapsack Problem*: Particularly the 0/1 Knapsack problem, where items with given weights and values must be placed in a knapsack of a fixed capacity to maximize total value. The naive exponential solution can be optimized using dynamic programming. 4. *Matrix Chain Multiplication*: Determining the most efficient way to multiply a chain of matrices. The problem can be solved in exponential time using a naive approach but becomes much more efficient with dynamic programming. 5. *Longest Common Subsequence*: Finding the longest subsequence common to two sequences. A classic dynamic programming problem that can be solved in polynomial time. 6. *Longest Increasing Subsequence*: Finding the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. 7. *Shortest Path Problems*: Like the Floyd-Warshall algorithm for finding the shortest paths in a weighted graph with positive or negative edge weights. 8. *Edit Distance (Levenshtein Distance)*: Finding the minimum number of edits (insertions, deletions, substitutions) needed to change one word into another.
- JohnKemeny 3y agoI just want to add 9. Longest Path in DAGs: Find a longest path in a directed acyclic graph. 10. Weighted Independent Set on a Path: Given an array of integers, compute the maximum sum of numbers provided that you may not take two consecutive cells.
- dahart 3y ago> “Bootstrap” is an imaged expression to point to the absurdity and impossibility of a task This is an archaic definition that I didn’t know, and it’s fairly interesting. At the bottom of the opening section on the history of “bootstrap” is this comment: “Critics have observed that the phrase is used to portray unfair situations as far more meritocratic than they really are.[8][9][7] A 2009 study found that 77% of Americans believe that wealth is often the result of hard work.[10] Various studies have found that the main predictor of future wealth is not IQ or hard work, but initial wealth.[7][11]” Interesting (to me, anyway) because it used “meritocratic” which itself is a word that was coined with a somewhat different meaning than it has today. Meritocracy was originally used to point out that merit itself is an outcome of social advantages, not inherent skill. https://reagle.org/joseph/pelican/social/the-surprising-socialist-origins-of-meritocracy.html https://reagle.org/joseph/pelican/social/the-surprising-soci...
- wibblewobble125 3y agoAmusingly, merit’s other meaning is the verb “to be worthy.”
- Futurebot 3y agoI like the short forumlation to explain it: "Dynamic Programming is approximately recursion + memoization + guessing"
- coolThingsFirst 3y agoIt's black magic bcs ppl don't want to admit they don't understand recursion lol. Fibonacci has always been a bad example to teach recursion. That and towers of hanoi are the greatest failure in teaching CS
- zelphirkalt 3y agoWhy is Tower of Hanoi a bad example?
- flobosg 3y agoOne cool application of dynamic programming is the pairwise alignment of nucleotide/protein sequences: * https://en.wikipedia.org/wiki/Sequence_alignment https://en.wikipedia.org/wiki/Sequence_alignment * https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algor... * https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorit...
- gww 3y agoI would argue that these are some of the most important algorithms in bioinformatics/biology. They have a wide range of applications.
- RespectYourself 3y agoGood rant about BS terminology. He should've included "responsive" Web pages.
- thefaux 3y agoI don't understand why you would use memoization for fibonacci ever and hence its relevance for dynamic programming. It can be solved with a tail recursive function with three input parameters. Solution left to the reader as an exercise.
- peterfirefly 3y agoMemoization generalizes much better than accumulator parameters.
- TotoHorner 3y agoBecause it's a good example to teach dynamic programming?
- deleted 3y ago[deleted]
- qsantos 3y agoBut how to you systematically deduce the tail recursion version? I feel like, in this case, the recursivity in definition of Fibonacci and the recursivity in the tail recursion is just a coincidence, with the second just being a contrived way to write the loop you get after applying dynamic programming and trimming the table to only the last two elements.
- tmoertel 3y ago> But how to you systematically deduce the tail recursion version? Here's one way: https://gist.github.com/tmoertel/5798134 https://gist.github.com/tmoertel/5798134
- qsantos 3y agoThanks! If I understand correctly, you would use that method, while substituting tail recursion in place of the look. However, I feel there is a lot of magic in https://gist.github.com/tmoertel/5798134#file-gistfile1-py-L83-L86 https://gist.github.com/tmoertel/5798134#file-gistfile1-py-L....
- stevefan1999 3y agoDynamic programming is not a black magic, _proving it can be dynamically programmed and their correctness_ is. You need to use mathematical induction to formally proof it just like with greedy algorithms which are very counterintuitive (take for example, greedy coloring) when I learned them both in uni.
- thayne 3y agoAs a primarily self-taught programmer, when I was first looking for a job, after college if I had been asked on an interview to use dynamic programming I would have had no idea what that was. Thankfully that never happened to me. But I was familiar with the technique, and used it in multiple interviews.
- DonHopkins 3y agoEmacs's infamous "Ultra-hot screen management package" with its "Skull and Crossbones" warning was definitely black magic: https://news.ycombinator.com/item?id=33450034 https://news.ycombinator.com/item?id=33450034 >James Gosling's Emacs screen redisplay algorithm also used similar "dynamic programming techniques" to compute the minimal cost path through a cost matrix of string edit operations (the costs depended i.e. on the number of characters to draw, length of the escape codes to insert/delete lines/characters, padding for slow terminals, etc). https://en.wikipedia.org/wiki/Gosling_Emacs https://en.wikipedia.org/wiki/Gosling_Emacs A redisplay algorithm, by James Gosling (ACM SIGPLAN Notices, April 1981): https://donhopkins.com/home/documents/EmacsRedisplayAlgorithm.pdf https://donhopkins.com/home/documents/EmacsRedisplayAlgorith... https://donhopkins.com/home/archive/emacs/mw/display.c https://donhopkins.com/home/archive/emacs/mw/display.c https://donhopkins.com/home/archive/emacs/skull-and-crossbones.txt https://donhopkins.com/home/archive/emacs/skull-and-crossbon... /-------------\ / \ / \ / \ | XXXX XXXX | | XXXX XXXX | | XXX XXX | \ X / --\ XXX /-- | | XXX | | | | | | | I I I I I I I | | I I I I I I | \ / -- -- \-------/ XXX XXX XXXXX XXXXX XXXXXXXXX XXXXXXXXXX XXXXX XXXXX XXXXXXX XXXXX XXXXX XXXXXXXXX XXXXXXXXXX XXXXX XXXXX XXX XXX ************** * BEWARE!! * ************** All ye who enter here: Most of the code in this module is twisted beyond belief! Tread carefully. If you think you understand it, You Don't, So Look Again.
- toomanyrichies 3y agoOrigin of the name "dynamic programming", from its inventor, Richard Bellman: "I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes. An interesting question is, ‘Where did the name, dynamic programming, come from?’ The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word, research. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term, research, in his presence. You can imagine how he felt, then, about the term, mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word, ‘programming.’ I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying—I thought, let’s kill two birds with one stone. Let’s take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it’s impossible to use the word, dynamic, in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It’s impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities”. Source: https://alliance.seas.upenn.edu/~cis520/dynamic/2021/wiki/index.php?n=Notes.DP https://alliance.seas.upenn.edu/~cis520/dynamic/2021/wiki/in...
- dps 3y ago>This year’s Advent of Code has been brutal (compare the stats of 2023 with that of 2022, especially day 1 part 1 vs. day 1 part 2). I enjoyed completing AoC this year. While it was very clear that day 1 (esp. part 2) was significantly harder than previous years (I wrote about this among other things [0]), OP's claim seemed not obviously self evident when comparing _current_ 2022 stats to _current_ 2023 stats, as folks have had an additional full year to complete the 2022 puzzles. I grabbed the 2022 stats from Jan 14th 2023 [1] and, indeed, the difference is quite stark. Graphing the part two completion stats[2] for both years, there was a relatively similar starting cohort size on day 1, but 2023 looks clearly harder than 2022 up until day 15. As OP observes, the ratio[3] of folks completing pt1 but not going on to complete pt 2 is way higher for a lot of days in 2023 and suggests the day 5, 10, 12 and especially day 22 part 2s were particularly difficult. [0] https://blog.singleton.io/posts/2024-01-02-advent-of-code-2023/ https://blog.singleton.io/posts/2024-01-02-advent-of-code-20... [1] https://web.archive.org/web/20230114172513/https://adventofcode.com/2022/stats https://web.archive.org/web/20230114172513/https://adventofc... [2] https://blog.singleton.io/static/imgs-aoc23/completion.png https://blog.singleton.io/static/imgs-aoc23/completion.png [3] https://blog.singleton.io/static/imgs-aoc23/ratios.png https://blog.singleton.io/static/imgs-aoc23/ratios.png
- Kwpolska 3y agoEarly AoC was fun, you could get away without anything fancy until late in the game. Then it got harder, not fun, so I gave up and stopped touching it.
- qsantos 3y agoThanks for the details. To add to this discussion, I have a script to see the progression over the days. Looking at the last two columns, you can see how brutal 2023 was compared to 2022. Especially in the beginning. The first few days, most people keep playing, with a retention higher than 80% most days, and virtually everyone people solve both parts. In contrast, only 76% of people solved part 2 after solving part 1. And many people gave up on days 3 and 5. Interestingly, the last few days are not that much lower. And that can be explained by the fact that AoC 2023 is more recent than AoC 2022, like you said. My interpretation is that this group of people will get over all the challenges regardless of the difficulty (to an extent, of course), while many other people will give up when they realize it will take too much of their time. Stats for year 2022 of Advent of Code ------------------------------------- Day Both puzzles One puzzle Total Rel. puzzle 1/2 Rel. day before 1 280,838 15,047 295,885 95 % 100 % 2 232,752 12,403 245,155 95 % 83 % 3 200,016 11,392 211,408 95 % 86 % 4 184,435 3,734 188,169 98 % 92 % 5 157,392 3,116 160,508 98 % 85 % 6 155,921 1,602 157,523 99 % 99 % 7 113,241 2,592 115,833 98 % 73 % 8 107,224 7,659 114,883 93 % 95 % 9 82,414 11,449 93,863 88 % 77 % 10 85,075 5,511 90,586 94 % 103 % 11 68,838 9,258 78,096 88 % 81 % 12 59,253 1,061 60,314 98 % 86 % 13 51,512 1,220 52,732 98 % 87 % 14 49,051 991 50,042 98 % 95 % 15 39,677 5,773 45,450 87 % 81 % 16 23,298 5,650 28,948 80 % 59 % 17 21,525 6,237 27,762 78 % 92 % 18 25,420 4,927 30,347 84 % 118 % 19 17,516 928 18,444 95 % 69 % 20 22,141 1,003 23,144 96 % 126 % 21 23,022 3,060 26,082 88 % 104 % 22 15,393 5,083 20,476 75 % 67 % 23 18,531 254 18,785 99 % 120 % 24 16,419 252 16,671 98 % 89 % 25 13,192 7,473 20,665 64 % 80 % ~/src/advent-of-code% ./stats.py 2023 Stats for year 2023 of Advent of Code ------------------------------------- Day Both puzzles One puzzle Total Rel. puzzle 1/2 Rel. day before 1 230,737 73,941 304,678 76 % 100 % 2 196,352 9,256 205,608 95 % 85 % 3 130,406 19,913 150,319 87 % 66 % 4 130,271 17,691 147,962 88 % 100 % 5 80,255 31,029 111,284 72 % 62 % 6 103,358 1,918 105,276 98 % 129 % 7 81,905 7,308 89,213 92 % 79 % 8 74,034 14,707 88,741 83 % 90 % 9 76,438 1,229 77,667 98 % 103 % 10 48,313 17,054 65,367 74 % 63 % 11 57,339 2,386 59,725 96 % 119 % 12 30,985 14,440 45,425 68 % 54 % 13 38,217 5,223 43,440 88 % 123 % 14 36,500 7,457 43,957 83 % 96 % 15 40,881 4,156 45,037 91 % 112 % 16 35,347 1,023 36,370 97 % 86 % 17 24,014 1,097 25,111 96 % 68 % 18 24,799 4,937 29,736 83 % 103 % 19 22,525 7,197 29,722 76 % 91 % 20 18,287 4,398 22,685 81 % 81 % 21 14,311 10,149 24,460 59 % 78 % 22 15,830 988 16,818 94 % 111 % 23 14,562 2,964 17,526 83 % 92 % 24 11,864 4,918 16,782 71 % 81 % 25 10,522 3,048 13,570 78 % 89 %
- mgaunard 3y agomemoize is not "terrible academic vernacular"
- deely3 3y agoWhat bothers me a bit, is that in example where we trying to find Levenstein distance between two string are we 100% sure that calculated distance from end of string to the start will result in the same value as when we calculate distance from start to end?
- qsantos 3y agoThat's a very good question. I think the simplest approach to prove it would be to show that both computations yield the global minimum. Since there is only one global minimum, then they must be equal.
- mbwgh 3y agoI find it disappointing that the "coming up with a recurrence formula" part is always glanced over, which to me is very much the hard part.
- qsantos 3y agoI understand! I do not think there is a magic formula for this. This only comes with a lot of practice.
- tromp 3y agoDynamic programming is what allowed me to compute the number of legal Go positions [1,2], a 171 digit number. While the naive method would take time 3^n^2 to examine all possible positions on an nxn board, dynamic programming effectively strips away one dimension, reducing time to O(n^5 * 5.4^n), while using space O(n * 5.4^n). [1] https://tromp.github.io/go/legal.html https://tromp.github.io/go/legal.html [2] https://tromp.github.io/go/gostate.pdf https://tromp.github.io/go/gostate.pdf
- qsantos 3y agoInteresting, I have never really looked into this kind of calculation. Thanks for the links!
- AtNightWeCode 3y agoAny benchmarks for implementing caching in fib in a lang with a good compiler? A long time ago I worked on a mathlib in C/C++ and when reviewing the assembler output it often did some really clever things.
- ram_rar 3y agoI wonder how much mechanical sympathy the Dynamic programming (DP) has as opposed to brute force or other simpler techniques. On paper it seems like a smart technique, in reality, I have rarely seen that being used in critical production systems. In fact, anything recursion-esque is eschewed. Can someone comment on their experience in implementing DP in critical production systems or beyond the scope of programming contest, academia.
- venil 3y agoIn general, it has great mechanical sympathy. You need to split your larger problem into smaller sub-problems, and then figure out which sub-problems depend on each other using the recursive formulation. Once you have done that, there should be no more need to have a stack, so you can just use an array to store the results of the depended on problems, and a loop to change which problem is being solved. This article doesn't make the final step from recursion to loop but you would probably want to if you were doing DP in production. Edit: Actually the article does make this jump. See the last code snippet before the conclusions section. Note also the second note after the snippet, which explains that the snippet itself uses a larger array than is necessary.
- neveroddoreven 3y agoReminds me of how the mathematician behind DP, Richard Bellman, purposely chose the name "Dynamic Programming" because it sounded impressive and non-mathematical so that he'd be more likely to get government funding.