Have you lost interest in the various challenges because you're tired of code golf or unrealistic constraints on problem solving?

If so, here's a good old-fashioned computer science algorithm problem:

How well can you optimise a solution for The Travelling Salesman problem?

(Try to find the shortest route that passes through all the given cities once and returns to the start city. In this version, distance is a simple straight line; cities are specified as X and Y coordinates)

Ideally the results would be judged solely on the length of the calculated route, but there's a possibility that someone will write a solution that runs for a week to gain just a few extra distance points, so the complicated rules on timing below are meant to keep that sort of thing under control, and remind you that optimising a solution has to balance several factors - the quality of the result, the time it takes to write the code, the runtime of the code, and even the understandability and ease of maintenance of the code.

So… if your algorithm runs to completion, enter it like that. I'll note the time it takes. The results of all such algorithms will be plotted as route length vs execution time. The best solution is not necessarily the fastest solution or the shortest route, but the most efficient route-length/solution-time ratio for non-trivial solutions. (I.e don't return a result almost immediately with a very non-optimal solution that's just a little better than random because the ratio works out high. This is a common sense/no lawyering competition.)

However if you write the kind of solution that iteratively improves and could run forever unless you explicitly stop it, then it will be allowed to run for a fixed time that will be determined from the best solution of the entries which ran to completion without requiring intervention. You should keep the result list updated so it is consistent when your code is forcibly halted.

Friday 25th November should be long enough to produce a solution. I will be doing this myself for the fun of it but not as an entrant.

And I've taken a leaf from Martin's book by producing a standardized testbed: https://scratch.mit.edu/projects/131310201/ - All you should modify is the ‘Solve’ sprite.

Anyone who has already tackled this can use their existing code as a starting point if they want, though with the upper limit on the number of cities being 300 (to match the clone limit and make the resulting code useful in other projects!), chances are that existing solutions won't scale to that size of problem…

G

Ohh I may try this…

IcyCoder wrote:

Ohh I may try this…

You found it too late, I'm already working on my algorithm

Saiid

Question - Are we allowed to use additional variables and lists? Forgive me if I'm being an idiot

Saiid

Saiid wrote:

Are we allowed to use additional variables and lists?

Yes. Graham said no unrealistic constraints!

Forgive me for the only tangentially related question, but; I'm thinking about how best to add pathfinding to my TTD game, and I'm not sure how to go about it. Ideally I'd use something like A*, but as I understand it that needs several complicated data structures (e.g. priority queue?) and is probably too slow in scratch to run in a single frame of the game… so I might end up going with a naive greedy algorithm that, while it uses heuristics like distance, doesn't necessarily find the optimal path.
It's further complicated by the fact that because of the nature of train track, you can reach the same tile more than once from different directions, so the optimal route to some tile may not be the optimal route to the final destination…

blob8108 wrote:

Saiid wrote:

Are we allowed to use additional variables and lists?

Yes. Graham said no unrealistic constraints!

Forgive me for the only tangentially related question, but; I'm thinking about how best to add pathfinding to my TTD game, and I'm not sure how to go about it. Ideally I'd use something like A*, but as I understand it that needs several complicated data structures (e.g. priority queue?) and is probably too slow in scratch to run in a single frame of the game… so I might end up going with a naive greedy algorithm that, while it uses heuristics like distance, doesn't necessarily find the optimal path.
It's further complicated by the fact that because of the nature of train track, you can reach the same tile more than once from different directions, so the optimal route to some tile may not be the optimal route to the final destination…

Oh.

What? What's TTD?

Saiid

blob8108 wrote:

Forgive me for the only tangentially related question, but; I'm thinking about how best to add pathfinding to my TTD game, and I'm not sure how to go about it. Ideally I'd use something like A*, but as I understand it that needs several complicated data structures (e.g. priority queue?) and is probably too slow in scratch to run in a single frame of the game… so I might end up going with a naive greedy algorithm that, while it uses heuristics like distance, doesn't necessarily find the optimal path.
It's further complicated by the fact that because of the nature of train track, you can reach the same tile more than once from different directions, so the optimal route to some tile may not be the optimal route to the final destination…

Quick answer: a simple breadth-first search will work (like I use in my pacman style game - see also in my maze studio for other examples including Dijkstra's algorithm and one person implemented A* which is quite fast enough for your purposes if you really need it). The fact that you have a graph not a tree is not an issue as these algs don't rely on it being a tree - although if it is you can *pre-calculate* the solutions which isn;t possible if it's a graph. If you need more detail, please start another thread and I'll answer there.

Saiid wrote:

Question - Are we allowed to use additional variables and lists? Forgive me if I'm being an idiot

Saiid

Yes but for neatness (as a judging program may end up including everyone's entries) please try to keep all your variables as local to your sprite unless cloning constraints force otherwise. Also keep your solving code to the one sprite. thanks.

gtoal wrote:

Saiid wrote:

Question - Are we allowed to use additional variables and lists? Forgive me if I'm being an idiot

Saiid

Yes but for neatness (as a judging program may end up including everyone's entries) please try to keep all your variables as local to your sprite unless cloning constraints force otherwise. Also keep your solving code to the one sprite. thanks.

Ah okay let me go make them local then. The code, of course was already all in the one.

Saiid

Not a necessity but for long-running programs, some occasional graphical feedback to let us know it is still alive might be an idea. For instance updating a ‘best solution so far’ display once a minute…

gtoal wrote:

Not a necessity but for long-running programs, some occasional graphical feedback to let us know it is still alive might be an idea. For instance updating a ‘best solution so far’ display once a minute…

Did you see my entry?

Saiid

Saiid wrote:

gtoal wrote:

Not a necessity but for long-running programs, some occasional graphical feedback to let us know it is still alive might be an idea. For instance updating a ‘best solution so far’ display once a minute…

Did you see my entry?

Saiid

Yes, thanks - which was actually the reason for my comment above - I ran your code for nearly an hour before cancelling it - wasn't sure if it had crashed or not. It was making my portable so slow I couldn't get anything else done and there was no feedback at all to tell me if it was doing anything - the display was still the initial random 30-city layout. How long does it take on your system before you see something happen?

G

gtoal wrote:

Saiid wrote:

gtoal wrote:

Not a necessity but for long-running programs, some occasional graphical feedback to let us know it is still alive might be an idea. For instance updating a ‘best solution so far’ display once a minute…

Did you see my entry?

Saiid

Yes, thanks - which was actually the reason for my comment above - I ran your code for nearly an hour before cancelling it - wasn't sure if it had crashed or not. It was making my portable so slow I couldn't get anything else done and there was no feedback at all to tell me if it was doing anything - the display was still the initial random 30-city layout. How long does it take on your system before you see something happen?

G

Yeah that's what I figured. I'm not completely sure what's wrong with it, my code theoretically checks out. For me it won't go past that, but doesn't really slow anything down on my computer.

Saiid

Here is my solution: https://scratch.mit.edu/projects/131498935/

EDIT: I didn't realize that I had to remix your project.

EDIT 2: I'm putting my sprite into a remix of your project. Is Next City the list where I need to put my solution? Is the first city in the list the “home?”

Chibi-Matoran wrote:

Here is my solution: https://scratch.mit.edu/projects/131498935/

EDIT: I didn't realize that I had to remix your project.

Well, I'm not going to enter 300 points by hand each time I run it, so would you mind moving your logic into my test framework please? It really shouldn't be too hard, it's a trivial interface - just an array of x,y locations.

Btw, does ‘brute force’ mean e^n complexity? If so you'll be lucky to handle 30 cities and I be very surprised if it handles 300! I chose big numbers deliberately so that people *wouldn't* get away with brute force algorithms and would have to invent heuristics…

Chibi-Matoran wrote:

EDIT 2: I'm putting my sprite into a remix of your project. Is Next City the list where I need to put my solution? Is the first city in the list the “home?”

Actually it's a loop, so it doesn't matter where you start. The salesman has to come home at night! Yes, the result is the list of next cities. My code will draw the cities with lines linking them using those links. Your code is welcome to draw intermediate solutions or steps.

Does it have to be a perfect solution, or can it just be a “close-enough” solution?

iamunknown2 wrote:

Does it have to be a perfect solution, or can it just be a “close-enough” solution?

Pretty much the only rule to the solution is that it has to touch all the lines and come back to the beginning, I believe.

Saiid

gtoal wrote:

Chibi-Matoran wrote:

EDIT 2: I'm putting my sprite into a remix of your project. Is Next City the list where I need to put my solution? Is the first city in the list the “home?”

Actually it's a loop, so it doesn't matter where you start. The salesman has to come home at night! Yes, the result is the list of next cities. My code will draw the cities with lines linking them using those links. Your code is welcome to draw intermediate solutions or steps.

My error script says that i missed one every time, and your thing does too, but from what I can see, they all connect and my code should be fine.

Saiid

If the path taken is 1 2 3 1, should the Next City list be [2, 3, 1]?