65 lines
1.6 KiB
Python
65 lines
1.6 KiB
Python
# Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468.
|
|
#
|
|
# Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 66420.
|
|
#
|
|
# We shall call a positive integer that is neither increasing nor decreasing a "bouncy" number; for example, 155349.
|
|
#
|
|
# Clearly there cannot be any bouncy numbers below one-hundred, but just over half of the numbers below one-thousand (525) are bouncy.
|
|
# In fact, the least number for which the proportion of bouncy numbers first reaches 50% is 538.
|
|
#
|
|
# Surprisingly, bouncy numbers become more and more common and by the time we reach 21780 the proportion of bouncy numbers is equal to 90%.
|
|
#
|
|
# Find the least number for which the proportion of bouncy numbers is exactly 99%.
|
|
|
|
from projecteuler import timing
|
|
|
|
|
|
def is_bouncy(n):
|
|
i = 0
|
|
|
|
n = str(n)
|
|
l = len(n)
|
|
|
|
while i < l - 1 and n[i] == n[i + 1]:
|
|
i += 1
|
|
|
|
if i == l - 1:
|
|
return False
|
|
|
|
if n[i] < n[i + 1]:
|
|
for i in range(i, l - 1):
|
|
if n[i] > n[i + 1]:
|
|
return True
|
|
|
|
if n[i] > n[i + 1]:
|
|
for i in range(i, l - 1):
|
|
if n[i] < n[i + 1]:
|
|
return True
|
|
|
|
return False
|
|
|
|
|
|
@timing
|
|
def p112():
|
|
i = 100
|
|
n_bouncy = 0
|
|
ratio = 0.0
|
|
|
|
while True:
|
|
if is_bouncy(i):
|
|
n_bouncy += 1
|
|
|
|
ratio = n_bouncy / i
|
|
|
|
if ratio == 0.99:
|
|
break
|
|
|
|
i += 1
|
|
|
|
print('Project Euler, Problem 112')
|
|
print(f'Answer: {i}')
|
|
|
|
|
|
if __name__ == '__main__':
|
|
p112()
|