|
December 2000 Programmer's Challenge
Crutches
Mail solutions to:
progchallenge@mactech.com
Due Date: 11:59pm ET, Friday, 1 December 2000
Crutches? What an odd topic for a Programmer’s Challenge, you might think. Let me explain. This month’s problem was actually suggested by my wife, whose connection with the Challenge has until now been limited to the patience required to put up with the amount of time I spend running the contest. She recently had the misfortune to break her foot, which has, you guessed it, put her on crutches for six or so weeks. Being on crutches gives one a new perspective on distance, particularly distance between points around the house. And while she tries to stay off the foot as much as possible, she still has to get from place to place, so the broken foot also motivates one to find ways to minimize distance. Which leads us to this month’s Challenge, a practical extension of the well-known Traveling Salesperson problem.
The prototype for the code you should write is:
typedef long Node; /* Nodes are not numbered sequentially */
typedef long Weight;
typedef struct Connection {
Node node1; /* a connection exists between node1 ... */
Node node2; /* ... and node2 .... */
long distance; /* ... separated by this distance */
} Connection;
typedef struct Task {
Weight weight; /* you need to carry an object with this weight ... */
Node fromNode; /* ... from fromNode ... */
Node toNode; /* ... to toNode */
} Task;
typedef enum {kPickUpObject=1, kDropOffObject, kMoveTo} ActionType;
typedef struct Action {
ActionType action; /* actions comprising the solution */
long object; /* kPickUpObject or kDropOffObject this object */
Node node; /* kMoveTo this node */
} Action;
long /* actions in solution */ Crutches (
const Node nodes[], /* Nodes defining the problem */
long numNodes, /* number of Nodes */
const Connection connections[], /* Connections between nodes */
long numConnections, /* number of Connections */
const Task objectsToMove[], /* objects to be moved, numbered as index into objectsToMove */
long numObjects, /* number of objectsToMove (Tasks) */
Node startingNode, /* start from this node */
Weight maxWeightToCarry, /* maximum weight that you can carry */
Action solutionPath[], /* return your solution here */
long maxActions /* size of solutionPath array */
);
Your job is to write code that will perform a set of Tasks and minimize the distance traveled in doing so. Each Task consists of moving an object of a specified weight from one place (Node) to another. You can travel from one Node to another only if a Connection exists between the Nodes, and moving between a pair of Nodes requires traveling the associated distance along that Connection.
At the start of the problem, you are located at the startingNode. You are given the numNodes Nodes describing the problem space and the numConnections Connections between them. You are also given numObjects objectsToMove, each of which needs to be transported from the fromNode to the toNode. You can carry more than one object along your journey, provided the sum of the weights of the objects being carried does not exceed the maxWeightToCarry. The solution is described as a sequence of Actions. An Action consists of picking up an object (kPickUpObject) from the current Node, dropping off an Object at the current Node (kDropOffObject), or moving to an adjacent Node (kMoveTo) and carrying all objects that have been picked up to that Node. You may not pick up an object if doing so would cause the maxWeightToCarry to be exceeded. The sequence of Actions that transports all of the objectsToMove to the appropriate Nodes should be returned as the solutionPath, and Crutches should return the number of Actions in your solution.
None of the Tasks will be impossible to perform. No object will have a weight greater than maxWeightToCarry, so it will be possible to carry each object. It will be possible to reach each fromNode and each toNode by traversing Connections from the startingNode. Connections may not satisfy the triangle inequality, that is, it may be the case that a direct Connection between two Nodes is not the shortest path between them. No other a priori information about the Connections, Nodes, or Tasks is available.
Your solution will be evaluated first on correctness (as always), and then on score. Your score for this Challenge will be the total distance traveled to perform the required Tasks, plus a 10% penalty for each second of execution time expended. Lower scores are, of course, better.
The Challenge prize will be divided between the overall winner and the best scoring entry from a contestant that has not won the Challenge recently. If you have wanted to compete in the Challenge, but have been discouraged from doing so by the quality of the entries from our veteran contestants, perhaps this is your chance at some recognition and a share of the Challenge prize.
This will be a native PowerPC Challenge, using the CodeWarrior Pro 6 environment. Solutions may be coded in C, C++, or Pascal.
Next month, perhaps we’ll solve the problem of how to motivate a couple of teenage children to perform these Tasks, allowing the broken foot more time to rest and heal. But perhaps that would be too difficult, even for Challenge readers. (Actually, the kids are being very helpful with the household chores.)
Test code for this Challenge is available.
You can get a head start on the Challenge by reading the
Programmer's Challenge mailing list. It will be posted to the list on
or before the 12th of the preceding month. To join, send an email to
listserv@listmail.xplain.com
with the subject "subscribe challenge-A". You can also join the
discussion list by sending a message with the subject "subscribe
challenge-D".
|
Slashdot
Digg
del.icio.us
reddit
newsvine
Y! MyWeb
