Archive     Blog     Cast     Forum     RSS     Books!     Poll Results     About     Search     Fan Art     Podcast     More Stuff     Random     Support on Patreon New comics Mon-Fri; reruns Sat-Sun
<   No. 3937   2019-02-26   >

1 Dwalin: Soo where do hobbits live? Oondergroond?
2 Lambert: We live in villages. The best houses are finely furnished shallow burrows, but many live in cottages.
3 Lambert: The village street layout is critical. They need to be arranged so you can visit every house without travelling the same street more than once.
4 Dwalin: Why?
4 Lambert: Otherwise the path won't be Hobbitonian!

 First (1) | Previous (3936) | Next (3938) || Latest Rerun (2139) | Latest New (4435) First 5 | Previous 5 | Next 5 | Latest 5 Fantasy theme: First | Previous | Next | Latest || First 5 | Previous 5 | Next 5 | Latest 5 This strip's permanent URL: http://www.irregularwebcomic.net/3937.html Annotations off: turn on Annotations on: turn off

Yep, it's been 100 strips since the last hobbit pun.

A Hamiltonian path is, in graph theory, a path that connects every vertex of a graph (or every house in a village, as a concrete example), without traversing any edge of the graph (or any street of the village) more than once.

Hamiltonian paths come up in the famous travelling salesman problem: Given a list of cities and the distances between them all, what is the shortest path that visits each city and returns to the starting point? This problem is an optimisation problem of finding a Hamiltonian path that visits the cities, with the extra constraint that the path must be the shortest possible Hamiltonian path. It is a well known problem in the field of computational complexity because it is a classic example of an NP-hard problem - a full explanation of which would require digging deep into the realms of computational complexity theory, but which may be summarised as being a problem that is incredibly difficult to solve as the number of cities increases.

Given that hobbits deal with this sort of problem all the time in their villages, one suspects that while it's a difficult optimisation problem, it's not a very difficult hobbitimisation problem.

I think you have discovered a major piece of Middle-earth anthropology - how the Shire kept its idyllic structure of scattered villages. Villages can only grow as long as its Hobbitonian-ness can be checked by brute force - that is, by hobbits wandering round visiting their friends while recording their path. Obviously, a new street cannot be built until this property has been checked, a task which becomes impossible when a village exceeds the optimum size.

 LEGO® is a registered trademark of the LEGO Group of companies, which does not sponsor, authorise, or endorse this site. This material is presented in accordance with the LEGO® Fair Play Guidelines.

My comics: Irregular Webcomic! | Darths & Droids | Eavesdropper | Planet of Hats | The Dinosaur Whiteboard | mezzacotta
My blogs: dangermouse.net (daily updates) | 100 Proofs that the Earth is a Globe (science!) | Carpe DMM (long form posts) | Snot Block & Roll (food reviews)
More comics I host: The Prisoner of Monty Hall | Lightning Made of Owls | Square Root of Minus Garfield | iToons | Comments on a Postcard | Awkward Fumbles