Hacker News Reader

For #14, some of us went a little nuts optimizing the dynamic programming solution down from months/OOM to milliseconds, and going past the original suggested problem size of a few hundred to a maximum problem size of 133 million: https://gwern.net/problem-14

View on HN

I clicked your link, saw DP, and tabbed away to try and solve it myself first. (I also forgot to sample without replacement and wound up with $2.86.)

Delightful read!

Pleased to hear that - I felt dumb when I made that mistake! But now I know I'm not alone.

is this a related problem to the how many times to flip a coin with a chance to increase your wealth by 50% ? https://www.jasoncollins.blog/posts/ergodicity-economics-a-p...

No because it's not a random walk. Cards in this problem are not put back in the deck after they are drawn, therefore the probability of going +1/-1 depends on how many cards of each color were drawn so far.

It's still markovian though, which means it's straightforward to find a solution (unless you want to go crazy with optimizations as OP suggests).

Reply on news.ycombinator.com