Discussion on Bowling Pins Challenge

8 years ago+ 3 comments

I'd say this problem is both Recursion and Game Theory, and I get why it might be placed in either category but I'd say it's more Game Theory than recursion. You can't solve it without both, but the "Advanced" part is mostly a full undertanding of the Sprague-Grundy theorem and how it applies to multi-sub games. For those that might be struggling here's a good progression:

Recursive Attempts

Start with a simple mini-max implementation using True/False. Essentially, you take each state, ex: XXIIIXII, and calculate all possible moves from that state and which player is making the move. Then recursively proceed again from that state to find moves for depth + 1. You're essentially creating branches to find out all terminal states. A branch that ends in a True state for player1 means player1 will win. Obviously, this quickly baloons in complexity and memory requirements as you're recursively checking each branch depth first. You'll pass maybe the first 2 or 3 tests, depending on your language, and timeout on the rest.
If you examine the all moves possible from a state, you may deduce that many moves are essentially equivalent. For example, given the state: XIIIIX, knocking down pin state[1] is exactly the same thing as knocking down pin state[4]. Both result in a group of 3 pins. Just as knocking down pin state[2] is the same as knocking down pin state[3] because both result in creating groups of [1, 2] pins. The point here is a lot of actions are equivalent. Instead of representing a "state" as the placements of bowling pins, represent the state of the game as "groups" of pins. So XXIIIXII becomes [3, 2] and XIIIXXIXIIX becomes [3, 1, 2]. Moves will either diminish a group, split a group, or remove a group. This will remove duplicate branches, but will only help pass maybe a few more tests. The majority will time out.

Game Theory

In order to solve the problem within the testing timouts, you need to understand the Sprague-Grundy theorem. I won't go into details about how that works (Google search if you don't know). The important part is the Grundy number of n is the xor of n's component sub games. If you have a game of [1, 2, 2, 1], you can simple xor the Grundy numbers of each element. But if you have any group more than 2, that group essentially represents a set of sub-games. For example: 4 can be divided into [3], [1, 2] and [1, 1] games. The Grundy of 4 then represents the xor of the result of each game. This is the recursion necessary to solve the problem. You still have a 3 to deal with and that represents the xor of another set of games.

The last element you should consider is caching. Using the Sprague-Grundy theorem will get you far, but you'll still end up re-caclulating a lot of games. So passing a cache (dict) that keeps track of the grundy for specific values of n will help you pass all the tests.

Here's an example using Python 3: https://www.hackerrank.com/challenges/bowling-pins/submissions/code/44192663

8 years ago+ 3 comments

Excellent analysis!

Here is a great article that explains all the necessary theory: nim.pdf

I solved it using the game theory approach and found a much shorter solution (Python 2):

# precompute the Sprague-Grundy (SG) function for all 0 <= n <= 300
g = [0, 1, 2]
for n in xrange(3, 301):
    s = set()
    # hit one or two pins
    for l in (1, 2):
        # the group of n pins can be split into two 
        # grops of i and n - l - i pins
        for i in xrange((n - l)/2 + 1):
            s.add(g[i]^g[n - l - i])
    # compute mex (minimum excluded value)
    m = 0
    while m in s:
        m += 1
    g.append(m)

for t in xrange(int(raw_input().strip())):
    raw_input()
    ret = 0
    # split the pins into groups and xor the SG values
    for p in raw_input().strip().split('X'):
        ret ^= g[len(p)]
    print 'WIN' if ret else 'LOSE'

4 years ago+ 0 comments

There's a mistake in the pdf. Page 4

3 011 + 5 100 = 7 111

The binary expansion of 5 is 101 and the answer should be 6 which is shown on the table on page 5 of the paper.

4 years ago+ 0 comments

here is problem solution in java python c++ and c programming. https://programs.programmingoneonone.com/2021/07/hackerrank-bowling-pins-problem-solution.html

View more Comments..

7 years ago+ 0 comments

"For example: 4 can be divided into [3], [1, 2] and [1, 1] games."
What about [2] ? IIII -> IIXX

Can you please explain this idea of xor'ing results of sub-games? I'm not sure about it.

Btw, how do you deal with duplicate sub-games? Fro example, [3,3] can became both [2,3] and [3,2]. and if they are win-states, their xor will be 0 as if both of them be fail-states. What's the poin of xoring here?

3 years ago+ 0 comments

Interesting... Before I went through these comments, I'd deduced you could eliminate 2 piles of any length, as the second player could ostensibly and definitively negate any moves the first player did.

I hadn't been able to parse down to the XOR component that brought that same principle to a greater scope. Thanks for this.

Cookie support is required to access HackerRank

Please signup or login in order to view this challenge