Project Euler 112: Investigating the density of “bouncy” numbers

Problem 112 of Project Euler we deal with Bouncy numbers. Something which I have never heard of before. However, it is a pretty easy concept to grasp, so go ahead and read the problem description

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

I am pretty certain that we can solve this problem in many ways, but since we are dealing with bouncy numbers in problem 113 as well I took the easy route this time and went for a brute force solution.

The main thing here is to figure out a way to determine if a number is bouncy or not. I did it with this function

private bool isBouncy(int number) {

    bool inc = false;
    bool dec = false;

    int last = number % 10;
    number /= 10;

    while (number > 0) {
        int next = number % 10;
        number /= 10;
        if (next < last)
            inc = true;
        else if (next > last)
            dec = true;

        last = next;

        if (dec && inc) return true;
    }

    return dec && inc;
}

which simply checks to see if a number has increasing and decreasing properties. In that case it will be bouncy. The check in line 19 is not strictly necessary as we would get the same result if we let it run, but I found that it will improve the performance if we have the possibility to return as early as possible.

Once we can check if a number is bouncy all we need is to keep finding bouncy numbers until we reach the 99% percent limit. This is done with the piece of code here

int i = 99;
int bouncies = 0;

while(100*bouncies < 99*i) { i++; if(isBouncy(i)) bouncies++; } [/csharp]

Wrapping up

I know this was a very short post, but it solves the problem in 54ms, which is not blindly fast, but certainly okay. Especially since we need to deal with this again in Problem 113, so we get a chance to revisit this problem.

The solution from the code gives me

We reach 99% at 1587000

As usual you can find the source code here.

The blog image today is take by Joe Dunckley and kindly shared under the creative commons license.

Posted by Kristian

11 comments

Yes, brute force is sometimes better then more complicated code.
If you can brute force it, with a good speed, brute force.

here is C++. And I have some problems to post my solutions in C++, or C.
Could you tell me how to use those code tags.

#include <iostream>
#include <ctime>

using namespace std;
bool isBouncy(int num);


int main()
{
    time_t start = clock();
      int bouncy = 0;
     for(int number = 100;;number++){
     
     if(isBouncy(number))
          bouncy++;
          
          if(bouncy * 100 / number == 99){
              cout<<"Project Euler 112:\t"<<number<<endl;
              cout<<"PROGRAM LAST:\t"<<(clock()- start)<<endl;
              exit(0);
          }
                    
         // cout<<number<<endl;               
     }

    if(num % 10 < digit)
        increasing = true;

     else if(num % 10 > digit)
        decreasing = true;

    digit = num % 10;
    num /= 10;
}

return decreasing == true && increasing == true;

}

You use them just as explained below the comment box. so just put in cpp as a language instead of c++.

And thanks for the code 🙂

Of course 🙂 I forgot to use cpp instead of C++ 🙂

#include <iostream>
#include <ctime>
using namespace std;
bool isBouncy(int num);

int main()
{


    time_t start = clock();
     int bouncy = 0;
     for(int number = 100;;number++){
     
     if(isBouncy(number))
          bouncy++;
          
          if(bouncy * 100 / number == 99){
          cout<<"Project Euler 112:\t"<<number<<endl;
          cout<<"PROGRAM LAST:\t"<<(clock()- start)<<endl;
          exit(0);
          }
          
     
     }
}

bool isBouncy(int num){
bool decreasing = false, increasing= false;
int digit = num % 10;
num /= 10;
while(num != 0){

if(num % 10 < digit)
increasing = true;

else if(num % 10 > digit)
decreasing = true;

digit = num % 10;
num /= 10;
}

return decreasing == true && increasing == true;
}
Jean-Marie Hachey

Project Euler 112 refers to 3 categories of numbers :

1) Increasing numbers
2) Decreasing numbers
3) Bouncy numbers

But what about a fourth category : « repeating-same-digit numbers » (ex. 55555) ?

They are considered both increasing and decreasing, but not bouncy.

Jean-Marie Hachey

Euler Project Problem 112
Some results and graph …

Table 1
Evolution of bouncy numbers proportions (%) with increasing
least numbers limits between 102 and 1587000.

Lines Least Proportion of
Numbers Bouncy
Numbers
(%)
1 102 1
2 103 2
3 106 5
4 132 10
5 175 20
6 213 30
7 317 40
8 538 50
9 1518 60
10 2154 70
11 4770 80
12 21780 90
13 1587000 99

___

Fig. 1:
Evolution of bouncy numbers proportions (%) with increasing
least numbers limits between 102 and 1587000.
Abcissa:
Least numbers within the limits of bouncy numbers.
[1=>102; 2=>103; 3=>106; 4=>132; 5=>175;
6=>213; 7=>317; 8=>538; 9=>1518; 10=>2154;
11=>4770; 12=>21780; 13=>1587000].
Ordinate:
Proportions (%) of bouncy numbers between 1 and 99%.

http://imageshack.us/a/img694/4023/pe113fig1.jpg

___

Source of Data :

Project Euler 112: Investigating the density of “bouncy” numbers
Written by Kristian on 1 September 2012
http://www.mathblog.dk/project-euler-112-density-bouncy-numbers/

Source code:
http://www.mathblog.dk/files/euler/Problem112.cs

Jean-Marie Hachey

Table 2
Evolution of bouncy numbers proportions (%) with increasing
least numbers limits between 102 and 213.

table.tableizer-table {border: 1px solid #CCC; font-family: Arial, Helvetica, sans-serif; font-size: 12px;} .tableizer-table td {padding: 4px; margin: 3px; border: 1px solid #ccc;}
.tableizer-table th {background-color: #104E8B; color: #FFF; font-weight: bold;}

   LinesLeast Proportion of  NumbersBouncy   Numbers   (%) 11021 21032 31065 413210 517520 621330

___

Fig. 2:
Evolution of bouncy numbers proportions (%) with increasing
least numbers limits between 102 and 213.
Abcissa:
Least numbers within the limits of bouncy numbers.
[1=>102; 2=>103; 3=>106; 4=>132; 5=>175;
6=>213].
Ordinate:
Proportions (%) of bouncy numbers between 1 and 30%.

http://imageshack.us/a/img818/6228/pe113fig2.jpg

25, 25 30 traginle is the sum of 2 rht. traginle whose sides are 25, 15 2o ( if these traginles joins with the side 20 we get 25 25 30 traginle)lllrly 25, 25 40 traginle is the sum of 2 rht. traginle whose sides are 25, 15 2o (if these traginles joins with the side 15 we get 25 25 40 traginle)Also If we join 2 rht. traginles whose sides are 5 12 13 with the side 5 we get 13,13 24 traginleIf we join 2 rht. traginles whose sides are 5 12 13 with the side 12 we get 13 13 10 traingleie area same perimeter different

Antonio Sanchez

I took a completely different approach. I started dividing up the number line into different categories: increasing (I), decreasing (D), equal (E) and bouncy (B). By prepending digits, you create a new interval, and can easily figure out what type it is.

Let’s say you have a numerical interval with “K” digits. When you prepend a new digit “d”, compare the most-significant digit of the old interval (“m”) to the new one (“d”). Based on this comparison and the original interval type, you know how to classify the new interval. E.g. prepending a lower digit to a decreasing interval means we now increase then decrease, meaning we created a bouncy interval (1 + 5432 -> 15432).

d D, E->D, I->B, B->B
d = m: D->D, E->E, I->I, B->B
d > m: D->B, E->I, I->I, B->B

Start with intervals:
[0 -> 0, E]
[1 -> 1, E]
[2 -> 2, E]

[9 -> 9, E]

Prepend digits 0-9:
[00 -> 00, E]
[01 -> 01, I]

[09 -> 09, I]
[10 -> 10, D]
[11 -> 11, E]
[12 -> 12, I]

[19 -> 19, I]

It turns out you don’t need to prepend zeroes if you manually add up to two intervals per prepended digits:
[d0000..00 -> d0000..00, D]
[d0000..01 -> d0999..99, B]

The last trick is to collapse intervals with equal type as you go along, keeping your list of intervals quite small (I have 2463 intervals to get to the solution). While building your sets, keep track of the number of bouncy numbers. For each interval, you can compute the fraction of bouncy numbers at the beginning and end. You’re looking for an interval that straddles the target fraction, and with a little algebra, can compute that number exactly as long as there is an integer solution.

Runs in about 5 ms.

Why do you start the total value at 99, and the bouncy numbers at 0? The challenge description gives that when we’ve reached 21780 as total value, the amount of bouncy numbers is 90%, so you could start at i=21780 and bouncies=19602 (90% of i). It’s not much, but every bit helps I guess. 😉

Nice blog btw. I’ve came across your blog a few challenges ago when I was completely stuck, and it really helped me understand the challenge better. I still did it mostly by myself, but your blog really made me understand some flaws my code had. And when I look back at other challenges on your blog I see most of your answers are more efficient (and more mathematically based) than mine. I’m very impressed by some of them, so well done!

Greetings,
Kevin

Leave a Reply