Duncan's blog

October 8, 2014

Project Euler: problem 29 (PHP) – Distinct powers

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

29I previously blogged about this Project Euler puzzle nearly 6 years ago, using ColdFusion.  This is my approach using PHP as a simple practical exercise for myself, and I’d appreciate any feedback on my PHP code.

Problem 29:

Consider all integer combinations of ab for 2 <= a <= 5 and 2 <= b <= 5:

22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by ab for 2 <= a <= 100 and 2 <= b <= 100?

Here’s my code:

<?php
ini_set('max_execution_time', 100);

$limit = 100;
$numbers = [];

for ($i = 2; $i <= $limit; $i++) {
	for ($j = 2; $j <= $limit; $j++) {
		$x = bcpow($i, $j);
		
		$newNumbers = array_flip($numbers);
		
		if (!isset($newNumbers[$x])) {
			$numbers[] = $x;
		}
	}
}

echo count($numbers);

Taking a similar approach as with the ColdFusion.  Initially I tried using the in_array() function to check if the current value was already in the $numbers array. That didn’t seem to work (I can’t remember why not), so instead I went with isset().  Prior to being able to do that I had to use array_flip() to swap the keys and values, i.e. this:

$numbers = [
	[0] => 4,
	[1] => 8,
	[2] => 16,
	...
];

becomes:

$numbers = [
	[4] => 0,
	[8] => 1,
	[16] => 2,
	...
];

So the isset() is just checking if we have a key in the array matching the current value of $x.  And again I’m having to use bcpow() for dealing with large numbers.


Update: My mate and colleague Adam Cameron suggested a much better way of doing this.

<?php
$limit = 100;
$numbers = [];

for ($i = 2; $i <= $limit; $i++) {
	for ($j = 2; $j <= $limit; $j++) {
		$x = bcpow($i, $j);
		
		$numbers[$x] = true;
	}
}

echo count($numbers);

My problem is I’ve been doing mostly straight conversions of old CFML/Python code into PHP, rather than trying to re-think it properly. So previously with ColdFusion  I had a list which I was examining at every iteration of the inner loop, to see if a value already existed in the list. This isn’t particularly efficient; at the time I couldn’t have used ArrayFind as that was only added in CF 9, which I didn’t have access to at the time. However even then I’d have been better using a ColdFusion struct, which is similar to PHP arrays. And simply by adding the values into the struct, at worse I might overwrite the same value multiple times; this is much more efficient than doing an IF statement on every iteration, thousands of times! This was significantly faster.

PS: Adam also solved it using PHP’s array_reduce, array_merge and array_unique functions with callbacks, which makes logical sense (although I’m still getting my head round these), and was only fractionally slower than the updated version of the code above.

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: