With lru_cache/setrecursionlimit and without clear solution for The Stones by Phil15 - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

With lru_cache/setrecursionlimit and without solution in Clear category for The Stones by Phil15

## "Short code" version (it was without sys import)
#from sys import setrecursionlimit # We can't import sys on Checkio's website.
#setrecursionlimit(4000) # we need it if pile is a big number
#from functools import lru_cache
#win1=lru_cache()(lambda n,L:n<1 or(n>min(L)and any(not win1(n-k,L)for k in L)))
## or #win1 = lru_cache()(lambda n, L: n<=0 if n<=min(L) else any(not win1(n-k, L) for k in L))
#stones = lambda pile, moves: (2,1)[win1(pile, tuple(moves))] # tuple is needed for lru_cache

def stones(pile, moves):
    one_win_for = set()
    for n in range(min(moves) + 1, pile + 1):
        if any(n - k not in one_win_for for k in moves if n - k > 0):
            one_win_for.add(n)
    return (2,1)[pile in one_win_for]

Sept. 20, 2018

Comments:

Phil15 on Sept. 20, 2018, 12:44 p.m.
Given a list of moves L, the sequence <pre class='brush: python'>(stones(n, L) for n>=0) </pre> is eventually periodic (and very often periodic), and the period depends only on L. Unfortunately, compute this period is not really simple in general. But with it, we can compute stones(n, L) easily for very large numbers n. We do n = n%period and just have to know stones(k, L) for k<=period (well here it's for periodic sequence, not eventually periodic, but it's not so hard to generalize). And doing it, we don't need sys.setrecursionlimit in the first version of my code.

Escher

0 %

You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.