# Pinewood Derby Chart (#56)

**URL:** <https://www.ruby-forum.com/t/pinewood-derby-chart-56/91501>\
**Category:** Ruby\
**Created:** [December 1, 2005, 2:51pm UTC](https://www.ruby-forum.com/t/pinewood-derby-chart-56/91501 "2005-12-01T14:51:24Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [December 1, 2005, 2:51pm UTC](https://www.ruby-forum.com/t/pinewood-derby-chart-56/91501/1 "2005-12-01T14:51:24Z")

</div>

by Bob S.

[Ediitor’s Note: I hope everyone noticed that Bob just ran, solved, and  
summarized a Ruby Q. 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:

```
# Pinewood Derby chart
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:

```
# prints the 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:

```
class RoundRobinChart < Chart

  # 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:

```
class ChaoticChart < Chart

  # 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 S. 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.