Duncan's blog

November 8, 2014

New Zealand and Australian coffee shops

Filed under: Coffee — duncan @ 11:16 pm
Tags: , , , , ,

I had a brilliant 3-week holiday in New Zealand and Australia with my girlfriend recently. I thought I’d list some of the decent coffee shops we visited, similarly to how I’ve done it before with New York and Zagreb. This is far from comprehensive; we only went to a few cities, and didn’t try specifically to seek out the best cafés, they were more just those we came across in our wanderings. In summary I was very impressed with the quality of coffee shops in both New Zealand and Australia.

New Zealand

We were briefly in Auckland, then the rest of the time in the South Island, including a couple of visits to Christchurch.

Auckland

Remedy

1 Wellesley Street West, Auckland CBD, Auckland 1010 (map)

A quirky little place with lots of things to keep you distracted in the cafe, like books, board games and an arcade machine, making it a fun place to hang out. But the important thing is the coffee, which was good.
P1160063P1160064P1160065-001

Good One

42 Douglas Street, Ponsonby, Auckland 1011 (map)

Slightly off the main Ponsonby Road, down what is otherwise mostly a residential street, tucked away in a small light industrial unit. It’s worth discovering though; it’s a decent size inside with plenty of seating areas. A huge collection of National Geographics provides some colour in keeping with their yellow theme.
P1160091P1160096P1160095P1160093P1160094P1160092

Christchurch

Coffee Lovers

25 New Regent Street, Christchurch (map)

One of several cafes on the funky little pastel-coloured New Regent Street, right outside where the historic tram currently stops. A small seating area upstairs, reasonable coffee.
P1160605

Crafted Coffee Company

Re:Start Container Mall, Cashel Street, Christchurch (map)

In the centre of Christchurch, following the devastating earthquake of 2011, they’ve constructed a pop-up space of shops and cafes made from shipping containers, ‘Re:Start‘, very similar to the Boxpark in Shoreditch, London.  In one of those units is Crafted Coffee, in a two-storey affair (although the upper area was closed when we were there).  It’s a decent little cafe, and I thought they displayed good customer service.

There were a couple other coffee shops in Re:Start, and given enough time I’d have tried them all.
P1160661P1160660

Robert Harris, Christchurch

YMCA Building, 12 Hereford Street, Christchurch 8013 (map)

In the ground floor of the YMCA youth hostel is a decent sized Robert Harris cafe, doing reasonable coffees and teas and food.  Not quite pure artisan coffee, but a step up from global chains like Starbucks.
P1160588

Vespa Bar

225 High Street, Christchurch (map)

The original Vespa Bar got destroyed in the earthquake, but has been able to re-open in a new building nearby to their original location.  It was more of a bar than a coffee shop, but the food and coffee we had was perfectly fine.

P1160656P1160657

 

Queenstown

Vudu Cafe

23 Beach Street, Queenstown 9197 (map)

In Queenstown there are two Vudu’s, presumably reasonably similar… don’t confuse this Vudu Cafe with Vudu Cafe & Larder round the corner!  We only went to this one, twice.  The coffees were good, and the food was beautifully presented yumminess.  It was quite popular and busy, although there was a semi-covered side-area which didn’t seem to get so crowded.
P1160457P1160455P1160434P1160435P1160436P1160453

Post Office Cafe

19 Ballarat Street, Queenstown 9348 (map)

aka The Exchange, a large coffee shop just round the corner from, er, the post office.
P1160439P1160440

Elsewhere…

Relishes cafe, Wanaka

1/99 Ardmore Street, Wanaka 9305 (map)

There seemed to be several decent looking places along the lakeside in Wanaka; we just chanced on this one.  I had a delicious ‘free range pulled pork shoulder in a Turkish bun with apple slaw‘.  Never heard of Turkish bun before, but it just turned out to be a big soft roll, I think with some herbs and spices.
P1160405

Cafe Mondo, Arrowtown

4/14 Buckingham Street, Arrowtown 9196 (map)

Arrowtown is an interesting little place near Queenstown where the town centre looks like something from the Wild West, having been an old gold mining settlement.  Not sure how much of that is genuinely old and how much is retro-fitted.  Cafe Mondo looked like about the best spot for coffee.  Friendly service.
P1160503

Australia

We were in Melbourne for a few days, but less than 48 hours in Sydney.

Melbourne

Cheeky Monkey

89A Swan Street, Richmond VIC 3121 (map)

Melbourne as a whole is full of good coffee shops, although there didn’t seem to be that many around this area; I recall walking down Swan Street looking for anywhere decent, then finding Cheeky Monkey and opposite it was Book Talk Cafe (a ‘cafebreria‘) which also looked good.

Sacred Alley espresso bar

12 Equitable Place, Melbourne, VIC 3000 (map)

This little alleyway in the Melbourne CBD laneways is full of cafes and restaurants, many of which looked like they’d be good for coffee, and we just opted for this one, which was perfectly good.
P1160779P1160778

Jasper Coffee

Stall 105, 163 Commercial Road, Prahran, Victoria 3181 (map)

Prahran has a large indoor market full of fresh meat, fish, fruit + veg stalls.  Towards the back is this little coffee stand, with an impressive selection of beans available for purchase.  Quite busy, at least at the weekend, but good coffee.

Market Lane is another coffee shop in the Prahran Market that looks very good.

Huckleberry Finn

538 Glenferrie Road, Hawthorn, Victoria (map)

Came across this little place by luck, as we had a few minutes while changing trams and got some takeaway coffees here.  Lovely teal La Marzocco machine.
P1170177P1170176

Slowpoke

157 Brunswick Street, Fitzroy, Victoria 3065 (map)

This was in the Fitzroy area, towards the southern end of Brunswick Street.  They had an open fire in the back, a sort of long narrow affair with different seating areas.  I had some ‘baked eggs in spicy napoli sauce with chorizo & feta’ which was quite nice, and the coffees were very good.  It was indeed nice inside.
P1170367P1170368P1170369

Miss Frank cafe

200 Through Road, Camberwell, Victoria 3124 (map)

This coffee shop was out in Camberwell, luckily quite close to where we were staying.  It’s a good size inside, with friendly service.  Nice food, good coffees, much better than I would expect to typically find out in the suburbs.
P1170221-001P1170222P1170223

Sensory Lab

297 Little Collins Street, Melbourne VIC 3000 (map)

Based in the ground floor of department store David Jones.  They seemed to know what they were doing.

P1160842P1160839P1160840

Sydney

Ground Control cafe

Alfred Street, Sydney, NSW 2000 (map)

A small coffee shop conveniently located in the ground floor under the Circular Quay train station.  Small seating area, reminded me of Dose in London.
P1170886P1170885

Social Brew cafe, Sydney

Harris Street, Pyrmont, NSW 2009 (map)

This coffee shop is near the Sydney Fish Market in Pyrmont (which is worth a visit).  We went there on a Saturday lunch time, and it was very busy with people enjoying brunch, but we were only having coffees, which were good.
P1170887P1170888

AquaBar, Bondi

4/266 Campbell Parade, Bondi Beach, NSW 2026 (map)

On a wet and windy day we took refuge here at the far end of Bondi Beach.  There were about three cafes here all grouped together.  The coffee was ok, and I had a delicious ‘Mediterranean Eggs‘ (poached eggs, lime-infused zatar, feta, pine nuts, Israeli salad with sourdough).
P1170901P1170900

November 2, 2014

Project Euler: problem 95 (PHP) – Amicable chains

Filed under: PHP,Project Euler — duncan @ 3:50 pm

bike chainI’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 95:

The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors of 28 are 1, 2, 4, 7, and 14. As the sum of these divisors is equal to 28, we call it a perfect number.

Interestingly the sum of the proper divisors of 220 is 284 and the sum of the proper divisors of 284 is 220, forming a chain of two numbers. For this reason, 220 and 284 are called an amicable pair.

Perhaps less well known are longer chains. For example, starting with 12496, we form a chain of five numbers:

12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → …)

Since this chain returns to its starting point, it is called an amicable chain.

Find the smallest member of the longest amicable chain with no element exceeding one million.

This puzzle took me a while to get right.  The question doesn’t really give you enough details I think, so it pays to do a bit of research into what perfect numbers, amicable pairs and amicable chains are.  Perfect numbers are an amicable chain with length = 1, and amicable pairs are amicable chains with length = 2.

Continuously adding up the divisors of numbers (the factors of a number apart from the number itself) is called the Aliquot sequence.  Eventually you should either end up running into an amicable chain, or you’ll reach a prime number (i.e. its divisors = 1, and you can’t go any further).  However there are theoretically numbers who’s Aliquot sequence never terminates.  I guess that’s why this question makes sure we don’t have any individual numbers over 1 million.

One thing that’s useful to know, the question doesn’t give you a clue on when you’ll know you’ve reached the longest amicable chain; I assumed it might be into the hundreds.  Fortunately the Wikipedia article on sociable numbers reveals that the longest one is a chain of only 28 numbers in length.

Code:

<?php
$start = microtime(true);

$number = 1;
$limit = 1000000;
$amicableChains = []; 
$length = 0;
$maxLength = 28;

while ($length < $maxLength) {
	$chain = [];
	$currentNumber = $number;

	while (true) {
		$divisors = getDivisors($currentNumber);
		$currentNumber = array_sum($divisors);
		
		if (array_key_exists($currentNumber, $amicableChains)) {
			$amicableChains[$number] = $amicableChains[$currentNumber];
			break;
		}
		
		if ($currentNumber == 1) {
			break;
		}
		
		// break out if we're over a certain length of number
		if ($currentNumber > $limit) {
			break;
		}
		
		if (in_array($currentNumber, $chain)) {
			$key = array_search($currentNumber, $chain);
			$amicableChains[$number] = array_slice($chain, $key);
			$length = count($amicableChains[$number]);
			break;
		}
		
		$chain[] = $currentNumber;
	}
	
	$number++;
}

uasort($amicableChains, function($a, $b) {
	return count($a) > count($b);
});


echo min(end($amicableChains));

$end = microtime(true);
printf("<br>Execution time: %dms", ($end - $start) * 1000);


function getDivisors($number) {
	$factors = [1];
	$root = sqrt($number);
	for ($i = 2; $i <= $root; $i++)
	{
		if ($number % $i == 0)
		{	// it's a factor
			$factor1 = $i;
			$factor2 = $number / $i;
			
			$factors[] = $factor1;
			
			if ($factor1 != $factor2) {
				$factors[] = $factor2;
			}
		}
	}
	
	return $factors;
}

So we loop until we’ve reached a chain with a length of 28+.

Within that loop we have an inner loop, where we calculate the sum of the divisors.  We break out of that inner loop if:

  • we reach a value we already have the amicable chain for
  • the sum of divisors reaches 1
  • we have a value that exceeds one million
  • we get to a value that we already have in the current chain, i.e. we’ve reached a new amicable chain

Initially I had some logic in that inner loop to break out if the current number equalled the previous number, i.e. we had reached a perfect number, an amicable chain of length = 1.  However that wasn’t really required, as the final if statement further down covered it anyway, and it didn’t really slow things down to just use that.

Once we get an amicable chain, I store that chain keyed on the number we’re currently looping over.  N.B this number may not be part of the chain itself.  For instance the divisors of 562 are 1, 2 and 281.  The sum of these is 284.  We already know that 284 is part of the amicable chain 220 → 284.  So the aliquot sequence for 562 is 220 → 284.

Once we’ve reached our limit of a chain with length of 28, I then use the uasort() function to have a user-defined function which sorts my array of amicable chains based on the length of each array within it.  Then I use end() to get the last of those amicable chains, i.e. the longest.  And min() to get the smallest value within that chain.

Job done, running time about 1.5 seconds on average.

 

October 29, 2014

Project Euler: problem 99 (PHP) – Largest exponential

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

99I’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 99:

Comparing two numbers written in index form like 211 and 37 is not difficult, as any calculator would confirm that 211 = 2048 < 37 = 2187.

However, confirming that 632382518061 > 519432525806 would be much more difficult, as both numbers contain over three million digits.

Using base_exp.txt, a 22K text file containing one thousand lines with a base/exponent pair on each line, determine which line number has the greatest numerical value.

NOTE: The first two lines in the file represent the numbers in the example given above.

Interesting, sounds quite difficult.  At first I thought I could use the BC Math functions which have proven so useful in many of the previous puzzles and “support numbers of any size and precision”.  However they didn’t seem to work; according to this StackExchange question they “can handle numbers greater than 2^1000000 (which is 301,030+ digits)“. We’re dealing with numbers here that are ten-fold of that!  So I used the GMP functions instead, which “allow you to work with arbitrary-length integers”.

<?php
$pairs = file('p099_base_exp.txt');

$max = 0;

foreach($pairs as $key=>$pair) {
	$numbers = explode(",", $pair);
	$base = $numbers[0];
	$exponent = $numbers[1];

	$power = gmp_pow($base, intval($exponent));
	
	if (gmp_cmp($power, $max) > 0) {
		$max = $power;
		$lineNumber = $key;
	}
}

echo $lineNumber+1;

I read the file in using file(), turning each line into an array element.  I then loop over those 1000 array elements, using explode() to split each line into its base and exponent parts.

Then I use the gmp_pow() function; however when I tried it initially simply using gmp_pow($base, $exponent) it threw up this error: “A non well formed numeric value encountered“.  It expects $exponent to be an integer, which to all intents and purposes, it seems to be.  However I had to explicitly cast it to an integer, using either intval($exponent) or (int)$exponent – both seemed to work.

Initially I thought I had to use a GMP number for the base, so was using gmp_init() to create one from $base.  However in the end that didn’t seem to be necessary.  So the gmp_pow() function is fussy about what kind of value it gets for the exponenent, but less-so for the base… curious.

After working out the power, I then compare it the maximum power so far, using gmp_cmp().  Each time I get a new maximum value I keep track of which line number that belongs to.  At the end when I output that I increment it by 1, due to PHP arrays being zero-indexed.

This is very slow code, taking close to 5 minutes!

PS: to get the GMP functions to work on my Windows environment I had to uncomment this line in php.ini:

extension=php_gmp.dll

October 28, 2014

Project Euler: problem 74 (PHP) – Digit factorial chains

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

74I’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 74:

The number 145 is well known for the property that the sum of the factorial of its digits is equal to 145:

1! + 4! + 5! = 1 + 24 + 120 = 145

Perhaps less well known is 169, in that it produces the longest chain of numbers that link back to 169; it turns out that there are only three such loops that exist:

169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872

It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,

69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)

Starting with 69 produces a chain of five non-repeating terms, but the longest non-repeating chain with a starting number below one million is sixty terms.

How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?

Code:

<?php
$countChains = 0;
$limit = 1000000;
$terms = 60;

$factorials = getFactorials();

foreach (range(1, $limit) as $number) {
	$currentNumber = $number;
	$count = 0;
	$chain = [$currentNumber];
	
	while (true) {
		$sum = 0;
		$count++;

		$digits = str_split($currentNumber);
		
		foreach($digits as $digit) {
			$sum += $factorials[$digit];
		}		
		
		$currentNumber = $sum;
		
		if (in_array($currentNumber, $chain)) {
			break;
		}
		
		$chain[] = $sum;
		
	}
	
	if ($count == $terms) {
		$countChains++;
	}
}
              
echo $countChains;

function getFactorials() {
	$factorials = [];
	
	for ($i = 0; $i <= 9; $i++) {
		$factorials[$i] = factorial($i);
	}
	
	return $factorials;
}

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

Re-using the approach here from Problem 34, where I first calculated the factorials for the digits 0..9.

Then I loop from one to a million.  I create an array which initially contains the current number.  I then loop over the digits of that number, adding up the factorials of each digit.

If that value is already in our array, then we need to break out of the inner loop, as we’ve reached a repeating term.

Otherwise, add that into the array, and keep on adding up the factorial values of that new value, ad infinitum (well, ad 60 really).

After finishing with our inner loop, i.e. the point at which we’ve reached a repeating term, I check if the length of that chain was 60.

This is pretty slow stuff, taking over 2 minutes to execute!

October 27, 2014

Project Euler: problem 112 (PHP) – Bouncy numbers

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

Photo by Leo Reynolds

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

Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468.

Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 66420.

We shall call a positive integer that is neither increasing nor decreasing a “bouncy” number; for example, 155349.

Clearly there cannot be any bouncy numbers below one-hundred, but just over half of the numbers below one-thousand (525) are bouncy. In fact, the least number for which the proportion of bouncy numbers first reaches 50% is 538.

Surprisingly, bouncy numbers become more and more common and by the time we reach 21780 the proportion of bouncy numbers is equal to 90%.

Find the least number for which the proportion of bouncy numbers is exactly 99%.

Code:

<?php
$proportion = 0;
$bouncies = 0;
$limit = 99;
$number = 1;

while (true) {
	if (isBouncy($number)) {
		$bouncies++;
	}
	
	$proportion = $bouncies / $number * 100;
	
	if ($proportion == $limit) {
		echo $number;
		break;
	}
	
	$number++;
}

function isBouncy($number) {
	return !(isIncreasing($number) || isDecreasing($number));
}

function isIncreasing($number) {
	$digits = str_split($number);
	
	for($i = 1, $len = count($digits); $i < $len; $i++)  {
		if($digits[$i] < $digits[$i-1]) {
			return false;
		}
	}
	
	return true;
}

function isDecreasing($number) {
	$digits = str_split($number);
	
	for($i = 1, $len = count($digits); $i < $len; $i++)  {
		if($digits[$i] > $digits[$i-1]) {
			return false;
		}
	}
	
	return true;
}

Looping until I reach the 99% proportion.  For each number, work out if it’s bouncy.  Keep track of how many bouncy numbers we have, continually calculating the proportion that are.  The isBouncy function just being a wrapper to find out which numbers are neither increasing nor decreasing.  Those functions looping over all the digits of the number, comparing each digit to the previous one.

There’s obvious duplication between the isIncreasing and isDecreasing functions.  Refactoring this to reduce that duplication:

function isBouncy($number) {
	$digits = str_split($number);
	$isIncreasing = false;
	$isDecreasing = false;
	
	for($i = 1, $len = count($digits); $i < $len; $i++)  {
 		if($digits[$i] > $digits[$i-1]) {
			$isIncreasing = true;
		} elseif ($digits[$i] < $digits[$i-1]) {
			$isDecreasing = true;
		}
		
		if ($isIncreasing && $isDecreasing) {
			return true;
		}
	}
	
	return false;
}

Doing this reduced execution time from about 14 seconds to more like 8.8.

October 26, 2014

Project Euler: problem 80 (PHP) – Square root digital expansion

Filed under: PHP,Project Euler — duncan @ 11:41 am
Tags: ,

80I’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 80:

It is well known that if the square root of a natural number is not an integer, then it is irrational. The decimal expansion of such square roots is infinite without any repeating pattern at all.

The square root of two is 1.41421356237309504880…, and the digital sum of the first one hundred decimal digits is 475.

For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.

So this Euler puzzle has only been solved by a little over 10,000 people at the current point, a relatively low number, from which I surmise this is conceivably the hardest puzzle I’ve solved.  In reality it wasn’t that hard however, thanks to PHP’s BC Maths functions.

<?php
$sum = 0;

for ($number = 1; $number <= 100; $number++) {
	$root = bcsqrt($number, 99);
	
	if ($root != round($root)) {
		$decimal = explode(".", $root);
		
		$sum += $decimal[0];
		$sum += array_sum(str_split($decimal[1]));
	}
}

echo $sum;

Using bcsqrt() to calculate the square root of every number from 1 to 100, and I’ve specified 99 as the scale parameter, for how many digits after the decimal point I want.

I’m still not having any luck with the is_int() function, so comparing the value to its integer version using round() to see if we’re dealing with integers or irrational numbers.  Initially I didn’t think I would need to do this, as things like bcsqrt(4, 99) would return 2.000…  so adding all those zeroes wouldn’t affect my total.  However bcsqrt(1, 99) just returns 1, not 1.000… which caused an error further down in the code when using explode(), as there wasn’t any decimal point in the value.

I then turn the number into an array using explode(), splitting it on the decimal point.  I add the integer part.  Then I use str_split() to convert decimals like 4142… into arrays like [4, 1, 4, 2, ...].  And then array_sum() to total up all those digits.  If we were dealing with numbers any greater than 100 then I’d need to do the same with the integer value, but otherwise I know we’re never going to have values with the integer part more than 1 digit long.

Initially I thought when it said the digital sum of the first one hundred decimal digits that it meant the first 100 digits after the decimal point.  e.g. for the square root of 2 (1.4142…) it would be 4 + 1 + 4 + 2… etc.  However I wasn’t getting the right answer.  Comparing the value I was getting for adding up the digits of the square root of 2  with the answer they’d given for that (475), I was able to see where I’d gone wrong.  They really meant just the first 100 digits of the value, including the integer part, e.g. 1 + 4 + 1 + 4 + 2… etc.

So to cater for that I reduced the scale on the bcsqrt() from 100 to 99 and also added the integer part of each square root.

October 25, 2014

Project Euler: problem 12 (PHP) – Highly divisible triangular number

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

12I’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 12:

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Let us list the factors of the first seven triangle numbers:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

Here’s my code:

<?php
$limit = 500;
$counter=1;

do {
	$currentTriangle = getTriangle($counter);

	$countFactors = getCountFactors($currentTriangle);
	
	$counter++;
} while ($countFactors <= $limit);

echo $currentTriangle;


function getTriangle($number) {
	return $number * ($number + 1) / 2;
}


function getCountFactors($number) {
	$countFactors = 0;
	$root = sqrt($number);
	
	for ($i = 1; $i <= $root; $i++) {
		if ($number % $i == 0) {
			$countFactors += 2;
		}
	}
	
	return $countFactors;
}

To begin with I was adding each factor into an array, returning that, then counting the length of the array.  However I later realised I didn’t really need to do that, I could just increment the count of factors by 2 each time.  Originally I was doing:

	for ($i = 1; $i <= sqrt($number); $i++) {
		if ($number % $i == 0)
		{	
			$factors[] = $i;
			$factors[] = $number / $i;
		}
	}

Getting rid of that array didn’t really make any improvements on speed.  However, one other amendment did; in my for loop I was calculating the square root on every iteration of the loop:

	for ($i = 1; $i <= sqrt($number); $i++) {

Moving that value into a variable prior to the for loop more than halved the execution time, from about 25 seconds(!) to about 11:

	$root = sqrt($number);
	
	for ($i = 1; $i <= $root; $i++) {

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!

October 22, 2014

Project Euler: problem 35 (PHP) – Circular primes

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

Punch meI ignored this Project Euler puzzle first time round I tried doing them, 5-6 years ago, with ColdFusion and Python.  Looking at it again recently I thought I could tackle it with PHP.  I’m doing these  as a simple practical exercise for teaching myself PHP, and I’d appreciate any feedback on my code.

Problem 35:

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

It took me a little while to get close to the answer, and I know this code isn’t the most efficient, but it works:

<?php
require 'isPrime.php';

$primes = [2 => 1];
$limit = 1000000;
$circulars = 1;
$arrCirculars = array('2' => true);

function getExcludedDigits($value) {
	return $value % 2 == 0 && $value != 5;
}

for ($i = 3; $i < $limit; $i+=2) {
	$isCircular = false;
	$rotatedDigits = str_split($i);
	
	if (count(array_filter($rotatedDigits, 'getExcludedDigits')) == 0) {
		for ($j = 1; $j <= strlen($i); $j++) {
			array_push($rotatedDigits, array_shift($rotatedDigits));
			$rotatedNumber = implode($rotatedDigits);

			// if this number's already in our primes[], move onto the next iteration
			if (array_key_exists($rotatedNumber, $primes)) {
				continue;
			}
			
			if (!isPrime($rotatedNumber)) {
				$isCircular = false;
				break;
			}
			
			$isCircular = true;
			$primes[$rotatedNumber] = true;
		}
		
		if ($isCircular) {
			if (substr_count($rotatedNumber, substr($rotatedNumber, 0, 1)) == strlen($rotatedNumber)) {
				$circulars++;
			} else {
				$circulars += strlen($rotatedNumber);
			}
			$arrCirculars[$i] = true;	
		}
	}
}

echo $circulars;

Re-using my isPrime function from puzzle 3.

One thing you’ll quickly realise is that we don’t have to calculate if every number is prime.  For instance early on in the loop you get 1951, which is a prime number.  Shifting the first number off there and sticking it on the end, you get 9511, which is also prime.  And doing it again, you get 5119, which is prime too.  However on its fourth iteration you have 1195, which is divisible by 5 and therefore not prime.  However rather than calculate if any of those four rotations of those digits would be prime, you can save time by excluding it as soon as you see there’s a 5 in there.  Similarly with numbers containing any even digits.

During the loop, I store every prime number to an array.  If it’s already in the array, then I know I don’t need to do it again.

At the end of the inner for loop, I increment my counter by the length of the number I’ve currently been looking at.  e.g. if I was on 197, which is prime, and its rotations 971 and 719 are also prime, I simply increment by 3.  I make a special exception for numbers like 11 where all the digits are the same, to make sure I don’t double-count it.

October 21, 2014

Project Euler problem 58 (PHP) – Spiral primes

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

AmmoniteI previously blogged about this Project Euler puzzle over 5 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 58:

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

Code:

<?php
require 'isPrime.php';

$numPrimes = 0;
$spiralLength = 1;
$number = 1;
$increment = 2;
$ratio = 100;

while ($ratio > 10) {
	$spiralLength += 2;

	// add our increment 4 times, calculating each time if it's prime
	for ($corner = 1; $corner <= 4; $corner++) {
		$number += $increment;

		// the 4th corner is never prime
		if ($corner < 4 && isPrime($number)) {
			$numPrimes++;
		}
	}
	
	$ratio = $numPrimes / ((2 * $spiralLength) - 1) * 100;
	
	$increment += 2;
}

echo $spiralLength;

Re-using the isPrime function from Problem 3.

Looping until we fall beneath a 10% ratio, adding up the numbers of primes along the corners of the spiral and calculating that amount as a ratio of the current length of the spiral’s side.

Next Page »

The Rubric Theme. Create a free website or blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 537 other followers