A Sequenced Grid

Printable View

Nov 1st, 2003, 07:31 PM
PeterPigmy

A Sequenced Grid

Guys, I am stumped. It's my first post in this section because usually I don't have a problem with logic or algorithms, just coding them!

This one, however is TOTALLY beyond me.

Now, run with me for a while.

Imagine this scenario. You are running a Model Car Racing track.

30 Guys want to race their cars.
They have to do 6 races each.
There has to be 6 people in each race... AND

The grids have to be fair so that (imagning points were allocated for finishing positions) if everyone finished every race in the same position they started every race, that everyone would end up with the same points.

Difficult enough I hear you mutter BUT......

Because they need time to re-charge their cars they cannot race in consequetive races, in fact they need a gap of TWO races.

This in itself would be bad enough, but what I really need to make is a sequencer that can build this grid with the following variables

No of Car Racers (theoretical >9 and < 250)
No of races each (>3 and <11)
No of racers in each race (>3 and <20)

If ANYONE can give me ANY pointers about how I can go about this I would be eternally grateful and remember you at Christmas time!

Thank you, in advance, for ANY help or pointers in the right direction!

Pigmy
:cool:
Nov 2nd, 2003, 06:18 AM
NotLKH

Re: A Sequenced Grid

It sounds like a fun challange, however one thing prevents me
from starting.

Quote:

Originally posted by PeterPigmy
The grids have to be fair so that (imagning points were allocated for finishing positions) if everyone finished every race in the same position they started every race, that everyone would end up with the same points.

:ehh:

If its possible, could you create a graphical representation of what we have to try to achieve? Or, if it lends itself, an Excell Table?
With pointers and explaination bubbles?

Really :confused:
-Lou
Nov 2nd, 2003, 07:07 AM
PeterPigmy

Re: Re: A Sequenced Grid

Quote:

Originally posted by NotLKH
It sounds like a fun challange, however one thing prevents me
from starting.

:ehh:

If its possible, could you create a graphical representation of what we have to try to achieve? Or, if it lends itself, an Excell Table?
With pointers and explaination bubbles?

Really :confused:
-Lou

Aha, someone who recognises the challenege. Thank you for even replying NotLKH!

A Grid
-------

1 8 13 16 22 27
2 9 14 17 23 28
3 10 15 18 24 29
4 11 16 19 25 30
5 12 17 20 26 1
6 13 18 21 27 2
7 14 19 22 28 3
8 15 20 23 29 4
9 16 21 24 30 5
10 17 22 25 1 6
11 18 23 26 2 7
12 19 24 27 3 8
13 20 25 28 4 9
14 21 26 29 5 10
15 22 27 30 6 11
16 23 28 1 7 12
17 24 29 2 8 13
18 25 30 3 9 14
19 26 1 4 10 15
20 27 2 5 11 16
21 28 3 6 12 17
22 29 4 7 13 18
23 30 5 8 14 19
24 1 6 9 15 20
25 2 7 10 16 21
26 3 8 11 17 22
27 4 9 12 18 23
28 5 10 13 19 24
29 6 11 14 20 25
30 7 12 15 21 26

Excuse the lack of Excel. This is a succesful grid (which someone produced for me years ago!) for 30 drivers racing 6 times each in grids of 6 which fulfils all the "rules".

Each Driver gets 6 races. His races are separated by at least 2 races he is not in.

If you allocate a points system ie.

1st - 6 Pts
2nd - 5Pts
3rd - 4Pts
4th - 3Pts
5th - 2Pts
6th - 1Pt

And assume these were the FINISHING positions for the race then EVERYONE ends up with 21Pts, so it is a FAIR Grid.

Now I think this is one of the easier type beacuse the NO OF DRIVERS IN EACH RACE = NO OF RACES FOR EACH DRIVER ie. 6 Drivers in Each race, everyone does 6 races. Some types of grid get more complicated ie. 6 Races each and 8 drivers in each race.

The grid must be as fair as possible and even if it is unachievable to get identical points then the smallest difference eshould be aimed at.

Does this help? I really appreciate you input! I DO recognise how tough this is gonna be!!!!

Pigmy
:cool:
Nov 2nd, 2003, 01:50 PM
NotLKH

So, in the example grid, each row represents 1 race, and each element in the row represents the racer which raced in that race.

Which, upon inspection, since each racer has to skip at least 1 race between the races he enters, taking race 1 = racers 1 8 13 16 22 27, we see that none of these are in the next race.
Indeed, its until race 4 {4 11 16 19 25 30} before even 1 of the entrents in race 1 races again. {16}

Ok. I think I've got that concept down.

BUT Now, the point system.

Quote:

If you allocate a points system ie.

1st - 6 Pts
2nd - 5Pts
3rd - 4Pts
4th - 3Pts
5th - 2Pts
6th - 1Pt

And assume these were the FINISHING positions for the race then EVERYONE ends up with 21Pts, so it is a FAIR Grid.

How are we to determine the ending positions of the drivers?
Nov 2nd, 2003, 01:53 PM
NotLKH

Wait a minute.

Is each column representative of their finishing position?
Nov 2nd, 2003, 02:56 PM
PeterPigmy

Quote:

Originally posted by NotLKH
Wait a minute.

Is each column representative of their finishing position?

I really appreciate the time you're taking even trying to understand my problem!!!

Yes, The way i'm thinking of it is that the column represents their FINSIHING position. ie. No-one passed anyone else in ANY race. So for each race STARTING POSN = FINISH POSN.

So yes, in the table, each column represents finsihing position.

The more I think about this the tougher it becomes!!!

THANKS AGAIN!

Pigmy
:cool:
Nov 3rd, 2003, 08:23 PM
PeterPigmy

I'm guessing here that everyone is looking and doing what I did, going "no way!!!".

I understand that!

Does anyone have any ideas on another forum ANYWHERE that might contain the boffins I need.

This is serioulsy out of my league!!!!!

Pigmy
:cool:
Nov 3rd, 2003, 09:22 PM
jemidiah

To me, that grid indicates you ran 30 races instead of 6 (6 cars per race * 6 races = 36 slots total. There are 180 in that grid). I'd bet that this grid would work (it'd be closest to what's possible):

Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 6 5 4 3 2 1

Now, 1-6 would have 7 points and the others would have scattered points (1-6). You could make it so that 12 get 0 while 18 of them get 7 like this:

Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 6 5 4 3 2 1 12 11 10 9 8 7 18 17 16 15 14 13

I'm assuming rows are race number and columns are starting (and finishing) places.
Nov 4th, 2003, 06:50 AM
PeterPigmy

Quote:

Originally posted by jemidiah
To me, that grid indicates you ran 30 races instead of 6 (6 cars per race * 6 races = 36 slots total. There are 180 in that grid). I'd bet that this grid would work (it'd be closest to what's possible):

I'm assuming rows are race number and columns are starting (and finishing) places.

Hi Jemidiah,

you are correct with your assumption about cols and rows.

You've missed one point though. It's not just 6 cars per race and 6 races, it's 6 cars PER RACE and 6 RACES per DRIVER

So, if the no of races EACH and the GRID size are the same then there will always be the same total number of races as there are drivers. The grid I posted before for 30 drivers is perfect as every driver receives 6 races and, if you total the points, everyone receives the same.

I know this IS a toughy!

Thanks for your input though. This'll scramble your brain, I promise.

Pigmy
:cool:
Nov 12th, 2003, 09:40 PM
TheAlchemist

hey man,
i think the task here is to assign each driver a unique position in a table 6 columns wide and 30 rows tall. I started coding a small app to do this, its pretty simple. I had a lot of stuff to do though so i didn't finish. I'll post it as soon as i get some time to finish it off.
Nov 13th, 2003, 04:21 AM
PeterPigmy

Quote:

Originally posted by TheAlchemist
hey man,
i think the task here is to assign each driver a unique position in a table 6 columns wide and 30 rows tall. I started coding a small app to do this, its pretty simple. I had a lot of stuff to do though so i didn't finish. I'll post it as soon as i get some time to finish it off.

If there is something i've missed and it's easier than i'm imagining then i'd be the happiest person around, coz it's driving me nuts!

Thank you Mr Almchemist, I look forward to your next post!

Thanx!

Pigmy
:cool:
Nov 20th, 2003, 01:02 AM
TheAlchemist

no problem man, thanks for posting the problem!
i still haven't managed to get time to finish the app off but following is how i was trying to do it:

set up an array, possibly dimmed as a user defined type for the 30 drivers. then set up another 2 dimesional array to hold the table. next we need to set up a loop(s) and work with both arrays together. initially we could populate the first 3 rows of the table in linear order(1,2,3...)( it is not till the fourth row that the possiblity of a repition of one of the first row drivers occurs.) this is where the user defined type comes in. It would be neccesary to store a list of positions associated with a driver (so that the driver does not take the same position twice). <--This is how far i am so far.
after the third row the pattern changes. it may be neccesary to have another an ordered array to hold the list of drivers elligible for the following race. we would add one driver form this list to the table and then fill the five remaining places with drivers who haven't raced yet. Once all the drivers have raced at least once, the pattern will change again. We will have to start populating the remaing rows under some added constraints: drivers who have waited longest would be elligible for positioning first. in the case that two drivers have waited an equal number of races without racing, we would assign them both to the same race in different positions. You may have noticed that two things are vital to this algorithm: first the ordered array of drivers waiting for a race. second the list of positions already occupied by each driver.

this was just a quick explanation, there may be gaps in the logic, but this is how i propose to solve the problem. Hope it helps
Nov 23rd, 2003, 06:35 AM
TheAlchemist

1 Attachment(s)

ok man, i've done it.

just made a small modification to the my previous logic. (the logic still persists but i've coded it in such a way that there is no need to explicitly carry out the steps) --> why? because i intergrated the 2 and 3 portions of it.