Puzzle that defies the brute force approach?

Question

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?

Answer 1

here's a quick and dirty python script:

#!/bin/env python

disc = 0
stickers = {
    0: 0, 1: 0,
    2: 0, 3: 0,
    4: 0, 5: 0,
    6: 0, 7: 0,
    8: 0, 9: 0 }

def buyDisc():
    global disc
    disc += 1
    for k in stickers.keys():
        stickers[k] += 1

def labelDisc():
    lbl = str(disc)
    for c in lbl:
        if(stickers[int(c)] <= 0): return False;
        stickers[int(c)] -= 1;
    return True

while True:
    buyDisc()
    if not labelDisc(): break

print("No stickers left after " + str(disc) + " discs.")
print("Remaining stickers: " + str(stickers))

i don't know if it yields the correct result though. if you find logical errors, please comment

result with debug output:

Bought disc 199991. Labels: 
Remaining stickers: {0: 111102, 1: 0, 2: 99992, 3: 99992, 4: 99992, 5: 99997, 6: 99992, 7: 99992, 8: 99992, 9: 100024}

Answer 2

Stealing this solution from my lovely fiancee. Don't write a program, don't buy more stickers - buy a pen. When it runs out, buy another one.

Now the new problem becomes - how many numbers can you write on a DVD? :)

Answer 3

Here is proof that a solution exists:

Assuming you ever get to 21 digit numbers, you will start losing a sticker with every DVD you purchase and label ((+20) + (-21)).
It doesn't matter how many stickers you have accumulated until this point. From here on it is all downhill for your sticker stash and you will eventually run out.

Answer 4

This is old solution, completely new 6 bajillion times faster solution is on the bottom.

Solution:

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

real    1m53.493s
user    1m53.183s
sys 0m0.036s

Code:

OPTIMIZE_1 = True # we assum that '1' will run out first (It's easy to prove anyway)

if OPTIMIZE_1:
    NUMBERS = [1]
else:
    NUMBERS = range(10)

def how_many_have(dight, n, stickers):
    return stickers * n

cache = {}
def how_many_used(dight, n):
    if (dight, n) in cache:
        return cache[(dight,n)]
    result = 0
    if dight == "0":
        if OPTIMIZE_1:
            return 0
        else:
            assert(False)
            #TODO
    else:
        if int(n) >= 10:
            if n[0] == dight:
                result += int(n[1:]) + 1
            result += how_many_used(dight, str(int(n[1:])))
            result += how_many_used(dight, str(int(str(int(n[0])-1) + "9"*(len(n) - 1))))
        else:
            result += 1 if n >= dight else 0
    if n.endswith("9" * (len(n)-4)): # '4' constant was pick out based on preformence tests
        cache[(dight, n)] = result
    return result

def best_jump(i, stickers_left):
    no_of_dights = len(str(i))
    return max(1, min(
        stickers_left / no_of_dights,
        10 ** no_of_dights - i - 1,
    ))

def solve(stickers):
    i = 0
    stickers_left = 0
    while stickers_left >= 0:
        i += best_jump(i, stickers_left)

        stickers_left = min(map(
            lambda x: how_many_have(x, i, stickers) - how_many_used(str(x), str(i)),
            NUMBERS
        ))
    return i - 1

for stickers in range(10):
    print '%d: %d' % (stickers, solve(stickers))

Prove that '1' will run out first:

def(number, position):
    """ when number[position] is const, this function is injection """
    if number[position] > "1":
        return (position, number[:position]+"1"+number[position+1:])
    else:
        return (position, str(int(number[:position])-1)+"1"+number[position+1:])

Answer 5

Here's some thoughts on the upper bound demonstrated by @Tal Weiss:

The first 21-digit number is 10^20, at which point we will have at most 20 * 10^20 stickers. Each subsequent DVD will then cost us at least 1 net sticker, so we will definitely have run out by 10^20 + 20 * 10^20, which equals 21 * 10^20. This is therefore an upper bound on the solution. (Not a particularly tight upper bound by any means! But one that's easy to establish).

Generalising the above result to base b:

• each DVD comes with 2b stickers
• the first DVD that costs us 1 net sticker is number b ^ (2b), at which point we will have at most 2b . b ^ (2b) stickers
• so we will definitely run out by b ^ (2b) + 2b . [b ^ (2b)], which equals (2b + 1)[b ^ (2b)]

So for example if we work in base 3, this calculation gives an upper bound of 5103; in base 4, it is 589824. These are numbers it is going to be far easier to brute-force / mathematically solve with.

Answer 6

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'+i[1:])), stickers) + end_state(i[0] + '0'*(len(i)-1), stickers))
        lowest_candidats.append(lowest_state(tail, stickers))
    result =  min(lowest_candidats)
    cache2[(i, stickers)] = result
    return result

def solve(stickers):
    i=1
    while lowest_state(str(i), stickers) >= 0:
        i *= 2

    top = i
    bottom = 0
    center = 0

    while top - bottom > 1:
        center = (top + bottom) / 2
        if lowest_state(str(center), stickers) >= 0:
            bottom = center
        else:
            top = center

    if lowest_state(str(top), stickers) >= 0:
        return top
    else:
        return bottom

import sys
sys.setrecursionlimit(sys.getrecursionlimit() * 10)

for i in xrange(10):
    print "%d: %d" % (i, solve(i))