4 ms·

Solving the bowling problem with dynamic programming

48 points by signa11 2y ago

pxx 2y ago
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 2y ago
  was thinking about the same related problem. sounds awfully similar to https://leetcode.com/problems/burst-balloons/description/ https://leetcode.com/problems/burst-balloons/description/
  - pxx 2y ago
    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 2y ago
Another interesting variant of the problem is after each roll of the ball, the pins are reset to all be adjacent
sltkr 2y ago
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 2y ago
Also a good explanation and analysis on a similar problem is available from MIT https://youtu.be/r4-cftqTcdI https://youtu.be/r4-cftqTcdI

48 points by signa11 2y ago

pxx 2y ago

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 2y ago
was thinking about the same related problem. sounds awfully similar to https://leetcode.com/problems/burst-balloons/description/ https://leetcode.com/problems/burst-balloons/description/
- pxx 2y ago
  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 2y ago

Another interesting variant of the problem is after each roll of the ball, the pins are reset to all be adjacent

sltkr 2y ago

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 2y ago

Also a good explanation and analysis on a similar problem is available from MIT https://youtu.be/r4-cftqTcdI https://youtu.be/r4-cftqTcdI