Puzzle that defies the brute force approach?

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 thi开发者_运维百科s 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?

---

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

---

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.

---

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

---

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}

---

The results for any base N and number of stickers per digit per DVD "S" are:

N\S ]      1 |        2 |          3 |         4 |    5 |        S?
===================================================================
  2 ]      2 |       14 |         62 |       254 | 1022 |   4^S - 2
----+--------+----------+------------+-----------+------+----------
  3 ]     12 |      363 |       9840 |    265719 |     (27^S - 3)/2
----+--------+----------+------------+-----------+-----------------
  4 ]     28 |     7672 |    1965558 | 503184885 |
----+--------+----------+------------+-----------+
  5 ]    181 |   571865 | 1787099985 |
----+--------+----------+------------+
  6 ]    426 | 19968756 |
----+--------+----------+
  7 ]   3930 | (≥ 2^31) |
----+--------+----------+
  8 ]   8184 |
----+--------+
  9 ] 102780 |
----+--------+
 10 ] 199990 |
----+--------+

I can't see any patterns.

---

Alternatively, if the sticker starts from 0 instead of 1,

N\S ]       1 |        2 |          3 |         4 |    5 |          S?
======================================================================
  2 ]       4 |       20 |         84 |       340 | 1364 | (4^S-1)*4/3
----+---------+----------+------------+-----------+------+------------
  3 ]      12 |      363 |       9840 |    265719 |       (27^S - 3)/2
----+---------+----------+------------+-----------+-------------------
  4 ]      84 |     7764 |    1965652 | 503184980 |
----+---------+----------+------------+-----------+
  5 ]     182 |   571875 | 1787100182 |
----+---------+----------+------------+
  6 ]    1728 | 19970496 |
----+---------+----------+
  7 ]    3931 | (≥ 2^31) |
----+---------+----------+
  8 ]   49152 |
----+---------+
  9 ]  102789 |
----+---------+
 10 ] 1600000 |
----+---------+

---

Let's assume that it's the “1” sticker running out first — which is indeed the case for most other computed info.

Suppose we are in base N and there will be S new stickers per digit per DVD.

At DVD #X, there will be totally X×S “1” stickers, used or not.

The number of “1” stickers used is just the number of “1” in the digits from 1 to X in base N expansion.

Thus we just need to find the cross-over point of X×S and the total “1” digit count.

• N = 2: 1,2,4,5,7,9,12,13,15,17,20,22,25,28,32,33,35,37,40,42,45,48,52,54,57,…
• N = 3: 1,1,2,4,5,5,6,6,7,9,10,12,15,17,18,20,21,21,22,22,23,25,26,26,27,…
• N = 10: 1,1,1,1,1,1,1,1,1,2,4,5,6,7,8,9,10,11,12,12,13,13,13,13,13,…

there does not seem to be a closed for all these sequences, so a loop proportional X iterations is necessary. The digits can be extracted in log X time, so in principle the algorithm can finish in O(X log X) time.

This is no better than the other algorithm but at least a lot computations can be removed. A sample C code:

#include <stdio.h>

static inline int ones_in_digit(int X, int N) {
    int res = 0;
    while (X) {
        if (X % N == 1)
            ++ res;
        X /= N;
    }
    return res;
}

int main() {
    int N, S, X;

    printf("Base N?   ");
    scanf("%d", &N);
    printf("Stickers? ");
    scanf("%d", &S);

    int count_of_1 = 0;
    X = 0;
    do {
        ++ X;
        count_of_1 += S - ones_in_digit(X, N);
        if (X % 10000000 == 0)
            printf("%d -> %d\n", X/10000000, count_of_1);
    } while (count_of_1 >= 0);
    printf("%d\n", X-1);
    return 0;
}

---

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.