Duncan's blog

October 18, 2014

Project Euler: problem 53 (PHP) – Combinatoric selections

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

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

Problem 53:

There are exactly ten ways of selecting three from five, 12345:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, 5C3 = 10.

In general,
nCr = n! / (r!(n-r)!)
where r <= n, n! = n*(n-1)*…*3*2*1, and 0! = 1.


It is not until n = 23, that a value exceeds one-million: 23C10 = 1144066.

How many, not necessarily distinct, values of nCr, for 1 <= n <= 100, are greater than one-million?

Code:

<?php
$values = 0;

function factorial($x) {
	$factorial = 1;
	
	for ($i = $x; $i > 1; $i--) {
		$factorial *= $i;
	}
	
	return $factorial;
}

function calc($n, $r) {
    return  factorial($n) / (factorial($r) * factorial($n-$r));
}

foreach (range(1,100) as $i) {
    foreach (range(1, $i) as $j) {
        if (calc($i, $j) > 1000000) {
            $values++;
	}
    }
}

echo $values;

One key difference here from how I did it in Python is I previously used the range() function in my factorial function.  Calling that function with ($n – $r) means that sometimes we’re calling factorial(0).   This means that we then call range(1,0), which in Python returns an empty list.  However in PHP this returns an array like this, even if I specify step=+1 :

array(2) {
    [0]=>int(1)
    [1]=>int(0)
}

So I would then have had to do an additional check that I’m not trying to calculate factorial(0), which slowed the code right down.  However I was able to re-use the factorial function from Problem 34, looping down from $x to 1, instead of doing a foreach loop over the array returned by range().  Doing so kept the code pretty quick.

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: