Project Euler Problem 112 Solution
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%.
import Data.List (sort, find) isIncreasing :: Integer -> Bool isIncreasing n = show n == sort (show n) isDecreasing :: Integer -> Bool isDecreasing n = show n == reverse (sort (show n)) isBouncy :: Integer -> Bool isBouncy n = not (isIncreasing n) && not (isDecreasing n) bouncy :: [(Integer, Integer)] bouncy = b' 1 0 where b' n acc | isBouncy n = (n, acc+1) : b' (n+1) (acc+1) | otherwise = (n, acc) : b' (n+1) acc main :: IO () main = print $ maybe 0 fst $ find (\(n, b) -> (n * 99) == (b * 100)) bouncy
$ ghc -O2 -o bouncy bouncy.hs $ time ./bouncy real 0m1.140s user 0m1.128s sys 0m0.000s
#!/usr/bin/env python from itertools import * def pairwise(iterable): "s -> (s0,s1), (s1,s2), (s2, s3), ..." a, b = tee(iterable) next(b, None) return zip(a, b) def digits(n): return list(map(int, str(n))) def is_increasing(n): return all(prev <= curr for prev, curr in pairwise(digits(n))) def is_decreasing(n): return all(prev >= curr for prev, curr in pairwise(digits(n))) def is_bouncy(n): return not is_increasing(n) and not is_decreasing(n) def running_total(iterable): total = 0 for element in iterable: total += element yield total def main(): nums = count(1) bouncy = running_total(map(lambda n: float(is_bouncy(n)), count(1))) print(next((n for n, b in zip(nums, bouncy) if b / n == 0.99))) if __name__ == "__main__": main()
$ time python3 bouncy.py real 0m17.846s user 0m17.720s sys 0m0.008s
Questions? Comments? Send me an email: [email protected]