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