Duncan's blog

December 3, 2014

Project Euler: problem 32 (PHP) – Pandigital products

Filed under: PHP,Project Euler — duncan @ 1:24 pm
Tags:
123456789

Photo by Lars Dahlin

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 32:

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

This if the first one of these Project Euler puzzles I’ve completed in the last month.  I’d been sidelined by a much harder one, given up on it for now, and tried this instead for the first time.  It wasn’t too hard either; I’m not sure why I hadn’t attempted it previously.

<?php
$sums = [];

for ($i = 1; $i < 9; $i++) {
	for ($j = 1234; $j < 9876; $j++) {
		getPandigitalProduct($i, $j, $sums);
	}
}

for ($i = 12; $i < 98; $i++) {
	for ($j = 123; $j < 987; $j++) {
		getPandigitalProduct($i, $j, $sums);
	}
}

echo array_sum($sums);

function getPandigitalProduct($multiplicand, $multiplier, &$sums) {
	$product = $multiplicand * $multiplier;
	$number =  $multiplicand . $multiplier . $product;
	
	if (isPandigital($number)) {
		$sums[$product] = $product;
	}
}

function isPandigital($number) {
	$length = strlen($number);
	
	if ($length != 9) {
		return false;
	}
	
	for ($i = 1; $i <= $length; $i++) {
		if (strpos($number, (string)$i) === false) {
			return false;
		}
	}
	
	return true;
}

Not the cleanest code, but it’s reasonably fast.  In the isPandigital function I just loop from 1 to 9, checking that each of those digits is present in the number (after checking that it’s 9 digits long of course).

The important thing to understand is why I’m doing two separate nested loops.  The first one is for getting 9-digit identities which look like:

1 * 2345 = 6789

The second one is for getting identities which look like:

12 * 345 = 6789

Initially I had it in one set of nested loops, like:

for ($i = 1; $i < 99; $i++) {
	for ($j = 1; $j < 9999; $j++) {
		...
	}
}

However that made 979804 iterations!  Doing it this way there’s a total of 143440 iterations (still way too many of course).

Also note I’m explicitly passing the $sums array by reference by specifying the ampersand before the argument in the function declaration.

What else… I had to cast the value of $i to a string before being able to use it succesfully with the strpos function.

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

Create a free website or blog at WordPress.com.

%d bloggers like this: