Travelling Salesman

Rate this contribution

+14

Make the contribution public (lvl 20+)

Comments

53 Comments

about 2 years ago

300 is far too few nodes, 1000 would be decent and with some map setups: - big cities scattered - lines of nodes - nodes in various shapes Also, the leaderboard ordering is wrong

zLuki Unnamed CodinGamer

about 2 years ago

If I give more than 500 nodes as input the game Enginge throws an exception. I don't know how to fix it, I also asked on discord

leojean890 Unnamed CodinGamer

about 2 years ago

✅ Approved the contribution. Comment: I approve this contribution, because it's a well-known topic, interesting to try to master at best. I want to improve my level using this tool. There are better versions of this topic elsewhere as told by eulerscheZahl, because containing more cities, but it may be interesting to have it here as well, because it will be visible for more developers and be an opportunity for more begginer developers to have an "easier" version to train. I tried it and I like the visuals showing the best path we found.

eulerscheZahl Unnamed CodinGamer

about 2 years ago

❌ Rejected the contribution. Comment: CodinGame indeed lacks a TSP problem as far as I know. But I have doubts that an optimization problem is the right way. There are highly optimized solvers like concorde freely available for offline solving. https://www.math.uwaterloo.ca/... - on their website they claim to handle 85900 cities - and from my own experiences with it (finding a Hamilton path in over 10k nodes) it's extremely fast and not even that hard to use. With such tooling I predict lots of optimal solutions on the leaderboard. I suggest moving it to the puzzle section and demanding a certain level of optimization to pass the testcase, then I'd gladly approve. How is the distance defined? Euclidean? Edit: I inserted test 5 (the first with 300 nodes) into an online solver: https://neos-server.org/... Optimal Solution: 17112.00 (we could argue about the rounding but I could simply multiply every input number by a large factor) Total Running Time: 2.64 (seconds) And hardcoded on CG: https://i.imgur.com/...

zLuki Unnamed CodinGamer

about 2 years ago

How should I prevent people from creating hardcoded solutions?

jacek Unnamed CodinGamer

about 2 years ago

I would add coords on hover on points (at least in debug mode). And default stub doesn't have starting/ending point at the end.

Astrobytes Unnamed CodinGamer

about 2 years ago

✅ Approved the contribution. Comment: Simple, straightforward and fiendish classical problem.

ggrn Unnamed CodinGamer

about 2 years ago

Nice one. I think it is worth mentioning how distances are calculated. It would be also nice to have a more dynamic visual representation (connecting one node after the other) as opposed to all at once.

darkhorse64 Unnamed CodinGamer

about 2 years ago

✅ Approved the contribution. Comment: easy to explain, hard to master

darkhorse64 Unnamed CodinGamer

about 2 years ago

There is a huge bug in the referee: for instance, with the five nodes test, "4 3 0 2 1 0" or "4 3 0 1 0 2" are considered as valid responses. It's missing a check on starting and ending points.

Astrobytes Unnamed CodinGamer

about 2 years ago

Good catch. I had tested with the 0's missing from either or both ends but I omitted them entirely. It appears to check the length of the answer string and nothing more.

darkhorse64 Unnamed CodinGamer

about 2 years ago

We are getting closer but there are still a few hiccups. You wrote : "Your most recent submission will be used for the final ranking" which is wrong. Correct is "Your most successful submission will be used for the final ranking". The allocated time to answer is 1s (the default) not 2s (which is already rather short). You probably forgot to set the duration. I would also remove the two points test because it is too trivial. Please name your tests and validators using the number of points for instance.

zLuki Unnamed CodinGamer

about 2 years ago

Ok I'll work on it. But why is the allocated time 1s? I set gameManager.setTimePerTurn(2000) Is there another way to set the time?

Konstant Unnamed CodinGamer

over 2 years ago

To save server wear I suggest pre-calculate distances for each pair of points and hardcode them in dictionary in game source. Those distances wouldn't change at all in static validators.

darkhorse64 Unnamed CodinGamer

over 2 years ago

The savings are not worth the hassle

darkhorse64 Unnamed CodinGamer

over 2 years ago

Interesting problem. There are a lot of typos remaining in the statement: * Not all Nodes are in you Path! -> Not all nodes are in your path! * loose -> lose * heurisitc -> heuristic * recieve -> receive *The program must first read the xy coordinates of the given points from standard input. Then, provide -> The program must first read the xy coordinates of the given points from standard input, then provide * the amount of given Points -> the number of input points * given -> input You should remove the lone point test case which is valid for a puzzle but meaningless for an optim. The validators should only feature large numbers of points. On submits, the path length overwrites the text.

zLuki Unnamed CodinGamer

about 2 years ago

- Fixed typos - Removed lone point test - Added some more validators that feature large number of points - The path length doesn't overwrite the text anymore Thank you :)

Wontonimo Unnamed CodinGamer

over 2 years ago

Don't know why the game responds with "Correct path with length: 20417.39795539123" Is that your algos length, the absolute best score, or my algos length? Couldn't see where in the docs that is mentioned. Also, nowhere in your docs does it say that the first position visited has to be zero. That's a pretty important aspect

zLuki Unnamed CodinGamer

about 2 years ago

That is the length of the path that you returned. I added that it always has to start with index 0 Thank you :)

Wontonimo Unnamed CodinGamer

over 2 years ago

I got a total length using javascript and simple GA of 470662

darkhorse64 Unnamed CodinGamer

over 2 years ago

185 812,812 for now with a greedy algorithm

Butanium Unnamed CodinGamer

over 2 years ago

Why don't you display edges on screen ?

Butanium Unnamed CodinGamer

over 2 years ago

test case 2 : Standard Error Stream: n : 2 Standard Output Stream: 1 0 Game information: Not all Nodes are in you Path! Also : Rules are simple: - You win if your output is correct! - You loose if your output isn't correct! what's a "correct" path ? The best one or just a valid one ? If it's the best one, how do you expect people to solve 300 cities instances in 2 seconds ? Even state of art as the concorde TSP solver can't do that

zLuki Unnamed CodinGamer

about 2 years ago

The correct path is just a valid one and for test case 2 the output 1 0 is not valid. You have to start from 0 visit all points and return to 0. So the only valid path is 0 1 0. I'll try to make the statement clearer

loberhauser Unnamed CodinGamer

over 2 years ago

Really nice interpretation. I will work on it tomorrow. Found no mistake while trying it out👍

zLuki Unnamed CodinGamer

about 2 years ago

Thank you :)

ABOUT US CAREERS PRIVACY FAQ BLOG

The #1 tech hiring platform

SCREENING INTERVIEWING