We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Recursion
  4. Bowling Pins
  5. Discussions

Bowling Pins

  • cafelatte
     + 0 comments

    Took a look at your python solution:
    While it is fine and fast, it doesn't use recursion.
    (I guess, all this problems in the 'Recursion' category are meant as an exercise how to make proficient use of recursion.)

    Here is some recursive solution in python:

    from functools import cache, reduce
from operator import xor

def mex(seq):
    vals, ret = set(seq), 0
    while ret in vals: ret += 1
    return ret
@cache
def nim(run):
    reachable = []
    reachable.extend(nim(i) ^ nim(run-i-1) for i in range(0,(run+1)//2))
    reachable.extend(nim(i) ^ nim(run-i-2) for i in range(0,run//2))
    return mex(reachable)

def isWinning(n, config):
    # Return WIN or LOSE depending on whether you will win        
    runs = list(map(len, config.replace("X", ' ').split()))
    return "WIN" if reduce(xor, map(nim, runs)) else "LOSE"