How Many Ways Round Bhaktapur’s Temples?

Use the map above.

• a.Make three or four round trips. Write down the shortest you find.
• b.Press Try every round trip. The page checks all 12 and draws the shortest in green. Did you find it?
• c.Look at the shortest trip. What does it do that your longer trips didn’t?

More temples

Now add temples one at a time and watch the number of round trips.

Counting the round trips

Start at the Nyatapola with four other temples to visit. You have 4 choices for the first. Then 3 are left for the second, 2 for the third, and 1 for the last. That makes 4 × 3 × 2 × 1 = 24 orders.

But a round trip and the same trip walked backwards are the same walk, the same length. Nyatapola → 2 → 3 → 4 → 5 → Nyatapola and Nyatapola → 5 → 4 → 3 → 2 → Nyatapola are one trip. So every trip has been counted twice, and there are 24 ÷ 2 = 12.

Multiplying a number by every whole number below it has a name: the factorial, written with an exclamation mark. 4! (“four factorial”) is 4 × 3 × 2 × 1 = 24. For n temples the round trips are (n − 1)! ÷ 2:

This grows faster than doubling. In “How many moves to move 64 disks?”, each extra disk doubled the work. Here each extra temple multiplies it by 5, then 6, then 7, then more each time.

Python, from Grade 8. First the length of one trip. Each temple is a pair of numbers, its place in meters east and north of a corner of the map, measured on OpenStreetMap. math.dist(a, b) gives the straight-line distance between two places. The trip goes back to its start at the end: (i + 1) % len(trip) is the next temple, and after the last it is 0, the first.

import math places = {    'Nyatapola': (943, 312),    'Siddhi Laxmi': (876, 390),    'Inaga Ganesh': (177, 308),    'Mahakali': (1141, 813),    'Dattatreya': (1532, 549),} def trip_length(trip):    total = 0    for i in range(len(trip)):        here = places[trip[i]]        there = places[trip[(i + 1) % len(trip)]]        total = total + math.dist(here, there)    return round(total) print(trip_length(['Nyatapola', 'Siddhi Laxmi', 'Inaga Ganesh', 'Mahakali', 'Dattatreya']))print(trip_length(['Nyatapola', 'Mahakali', 'Siddhi Laxmi', 'Dattatreya', 'Inaga Ganesh']))

30023855

The first is the shortest round trip, the second the longest. Check one of them on the map above.

Every round trip

Writing out every order by hand is slow. Python’s itertools module has permutations(things), which gives every order of a list, one at a time. (A permutation is one order of a set of things.) The program fixes the Nyatapola as the start, tries every order of the other four, and skips each trip walked backwards: of a trip and its reverse, it keeps only the one whose first temple comes before its last in the alphabet.

import mathfrom itertools import permutations places = {    'Nyatapola': (943, 312),    'Siddhi Laxmi': (876, 390),    'Inaga Ganesh': (177, 308),    'Mahakali': (1141, 813),    'Dattatreya': (1532, 549),} def trip_length(trip):    total = 0    for i in range(len(trip)):        here = places[trip[i]]        there = places[trip[(i + 1) % len(trip)]]        total = total + math.dist(here, there)    return round(total) names = list(places)count = 0best = Nonebest_length = 0for order in permutations(names[1:]):    if order[0] < order[-1]:        # each trip once, not also backwards        trip = [names[0]] + list(order)        length = trip_length(trip)        count = count + 1        print(count, ' → '.join(trip), length, 'm')        if best is None or length < best_length:            best = trip            best_length = lengthprint('Shortest:', ' → '.join(best), best_length, 'm')

1 Nyatapola → Inaga Ganesh → Siddhi Laxmi → Dattatreya → Mahakali 3155 m2 Nyatapola → Inaga Ganesh → Mahakali → Dattatreya → Siddhi Laxmi 3104 m3 Nyatapola → Inaga Ganesh → Dattatreya → Siddhi Laxmi → Mahakali 3855 m4 Nyatapola → Inaga Ganesh → Dattatreya → Mahakali → Siddhi Laxmi 3216 m5 Nyatapola → Mahakali → Inaga Ganesh → Dattatreya → Siddhi Laxmi 3781 m6 Nyatapola → Mahakali → Dattatreya → Inaga Ganesh → Siddhi Laxmi 3193 m7 Nyatapola → Dattatreya → Siddhi Laxmi → Inaga Ganesh → Mahakali 3641 m8 Nyatapola → Dattatreya → Siddhi Laxmi → Mahakali → Inaga Ganesh 3663 m9 Nyatapola → Dattatreya → Inaga Ganesh → Siddhi Laxmi → Mahakali 3753 m10 Nyatapola → Dattatreya → Inaga Ganesh → Mahakali → Siddhi Laxmi 3701 m11 Nyatapola → Dattatreya → Mahakali → Siddhi Laxmi → Inaga Ganesh 3076 m12 Nyatapola → Dattatreya → Mahakali → Inaga Ganesh → Siddhi Laxmi 3002 mShortest: Nyatapola → Dattatreya → Mahakali → Inaga Ganesh → Siddhi Laxmi 3002 m

Twelve trips, as you counted. Trying every possibility like this is called brute force: it always finds the best answer, because it never skips one.

How long would more temples take?

Now let the program time itself. This one uses ten temples as a list (numbered from 0, the Nyatapola) and checks every round trip of the first 5, 6, 7, 8 and 9. time.perf_counter() is a clock that counts seconds. From the last count it works out how many trips this computer checks in a second, and how long bigger lists would take at that speed.

import math, timefrom itertools import permutations temples = [(943, 312), (876, 390), (177, 308), (1141, 813), (1532, 549),           (1571, 732), (1584, 364), (1051, 169), (1700, 543), (1880, 948)] def trip_length(trip):    total = 0    for i in range(len(trip)):        total = total + math.dist(temples[trip[i]], temples[trip[(i + 1) % len(trip)]])    return total for n in range(5, 10):    start = time.perf_counter()    count = 0    best = None    for order in permutations(range(1, n)):        if order[0] < order[-1]:            length = trip_length((0,) + order)            count = count + 1            if best is None or length < best:                best = length    seconds = time.perf_counter() - start    print(n, 'temples:', count, 'trips in', round(seconds, 3), 's, shortest', round(best), 'm') per_second = count / secondsprint('This computer checks about', round(per_second), 'trips a second.')for n in [10, 15, 20, 25, 30]:    trips = math.factorial(n - 1) // 2    seconds = trips / per_second    years = seconds / (60 * 60 * 24 * 365.25)    if seconds < 60:        print(n, 'temples:', trips, 'trips, about', round(seconds, 1), 'seconds')    elif years < 1:        print(n, 'temples:', trips, 'trips, about', round(seconds / 3600), 'hours')    else:        print(n, 'temples:', trips, 'trips, about', round(years), 'years')

Your times depend on your computer, so they aren’t printed here. These are ours:

The times changed from run to run, in the web page by up to half, and a phone is slower still. The first run on a page is the slowest, while Python gets going. Change range(5, 10) to range(5, 11) to check 10 temples for real: it takes about nine times as long as 9, a second or so on a computer and several seconds on a phone.

The number of round trips, counted exactly by this short program (one more temple: times the number of temples before it):

orders = 1                       # 2 temples: 1 way to go on from the startfor n in range(3, 31):    orders = orders * (n - 1)    # a new temple: times the number before it    if n % 5 == 0:        print(n, 'temples:', orders // 2, 'round trips')

5 temples: 12 round trips10 temples: 181440 round trips15 temples: 43589145600 round trips20 temples: 60822550204416000 round trips25 temples: 310224200866619719680000 round trips30 temples: 4420880996869850977271808000000 round trips

• 5 temples have 12 round trips. You can try them all by hand.
• 10 have 181,440. Our office computer checks them in under half a second.
• 20 have 60,822,550,204,416,000, about 61 million billion. At our office computer’s speed that is about 3,000 years.
• 25 would take about 16 billion years, longer than the universe has existed (about 13.8 billion years). And Bhaktapur has far more than 25 temples.

That is the lesson: checking every possibility stops working very fast when the possibilities are orders. Programmers call this a combinatorial explosion. A computer a million times faster hardly helps: with 20 temples it would still need about a day, with 21 about three weeks, and with 22 more than a year. Problems like this one need cleverer ideas than trying everything.

The same problem comes up wherever something goes round many places and back: a delivery rider with parcels for 30 houses, a school bus picking up children, a machine drilling holes in a circuit board, a telescope turning from star to star. Its name is the traveling salesman problem: a salesman must visit every town on his list once and come home by the shortest route.

The nearest temple next

A quick rule a person would use: from where you are, always walk to the nearest temple you haven’t visited. A rule like this, which makes the best-looking choice at each step without looking ahead, is a greedy rule. It needs far fewer steps: with 1,000 temples, about half a million distances, done in a moment. Is it as good as trying everything?

import mathfrom itertools import permutations temples = [(943, 312), (876, 390), (177, 308), (1141, 813), (1532, 549),           (1571, 732), (1584, 364), (1051, 169), (1700, 543), (1880, 948)] def trip_length(trip):    total = 0    for i in range(len(trip)):        total = total + math.dist(temples[trip[i]], temples[trip[(i + 1) % len(trip)]])    return total def nearest_next(n):    trip = [0]    while len(trip) < n:        here = temples[trip[-1]]        best = None        for t in range(n):            if t not in trip:                if best is None or math.dist(here, temples[t]) < math.dist(here, temples[best]):                    best = t        trip.append(best)    return trip def shortest(n):    best = None    for order in permutations(range(1, n)):        if order[0] < order[-1]:            length = trip_length((0,) + order)            if best is None or length < best:                best = length    return best for n in range(5, 10):    print(n, 'temples: nearest next', round(trip_length(nearest_next(n))), 'm, shortest', round(shortest(n)), 'm')

5 temples: nearest next 3216 m, shortest 3002 m6 temples: nearest next 3369 m, shortest 3154 m7 temples: nearest next 3593 m, shortest 3355 m8 temples: nearest next 3623 m, shortest 3458 m9 temples: nearest next 3833 m, shortest 3648 m

The greedy rule is never the shortest here, but never more than about 7% longer, and it would finish 1,000 temples in a moment. Menger was right in 1930. Real route planners start from a quick trip like this and then improve it, for example by undoing every place where the trip crosses itself.

Walking the lanes

Our distances are straight lines. Walking, you follow Bhaktapur’s lanes, so every distance is longer, and the shortest trip might change. But the number of trips to check is just the same: the counting never looked at the distances.

★ Count the round trips (blocks)

The program counts k from 2 up to the number of temples. Finish it so that, when you type the number of temples, it says how many round trips there are and nothing else (5 temples: 12). Then press Test.

★★ How long is the trip? (Python, from Grade 8)

Write trip_length(trip, places). places is a dictionary of temple names and their (x, y) places in meters; trip is a list of names in the order visited, starting at the start. Give back the length of the round trip, back to the start included, rounded to the nearest meter.

import math def trip_length(trip, places):    # give back the round trip's length in meters    return 0 print(trip_length(['A', 'B', 'C'], {'A': (0, 0), 'B': (300, 0), 'C': (300, 400)}))

★★★ The shortest round trip (Python, from Grade 8)

Write shortest_trip(places): give back the length, to the nearest meter, of the shortest round trip that visits every place in the dictionary once and comes back to where it started. The tests have up to 8 places.

import mathfrom itertools import permutations def shortest_trip(places):    # every place once, back to the start; the shortest length in meters    return 0 print(shortest_trip({'A': (0, 0), 'B': (300, 0), 'C': (300, 400), 'D': (0, 400)}))

• Grade 8, Repeating with for: the loops these programs are built from.
• Grade 8, Lists: the lists that hold a trip.
• Grade 9, Exponential: every group: work that doubles, and how computer scientists name the ways work grows.
• How many moves to move 64 disks?: a puzzle whose work doubles with each disk.
• Can four colors paint any map of Nepal? Another map, another problem where trying everything is too slow.