Simple DP speedy solution for Mathematically Lucky Tickets by nickie - python coding challenges

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

Simple DP solution in Speedy category for Mathematically Lucky Tickets by nickie

def combine(x, y):
    return [x+y, x-y, x*y] + ([x/y] if y != 0 else [])

def checkio(data):
    N = len(data)
    gen = {}
    for l in range(1,N+1):
        for i in range(0,N+1-l):
            gen[i, l] = set([int(data[i:i+l])])
            for k in range(1, l):
                gen[i, l] |= set(g for x in gen[i,k] for y in gen[i+k,l-k]
                                   for g in combine(x, y))
    return 100 not in gen[0, N]

Feb. 26, 2014

Comments:

macfreek on April 21, 2014, 6:41 p.m.
Very nice solution! And fast indeed! It took me a little while to understand your algorithm. For other interested readers, here it is with my annotations. <pre class='brush: python'>def checkio(data): """Solution by nickie""" N = len(data) print (data) # gen[i,l] is a set of all possible numbers that can be made of data[i:i+l], # thus from the digits starting at i with length l. gen = {} # loop through all combinations i,l (digit combinations. # Start with the shortest ones, so that longer ones can use the known # values for the shorter ones. for l in range(1,N+1): for i in range(0,N+1-l): # Starting point: the digits itself. gen[i, l] = set([int(data[i:i+l])]) # split the digits in two parts, and yield all existing values # with all possible operators. for k in range(1, l): gen[i, l] |= set(g for x in gen[i,k] for y in gen[i+k,l-k] for g in combine(x, y)) return 100 not in gen[0, N] </pre>

oduvan on April 22, 2014, 12:03 p.m.
some times we just do another solution in order to clearify solution of others

macfreek on April 22, 2014, 9:43 p.m.
One comment: you may potentially make it even faster by using the digits as the key in the gen dict, instead of the digit positions. For example, for checkio('237637') both gen[1,2] and gen[4,2] would both contain results that the two digits 3 and 7 could yield ({37, 10, -4, 3/7, 21}). You could have skipped this calculation the second time. I'll see if I can create this improvement and see if it is indeed faster. (It really depends, if this doesn't occur so often, the if statement to check if the result already exists also takes some time, meaning that it may potentially be slower if there are no duplicate digits).

juestr on Aug. 9, 2021, 3:18 p.m.
Nice. I thought about doing a top-down DP solution using `@cache`, but got lazy when the recursive generator felt fast enough.

Blizzard

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.