×

# Winners Announced! "Around The World In 80 Hours" Competition Results

Behold! The winning path through all 339 cities(as drawn up by Cheng Sun). For a description of the competition, see here.

## Grand Prize Winner:

Sreenath

*Sreenath Are *(17 — U.S.A.)

Route Distance: 217130 km Submission Time: 26 Jan 2014 17:36 GMT Programming Language: C++

Sreenath’s program is available here

He will receive a brand new Android tablet, a winner’s certificate, a Brilliant.org t-shirt, and some secret awesome prizes.

## Runner Up:

ChengSun

Cheng Sun (17 — U.K.)

Route Distance: 217130 km (same route as winner) Submission Time: 26 Jan 2014 22:40 GMT Programming Language: Python

Cheng’s program is available here

He will receive a certificate and a Brilliant.org t-shirt.

From opposite sides of the Atlantic, Sreenath and Cheng found the same route through different programming languages. Sreenath edged out a victory by submitting 5 hours ahead of Cheng. We think their routes are pretty impressive given the surprise nature of the competition, and the short time frame to submit a program.

Below are some summary statistics to give you sense of the overall shape of the competition.

Total Number of Valid Entries: 45

Mean Route Distance: 299 696 km

First Quartile: 236 642 km

Median: 258 891 km

Third Quartile: 279 591 km

Distribution of route lengths (log scaled):

distribution

Graph of individual entry lengths:

Imgur

We hope you enjoyed exploring a well known problem and claiming some sense of ownership of it for yourself. We sincerely wish that we could have awarded all participants free air travel along the winning route to all 339 cities. Alas, the brilliant.org private jet hasn't been built yet...

Imgur

So we have to settle for giving out material things to a winner and a runner up.

Thanks to everyone for participating!

Note by Peter Taylor
3 years, 8 months ago

Sort by:

Many congratulations to Sreenath! Funny that we independently found exactly the same tour. Maybe we'll meet along the tour in the future :)

A few notes on my approach: I tried several approaches, though ironically it was my first approach that worked the best.

• At first, I generated a greedy path as a starting point (see the function greedy). I sorted every single edge of the graph by length and kept taking the shortest edge that was valid to take.

• The first, and (disappointingly) the winning strategy, was to simply use 2-opt search with random perturbations. I kept applying 2-opt moves until a starting graph was 2-optimal (see do2opt), meaning that no more 2-opt moves can be made to improve the tour. Then, I randomly swap the order that two cities were visited in, and 2-optimise it again. This is done from the current best tour until I get a further improved tour. (see random2)

• I then tried to implement 3-opt search, with little success. I think I got the loop a bit wrong, but it gave inferior results to 2-opt(which should be impossible, as all 3-optimal tours are also 2-optimal). This was on top of it being horrifically slow. I tried using candidate lists, which sped things up, but that didn't make the actual 3-opt search correct!

• Because 2-opt is a local search technique, it can get trapped in local minima. I implemented simulated annealing to try to overcome this, where sometimes (depending on the "temperature") I would accept an inferior tour just to try to jump out of a local minimum. Unfortunately there was a tradeoff between the quality of the tour and how slowly I cooled the system, and running it for half an hour did not net any better results than the winning tour that I had previously achieved.

• I then looked around and just for fun decided to implement Ant Colony optimisation, where I simulated a bunch of ants wandering around the world and spreading pheromones along the best tours. This ended up being a fickle mess, because there were lots of tweakable parameters in the ant behaviour, and I didn't have the time to tune the system to give me ultimate ant world domination :( It was fun to code, though.

• Throughout all my experimentation my code always saved the best tour to disk on termination, so that I could kill the program half-way through, twiddle the code a bit, and resume the search later on. It also meant I could back up the best paths I had found. It meant I was never afraid to try something new, and lose the tours I had before.

In future I might investigate going directly for the optimal solution, by using branch-and-bound or some variant of that. I wasn't confident that I would get that working (fast enough) for this competition though.

(Apologies for the messy coding, if you're reading along. Also, in both of our codes, the double quotes seem to have been mangled: each " is transformed into two "".)

Anyway, I enjoyed this a lot, hope to see more competitions like it on Brilliant!

- 3 years, 8 months ago

I've fixed the wrong quote marks in both source code files. Thanks!

Staff - 3 years, 8 months ago

Oh, wow, my solution is exactly on median, lol.

Congrats to the winners! Congrats also to all of the participants to get their best! :D

Thanks for Brilliant to make this competition, and we are looking forward to your next challenges! ;)

- 3 years, 8 months ago

Can you organize more competitions like this?

- 3 years, 8 months ago

I'm a bit disappointed that there are no honorable mentions. Also, in my opinion, Cheng's code is much more elaborate and interesting.

- 3 years, 8 months ago

Hm, yeah, that's pretty disappointing. I'd be interested to see your code, and what your approach was though.

- 3 years, 8 months ago

Thanks to both of you for participating. As one of the staff who looked through the results, I can say that we felt it was appropriate to give honorable mention to Cheng, not only because his result was tied for first but also because his code showed several nice approaches to the problem.

While several other participants had good code and similar results, we didn't see anything that really struck us as contributing more to the community than posting the two winners listed here. Interestingly, several of the top results used professional software to solve the problem (Concorde TSP solver, Mathematica) but still didn't get better results than our two winners!

Staff - 3 years, 8 months ago

Congratulations to the winners!. I hope to see and participate in more competitions soon :).

- 3 years, 8 months ago

Congrats to both Shreenath & Chen

- 3 years, 8 months ago

congrats to both the winner and runner up.Could anyone post here the code in c as i don't know any other language?If anyone has solved this problem in C then please post it...Thanks,in advance.

- 3 years, 8 months ago

hey can you tell me which c++ compiler did you used..

- 3 years, 7 months ago