Coding Challenge Wrap-Up: Who Won the Map

Roman Trade Network

Compared to our previous coding challenges, May’s was a modest affair, with just three entries coming in from Rick Matter, Jon Pattinson and Jay Nagel. And, despite opening the entries to include Delphi, Go and Python as well as C/C++, Java and C#, all three were written in Java! (You can find all the competition files here.)

In this challenge, you were given a 20×20 map that contained 20 trading islands, each occupying a square. Each island was a trading port for gold, iron and wood. The goal was to sail your ship from the top left square and eventually end up at the bottom right having earned as much as possible.

Click here to see Java jobs.

Although the competition was straightforward, it was never going to be an easy one, as there were so many different routes available and the map used to test software was not the one used for the competition. Also, the competition’s map had a flaw, which only came out when Rick’s software crashed. It seems I had put two of the islands close enough that a ship could be set next to both. This would be the perfect arbitrage situation–just buy the cheap commodity from one island and immediately sell it to the other at a higher price without having to sail anywhere!

I fixed the map and Rick fixed his software just in case the two-islands situation came up again (it didn’t). With that, three entries ran smoothly.

The result was actually very close. Jay Nagel won with $6,756,004, while Rick Matter came second with $6,518,808 and Jon Pattinson third with $5,698,804.

In a sense I was a bit sneaky, as this was a loose kind of variant of the traveling salesman problem and the time taken to solve that is NP (Non deterministic Polnomial time), so well done to all three!

This is the map used for the competition:

~~~~~~*~~~~~L~~~~~~~
~~~~Q~*~G~~~~~~~~~~I
~~~~~~*~~~~***~~~~~~
~A~~~~*~~~~~**~R~~~~
~~~~*~*~~~~~~~~~~~~~
~~~~*~~~~~N~~~*****~
~~~**~D~~~~~*~~~~~~~
~~**~~~~~~~~**~S~~~~
~~*~~~~~~~~**~~~~~~~
T~~~~*~~~~~~*~~~~~~~
~~~~~**~~~~*****~~~~
~~~B~**~J~~***~~~~~~
~~~~~**~~~~**~~~~~~~
~~~~~*~~~~****~~~~M~
~~~P~~~~~**~*~~~~~~~
~~~~~~~~~~~~*~~O~~~~
C~~****~~~H~~~~~~*~~
~~~~~~~~~~~~~~****~E
~~~~F~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~K~~~~~
1,4,8,7
2,4,9,6
3,4,7,8
4,5,6,10
5,2,10,10
6,3,6,8
7,8,4,5
8,6,6,6
9,7,5,8
10,8,9,4
11,5,7,9
12,3,6,12
13,4,10,7
14,5,9,8
15,6,8,7
16,7,7,7
17,6,6,5
18,5,7,9
19,4,8,8
20,5,7,9

Conclusion

I’ve found before that the number of entries is inversely proportional to the complexity of the problem–so in future I’ll keep ‘em simple!

Related Articles

Image: Wikipedia

Post a Comment

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>