[HN Gopher] Solving the bowling problem with dynamic programming
       ___________________________________________________________________
        
       Solving the bowling problem with dynamic programming
        
       Author : signa11
       Score  : 39 points
       Date   : 2024-09-11 15:13 UTC (3 days ago)
        
 (HTM) web link (simonensemble.github.io)
 (TXT) w3m dump (simonensemble.github.io)
        
       | pxx wrote:
       | the listed dp strategy fails if you consider a related problem
       | where we collapse the list of pins every time we hit any so that
       | surviving pins remain adjacent to each other. in this modified
       | problem, you can get a score of 2 with [-1, 1, -1] by hitting the
       | center pin, then hitting both remaining pins, whereas in the
       | original problem you can only hit the center pin in the optimal
       | sequence.
       | 
       | a naive approach would involve looking at the 2**n set of "which
       | pins are remaining", but I think you can do this in quadratic
       | time with dp with the observation that you can only take r_{ij}
       | iff you knock down all the pins in between i and j, and that
       | necessarily precludes taking r_{kl} for i < k < j < l, so you can
       | do a sub-dp to find the optimal value of knocking down those in-
       | between pins.
       | 
       | can we do better than quadratic for this related problem? wait,
       | also, I think my solution only requires a linear scan in addition
       | to the recursive call but if we're not careful I think it quickly
       | becomes cubic.
        
         | tzudan wrote:
         | was thinking about the same related problem. sounds awfully
         | similar to https://leetcode.com/problems/burst-
         | balloons/description/
        
           | pxx wrote:
           | yeah, your linked problem is very similar but reward depends
           | on both left and right neighbor, and a variant of my solution
           | to the modified problem becomes cubic
        
       | tzudan wrote:
       | Another interesting variant of the problem is after each roll of
       | the ball, the pins are reset to all be adjacent
        
       | sltkr wrote:
       | This is a fairly standard dynamic programming problem. The
       | crucial insight is that if you take two pins with a single ball,
       | you split the problem into two independent subproblems, so the
       | core question is when to hit two pins at once.
       | 
       | This lends itself to a solution that doesn't use dictionaries or
       | even lists. To decide whether you want to: skip the current pin,
       | take the current pin alone, or take the current pin together with
       | the previous, you only need to keep track of the previous pin's
       | value, and the past two scores. For example, in Python:
       | values = [3, 4, -1, 6, -1, 6, 6, 3, -1, -1, 6, -2]
       | prev_val = prev_score = score = 0         for val in values:
       | prev_val, prev_score, score = val, score, max(score, score + val,
       | prev_score + val * prev_val)         print(score)  # 64
       | 
       | (This solution still has a list with the input values, but it is
       | only iterated over, so you could just as easily read those one-
       | by-one from an input file, for an O(1) memory solution.)
        
       | yohannesk wrote:
       | Also a good explanation and analysis on a similar problem is
       | available from MIT https://youtu.be/r4-cftqTcdI
        
       ___________________________________________________________________
       (page generated 2024-09-14 23:01 UTC)