Project Euler problem #112

Question

Problem statement:

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

My code:

import time
start = time.time()
def bouncy(N):
 '''Function determines whether arbitrary number N is a bouncy number.'''
 number = list(str(N))
 n1 = list(str(N))
 n2 = list(str(N))
 n1.sort()
 n2.sort(reverse=True)
 if (number != n1 and number != n2):
 return True
 else:
 return False
def find():
 start = 1
 total = 0
 bou = 0 
 while True:
 total += 1
 if bouncy(start):
 bou += 1
 if bou/total >= 0.99:
 break
 start += 1
 return start
print(find())
print(time.time() - start)

---

What can be improved?

• GZ0: Just FYI, here is an extended version of the same problem that requires to accept larger inputs (the website provides tests for the extended versions of the first 239 Project Euler problems). For those inputs, a better algorithm is necessary to pass the tests.

Answer 1

Code structure

The most common and widely accepted structure found in Python scripts from a high-level point of view looks something like:

# imports
import
...
# functions and classes, aka "library code"
class Foo:
 ...
def bar(batz):
 ...
if __name__ == "__main__":
 # part that is supposed to be run as script
 ...

Your code on the other hand does not follow this structure since there is some script code at the top (start = time.time()), then come your functions, followed by another block of script code. I highly recommend to follow that structure.

Further reading: Explanation of if __name__ == "__main__": from the official Python documentation.

The code itself

bouncy

The most striking aspect of bouncy from a stylistic point is the capital N as parameter name that goes against the official Style Guide for Python Code (often just called PEP8). Usually parameter and variable names are written in snake_case, e.g. small letters, possibly separated by underscores.

With that said, let's look at the actual algorithm:

number = list(str(N))
n1 = list(str(N))
n2 = list(str(N))

Lots of repeated code here. An easy way out would be to do the conversion once, and copy the results afterwards. This can be done using slicing like n1 = number[:], the list constructor n1 = list(number) or the copy module. Also, sorted would create a copy indirectly, so no need to do this manually (see the next point).

The next thing you do in your code is sorting those lists. Once ascending, then descending. Since the second one should by definition be the mirror of the previous one, you can use slicing again to avoid that second sort.

sorted_number = sorted(number) # <- also does a copy

Oh, and did you know that sorted does work on strings as well and simply returns a new list? (sorted_number = sorted(N))

You could also use the result of the condition directly as return value of your function.

With some other minor changes you might end up with something like

def is_bouncy(number):
 '''Function determines whether arbitrary number N is a bouncy number.'''
 digits = list(str(number))
 sorted_digits = sorted(digits)
 return digits != sorted_digits and digits != sorted_digits[::-1]

find

find is almost as straightforward as it gets. I would advise to change the variable name bou to bouncy or n_bouncy now that the checking function is called is_bouncy. IMHO current would also likely be a better name for start. Also find_bouncy_boundary, maybe even with an optional "expected bounciness percentage" might be worth a thought.

From an optimization point of view, you could also start from 1000 if you're only looking for that 99%, since the task description tells you that there are exactly 525 bouncy numbers below 1000 ;-) But there is likely not much to gain from that.

The rest

Now all there is left to do is to take the spread out script code, wrap it up in if __name__ == "__main__":, and collect it at the bottom of the script:

if __name__ == "__main__":
 start = time.time()
 print(find())
 print(time.time() - start)

If the script part becomes more complex, this part is often put into a separate main() method.

• GZ0: number != sorted_digits[::-1] should be digits != sorted_digits[::-1]
• AlexV: @GZ0: you're correct. Will fix it :-)
• sanyassh: Actually, it is better to start from 21780 given from the problem statement that there are 2178 bouncy numbers among them.
• AlexV: @sanyash: That would be 10% then. The task states that exactly 90% are bouncy numbers below 21780, which would be about 19,602 then. Right?
• sanyassh: @AlexV yeah, my mistake :) 2178 non-bouncy and 19602 bouncy.

Answer 2

First of all, the question asks for the least number which the proportion is exactly 99%. Your code finds the first number that the proportion is more or equal to 99%. That is not quite right. Also, comparing floating-numbers is inaccurate and you should change it to integer comparision for exactness: bou * 100 == total * 99

Secondly, in the bouncy function, list(str(N)) is repeated three times unnecessarily. The twice sort calls are also unnecessary. It can be improved as follows

def bouncy(n):
 number = [*str(n)]
 sorted_n = sorted(number)
 return sorted_n != number and sorted_n[::-1] != number

Thirdly, the overall algorithm is a naive one. If you need a better performance, a better approach is needed, e.g. by exploiting the fact that if \$n\$ is a bouncy number, then \10ドルn+b\$ for any \$b\in[0,9]\$ is also a bouncy number and does not need to be checked again.

Answer 3

Speed up the bouncy function

Since you are timing it, I guess speed if of essence. You are sorting a list twice, while you actually don't need to sort it at all. Instead, just check the digits two at a time and see that the difference never change sign. That is O(n) instead of O(n*log(n)) as sorting.

Here's the code. Further changes are highlighted in comments. It only runs slightly faster, 5.8 seconds instead of 8.1 on my machien. My guess is that the reason for the small performance improvement is that Python sorts in C, which makes it comparably fast. But that's just a guess.

import time
# The big change is speeding up this function.
def bouncy(n): # Lower case n
 '''Function determines whether arbitrary number N is a bouncy number.'''
 # We can index directly into the string. No need to make a list of it.
 number = str(n)
 allowed_direction = 0
 # This could probably be done with cool fancy iterators somehow.
 for i in range(0, len(number) - 1):
 direction = cmp(number[i], number[i + 1])
 if allowed_direction == 0:
 allowed_direction = direction
 elif direction != 0 and allowed_direction != direction:
 return True
 return False
def cmp(a, b):
 return (a > b) - (a < b) 
def find():
 # Clearer variable names.
 # The start variable was the same as total, so I removed it.
 total_count = 100 # Start at 100, no bouncy numbers below anyway!
 bouncy_count = 0
 while True:
 if bouncy(total_count):
 bouncy_count += 1
 if bouncy_count / total_count >= 0.99:
 # No need for a break here. We can just return instead.
 return total_count
 total_count += 1
# Cleaner to have this together.
start = time.time()
print(find())
print(time.time() - start)

You want it faster?

This brute force approach of checking each number is simple, but not fast. When you are at 150 000, you know that the next non bouncy number is going to be 155 555. The 5 555 number in between that you are checking is just a waste of CPU cycles.

Implementing this is significantly harder, and is therefore left as an exercise for the reader.

Edit: Here's a ballpark non solution using the above approach. It runs in 0.15 s on my machine.

Answer 4

bouncy

You did a good job by extracting the check for bouncyness to a separate function. Plus points for the docstringThe function itself can be a bit better:

You can use the builtin sorted instead of list.sort. And since a string is an iterable too, you don't need the explicit casts to list You can also immediately return the result of the test number != n1 and number != n2

I don't like the names n1 and n2. They are the increasing and decreasing order of digits, so call em that. N

def bouncy(number):
 """Function determines whether arbitrary number N is a bouncy number."""
 digits = list(str(number))
 increasing = sorted(digits)
 decreasing = increasing[::-1]
 return digits != decreasing and digits != increasing

I've checked a few variations of this bouncyness check, but this is the fastest I can find.

def pairwise(iterable):
 "s -> (s0,s1), (s1,s2), (s2, s3), ..."
 a, b = tee(iterable)
 next(b, None)
 return zip(a, b)
def bouncy_pairwise(number):
 """
 tests whether a number is bouncy
 """
 digits = str(number)
 increasing = decreasing = False
 for a, b in pairwise(digits):
 if not increasing and a > b:
 increasing = True
 if not decreasing and a < b:
 decreasing = True
 if increasing and decreasing:
 return True

and

def bouncy_zip(number):
 """
 tests whether a number is bouncy
 """
 digits = str(number)
 increasing = decreasing = False
 for a, b in zip(digits, digits[1::]):
 if not increasing and a > b:
 increasing = True
 if not decreasing and a < b:
 decreasing = True
 if increasing and decreasing:
 return True

were faster when the bouncyness was in the beginning of the number, but slower for non-bouncy numbers

find

• You have the 0.99 hardcoded. I would pass this on as an argument to the list
• Of the double variables total and start, only 1 is needed
• Instead of the break, just return there
• instead of the while True loop, use itertools.count
• no need to shorten bou, you can use bouncy_count or something as a more clear variable name
• You could use the fact that int(True) is 1 and int(False) is 0, to replace if bouncy(i): bouncy_count += 1 by bouncy_count += bouncy(i)

With this result:

def find(fraction = .50):
 """Finds the first number where the ratio of bouncy numbers to all umbers is > `fraction`"""
 bouncy_count = 0
 for i in count(1):
 bouncy_count += bouncy(i)
 if bouncy_count / i > fraction:
 return i

timing

Instead of using time.time, you can use the timeit module

for example:

timeit.repeat("find_bouncy(.9)", globals={"find_bouncy": find_bouncy}, number = 100)

• GZ0: The checking conditions in bouncy_pairwise can be simplified: if a > b: increasing = True elif a < b: decreasing = True. Another alternative is increasing = increasing or a > b; decreasing = decreasing or a < b.