# Counting bouncy numbers

See Project Euler Problem 112: Find the point at which the porportion of bouncy numbers is 99%.

This is a simple problem to state, but has some tricks. First in the conversion of a number into its component digits. This can be neatly done with the [int (x) for x in str (n)] construct, which turns the number into a string, converts each character in the string into an int and builds a list with the result.

Detecting the "bounciness" is done efficiently in the function by moving to each digit (but the first) and comparing it to the previous. Moves up and down are recorded and if at any point we have seen both, we need not check any further.

The main loop runs from 100 to 5 million. There is no need to look
before 100, because it is the first number that has an opportunity to up
*and* down. (This introduces an interesting question as to whether the
answer is meant to also count numbers below 100.) 5 million was
arbitrarily chosen as an upper limit during development, just to catch
any run-away loops.

The final step, calculating when the percent bouncy numbers is *exactly*
99% is tricky. We can't do this using floats because floating point
arithmetic is inexact. (Unless we use decimal.) If we use integers, they
will round off any residue ( 9/10 is 0). So multiplying by 100 allows us
to make a comparison against 99. Even then rounding can occur (99001 /
1000 is 99), so we check with the modulo that the numbers divide evenly
into each other:

def is_bouncy (n): num_list = [int (x) for x in str (n)] goes_up = goes_down = False for index in range (1, len (num_list)): if (num_list[index-1] < num_list[index]): goes_up = True elif (num_list[index-1] > num_list[index]): goes_down = True if (goes_up and goes_down): return True return False # some test code for x in [100, 120, 138, 142, 144, 149]: print x, is_bouncy (x) trials = 0 bouncy = 0 for i in range (100, 5000000): trials += 1 if (is_bouncy (i)): bouncy += 1 percent_bouncy = bouncy * 100 / trials if (99 == percent_bouncy): if ((1559844 * 100) % 1575600 == 0): print "Number:", i, "trials:", trials, "bouncy:", bouncy break

The answer is 1575699. Computation time about 20 seconds..