Halloween and the Traveling Salesman Problem

As I was a kid, this celebration was unknown in my home town. It became slowly famous after we saw it in American movies but even now the children are not going trick-or-treating. It’s only an excuse for teenagers to party.

I’m living in Germany since almost 4 years now but this year was the first time I personally experienced Halloween. At our previous flat no children came so we didn’t expect any this year at our new flat either. We didn’t buy any sweets and we were just minding our own business playing on the Xbox when we suddenly heard kids yelling in front of our window.

I didn’t even know at that moment that it was Halloween. A few seconds later we heard our doorbell ring. It must be a mistake, I thought. But then when I saw my boyfriend searching around for sweets in the kitchen, I realized that the kids came trick-or-treating and we had none! So the first little guy was unlucky because the only thing what we found in such a hurry was a chocolate bar used for baking! He probably cursed us after we closed our door.

But then I remembered that I had a bag of Bounty bars in my drawer hidden for emergency cases and as I mentioned this, it was immediately confiscated with the solemn promise that I will get the next day another one in return. I’m still waiting for it to this day.

Nevertheless, we had now the bag of Bounty bars, some bonbons and a few of oranges. We were ready! These came handy because 5-6 groups of children came till the end of the evening. This tradition was so new and scary for me that I was hiding in the bedroom the whole time until it was over.

This topic came into discussion yesterday morning on a coffee break. Everyone told their story, including me, but I was astonished to hear the childhood memories of a colleague from the US.

There’s a whole strategy that kids come up with for the Halloween night. They plan upfront which streets they want to cover, which houses they want to hit, who gives the best sweets to go there first before it runs out, which neighbors are older to go to them earlier before they go to sleep and so on. It’s a competition and, even though most of the sweets will be thrown away by their parents, children are running around to get the most.

This colleague of mine was 7 years old and unconsciously he was already dealing with the Traveling Salesman Problem. If you studied Computer Science, you must know this.

In this case, TSP consists basically of a list of houses and the distances between them. The problem is finding the most optimal route which covers each house exactly once in the shortest time possible. Isn’t it amazing that we were solving these kinds of problems even as we were small kids but we had no idea about it?

Related links: