Euler Solution 112

From ProgSoc Wiki

Jump to: navigation, search

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%.


Python by Althalus

With this problem, progsoc has now reached level 3. Runtime: 24sec

def bounce(n):
 n = [int(x) for x in str(n)]
 up,down,check = False,False, n[0]
 for c in n:
  if c > check: up = True
  if c < check: down = True
  if up and down: return True
  check = c 
 return False

def infGen(start=0,iter=1): #Why? Because I can :)
 count =  start
 while 1:
  count +=iter
  yield count

count,test = 525,1000
inf = infGen(1000)
for x in inf:
 if x % 100000 == 0: print x
 if bounce(x): count+=1
 test +=1 
 if count*100.0/test == 99.0: print '99%: ', x; break
Personal tools