Caffinated Hijinks

Not being a drinker myself, I’ve never understood the concept of your pub crawl. When I first heard the term, I had a mental image of a group of people traversing the many pubs around the city on their hands and knees. I asked someone about it some years later and was told that my imagery was probably pretty accurate. My philosophy in life is that all actions must serve some purpose, so me being what I am, my first question was: “What’s the point of that?”

At a conference dinner some years back I sat next to a coffee connoisseur (at least compared to my coffee drinking practices he passed for one) who seemed to hold the opinion that drinking instant coffee was a criminal offence. After listening at length about the merits of Italian coffee and the virtues of the cafes in my own city from this out-of-towner, I decided it was high time to lace up my trusty walking shoes and explore the labyrinthine lanes, mapping out all the little cafes with nothing but my nose to guide me.

I had the thought that I should go on a coffee crawl around the Melbourne CBD. I suppose it wouldn’t be a coffee crawl – more like a coffee jitter or a coffee sprint. I probably wouldn’t sleep for days afterwards. Perhaps I could use some graph theory to work out how to visit all the cafes but travel the least distance possible.

I decided to start my tally of Melbourne cafes with the one that the out-of-towner had recommended. A couple of doors or so from the conference venue he said. There were three cafes to the right and another two to the left, and a few across the street about 100 metres down. And this was only Queen Street, the street with the lawyers’ offices. By no means the Italian Lygon Street renown for its MANY cafes, or even the trendy Collins Street. By golly, we Melbournians must really love our coffee.

At this point it was obvious that visiting all the cafes in the least travel distance was not a viable thing to do. My 2-cups-a-day system would be overloaded with caffeine before I had even made it down the length of one block, let alone one street. Clearly, I needed a new strategy.

My cup of coffee

• Let us assume that there are m number of independent cafes in Melbourne CBD and its surrounds (within 2 km of the CBD).
• Let us also assume that there are N number of streets, alleys, thoroughfares, etc., in the Melbourne CBD and its surrounds. Denote the number of coffee places on each street, etc., by S _i, 0 <= S _i <= M where i = 1, ..., N is the number allocated to each street for identification purposes; M being the maximum number of cafes found on a street.
• Let x a positive integer represent the number of coffees drunk per trip. The total number of trips required to visit each independent coffee outlet would then be [m/x] =:T, where [ ] denotes the greatest integer function.
• Since the coffee jitter also serves as a Melbourne site-seeing tour, no street is visited more than once per trip. However, in the event that for any i = 1, ..., N, S _i > T, S _Lygon say, then for the minimum necessary number of trips, the journey begins from the middle of Lygon, traverses its set route for the day and comes full circle to the starting point.
• One chain of coffee shops is counted as one independent café. The shop on the street with the lowest number of independent coffee shops is the one that is visited.
• Visits to each street are made such that there is a significant lapse between visits, i.e., we do not visit the same street on successive trips, but at z trip intervals, where z is an integer with a value close to [T/ S _i ] .
• All journeys are unique and we seek a complete coffee jitter plan with a maximum variation of routes.

Conclusion: It would be easier to go on a pub crawl.