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 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 Imgur

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

A good conversation already began in the other thread, but feel free to trade notes and discuss your programs in this thread or in other Notes.

Thanks to everyone for participating!

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
list

Note: you must add a full line of space before and after lists for them to show up correctly

paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)

example link

> This is a quote

This is a quote

    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"

# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"

Math

Appears as

Remember to wrap math in $ ... $ or \[ ... \] to ensure proper formatting.

2 \times 3

2 \times 3

2^{34}

2^{34}

a_{i-1}

a_{i-1}

\frac{2}{3}

\frac{2}{3}

\sqrt{2}

\sqrt{2}

\sum_{i=1}^3

\sum_{i=1}^3

\sin \theta

\sin \theta

\boxed{123}

\boxed{123}

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

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!

Cheng Sun - 7 years, 4 months ago

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

Arron Kau Staff - 7 years, 4 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! ;)

Ammar Fathin Sabili - 7 years, 4 months ago

Can you organize more competitions like this?

Daniel Lim - 7 years, 4 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.

Ivan Stošić - 7 years, 4 months ago

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

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!

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

Petko Petkov - 7 years, 4 months ago

Congrats to both Shreenath & Chen

Vikram Pandya - 7 years, 4 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.

Sayan Chaudhuri - 7 years, 4 months ago

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

Sanjay Meena - 7 years, 3 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$