Duncan's blog

October 23, 2014

Project Euler: problem 39 (PHP) – Integer right triangles

Filed under: PHP,Project Euler — duncan @ 8:00 am
Image from page 208 of "The California fruits and how to grow them; a manual of methods which have yielded greatest success, with the lists of varieties best adapted to the different districts of the state" (1912)

Photo courtesy of Internet Archive Book Images

This is another Project Euler puzzle I hadn’t tried before.  I’m doing these  as a simple practical exercise for teaching myself PHP, and I’d appreciate any feedback on my code.

Problem 39:

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p ≤ 1000, is the number of solutions maximised?

Here’s my code, I’m not sure it’s particularly efficient, taking a brute force approach to working out all the hypotenuses for right-angled triangles with sides adding up to 1000.

<?php
$solutions = [];
$limit = 1000;
	
for ($adjacent = 1; $adjacent <= $limit; $adjacent++) {
	for ($opposite = 1; $opposite <= $limit; $opposite++) {
		$hypotenuse = sqrt(pow($adjacent, 2) + pow($opposite, 2));
		
		if ($hypotenuse != round($hypotenuse)) {
			continue;
		}
		
		$perimiter = $hypotenuse + $adjacent + $opposite;
		
		if ($perimiter > $limit) {
			break;
		}
		
		if (isset($solutions[$perimiter])) {
			$solutions[$perimiter]++;
		} else {
			$solutions[$perimiter] = 1;
		}
	}
}

arsort($solutions, SORT_NUMERIC);

echo key($solutions);

I found I was able to slightly optimise the code post-completion by amending:

for ($adjacent = 1; $adjacent <= $limit; $adjacent++) {
	for ($opposite = 1; $opposite <= $limit; $opposite++) {

to:

for ($adjacent = 1; $adjacent <= $limit/2; $adjacent++) {
	for ($opposite = 1; $opposite <= $limit/2; $opposite++) {

… but this was just through trial-and-error without any real thought as to why exactly. Obviously I didn’t need to loop all the way up to the limit for the length of either individual side. In fact I could amend the outer loop to only go up to $limit/3 although that was more luck than anything; for the test limit of 120 that didn’t work.

I only wanted to work with values where the hypotenuse was an integer.  For some reason the is_int() and is_float() functions didn’t seem to work for me, so I had to use round() to check the value was identical to its integer component.

I then increment the count of how many solutions there are for this length of perimiter.  After the loop I use arsort() to reverse-sort on value (keeping the associated keys), and key() to output the value of the first element of the array.

Make sure not to confuse arsort with the multitude of other functions that sort arrays, including:

  • sortSort an array

  • rsortSort an array in reverse order

  • asortSort an array and maintain index association

  • arsortSort an array in reverse order and maintain index association

  • ksortSort an array by key

  • krsortSort an array by key in reverse order

  • natsortSort an array using a “natural order” algorithm

  • natcasesortSort an array using a case insensitive “natural order” algorithm

  • array_multisortSort multiple or multi-dimensional arrays

  • usortSort an array by values using a user-defined comparison function

  • uksortSort an array by keys using a user-defined comparison function

  • uasortSort an array with a user-defined comparison function and maintain index association

Phew!

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: