Dec 00 Challenge
Volume Number: 16
Issue Number: 12
Column Tag: Programmer's Challenge
Programmer's Challenge
By Bob Boonstra, Westford, MA
Crutches
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;
typedef long Weight;
typedef struct Connection {
Node node1; /* a connection exists between node1 ...
*/
Node node2; /* ... and node2 .... */
long distance; /* ... separated by this distance */
Weight weight; /* you need to carry an object with this weight
... */
Node fromNode; /* ... from fromNode ... */
Node toNode; /* ... to toNode */
typedef enum {kPickUpObject=1, kDropOffObject, kMoveTo} ActionType;
ActionType action, /* actions comprising the solution */
long object, [TOKEN:12074] kPickUpObject or
kDropOffObject this object */
Node node [TOKEN:12074] kMoveTo this node */
long /* actions in solution */ Crutches (
const Node nodes[], /* Nodes defining the
problem */
long numNodes,
const Connection connections[], /* Connections between nodes
*/
long numConnections,
const Task objectsToMove[], /* objects to be moved */
long numObjects,
Node startingNode, /* start from this node
*/
Weight maxWeightToCarry, /* maximum weight that you can carry
*/
Action solutionPath[] /* return your solution here */
);
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 5 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.)
Three Months Ago Winner
Congratulations to Claes Wihlborg (Sweden) for submitting the winning entry to the
September Busy Beaver Challenge. This Challenge required contestants to do two
things. First, contestants were to produce a 5-state "Busy Beaver" Turing Machine
that writes as large a number of 1s as possible when given a blank input tape. Second,
they had to write a general Turing Machine simulator that executes this Busy Beaver
as quickly as possible. The problem statement provided a reference to a Turing
Machine demonstrating that BB(5), the maximum number of 1s produced by any
5-state Busy Beaver, is at least 4098. Alas, none of the nine entries in this Challenge
broke new ground in Busy Beaver research by providing a Busy Beaver that produced
more than 4098 1s. So this competition was based on how quickly the Busy Beaver
could be executed.
Claes' solution is extraordinarily fast, five times faster than the second place solution,
and more than sixty times faster than the third-place solution. Upon investigation,
while somewhat difficult to understand because of sparse commentary, Claes' entry is
fascinating. To fully understand it, I inserted some debugging code and watched it in
operation. I'll try to compensate for the terseness of the code by providing some
additional explanation here.
The first thing Claes does is to call the CreateOptimizedTMRules routine to compile the
Turing Machine rules into OptimizedTMRules. Two OptimizedTMRules are created for
each Turing Machine rule, encoding both the rule and the associated binary input
symbol. Each OptimizedTMRule contains a OneBitActionRoutines action field that
combines two elements of the original Turing Machine rule: the move direction, and
whether the output symbol is unchanged, 0, or 1. These actions are encoded as follows:
abaLeft, abaRight , abaHalt - leave the input unchanged and move left, right, or halt
abaLeftSet, abaRightSet, abaHaltSet - write a 1 and move left, right, or halt
abaLeftClear, abaRightClear, abaHaltClear - write a 0 and move left, right, or halt
This optimization allows Claes to factor out some logic tests during the Turing Machine
simulation, and to avoid modifying the output tape when it doesn't change.
The runNBitTuringMachine performs the Turing Machine simulation. This routine
processes the input tape in chunks of either 6 bits or 8 bits in size, trying the former
first, and the latter if the former fails. It creates and uses two additional data
structures, the TapeSegment structure that encodes a segment of the Turing Machine
tape, and the MacroNTMRule data structure that further encodes the
OptimizedTMRules. The TapeSegment data structure takes advantage of the fact that
repeating sequences can occur on a Turing Machine tape, and do occur on Busy Beaver
Turing Machines. It contains a symbol field, which is a 6- or 8-bit section of the
tmTape, an exponent that contains a repetition count for that section, and left and right
pointers to adjacent tape segments.
The MacroNTMRule is a little more difficult to explain. The 256 Turing Machine states
that the problem statement requires entries to support are expanded into 512
OptimizedTMRules, and further expand into 512*256 MacroNTMRules. A
MacroNTMRule is indexed by 8 bits that identify the OptimizedTMRule, plus of the
TapeSegment symbol value (6 or 8 bits). In effect, the MacroNTMRule expands the
symbol set from 1 bit to 6 or 8 bits, and expands the set of Turing Machine states
accordingly.
When runNBitTuringMachine executes the Turing Machine, it first looks to see if the
MacroNTMRule corresponding to the current state has been created. If not, it calls the
createNbitMacroRule routine to create it. This routine simulates the effect of the
OptimizedTMRules on the current input symbol, determines what newSymbol output is
produced, counts the number of OptimizedTMRules executed for this one
MacroNTMRule, characterizes the nature of the rule into an NBitActionRoutines
action, and stores a pointer to the new MacroNTMRule state.
The NBitActionRoutines field characterizes the MacroNTMRule by encoding the move
direction, whether the output is different from the input, and whether the state is
changed after processing this chunk of input. The most interesting values for this
NBitActionRoutines field are as follows:
• tbaBounceLeft, tbaBounceRight - leave the input unchanged and reverse
direction left or right
• tTbaBounceLeftChange, tbaBounceRightChange - write changed output and
reverse direction left or right
• tTbaThruLeft, tbaThruRight - leave the input unchanged, continue moving
left or right, and modify the state
• tTbaThruLeftChange, tbaThruRightChange - write changed output,
continue moving left or right, and modify the state
• tTbaThruOptimized tbaThruRightOptimized - leave the input unchanged,
continue moving left or right, and stay in the same state
• tTbaThruChangeOptimized tbaThruRightChangeOptimized - write changed
output, continue moving left or right, and stay in the same state
The optimizations in the runNBitTuringMachine code allow the final output of Claes'
Busy Beaver to be represented in a few TapeSegments:
Segment Symbol (Hex) Exponent (Hex)
0 0 180
1 1 1
2 36 1023
3 37 1
4 0 395
When runNBitTuringMachine returns, it indicates whether the attempt to execute with
6-bit tape segments succeeded or failed. If it failed, it is run again using 8-bit
segments. While the 6-bit optimization is clearly intended to speed up the 5-state
Busy Beaver Turing machines, it also kicks in for other machines. More importantly,
the program meets the requirement of correctly simulating any Turing Machine with
up to 256 states, without hard-coding any particulars of the Busy Beaver problem.
Before RunTuringMachine returns, it copies the TapeSegments back to the Turing
Machine tape. (Until this point, the output of the Turing Machine exists only in the
TapeSegment database.) For the 6-bit tape segment case, Claes uses an unrolled loop.
For the 8-bit case, he uses memset. In both cases, the exponent field in the
TapeSegment controls the number of times a TapeSegment symbol is copied.
I'd encourage you to take a look at Claes solution. I found it to be very clever.
The table below lists, for each of the solutions submitted, the number of 1s generated
by the entry's Busy Beaver Turing Machine, the number of rules executed by that
machine, the execution time of the Busy Beaver in milliseconds, and cumulative test
case execution time. It also provides the code size, data size, and programming language
used for each entry. As usual, the number in parentheses after the entrant's name is
the total number of Challenge points earned in all Challenges prior to this one.
Name # of 1s # of Rules BB Time (msecs) Time (msecs) Code Size
Data Size Lang
Claes Wihlborg (9) 4098 11798826 0.93 3.04 6680
1080033 C
Ernst Munter (651) 4098 11798826 5.10 22.82 4764
749 C++
Mike Miller 4098 11798826 61.49 306.93 2044
410 C
Rob Shearer (51) 4098 11798826 64.92 311.59 1432
716 C++
Randy Boring (133) 4098 11798826 213.09 1066.58 4456
94 C++
Willeke Rieken (112) 4098 11798826 489.74 2456.34
912 16 C
Tom Saxton (165) 4098 11798826 734.27 3678.83 708 180
Yung-Lueng Lan 4098 11798826 743.58 3726.49 1372
28 C
Ladislav Hala (7) 4098 47176870 2954.95 5922.87 1520
750 C
Top Contestants...
Listed here are the Top Contestants for the Programmer's Challenge, including
everyone who has accumulated 10 or more points during the past two years. The