Holiday Maths Problem #2 – Solution

So back in my previous post I discussed the problem of the Traveling Santa. He wants to deliver gifts as quickly as possible to seven different towns. At its essence, this is a Traveling Salesman Problem, a well known and very difficult problem in graph theory and combinatorial optimization. I decided to take my own crack at the problem and see if I could devise a solution.

I wrote a program to tell me the shortest Hamiltonian cycle through the 7 towns. I used the networkx library to set up my graphs and then generated a list of all the Hamiltonian cycles. Then using the weights provided by each edge I calculated the total distance for each of the paths. After that, I was able to narrow it down to the shortest ones.

One solution that my program found was the cycle that visits [7, 4, 2, 1, 5, 6, 3, 7] with a distance of 39. You can check out the code here, and I’d be interested to hear about your ideas or alternative implementations.

Advertisements

Holiday Maths Puzzle #2

Merry Christmas and Happy Holidays to everyone, I’m back with a new holiday themed puzzle to distract your mind away from annoying family members or holiday stress.

#2: Santa needs to deliver his presents, and fast! He has a map of the towns he needs to go to, but he doesn’t have much time left before Christmas is over! Help him deliver some last minute gifts in the shortest distance possible. You must visit every town at least once (duplicates are allowed, but for bonus points see if you can visit each town only once and still be as quick as possible). Each node in the graph is a town and the weight of each edge represents how far it is from one town to another. (Note: graph is not to scale)

Holiday Maths Puzzle #1

That time of year is upon us once again, and what better way to celebrate than by doing a few holiday-themed puzzles?

#1:  You brought home the perfect tree to decorate; however, it can only hold 10kg of decorations before the branches start to sag and it falls over. In addition, you can’t have too many items on the tree, there’s only so much space. Because of this, you only can hang 25 decorations of any kind at one time. These are the decorations you have available:

Type of Decoration	Weight (each)	Coverage (% of tree covered, each)
Tinsel (limit 1)	1kg	7%
Plastic Ornaments	0.1kg	1%
Glass Ornaments	0.4kg	5%
Angel Topper (limit 1)	2kg	10%
Popcorn String (limit 1)	0.75kg	6%
Icicle Hangers	0.25kg	3%
Lights (limit 1)	2.5kg	20%

We want to get the most covered tree we can without going over the weight limit. What is the lightest and most covered tree combination you can find?