23
8
Given a list of points, find the shortest path that visits all points and returns to the starting point.
The Travelling Salesman Problem is well-known in the computer science field, as are many ways to calculate/approximate it. It's been solved for very large groups of points, but some of the largest take many CPU-years to finish.
Don't get burned by the potato.
Hot Potato is a game where 2+ players pass a "potato" around in a circle while music plays. The object is to pass it to the next player quickly. If you are holding the potato when the music stops, you're out.
The object of Hot Potato Salesman is:
Given a set of 100 unique points, return those points in a better order (shorter total distance as defined further down). This will "pass" the problem to the next player. They have to improve it and pass it to the next, etc. If a player cannot improve it, they are out and play continues until one player is left.
To keep this from being a "brute-force-me-a-path" competition, there are these stipulations:
You cannot take more than one minute to pass the potato. If you haven't found and passed a shorter solution by the time one minute is up, you're out.
You cannot change the position of more than 25 points. To be exact,
>= 75
points must be in the same position as you received them. It does not matter which ones you decide to change, just the amount you change.
When only one player is left, he is the winner of that game, and receives one point. A tourney consists of 5*n
games, where n
is the number of players. Each game, the starting player will be rotated, and the remaining player order will be shuffled. The player with the most points at the end is the winner of the tourney. If the tourney ends with a tie for first place, a new tourney will be played with only those contestants. This will continue until there is no tie.
The starting player for each game will receive a set of pseudorandomly selected points in no particular order.
Points are defined as a pair of integer x,y
coordinates on a cartesian grid. Distance is measured using Manhattan distance, |x1-x2| + |y1-y2|
. All coordinates will lie in the [0..199]
range.
Input
Input is given with a single string argument. It will consist of 201 comma-separated integers representing the number of current players(m
) and 100 points:
m,x0,y0,x1,y1,x2,y2,...,x99,y99
The order of these points is the current path. The total distance is obtained by adding the distance from each point to the next (dist(0,1) + dist(1,2) + ... + dist(99,0)
). Don't forget to return to start when calculating total distance!
Note that m
is not the number of players that started the game, it is the number that are still in.
Output
Output is given in the same way as input, minus m
; a single string containing comma-separated integers representing the points in their new order.
x0,y0,x1,y1,x2,y2,...,x99,y99
The control program will wait for output for one minute only. When output is received, it will verify that:
- the output is well-formed
- the output consists of only and all the 100 points present in the input
>=75
points are in their original positions- the path length is less than the previous path
If any of these checks fail (or there is no output), you are out and the game will proceed to the next player.
Control Program
You can find the control program at this link. The control program itself is deterministic, and is posted with a dummy seed of 1
. The seed used during scoring will be different, so don't bother trying to analyze the turn order/point lists it spits out.
The main class is Tourney
. Running this will do a full tournament with contestants given as arguments. It spits out the winner of each game and a tally at the end. A sample tourney with two SwapBots looks like:
Starting tournament with seed 1
(0) SwapBot wins a game! Current score: 1
(1) SwapBot wins a game! Current score: 1
(1) SwapBot wins a game! Current score: 2
(1) SwapBot wins a game! Current score: 3
(0) SwapBot wins a game! Current score: 2
(1) SwapBot wins a game! Current score: 4
(1) SwapBot wins a game! Current score: 5
(1) SwapBot wins a game! Current score: 6
(1) SwapBot wins a game! Current score: 7
(1) SwapBot wins a game! Current score: 8
Final Results:
Wins Contestant
2 (0) SwapBot
8 (1) SwapBot
If you want to test just one game at a time, you can run the Game
class instead. This will run one game with players in the order given as arguments. By default, it will also print a play-by-play showing the current player and path length.
Also included are a few test players: SwapBot
, BlockPermuter
, and TwoSwapBot
. The first two will not be included in scoring runs, so feel free to use and abuse them during testing. TwoSwapBot
will be included in judging, and he's no slouch, so bring your A-game.
Miscellany
You cannot save state information, and each turn is a separate run of your program. The only information you will receive each turn is the set of points.
You cannot use external resources. This includes network calls and file access.
You cannot use library functions designed to solve/assist with the TSP problem or its variants.
You cannot manipulate or interfere with other players in any way.
You cannot manipulate or interfere with the control program or any included classes or files in any way.
Multi-threading is allowed.
One submission per user. If you submit more than one entry, I will only enter the first one submitted. If you want to change your submission, edit/delete the original.
The tournament will be running on Ubuntu 13.04, on a computer with an i7-3770K CPU and 16GB RAM. It will not be run in a VM. Anything I perceive as malicious will immediately disqualify the current and any future entry you submit.
All entries must be runnable from the command line with free (as in beer) software. If I have problems compiling/running your entry, I will request aid in the comments. If you do not respond or I cannot ultimately get it running, it will be disqualified.
Results (22 May 2014)
New results are in! UntangleBot has beaten the competition quite soundly. TwoSwapBot managed seven wins, and SANNbot snuck a victory in as well. Here's a scoreboard, and a link to the raw output:
Wins Contestant
22 (2) ./UntangleBot
7 (0) TwoSwapBot
1 (5) SANNbot.R
0 (1) BozoBot
0 (3) Threader
0 (4) DivideAndConquer
As it stands now, UntangleBot has won the checkmark. Don't let that discourage you from entering, though, since I'll run the tournament as more contestants appear and change the accepted answer accordingly.
Comments purged. Please notify me for any possible lost information. – Doorknob – 2014-05-23T12:14:50.613
Man why did this challenge have to be during my final exams (finally, done with school yeay). You sure are a bad planner Geobits ;) Weird/sadly enough at that time there were tons of king-of-the-hill questions and now there aren't any (maybe it works better if there is only one at a time, hint hint) ... – Herjan – 2014-05-28T16:16:45.800
@Herjan Feel free to try to tackle the current champ. I'll run the tourney again as new contestants appear, so the contest isn't over or anything. Beat SirDarius and it may spur him or someone else to beat yours, breathing life back into it ;) – Geobits – 2014-05-28T16:19:20.833
@Herjan Please do submit an entry ! I believe there is a lot of room for improvement here. Most of the solutions here, including mine, do not rely on clever algorithms specific to this problem. – SirDarius – 2014-05-29T17:57:56.030
I think there is a problem with modification limitation. As some times it will take to modify the entire set of data to get better solution. – Ilya Gazman – 2014-07-01T21:16:55.183