by Bob Showalter
I was a Cub Scout leader for five years and one of our favorite activities was the annual Pinewood Derby. For you non-Scouts, this is a competition between small gravity-powered cars made by the boys using standard kits containing a wood block, plastic wheels, and nails for axles. The cars compete against each other down a sloping, multi-lane track (2-6 lanes is typical) about 30 feet long.
Some Cub Scout packs use a "ladder" elimination system for their derby, but this isn't much fun for the boys that are eliminated early. Much more enjoyable is a "round-robin" approach that lets each boy's car run in the same number of heats, racing against different opponents each time.
You can find links to more Pinewood Derby information at:
This week's task is to create a Ruby program to generate a chart for a Pinewood derby. In order to make the event fair, each car should be scheduled into each lane of the track the same number of times (to compensate for any lane differences due to track imperfections.) We'll use the term "round" to refer to each car running once in each lane. The input to your program will be:
Number of cars
Number of lanes
Number of rounds
For example, let's assume we have 25 cars and a 4-lane track. If we want each car to run twice in each lane (2 "rounds"), that means:
Number of rounds: 2
Number of runs per car: 2 rounds x 4 lanes = 8
Total number of runs: 8 runs/car x 25 cars = 200
Total number of heats: 200 / 4 lanes = 50 heats
So we have to come up with a chart that assigns the cars to lanes and heats. If we number the lanes from 1 to 4 and the cars from 1-25, our chart might look something like this:
Heat Lane 1 Lane 2 Lane 3 Lane 4
---- ------ ------ ------ ------
1: 9 2 13 10
2: 12 8 5 21
3: 16 19 6 4
...and so on
The trick is to create a chart that is as fair as possible. A "perfect" chart would be one in which:
1) Each car runs in the same number of heats
2) Each car runs in each lane an equal number of times
3) Each car runs against every other opponent an equal number of times
4) The heats a car is assigned to are evenly spread throughout the event. (In
other words, a boy shouldn't run in the first 8 heats and then have to sit
out for the rest of the event.)
In practice, you cannot create a perfect chart for all combinations of inputs. For instance, if we ran just one round with our 25 cars, each car would run in 4 heats and face 12 opponents (3 opponents per heat). Since there are 24 opponents, it isn't possible to face all the opponents equally. But you would want to try to maximize the number of opponents faced, rather than having two cars face each other several times.
You may want to create a function to evaluate your chart against the criteria above, so you can rank charts as to their "quality".
Quiz Summary
by Bob Showalter
[Ediitor's Note: I hope everyone noticed that Bob just ran, solved, and summarized a Ruby Quiz solo. Take it from me, a guy with a little experience doing that very, not-so-fun thing, we all owe Bob a HUGE thank you! --JEG2]
This week's quiz failed to attract any submissions other than the rather weak ChaoticChart generator that I posted. (This code was actually adapted from a Perl version I created a couple of years ago.)
The problem with scheduling a derby is balancing fun with fairness. The factors to consider are:
* All the boys should be participating throughout the event (fun)
* Each boy should race the same number of times (fair)
* All lanes of the track should be used evenly (fair)
* Cars should race against the other cars as evenly as possible (fair)
Our challenge was to construct a chart given a track with a fixed number of lanes and a number of cars to participate. The event would consist of a number of "heats" in which a car was assigned to each lane. The total number of heats would be determined from the number of times each car would run in each lane.
My solution starts with a simple Chart class:
class Chart
attr_reader :lanes, :cars, :rounds, :chart
# create a new empty chart with given lanes, cars, and rounds.
def initialize(lanes, cars, rounds)
raise "Need at least #{lanes} cars" unless cars >= lanes
raise "Need at least 1 round" unless rounds >= 1
@lanes = lanes
@cars = cars
@rounds = rounds
@chart = []
end
Here we just take the three factors that control the chart's size (lanes, cars, and rounds) and put them into member variables (after doing some rudimentary sanity checking). A read-only accessor is created for each member.
The @chart member variable is initialized to an empty array. This will eventually receive the heats as they are assigned.
We need a way to print out a chart:
def print_chart(io = $stdout)
io.puts "Chart:"
h = 0
chart.each do |heat|
io.printf "%4d: ", h
heat.each do |car|
io.printf "%4d", car
end
io.puts
h += 1
end
end
This method just loops through the heats in the @chart member and prints them onto the supplied object (which defaults to standard output, but could be a File object or a StringIO object, or any object that acts like an IO object).
One simple way to assign cars to heats is through a "round robin" approach. Let's create a class that can generate such a chart. We'll do that by subclassing the Chart class and adding a generate method:
# generate chart via simple round-robin assignment
def generate
chart.clear
car = 0
(cars * rounds).times do |heat|
h = []
lanes.times do
h << car
car = (car + 1) % cars
end
chart << h
end
end
end
The algorithm here is extremely simple. The first four cars are assigned to the first heat. The second heat is assigned starting with the fifth, sixth, etc. cars, and so on. When we run out of cars, we start reassigning with the first car again.
Here's the output from generating a round robin chart for 1 round of 5 cars on 4 lanes (heats and cars are numbered from zero):
Chart:
0: 0 1 2 3
1: 4 0 1 2
2: 3 4 0 1
3: 2 3 4 0
4: 1 2 3 4
This is actually a perfect chart. Each car runs in four heats, and runs in each lane exactly once. Each car faces all the other cars exactly three times. Also, the assignments are evenly distributed through the event; there is never more than a single heat gap between any two runs of a given car.
However, the round robin algorithm breaks down when you begin to consider different combinations of inputs. For example, here's the output for 6 cars on 4 lanes for 1 round:
Chart:
0: 0 1 2 3
1: 4 5 0 1
2: 2 3 4 5
3: 0 1 2 3
4: 4 5 0 1
5: 2 3 4 5
If you'll notice, car 0 runs twice in the first and third lanes, but not at all in the second and fourth lanes. Further more, cars 0 and 1 run against each other a total of four times, while most of the other cars only meet each other twice.
If you checked any of the resources under "Pope's Pinewood Pages Portal", you may have come across the "Perfect-N" method. This is a variation on the naive round robin approach above that can achieve a "perfect" chart in terms of lane assignments and opponent matchups. Unfortunately, the Perfect-N method does not work for all combinations of inputs.
Let's consider another way of generating a chart. I'll call this a "chaotic" method, because we're going to assign cars to heats at random, while trying to maximize our fairness and fun criteria as we go.
Taking our 6 cars/4 lanes example from above, we could assign the first heat by just choosing four cars at random. For example:
0: 3 1 5 0
Now, let's start assigning cars to the second heat. Our objective is to run each car in each lane one time (one round), so car 3 is not a candidate for the first lane. Of the remaining cars, 1, 5, and 0 have run recently, while 2 and 4 have not, so we should prefer 2 or 4 over the others. Between 2 and 4, does it matter? No, so let's choose one at random:
0: 3 1 5 0
1: 2
Now, for assigning to the second lane, car 2 is obviously out (since a car can't run in two lanes in the same heat). Of the five remaining cars, all have run recently except for 4, so let's choose him:
0: 3 1 5 0
1: 2 4
The candidates for the third lane are 0, 1, and 3 (2 and 4 are already in this heat, and 5 has already run in this lane). Let's choose one at random:
0: 3 1 5 0
1: 2 4 0
The last lane can take 1 or 3. Again, we can just choose at random:
0: 3 1 5 0
1: 2 4 0 3
As we increase the number of cars, the matchups between cars will be an increasingly important factor. Given a number of cars to choose from for the last lane, we would want to favor those with fewer assignments against the opponents already slotted to the current heat.
So the algorithm is:
* rule out any cars already scheduled in this heat
* rule out any cars that have already run the maximum number of times in
this lane
* favor cars with fewer matchups against these opponents
* favor cars that have not been scheduled recently
Here's a ChaoticChart class that implements this logic:
# coefficients for weighting formula for lane assignment.
# these were derived by experimentation.
FL = 3.0
FP = 1.0
FD = 3.0
# generates the chart by assigning cars to heats
def generate
begin
# assigned heats by car, last heat by car
ah = Array.new(cars) { 0 }
lh = Array.new(cars)
# assignments by car/lane
al = Array.new(cars) { Array.new(lanes) { 0 } }
# matchups by car pair
op = Matchups.new
# schedule by heat by lane
chart.clear
# generate each heat
(cars * rounds).times do |heat|
# current car assignments by lane
h = []
# slot each lane
lanes.times do |lane|
# computed weights for each car
w = {}
# assign weights to each car for this slot
cars.times do |car|
# skip car if it's already been slotted to this heat
next if h.include? car
# skip car if it's already run max heats in this lane
next if al[car][lane] >= @rounds
# weight factor 1: no. of times slotted to this lane
f1 = FL * al[car][lane]
# weight factor 2: no. of times against these opponents
f2 = FP * h.inject(0) do |f, opp|
f + op[car, opp]
end
# weight factor 3: no. of heats since last scheduled
# (distribute cars through the heats)
f3 = 0
if lh[car]
f3 = FD * (cars / lanes) / (heat - lh[car])
end
# total weight for this car
w[car] = f1 + f2 + f3
end
raise NoCarsException if w.empty?
# sort by weight and get the lowest weight(s)
w = w.sort_by { |k, v| v }
w.pop while w[-1][1] > w[0][1]
# randomly choose a car and slot it
car = w[rand(w.size)][0]
# accumulate statistics
ah[car] += 1
lh[car] = heat
al[car][lane] += 1
h.each do |opp|
op[car, opp] += 1
end
# slot car to current heat
h << car
end
# add current heat to chart
chart << h
end
rescue NoCarsException
retry
end
end
end
The generate method tracks several things as it works:
* The number of heats each car has been assigned to
* The last heat each car was assigned to
* The number of times each car has been assigned to each lane
* The number of times each car has been matched against every other car
The algorithm steps through each heat and "slots" a car to each lane. For each slot, it first eliminates any cars that have run their maximum times in the current lane or that have already been scheduled to the current heat.
For the remaining cars, a "weight" factor is computed that considers the factors mentioned above. The "weight" value for each car acts as a bias against selecting that car; i.e. the car(s) with the lowest weights will be considered for slotting. If multiple cars have the lowest weight, a random choice is made from among them.
Daniel Sheppard provided some code to analyze a generated chart to see how fair it is. My second submission contains some analysis routines as well. Perhaps someone will take these starting points and come up with a technique for creating optimal charts for any combinations of inputs.
