Alex Rivera | Logout

Puzzle that defies the brute force approach?

Asked 2010-07-24T07:59:20.230
13

I bought a blank DVD to record my favorite TV show. It came with 20 digit stickers. 2 of each of '0'-'9'.
I thought it would be a good idea to numerically label my new DVD collection. I taped the '1' sticker on my first recorded DVD and put the 19 leftover stickers in a drawer.
The next day I bought another blank DVD (receiving 20 new stickers with it) and after recording the show I labeled it '2'.
And then I started wondering: when will the stickers run out and I will no longer be able to label a DVD?
A few lines of Python, no?

Can you provide code that solves this problem with a reasonable run-time?

Edit: The brute force will simply take too long to run. Please improve your algorithm so your code will return the right answer in, say, a minute?

Extra credit: What if the DVDs came with 3 stickers of each digit?

python math puzzle
Edit
Report

1 Answer

2

Completely new solution. 6 bajillion times faster than first one.

time { python clean.py ; }
0: 0
1: 199990
2: 1999919999999980
3: 19999199999999919999999970
4: 199991999999999199999999919999999960
5: 1999919999999991999999999199999999919999999950
6: 19999199999999919999999991999999999199999999919999999940
7: 199991999999999199999999919999999991999999999199999999919999999930
8: 1999919999999991999999999199999999919999999991999999999199999999919999999920
9: 19999199999999919999999991999999999199999999919999999991999999999199999999919999999918

real    0m0.777s
user    0m0.772s
sys 0m0.004s

code:

cache = {}
def how_many_used(n):
    if n in cache:
        return cache[n]
    result = 0
    if int(n) >= 10:
        if n[0] == '1':
            result += int(n[1:]) + 1
        result += how_many_used(str(int(n[1:])))
        result += how_many_used(str(int(str(int(n[0])-1) + "9"*(len(n) - 1))))
    else:
        result += 1 if n >= '1' else 0
    if n.endswith("9" * (len(n)-0)) or n.endswith("0" * (len(n)-1)):
        cache[n] = result
    return result

def how_many_have(i, stickers):
    return int(i) * stickers

def end_state(i, stickers):
    if i == '':
        return 0
    return how_many_have(i, stickers) - how_many_used(i)

cache2 = {}
def lowest_state(i, stickers):
    if stickers <= 0:
        return end_state(i, stickers)
    if i in ('', '0'):
        return 0
    if (i, stickers) in cache2:
        return cache2[(i, stickers)]

    lowest_candidats = []

    tail9 = '9' * (len(i)-1)
    if i[0] == '1':
        tail = str(int('0'+i[1:]))
        lowest_candidats.append(end_state(str(10**(len(i) - 1)), stickers))
        lowest_candidats.append(lowest_state(tail, stickers - 1) + end_state(str(10**(len(i) - 1)), stickers))
    else:
        tail = str(int(i[0])-1) + tail9
        series = end_state(tail9, stickers)
        if series < 0:
             lowest_candidats.append(lowest_state(str(int('0
answered 2010-07-25T09:06:48.357

Your Answer