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?

+2  A: 

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:
    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}
MPAA will send their goons to your house before you buy even half that number. :-)
Franci Penov
Seems to work correctly, but you are adding only 1 sticker of each 0-9 every round. Adding 2 would answer the original question, but not likely to stop any time soon...
@ jari, hm, yeah. you are right, missed that …
@jari: adding +2 in every round lets the number of stickers grow and grow and grow. no end in sight (only after integer overflow :D)
Guys, read the question label: brute force not likely to work for ya...
Tal Weiss
@tal weiss: when you get 2 new stickers each per dvd, you will never come to an end. at least that's what bruteforcing shows. number of stickers climbing and climbing
@knittl well, bruteforcing is not proof. I've posted a proof of why the sticker pile will eventually run dry.
Tal Weiss
+1  A: 

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? :)

Merlyn Morgan-Graham
usually about 4.7 billion
+1  A: 
4^S and 27^S and …. maybe it's (S^S)^S?
@knittl: Won't work for N>3 though.
+6  A: 

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.

Tal Weiss
To those upvoting this post: This is by the OP himself. OP: Please put this information into your original post.
Noon Silk
@silky: Answering your own question is useful and encouraged, since it adds to the community knowledge base.
@Daenyth: *sigh*. I wish I didn't have to explain this, but: 1) I don't disagree, 2) The op new this information at the time of posting the question.
Noon Silk
@silky: I did know this info at the time of posting but felt it was part of the answer, sort of like a spoiler for the movie plot or a hint for a puzzle. It is not information needed to solve the question. I wouldn't have wanted other such posts to give hints as part of the question.... That said, if people disagree I will move it to the question.
Tal Weiss
+7  A: 

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


time { python; } 
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


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

    NUMBERS = [1]
    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
        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))))
            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)),
    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:])
        return (position, str(int(number[:position])-1)+"1"+number[position+1:])
Tomasz Wysocki
And a beautiful pattern emerges +1! Very cool! Playing with it now. Can someone please explain the resulting pattern?Here is the logic, as I understand it: if you are at dvd # I (I being an N digit number), and you have S stickers in your leftovers stash, you can fast forward without checking the next S / N numbers (assuming there are that many N digit numbers left). This is the meaning of `min( stickers_left / no_of_dights, 10 ** (no_of_dights + 1) - i - 1)`
Tal Weiss
Less than 1 second to run on a very old desktop (for the requested 2 sticker version)! Less than 5 seconds to solve the 3 sticker version...
Tal Weiss
I'm happy to see that you are satisfied with this solution.
Tomasz Wysocki
There was bug in solution. It should be: min( stickers_left / no_of_dights, 10 ** no_of_dights - i - 1)I have fixed it (the results hasn't changed).
Tomasz Wysocki
The resulting pattern emerges once you understand that 1 runs out first. If you prefer, the problem can be stated like this: For which number `n` does the sum of *1* digits in `[1-n]` become greater than `2*n`? @Tomasz: Absolutely awesome solution, by the way.
Michael Foukarakis
@Tomasz - 10X boost in your code when I realized that, at most a tenth of every digit is a 1, so the fast-forward should be: min( 10 * stickers_left / no_of_digits, 10 ** no_of_digits - i - 1). Can you update your code please?
Tal Weiss
It's not quite right. What about numbers like: 111111111123? When you fast-forward by small number, every move takes almost the same number of '1's.
Tomasz Wysocki
Hmmm. You are right, of course.
Tal Weiss
Please look at new solution.
Tomasz Wysocki
+1  A: 

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.

+2  A: 

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

time { python ; }
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


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))))
        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))
        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):
    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
            top = center

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

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

for i in xrange(10):
    print "%d: %d" % (i, solve(i))
Tomasz Wysocki
Can you please add a few words about the algorithm? What does "lowest_state" do? I'm also pretty sure there is a way to calculate how_many_used directly, without recursion, but the code is already blazing fast as it is...
Tal Weiss
lowest_state returns what was lowest supply of '1' stickers when we buy `i` DVDs with `stickers` stickers in each.In fact this number is always 0 or negative (because starting supply is 0, so lowest supply can't be higher)
Tomasz Wysocki