Skip to content

Instantly share code, notes, and snippets.

@hickford hickford/pizza.py
Last active Sep 30, 2016

Embed
What would you like to do?
"""I'm thinking of a ten-digit integer whose digits are all distinct. It happens that the number formed by the first n of them is divisible by n for each n from 1 to 10. What is my number?
http://blog.pizzahut.com/flavor-news/national-pi-day-math-contest-problems-are-here-2/ """
digits = [None] * 10
def pretty(A):
return "".join(str(x) if x != None else "-" for x in A)
assert pretty([5, None, 3]) == "5-3"
def test(k):
"""Test first k digits"""
assert None not in digits[:k], digits[:k]
if not len(set(digits[:k])) == k:
return False
for i in range(1, k+1):
if int("".join(map(str, digits[:i]))) % i != 0:
return False
return True
def solve():
pos = 0
while True:
# advance at pos
assert digits[pos] != 9, digits
if digits[pos] == None:
digits[pos] = 0
else:
digits[pos] += 1
if test(pos+1):
print(pretty(digits))
pos += 1
if pos == 10:
solution = int("".join(map(str,digits)))
return solution
else:
print(pretty(digits) + " BUST")
# rewind
while digits[pos] == 9:
digits[pos] = None
pos -= 1
if pos < 0:
return "impossible"
print(solve())
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.