-
-
Save tmeers/8701826 to your computer and use it in GitHub Desktop.
| 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 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.
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.