Drinking your way around Dublin.
Let’s say that you wanted to go on a very ambitious pub crawl and drink a pint in every pub in Dublin. This seems like a reasonable enough goal and, being a reasonable person, you’d want to do it in as efficient a way as possible. You’d want to pick a starting point and go from pub to pub, being sure not to miss any out and without needless backtracking. Well in answer to that reasonable demand I’ve computed Dublin’s best pub crawl.
To begin with we need the names and locations of every pub in Dublin. Thankfully this isn’t hard to come by, you can go to Revenue.ie you can get a list of every pub in Ireland.1 This gives us the name, address, and some other info on each of the $6,778$ pubs in the Republic. Let’s first narrow our focus to Dublin,2 and the $521$ pubs in the city. We take those pubs and, using Google Maps, we find their exact locations – latitude and longitude.
Now that we have their locations we want to compute the most efficient closed path visiting each one. This is the classic traveling salesperson problem (TSP), which is known to be NP-hard. I’ve looked at this problem in a previous blog post, here where I computed an optimal road-trip around Ireland, and I’ll use the very same method to solve it in this instance.3
Once we’ve got the path we can use D3 to visualise it,
You can see the fullscreen map here, and here’s a version where the animation only plays once, making it a little easier to see the path.4 Finally here’s the full list with addresses in case you feel like giving it a try yourself.
In total the whole path takes in all of the pubs in around about $200$km. Bearing in mind that there are $521$ pubs, this means on average you’ll have to walk less than $400$m for your next pint.
For entirely arbitrary reasons (the main one being that I forgot about this distinction until I was about half way through the project) I have only selected pubs in Dublin city, i.e. with Dublin $N$ postcodes, and left out Co. Dublin. ↩
Since the problem is NP-hard I can’t guarantee that the solution I’ve computed is optimal, but it should be pretty good. ↩
Because of some browser issues the path may disappear in sections if you zoom really far in and pan around. This seems to be worse on Firefox than Chrome, but ymmv. ↩