Duncan's blog

October 27, 2014

Project Euler: problem 112 (PHP) – Bouncy numbers

Filed under: PHP,Project Euler — duncan @ 8:00 am
112

Photo by Leo Reynolds

I’m doing these Project Euler mathematical puzzles as a simple practical exercise for teaching myself PHP, and I’d appreciate any feedback on my code.

Problem 112:

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

Code:

<?php
$proportion = 0;
$bouncies = 0;
$limit = 99;
$number = 1;

while (true) {
	if (isBouncy($number)) {
		$bouncies++;
	}
	
	$proportion = $bouncies / $number * 100;
	
	if ($proportion == $limit) {
		echo $number;
		break;
	}
	
	$number++;
}

function isBouncy($number) {
	return !(isIncreasing($number) || isDecreasing($number));
}

function isIncreasing($number) {
	$digits = str_split($number);
	
	for($i = 1, $len = count($digits); $i < $len; $i++)  {
		if($digits[$i] < $digits[$i-1]) {
			return false;
		}
	}
	
	return true;
}

function isDecreasing($number) {
	$digits = str_split($number);
	
	for($i = 1, $len = count($digits); $i < $len; $i++)  {
		if($digits[$i] > $digits[$i-1]) {
			return false;
		}
	}
	
	return true;
}

Looping until I reach the 99% proportion.  For each number, work out if it’s bouncy.  Keep track of how many bouncy numbers we have, continually calculating the proportion that are.  The isBouncy function just being a wrapper to find out which numbers are neither increasing nor decreasing.  Those functions looping over all the digits of the number, comparing each digit to the previous one.

There’s obvious duplication between the isIncreasing and isDecreasing functions.  Refactoring this to reduce that duplication:

function isBouncy($number) {
	$digits = str_split($number);
	$isIncreasing = false;
	$isDecreasing = false;
	
	for($i = 1, $len = count($digits); $i < $len; $i++)  {
 		if($digits[$i] > $digits[$i-1]) {
			$isIncreasing = true;
		} elseif ($digits[$i] < $digits[$i-1]) {
			$isDecreasing = true;
		}
		
		if ($isIncreasing && $isDecreasing) {
			return true;
		}
	}
	
	return false;
}

Doing this reduced execution time from about 14 seconds to more like 8.8.

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: