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.

Advertisements

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: