425

7
+12  Q:

## 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 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:
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}
``````
MPAA will send their goons to your house before you buy even half that number. :-)
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: 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.
+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? :)

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.

To those upvoting this post: This is by the OP himself. OP: Please put this information into your original post.
@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.
@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.
+7  A:

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:])
``````
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)`
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...
I'm happy to see that you are satisfied with this solution.
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).
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.
@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?
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.
Hmmm. You are right, of course.
Please look at new solution.
+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 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))
``````
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...
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)