Category Archives: Computational Thinking

The Paper Round: The Best Route for a Marginal Gain

The current route (blue) is very inefficient because it doesn’t offload papers very quickly. It takes 4 units of distance (hops) to offload just 3 papers, and we still have 3 papers in the bag at H (hop 8) just 2 hops from the finish. If we take advantage of the fact that H is a block of flats where we delivery two papers, and head straight for that delivery (via D) then we can get rid of three papers in just two hops. This is the pink route on the map below.

Paper round best routeFrom H we cycle on to I, where we have a choice of routes to deliver the remaining five papers. Neither loop offloads papers faster than the other, so the decision here should be based on which offloads the heaviest paper/s first. E has the Telegraph, and J the Daily Mail if I recall, so lets take the loop that offloads the Telegraph first.

Bye the time we get to J (hop 8) we have delivered all our papers and have the luxury of cycling the final two hops with a paper free bag.

The marginal gains of the new route are probably best illustrated in a table.

Blue route Papers in bag Pink route Papers in bag
A
B
E
B
C
F
J
I
H
D
H
8
7
6
6
5
4
3
3
1
0
0
A
D
H
I
E
B
C
F
J
I
H
8
7
5
5
4
3
2
1
0
0
0
Hops = 10 Total Papers in bAG =  43 hOPS = 10 Total pAPERS IN BAG = 35

This may not look like a huge advantage, but remember these are the sort of ‘marginal gains’ British Cycling and Team Sky search for in the pursuit of Olympic gold and Tour de France glory. Just steer clear of the TUEs, unless you wake up with a bad cold!

FacebookTwitterGoogle+Share

The Paper Round: A Real World Exercise in Computational Thinking

Paper bag While doing my stepson’s paper round for him this morning, I couldn’t help but think the end part of the round seemed a bit inefficient.

Surely we can shave some time off the round by delivering these papers in a different order I thought. A little computational thinking (graph theory in this case) will reveal a shorter route is possible…

…so I drew a map (graph) of the current route, labelling the road junctions and mid points (called nodes or vertices in graph theory) A to J and marking the houses where papers are delivered with an X.

Paper round graph

The route must start at node A (there are papers to deliver just before we reach A) and finish at node H (the closest point to home).

The current route (blue arrows) A – B – E – B – C – F – J – I – H – D -H  has a total distance of 10 units, assuming the distance between each node is the same, which give or take a few metres it is. But I can’t beat 10 units!!! There is no shorter route.

But is there a marginal advantage to be gained by delivering the papers in a different order?

Given that newspapers are very heavy these days (especially on a Saturday and Sunday) which route minimises the number of papers in the bag and allows me (or my stepson) to cycle that bit faster? Can you prove which route is best? We always start with 8 papers at node A.

The Kayaker’s Conundrum: Solutions

Kayakers on the river Adur

Many thanks to everyone who suggested solutions to this conundrum.

It would appear there are two algorithms you can can follow to solve it. Your choice of algorithm depends on whether you live near the start or finish of the paddle. Either way, you only need one bike.

 

Algorithm 1: If you live near the start:

  1. Drive to the start, drop the two kayaks off. One of you stays with the kayaks.
  2. The other person drives to the finish, leaves the car there, then cycles back to the start and locks up the bike.
  3. You both paddle down the river to the finish.
  4. You both load the kayaks onto the car and drive back to the start.
  5. Unlock the bike, load it onto the car, and drive home.

Algorithm 2: If you live near the finish:

  1. Drive to the finish and lock the bike up.
  2. Drive to the start and unload the kayaks.
  3. You both paddle down the river to the finish.
  4. One of you stays with the kayaks, while the other unlocks the bike, cycles back to the start and loads the bike onto the car.
  5. Drive back to the finish, load the kayaks onto the car, and drive home.

Both algorithms work, whether you live nearer the start or the finish, but choosing the wrong algorithm could result in driving twice the distance you need to. Imagine the distance (by road) between start and finish is 10km, and you live at the start. Algorithm 1 will result in 20km of driving, while algorithm 2 will result in 40km of driving. If you live at the finish, it’s the reverse.

If you live midway between start and finish it doesn’t matter which algorithm you choose. they both involve 30km of driving.

So a little logic (‘selection’ in programming speak) is required before the correct algorithm is chosen:

IF home to start < home to finish

algorithm 1

ELSE

algorithm 2