Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
Created by @zLuki,validated by @darkhorse64,@Astrobytes and @leojean890.
If you have any issues, feel free to ping them.
Rules are so poorly written, that they even donāt tell you what you have to do to get a score. One star from me.
1 Like
Courtesy of @eulerscheZahl and @Daporan it came to our attention that that given the simplicity and relatively low value of the input size n , this is fairly trivial to solve using an online solver e.g Concorde Home or indeed simply using a slightly āsmarterā algorithm. Therefore we feel that the leaderboard would be overwhelmed with optimal solutions.
Noting the aforementioned issues, which were both noted on the contribution page and discussed in web chat, this should not have been blindly approved not long after eulerās rejection.
I will also take some blame here since I should have removed my approval/moved to reject last night pending further inquiry.
May I suggest that the author @zLuki fix the relatively minor issues pointed out on the contribution page, and regarding the rather more important issues I propose the following:
Each node in the given graph is a country, each country has a set of cities (sub-nodes), you must visit say k=3 cities (shortest route) before moving to the next country. Indeed, as @eulerscheZahl suggested during further discussion, k need not be the same for each country.
Also, increase test case input size to 500 - 1000 countries/nodes.
With these changes, this should hopefully prevent most brute-forced approaches/use of online solvers.
As noted by @eulerscheZahl during a discussion in chat today, there are now also many more options to improve the visualisation given these ideas.
Open to suggestions.
9 Likes
What? Isnāt the target to get the longest path to visit all nodes?
The leaderboard shows the highest score is the longest length!
Link to the initial discussion page with the source code including tests and validators: Coding Games and Programming Challenges to Code Better
1 Like
I donāt know if that was intentionalā¦ Maybe finding longest or shortest Hamilton cycle is similar in difficulty.
But we shall not call this problem the āTravelling Salesmanā. Poor salesman would never see his familyā¦ A more appriopriate name would be āFrequent Flyer Milesā problemā¦ 
1 Like
I agree that ATM the problem is too easy to solve. I tried to add more nodes but the game Engine throwes Exceptions for larger inputs and I donāt know how to fix it.
Iām sorry to say that I donāt like your idea to change the game. I liked it how it was, I donāt want to change it because of online tools who can solve it.
Itās just my opinion, please donāt hate
3 Likes
No hate. Thanks for replying!
@zLuki You donāt like idea to change the game. Itās OK.
But are you going to change the statement?
You still donāt say enough in it. You have to explain the task in detail.
4 Likes
@Astrobytes , are scripts allowed to connect to the Internet? I remember trying it some time ago, and didnāt succeed. If not, how online solvers can be used?
Validators are available here. Thatās by design, the puzzle creator canāt hide them.
To quote myself from the contribution page:
I inserted test 5 (the first with 300 nodes) into an online solver: https://neos-server.org/ā¦ Optimal Solution: 17112.00
Total Running Time: 2.64 (seconds)
And hardcoded on CG: https://i.imgur.com/ā¦
So all you have to do now is to hardcode all validators like this:
if map == 'xxx': print('XXX')
if map == 'yyy': print('YYY')
As you see, my score is by 3 points worse than the current best.
The only caveat remaining: concorde solves an integer problem, while the edge distances clearly are not integers. So you have to increase the precision by artificially increasing the distances. Multiply every x- and y-value by 100 and your score will increase a tiny bit.
Wow, I didnāt know that!
So, validators for any puzzle are available? Or only for certain ones? And why? 
@eulerscheZahl ah, I understand now (after reading the conversation here: Coding Games and Programming Challenges to Code Better )
ok well, I always re-invent the wheel. So since thereās no mouseover for node id nor coords. here is the 50 node testcase:
Hey so do you know what the optimal score is ? I just want to have a guess as to how far I am from it.
I got 201382, Iām pretty sure thatās as good as you can get. 201389 if I run concorde on the original input (it solves an integer problem, while the edges are not integer lengths), 201382 if I multiply every coordinate by 100 to minimize those rounding errors.
Validator 1: 3873
Validator 2: 4370
Validator 3: 8122
Validator 4: 10510
Validator 5: 17123
Validator 6: 10500
Validator 7: 12915
Validator 8: 14216
Validator 9: 15695
Validator 10: 17401
Validator 11: 17049
Validator 12: 17101
Validator 13: 17997
Validator 14: 17096
Validator 15: 17414
Damn, 3 of the top people on the leaderboard have a score of 201382. Are you sure they are not hardcoding it ?
dbdr is hardcoding but wrote his own solution instead of relying on concorde at least. I donāt know what the other two are doing.
Hardcoding in optimization problems is a common thing and there isnāt much you can do about it.
- huge testcases (like in 2048, you canāt just hardcode everything because of the code size limit): they will just hardcode certain moves and compute the rest online
- random validators (bulls and cows): spam submits until you get lucky
- harder levels that have to be solved (number shifting): forces players to do it offline but at least everyone knows about it
- making it a multiplayer game (code keeper - the hero): the game is in the wrong category then. But with random testcases hardcoding becomes impossible.
I think people who hardcode their solutions should be disqualified. It just promotes cheap competition and demotivates the people who are actually trying.
6 Likes
Does anybody knows how does āconcordeā works ? Iād like to be closer to the optimal solution, with my own solution (without hardcode) and my best score is 205 269.
I computed the ānearest neighbourā starting with each points, i applyed the 2 opt, 3 opt ā¦ 150 opt, and also tryied to ārollā (from any point and rolling 3, 4 ,5 ā¦ 300 points).
Excecution time is not a problem, but i donāt know what i can do then.