We are about to switch to a new forum software. Until then we have removed the registration on this forum.
Hi! I've always wanted to host some kind of online forum-based competition, and I've decided that the Processing Forum seems like the right place. As of yet, however, I've not decided on a unit of time to iterate these challenges with, so I'm just gonna post the first one and see how it does from there.
Enough about me. Here's how this will work: I'm gonna post a couple related problems and you guys have to answer them. The problems will range in complexity [Some of them may be impossible] and may be solved with any combination of the following languages:
Please compile your scripts when posting. If you wish to use a language that isn't listed, contact me and I [may] add it. Feel free to discuss these problems in the forum; the prize for this competition is just nerd-fame. It's meant to spark lively debate, not secret stealing!
Ok, now that the boring stuff is over, lemme get to the problems at hand. Today, I have n problems for you.
First is the traveling salesman problem.
The Travelling Salesman Problem describes a salesman who must travel between N cities. The order in which he does so is something he does not care about, as long as he visits each one during his trip, and finishes where he was at first. Each city is connected to other close by cities, or nodes, by airplanes, or by road or railway. Each of those links between the cities has one or more weights (or the cost) attached. The cost describes how "difficult" it is to traverse this edge on the graph, and may be given, for example, by the cost of an airplane ticket or train ticket, or perhaps by the length of the edge, or time required to complete the traversal. The salesman wants to keep both the travel costs, as well as the distance he travels as low as possible. Your task is to write a function that describes an optimal route between points, given an array of coordinate points.
For a more difficult version of the Travelling Salesman problem, incorporate Z coordinates into it.
Next is a new one of my own making: The school bus problem.
The School Bus Problem describes a fleet of school buses that, each starting from a central point (the school) must travel, collectively, to N points to deposit children. For simplicity, it is assumed that the roads between nodes are of optimal length and that buses travel at a constant speed. Your task is, much like in the salesman problem, to write a function that somehow describes a set of optimal routes between points, given an array of coordinate points, the coordinates of the school, and the number of buses.
Finally, the extended school bus problem. I'm pretty sure that this one's nearly impossible without a supercomputer, FORTRAN, and lots of time, but who knows?
The initial setup of this problem is the same as that of the school bus problem, but it has one important difference: School buses now stop for an amount of time whenever they come to an intersection. Intersections are defined as anywhere that a line between two nodes crosses a line between any other two nodes. Your task is the same as in the school bus problem.
Final answers should be posted as comments.