Duncan's blog

March 21, 2015

Google Maps API – locked draggable markers

Filed under: Google Maps,Javascript — duncan @ 1:53 pm
Tags: , , ,

This is a nice simple post, inspired by a recent question on StackOverflow:

How to check if marker is out of specific constant bounds?

In summary, the user had defined a bounds, and wanted users to be able to drag a marker, but not outside of those bounds.

So firstly, you can simply use the LatLngBounds contains’ function to determine if a point is within those bounds.  And you can have an event listener for when the user drags the marker.  Usually you’d just want to check for the dragend event, when they stop dragging.

In this example I’ve drawn a semi-transparent rectangle using the bounds, so it’s obvious the area where you can drag your marker in.

I also keep track of the coordinates the marker had when they start dragging it.  If they go outside of the bounds, I reset it to that position.

Initial state of the map:

bounds map1

And after the user drags the marker outside of the bounds:

bounds map2

Here’s the code:

<!DOCTYPE html>
<html>
<head>
	<title>Locked draggable markers</title>
	<meta name="viewport" content="initial-scale=1.0, user-scalable=no">
	<meta charset="utf-8">
	<style>
		#map {
			width: 640px; height: 480px;
		}
	</style>
	<script src="https://maps.googleapis.com/maps/api/js?v=3"></script>
	<script>
		function initialize() {
			var bounds = new google.maps.LatLngBounds(
				new google.maps.LatLng(51.5089872,-0.155157), 
				new google.maps.LatLng(51.599285,0.032984)
			);
			
			var map = new google.maps.Map(document.getElementById("map"), {
			  center: bounds.getCenter(),
			  zoom: 13,
			  mapTypeId: google.maps.MapTypeId.ROADMAP
			});
			
			map.fitBounds(bounds);
			
			var rectangle = new google.maps.Rectangle({
				bounds: bounds,
				map: map,
				fillOpacity: 0.2,
				fillColor: 'blue',
				strokeOpacity: 0
			});
					 
			var marker=new google.maps.Marker({
				map: map,
				position: bounds.getCenter(),
				draggable: true
			});
				
			var markerPosition;

			google.maps.event.addListener(marker, 'dragstart', function() {
				markerPosition = this.getPosition();
			});

			google.maps.event.addListener(marker, 'dragend', function() {
				if (bounds.contains(this.getPosition()) == false) {
					alert("You've dragged the marker outside of the bounds allowed. We've reset it");
					
					this.setPosition(markerPosition);
				}
			});
		}
		
		google.maps.event.addDomListener(window, 'load', initialize);
	</script>
</head>
<body>
	<div id="map"></div>
</body>
</html>

You’ll noticed I’m only declaring coordinates for the Bounds, and then getting the Bounds’ centre, and using that to plot the centre of the map and the initial coordinates for the marker.  And then making the map fit the bounds object.

One interesting note; The Google Maps API has started accepting coordinates in a lot of its classes in this shorthand format:

 {lat: x, lng: y}

… instead of having to create a new LatLng object every time:

 new google.maps.LatLng(x, y)

However, this doesn’t seem to work (yet) with the Bound class.

 

Secondly, as well as a bounds object, it might be useful to do the same thing on a polygon that you’ve drawn on the map.  This is slightly more complicated; the google.maps.Polygon class hasn’t got a contains event.  However the Geometry library does.  You need to load it in when you specify the Maps API URL:

<script src="https://maps.googleapis.com/maps/api/js?v=3&libraries=geometry"></script>

Here I’ve just plotted a polygon roughly corresponding to the border of Utah:

Locked_draggable_markers_-_2015-03-21_13.34.50

I construct that initially as an array of LatLng points.

var boundary = [
    new google.maps.LatLng(41.987058, -114.007506),
    new google.maps.LatLng(41.987058, -111.063170),
    new google.maps.LatLng(40.999595, -111.063170),
    new google.maps.LatLng(40.999595, -109.041686),
    new google.maps.LatLng(37.005844, -109.063658),
    new google.maps.LatLng(37.005844, -114.051451)
];

I then loop over the array, adding each coordinate to a bounds object.

var bounds = new google.maps.LatLngBounds();

for(var i = 0; i < boundary.length; i++) {
    bounds.extend(boundary[i]);
}

Then I use the array of coordinates (not the bounds), to plot the path for a polygon object.

var polygon = new google.maps.Polygon({
    paths: boundary,
    map: map,
    fillOpacity: 0.2,
    fillColor: 'blue',
    strokeOpacity: 0
});

And finally just a slight change to the event listener, to check if the polygon contains the marker’s position.

google.maps.event.addListener(marker, 'dragend', function() {
    if (google.maps.geometry.poly.containsLocation(this.getPosition(), polygon) == false) {
        alert("You've dragged the marker outside of the bounds allowed. We've reset it");
            
        this.setPosition(markerPosition);
    }
});

Nice and simple!

January 22, 2015

Animated paths with Google Maps

Filed under: Google Maps,Javascript — duncan @ 6:39 pm
Tags: , ,

I saw this question on StackOverflow a few days ago.  There was a map with animated polylines being drawn along a set of coordinates, with a minor bug in it.  The very next day I saw another question asking how to animate a route on a map.  I thought the approach I’d seen the day before was ideal, and posted a slightly re-written version of it as an answer. I thought there was enough merit in the technique used to turn it into a blog post.  Thanks to the OP Alex Man for the original version of the code.

Version 1

Animated_route_-_2015-01-22_18.35.41

function initialize() {
	var map = new google.maps.Map(document.getElementById("map"), {
	  center: {lat: pathCoords[0].lat, lng: pathCoords[0].lng},
	  zoom: 11,
	  mapTypeId: google.maps.MapTypeId.ROADMAP
	});
	
	autoRefresh(map);
}

function moveMarker(map, marker, latlng) {
	marker.setPosition(latlng);
	map.panTo(latlng);
}

function autoRefresh(map) {
	var i, route, marker;
	
	route = new google.maps.Polyline({
		path: [],
		geodesic : true,
		strokeColor: '#FF0000',
		strokeOpacity: 1.0,
		strokeWeight: 2,
		editable: false,
		map:map
	});
	
	marker=new google.maps.Marker({map:map,icon:"http://maps.google.com/mapfiles/ms/micons/blue.png"});

	for (i = 0; i < pathCoords.length; i++) {
		setTimeout(function (coords)
		{
			var latlng = new google.maps.LatLng(coords.lat, coords.lng);
			route.getPath().push(latlng);
			moveMarker(map, marker, latlng);
		}, 200 * i, pathCoords[i]);
	}
}

google.maps.event.addDomListener(window, 'load', initialize);

var pathCoords = [
	{
	"lat": 8.893260000000001,
	"lng": 76.61427
	},
	{
	"lat": 8.894430000000002,
	"lng": 76.61418
	},
	// etc for hundreds more coordinates

View full code

The interesting bit here is the ‘autoRefresh‘ function.  That creates an empty polyline, then loops over the global pathCoords array.  For each set of coordinates, it creates a call to this anonymous function, at 200 millisecond intervals:

function (coords) {
	var latlng = new google.maps.LatLng(coords.lat, coords.lng);
	route.getPath().push(latlng);
	moveMarker(map, marker, latlng);
}

So every 200 milliseconds it calls that function.  When using setTimeout I pass in a third parameter, which is a single set of coordinates.  I’m not sure this is an ideal approach, for instance if something in that function took longer than 200ms to execute, things could get a bit disjointed looking.  But it seems to work for now.

For each set of coordinates, it adds it to the current polyline’s path.  You might have thought I’d have to use setPath, but just pushing it onto the array that getPath returns works.

Then I update the position of the marker to the current point, and pan the map.

One thing worth noting: Google Maps have started accepting coordinates in this format in a lot of places:

	{lat: 1.234, lng: 2.345}

instead of having to always create new LatLng objects each time:

	new google.maps.LatLng(1.234, 2.345)

In the example above, the coords object was fine when passed straight to the moveMarker function, i.e. for setting the marker and panning the map.  However it didn’t work when pushing it into the array of the polyline’s path.  So I still had to create a LatLng object for that.  Possibly if I’d saved the polyline path from getPath into a variable, appended the coords parameter, then done setPath with the full array, it would have been fine.

See the map working here

Version 2

Animated_route_-_2015-01-22_18.36.08

Instead of having to hardcode hundreds of coordinates in our javascript, we can use the DirectionsService, simply specifying a start and end point.  The data it returns includes a list of all the coordinates we’d need.  Then instead of rendering the directions, we can simply use those coordinates to draw our own animated path.

function initialize() {
    var map = new google.maps.Map(document.getElementById("map"), {
      center: {lat: 51.5087531, lng: -0.1281153},
      zoom: 7,
      mapTypeId: google.maps.MapTypeId.ROADMAP
    });
    
    getDirections(map);
}

function moveMarker(map, marker, latlng) {
    marker.setPosition(latlng);
    map.panTo(latlng);
}

function autoRefresh(map, pathCoords) {
    var i, route, marker;
    
    route = new google.maps.Polyline({
        path: [],
        geodesic : true,
        strokeColor: '#FF0000',
        strokeOpacity: 1.0,
        strokeWeight: 2,
        editable: false,
        map:map
    });
    
    marker=new google.maps.Marker({map:map, icon:"http://maps.google.com/mapfiles/ms/micons/blue.png"});

    for (i = 0; i < pathCoords.length; i++) {                
        setTimeout(function(coords) {
            route.getPath().push(coords);
            moveMarker(map, marker, coords);
        }, 200 * i, pathCoords[i]);
    }
}

function getDirections(map) {
    var directionsService = new google.maps.DirectionsService();

    var request = {
        origin: new google.maps.LatLng(51.5087531, -0.1281153),
        destination: new google.maps.LatLng(48.8583694, 2.2944796),
        travelMode: google.maps.TravelMode.DRIVING
    };
    directionsService.route(request, function(result, status) {
        if (status == google.maps.DirectionsStatus.OK) {
            autoRefresh(map, result.routes[0].overview_path);
        }
    });
}

google.maps.event.addDomListener(window, 'load', initialize);

See the second map working here

Again, I wasn’t able to just use a coords struct, I had to create LatLng objects for passing into the DirectionsService request. The directions service happens asynchronously, so I have to wait for when it returns back an ‘OK’ status before creating the path.

Apart from replacing the array of coordinates with the value returned by the DirectionsService’s overview_path property, the code for drawing the path is basically the same as before.

Further ideas:

  • Instead of just creating a polyline from all the coordinates in the overview_path, we could loop over all the legs of the route.  This would give us more flexibility to amend the polyline, e.g. you could examine the duration property of each DirectionsStep and change the colour of the polyline.
  • We could use the bounds property of the DirectionsRoute to update the map’s bounds so the entire route is always visible.  Doing this you wouldn’t need to constantly pan the map centre.

January 5, 2015

Bristol coffee shops

Filed under: Coffee — duncan @ 8:00 am
Tags: , , ,

After a recent trip to Bristol, in keeping with previous articles on coffee shops in Dublin, New York, Zagreb and  New Zealand and Australia, I thought I’d do a write-up for some cafés we went to.

Playground Coffee House

45 St. Nicholas Street

The first place we called at was the Playground Coffee House.  It hadn’t opened for the morning, we were slightly too early, but we were still able to get some very nice coffees.  It looked like a fun place to go; from the usual like board games, to the unusual like, er, swings for seats.  Which come with their own warning, they maybe don’t mix too well with hot drinks!

The barista was very friendly, and recommended to us a few of the other best coffee shops in town.

P1010287 P1010288 P1010289 P1010291 P1010293

Facebook / Twitter

Reviews:

Bear Pit Social

St. James Barton Underpass

This place is housed in a converted shipping container, in the, er, interesting location of the Bearpit, aka the St. James Barton Roundabout underpass… not as bad as it sounds.  In fact they had quite a nice little seating area in one corner, and they were doing food in addition to the coffees.

P1010303

Facebook / Twitter

Reviews:

Spicer and Cole

1 Queen Square Avenue

Spicer and Cole was listed on our map, out in Clifton.  We didn’t go there, but they also had a branch in the centre, on Welsh Back, very close to Queen Square.  I overheard someone in the street raving about it to a couple who were looking for somewhere to eat.  I went there a couple of times; the coffee was ok; we had some nice Sunday breakfast.

P1010463 P1010465 P1010466

Website / Facebook / Twitter

Review:

Full Court Press – Speciality Coffee

59 Broad Street

Full Court Press I visited a couple of times.  The name’s apparently a basketball reference.  They seemed to take their coffee pretty seriously (as their sub-title would imply), and both times the baristas gave me good descriptions of the choice of beans available.

P1010434 P1010435 P1010585 P1010586

WebsiteFacebook / Twitter / Pinterest

Reviews:


I intended to visit some of these too, but unfortunately they were all closed on the Sunday:

  • Didn’t You Do Well
  • Workhouse Cafe
  • Small Street Espresso

The coffee map I bought in Playground was very useful; I’d recommend it if you were on a trip to Bristol and wanted to visit a few different cafés.  It listed 24 different places to go, with lots of information and an attractively-designed map.

Website / Twitter

(when I first checked the website was fine; but it seems be offline right now).

January 1, 2015

2014 in review

Filed under: Uncategorized — duncan @ 7:00 am

The WordPress.com stats helper monkeys prepared a 2014 annual report for this blog.

Here’s an excerpt:

The concert hall at the Sydney Opera House holds 2,700 people. This blog was viewed about 37,000 times in 2014. If it were a concert at Sydney Opera House, it would take about 14 sold-out performances for that many people to see it.

Click here to see the complete report.

December 18, 2014

Project Euler: problem 46 – Goldbach’s other conjecture

Filed under: PHP,Project Euler — duncan @ 11:57 pm
Tags: , , ,

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

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

This was another of those problems that I’d initially passed over, having decided it looked a bit tricky.  Then looking at it again realised it probably wasn’t too difficult.  And I turned out to be right!

A composite number is basically any positive integer that isn’t a prime number.

My logic is simply:

  • Loop through odd numbers, from 3 upwards.
  • For each number, if it’s prime, add it to an array of primes for later reference.
  • If it’s not prime, work out if it matches the conjecture:
    • Subtract the next largest prime, then examine the remainder
    • Divide the remainder by 2.  if it’s a square number then we’re meeting the conjecture.  Move onto the next odd number.
    • Otherwise keep subtracting the primes, checking the remainders.
    • If we’ve looped through all the primes then we must have reached a number that doesn’t meet the conjecture.

This runs in about 40ms:

<?php
$primes = [2];

$i= 1;

while (true) {
	$i+= 2;

	if (isPrime($i)) {
		$primes[] = $i;
	} else {
		for($j = count($primes)-1; $j > 0; $j--) {
			$remainder  = $i - $primes[$j];
			$remainder = $remainder / 2;
			$root = sqrt($remainder);
			if ((int) $root == $root) {
				continue 2;
			}
		}
		
		echo $i;
		break;
	}
}


function isPrime($x)
{
	$root = sqrt($x);
	
	for ($i = 3; $i <= $root; $i += 2) {
		if ($x % $i == 0) {
			return false;
		}
	}
	
	return true;
}

I’m using a modified version of my original isPrime function, just because I know I don’t need to check for even numbers.

The loop backwards through the primes was maybe a bit of overkill; using a simple foreach loop through the primes in ascending order took more like 100ms.

What else… I check if a square root is the same as when it’s cast to an integer (not sure this is the best approach).  Then use continue 2; to get out of our inner-most loop and move onto the next value in our parent loop.

December 14, 2014

Project Euler: problem 33 (PHP) – Digit cancelling fractions

Filed under: PHP,Project Euler — duncan @ 10:54 pm
Tags: ,
Fractions

Picture by jessicakelly

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

The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, 30/50 = 3/5, to be trivial examples.

There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.

If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

It took me a couple of tries to get this, I think as the question doesn’t give enough details about what the rules are for anomalous fraction cancellation.

Supposing we say our fractions are of the form ab / cd.  Initially I was checking each of the following:

  • a / c = ab / cd
  • a / d = ab / cd
  • b / c = ab / cd
  • b / d = ab / cd

i.e. each possible combination of the first and second numerator and denominator digits.

Then I realised I could omit two of these, as we didn’t want to look at those cases where it’s the first numerator digit divided by the first denominator digit, or the second numerator digit divided by the second denominator digit.  Reducing what I was checking down to:

  • a / d = ab / cd
  • b / c = ab / cd

So I was now just looking at the first numerator over the second denominator, and the second numerator over the first denominator.  However this was still giving me too much possible fractions.  Further reading illustrated that the example given, 49 / 98, where the second numerator digit and the first denomator digit are cancelled out, is the rule for all cases.  Reducing what I was checking to just:

  • a / d = ab / cd

The question also doesn’t really explain what else you can ignore.  Firstly if either digit is zero.  Secondly, the trivial examples include where a = b and c = d, e.g. 11 / 22.

And finally, I thought you could look at any values for ab and cd, e.g. I’d got 16 / 96 = 1 / 6.  But this meant I’d still got more than four ‘matching’ fractions.  What the question failed to mention is that the digits being cancelled out had to be identical, so really what I was checking was changed to:

  • a / c = ab / bc

Once I’d got all that cleared up, it was easy.

<?php
$product = 1;

for ($numerator = 10; $numerator <= 99; $numerator++) {
	for ($denominator = $numerator+1; $denominator <= 99; $denominator++) {
		$fraction = $numerator / $denominator;
		
		$numeratorAsString = (string)$numerator;
		$denominatorAsString = (string)$denominator;
		
		if (
			!isTrivial($numeratorAsString, $denominatorAsString) && 
			$numeratorAsString[1] == $denominatorAsString[0] && 
			$numeratorAsString[0] / $denominatorAsString[1] == $fraction
		) {
			$product *= $fraction;
		}
	}
}

function isTrivial($numerator, $denominator) {
	if ($denominator[1] == 0) {
		return true;
	}
	
	if ($numerator[0] == $numerator[1]) {
		return true;
	}
	
	return false;
}

echo $product;

I cast my numerators and denominators to strings, enabling me to then reference the digits within each using array notation.

Some useful links:

December 10, 2014

Project Euler: problem 27 (PHP) – Quadratic primes

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

Photo by Ianqui Doodle

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

Euler discovered the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

The incredible formula  n² − 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

n² + an + b, where |a| < 1000 and |b| < 1000
where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |−4| = 4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

This was another puzzle I’d ignored previously, then looked at it again and realised it wasn’t that hard after all.  First time I’ve really done anything with quadratics since school probably!

<?php
include 'isPrime.php';

$maxPrimes = 0;
$maxCoefficients = [];

calculatePrimes(1, 1);
calculatePrimes(1, -1);
calculatePrimes(-1, 1);
calculatePrimes(-1, -1);

function calculatePrimes($incrementA, $incrementB) {
	global $maxPrimes;
	$a = 0; 
	while (abs($a) < 1000) {
		$b = 0;
		while (abs($b) < 1000) {
			$n = 0;

			while (true) {
				$q = ($n * $n) + ($n * $a) + $b;
				
				if (!isPrime($q)) {
					if ($n > $maxPrimes) {
						$maxPrimes = $n;
						setMaxCoefficients($a, $b);
					}
					break;
				}
				
				$n++;
			}
			$b+= $incrementB;
		}
		$a+= $incrementA;
	}
}

function setMaxCoefficients($a, $b) {
	global $maxCoefficients;
	$maxCoefficients = [$a, $b];
}

echo $maxCoefficients[0] * $maxCoefficients[1];

So I’ve wrapped up most of the code into one function, which I call four times.  Each time I’m either adding or subtracting 1 from each of the two coefficients.  Then there’s nested loops so we’re going from zero to +/- 999 for both coefficients.  Within that we loop again, incrementing $n until our quadratic equation doesn’t return a prime number.  At that point, we check if the value of $n is more than the previous maximum number of primes.  And if it is, I update a global array with those coefficients.

After we finish looping, I then calculate the production from those stored coefficients.  Simple, but not particularly fast.

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.

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.

 

Next Page »

The Rubric Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 542 other followers