Rules for generating Pinewood Derby Race Heats in a "Chaotic-Rotation Method"

gistfile1.txt

 Get number of heats based on LaneCount and RacerCount: totalHeats
 
 Add a Race per Den
    For each Heat found above: 
    Select random racers for the lineup based on a "Chaotic-Rotation Method"
       Each Racer must race at least 3 times
       Each racer must race the same number of times
       Racers should be held in a race through as many heats as possible
       Racers cannot compete against themselves
       Racers should compete against as many different opponents as possible
    
   Given data:
     Den (Id, Name)
     List of Racers (RacerId, ScoutId, CarNumber, Weight)
     Number of Lanes (4 lanes is the easiest)
   Data to Generate
    -Number of Heats based on Lane and Racer counts
     3 lanes is almost 1 lane per racer, unless it's not
     4 lanes is 1 heat per racer
     6 lanes is the most complex though I'm sure it's simple math (that I don't know)
    -Race
       id
       denId
      -Heats
          id
          raceId
        - Contestants
            heatId
            racerId
            laneNumber
              

Some basic heat counts. I know there has to be some math to number of lanes with number of racers I just don't know what it is. So sticking with some basics for now until I can get that figured out as well.

        // Heat count based off of numbers from known working spreadsheets (ugh spreadsheets)  
        //        here: https://sites.google.com/site/pinewoodscore/Spreadsheets
        private int GenerateHeatCount(int laneCount , int racersCount )
        {
            if (laneCount == 4)
                return racersCount;

            if (laneCount == 6 && ((racersCount <= 7 && racersCount > 3) || racersCount == 9 || racersCount == 10 || racersCount == 12))
                return racersCount;

            if (laneCount == 6 && (racersCount <= 3))
                return 4;

            return laneCount;
        }

Some work on the problem has been completed but it's a very incomplete solution.

A sample console application that will generate heats for 5 racers on a 4 lane track.

    class Program
    {
        public static int LaneCount = 4;
        public static int HeatCount { get; set; }

        private static List<Contestant> usedContestants = new List<Contestant>();
        private static List<Racer> racers = new List<Racer>(); 

        static void Main(string[] args)
        {
            LaneCount = 4;

            racers = GetRacers();
            int totalHeats = GenerateHeatCount(LaneCount, racers.Count);

            Console.WriteLine("Total racers: " + racers.Count());
            Console.WriteLine("Total lanes: " + LaneCount);
            Console.WriteLine("Total heats: " + totalHeats);

            List<Heat> Heats = new List<Heat>();
            ICollection<int> lanes = new Collection<int>();
            bool firstHeat = true;
            int heatId = 1;
            for (int i = 0; i <= (totalHeats - 1); i++)
            {
                ICollection<Lane> usedLanes = new Collection<Lane>();
                var heat = new Heat();
                heat.Id = heatId;
                heat.RaceId = 1;
                heat.Contestants = new List<Contestant>();

                foreach (var lane in FillLineup(racers, heat.Id))
                {
                    var _lane = lane;
                    Contestant _contestant = new Contestant();
                    _contestant.HeatId = heat.Id;
                    _contestant.Car = racers.FirstOrDefault(x => x.Id == _lane.Car).Name;
                    _contestant.Lane = _lane.LaneNumber;
                    heat.Contestants.Add(_contestant);
                }

                Heats.Add(heat);
                heatId++;
                firstHeat = false;
            }

            foreach (var heat in Heats)
            {
                var _heat = heat;
                Console.WriteLine("Id: " + _heat.Id);
                Console.WriteLine("-------");
                foreach (var racer in _heat.Contestants)
                {
                    Console.WriteLine(racer.Lane + ": " + racer.Car);
                }
                Console.WriteLine(" ");
            }

            Console.ReadKey();
        }

        private static int GenerateHeatCount(int laneCount, int racersCount)
        {
            if (laneCount == 4)
                return racersCount;

            if (laneCount == 6 && ((racersCount <= 7 && racersCount > 3) || racersCount == 9 || racersCount == 10 || racersCount == 12))
                return racersCount;

            if (laneCount == 6 && (racersCount <= 3))
                return 4;

            return laneCount;
        }

        private static ICollection<int> GetLanes()
        {
            ICollection<int> lanes = new Collection<int>();
            for (int i = 1; i <= LaneCount; i++)
            {
                lanes.Add(i);
            }
            return lanes;
        }

        public static List<Racer> GetRacers()
        {
            var racers = new List<Racer>();
            racers.Add( new Racer() { Id = 1, Name = "aaaa" });
            racers.Add( new Racer() { Id = 2, Name = "bbbb" });
            racers.Add( new Racer() { Id = 3, Name = "cccc" });
            racers.Add( new Racer() { Id = 4, Name = "dddd" });
            racers.Add( new Racer() { Id = 5, Name = "eeee" });

            return racers;
        }

        public static int GetRandomLane(ICollection<Lane> usedLanes, int carId, int currentHeat)
        {
            IEnumerable<int> myValues = new List<int>(new[] { 1, 2, 3, 4 });
            var lastLane = usedLanes.FirstOrDefault(x => x.HeatId == (currentHeat - 1) && x.Car == carId);
            if (lastLane == null)
                return 1;

            Random r = new Random();
            IEnumerable<int> threeRandom = myValues.OrderBy(x => r.Next()).Take(1);

            return threeRandom.First();
        }

        private static List<Lane> FillLineup(List<Racer> racers, int heatId)
        {
            List<Contestant> previousHeat = usedContestants.Where(x => x.HeatId == heatId).ToList();
            var lanes = GetLanes();

            Random r = new Random();
            List<Racer> topRacers = racers.Where(f => !f.Finished).OrderBy(x => r.Next()).Take(4).ToList();
            var lineup = new List<Lane>();

            foreach (var item in lanes)
            {
                // loop over lanes 
                // look up next racer
                // assign lane
                var lane = item;
                bool racerAssigned = false;
                bool lanesFull = false;
                Racer _racer = new Racer();
                while ((!racerAssigned && topRacers.Any()))// && !lanesFull)
                {
                    Random rd = new Random();
                    _racer = topRacers.OrderBy(x => rd.Next()).Take(1).First();
                    var previousRaces = usedContestants.Where(x => x.RacerId == _racer.Id).ToList();

                    if (previousRaces.Count() < 4 && !lineup.Any(x => x.Car == _racer.Id))
                    {
                        //Console.WriteLine("using car: " + _racer.Name);
                        lineup.Add(new Lane() {Car = _racer.Id, LaneNumber = lane});
                        racerAssigned = true;
                        usedContestants.Add(new Contestant(){ Car = _racer.Name, HeatId = heatId, Lane = lane, RacerId = _racer.Id});
                    }
                    else
                    {
                        if (previousRaces.Count() == 4)
                        {
                            //Console.WriteLine("Completed race: " + _racer.Name);
                            var _completedRacer = racers.FirstOrDefault(x => x.Id == _racer.Id);
                            _completedRacer.Finished = true;
                        }

                        topRacers.Remove(_racer);
                        racerAssigned = false;
                    }

                    //if (lineup.Count == LaneCount || ValidateRace())
                    //    lanesFull = true;
                }

                //Console.WriteLine("Lane: " + lane + " - " + _racer.Name);
            }

            return lineup;
        }
        public static bool ValidateRace()
        {
            return true;
        }
    }
    public class Lane
    {
        public int HeatId { get; set; }
        public int Car { get; set; }
        public int LaneNumber { get; set; }
    }
    public class Racer
    {
        public int Id { get; set; }
        public string Name { get; set; }
        public bool Finished { get; set; }
    }

    public class Heat
    {
        public int Id { get; set; }
        public int RaceId { get; set; }
        public List<Contestant> Contestants { get; set; } 
    }

    public class Contestant
    {
        public int HeatId { get; set; }
        public string Car { get; set; }
        public int RacerId { get; set; }
        public int Lane { get; set; }
    }

This generates the output of:

Total racers: 5
Total lanes: 4
Total heats: 5
Id: 1
-------
1: eeee
2: aaaa
3: cccc
4: dddd

Id: 2
-------
1: aaaa
2: dddd
3: eeee
4: bbbb

Id: 3
-------
1: aaaa
2: dddd
3: eeee
4: bbbb

Id: 4
-------
1: aaaa
2: dddd
3: eeee
4: bbbb

Id: 5
-------
1: bbbb
2: cccc

You can see that not all heats are full, which they should be in this case. When you hit 4 lanes and 7 racers you start getting incomplete tracks and 8 heats. But with 5 racers and 4 lanes you should get a similar output to this:

Id: 1
1: aaaa
2: bbbb
3: cccc
4: dddd

BYE: eeee

Id: 2
1: bbbb
2: eeee
3: dddd
4: aaaa

BYE: cccc

Id: 3
1: dddd
2: aaaa
3: eeee
4: cccc

BYE: bbbb

Id: 4
1: cccc
2: dddd
3: bbbb
4: eeee

BYE: aaaa

Id: 5
1: eeee
2: cccc
3: aaaa
4: bbbb

BYE: dddd

As a note: The lane count is static and won't be changed for the entire process.
Here is the main working portion of the code:

            for (int i = 0; i <= (totalHeats - 1); i++)
            {
                var heat = new Heat();
                heat.Id = heatId;
                heat.RaceId = 1;
                heat.Contestants = new List<Contestant>();

                foreach (var lane in FillLineup(racers, heat.Id))
                {
                    var _lane = lane;
                    Contestant _contestant = new Contestant();
                    _contestant.HeatId = heat.Id;
                    _contestant.Car = racers.FirstOrDefault(x => x.Id == _lane.Car).Name;
                    _contestant.Lane = _lane.LaneNumber;
                    heat.Contestants.Add(_contestant);
                }

                Heats.Add(heat);
                heatId++;
            }

This loops the number of heats and for each heat calls FillLineup(int, int)

This FillLineup does the following:

    Gets a list of all racers that have not completed 4 races, ordered randomly
    Fills a list of Lanes for each lane on a track. 
    Loops the list of lanes
        Selects the first racer in the list of Racers
        Checks to see how many Heats it's been in previously
        If less than 4 heats, schedule the racer for the current lane
        If has been in 4 heats mark the racer as finished so it can't be selected during the next heat
    Return the List<Lane> to be added as contestants for the current heat

Expected data

With 4 lanes and 5 racers there should be 5 heats and each should have all 4 lanes filled, and one racer with a BYE for each heat. That racer should be in the next heat.

With 4 lanes and 6 racers there should be 6 heats and each should have all 4 lanes filled, and two racers with a BYE for each heat.

With 4 lanes and 7 racers there should be 8 heats and each should have all 4 lanes filled for 4 heats, and 3 lanes filled for the other 4, and no racers with a BYE for any heat.

With 4 lanes and 8 racers there should be 8 heats and each should have all 4 lanes filled, and no racer with a BYE for each heat.

With 4 lanes and 9 racers there should be 9 heats and each should have all 4 lanes filled, and one racer with a BYE for each heat. That racer should be in the next heat.

Here is my take on the problem:
https://github.com/pizzapanther/Race-Manager/blob/master/js/ctrl-race.js#L64-L189

I did things a little differently because I made some insights which I think could be good, but I'm not the best algorithm writer so it definitely needs improvement.

First instead of calculating heats I just make sure every racer races the correct amount of times and calculate races from that. I try to rotate them on the track with different opponents randomly. Also I noticed it is easier to calculate races if the number of racers is a multiple of the available tracks. So I fill in dummy racers to make this possible and hide them when displaying races. I also check to make sure a race has at least two real racers.

The downsides of this method is that because it is random it can fail a lot so I have to be lenient on the track requirement. Thus I allow a racer to end up on a track a max of two times.

I think I could get rid of this compromise of two times on a track if my algorithm was better. This reminds me of the 8-queens problem where you have to write an algorithm that is able to go back when a path fails. http://en.wikipedia.org/wiki/Eight_queens_puzzle

I failed that question on an Amazon interview so I guess I should have learned it now :-)

Lastly, I used Mario Kart scoring for each race which gives the 1st place racer the most points. At the end, I total everything and you get a winner.

The app is in the Chrome Store now: https://chrome.google.com/webstore/detail/race-manager/flgdapbfafoghifpocjbmhboaiikncoh

I'll probably create an Android Bundle too.