IDL Scheduling Puzzle: 2011 Edition (HELP THE IDL!)

[Ralphis]

Hey everybody! I'm Ralphis. I'm the commissioner of this little thing called the International Doom League. A few years ago we had a scheduling problem and thanks to this forum (namely Cernal Joson!!!), we had a schedule to use for our next few seasons.

Though we spent the last four seasons with only eight teams, this Winter we'll be moving back to twelve. With that, we need to restructure how we schedule. I have devised a formula that will determine how each season will play out.

There are two conferences with two divisions each. In each division, there are three teams. Each team will play two games each against both divisional opponents (4 games total), one game against each team from the opposite division in the conference (3 games total), and two games against the team that finished in the same rank from the season prior from both of the other conferences' divisions (so if a team finished second in the division last season, they'll play both teams that finished second in their divisions from the other conference) 2 games).

Because of this, the schedule is likely to change every season and my ultimate hope would be that some programming genius can come out and help us by writing a program to lay out a schedule for us each season based on how teams finish. Even if this doesn't happen, we can hopefully hit the ground running into this new expansion era with your help putting together the first season's schedule.

We're aiming for every team to have a game for all 9 weeks of the season, we're no longer using a bye week. This means there have to be six games each week. We generally don't want a string of consecutive divisional games (a team shouldn't have three div games in a row) and we definitely never want two divisional opponents to meet back to back. Those are the only guidelines.

Hopefully one of you smart guys here can help us! Here's a list of the games from this season that need to be played:

IDL 2011 DIVISIONAL ALIGNMENT

IDC NORTH
--------
(EBL)
(KGB)
(SHK)

IDC SOUTH
--------
(SUC)
(DMR)
(DCL)

WDC EAST
--------
(BSK)
(SPE)
(KNF)

WDC WEST
--------
(BBC)
(FLS)
(LST)

--------------------------
DIV - Divisional Game
ICF - Inter-conference Game

EBL v KGB (DIV)
EBL v KGB (DIV)
EBL v SHK (DIV)
EBL v SHK (DIV)
KGB v SHK (DIV)
KGB v SHK (DIV)
SUC v DMR (DIV)
SUC v DMR (DIV)
SUC v DCL (DIV)
SUC v DCL (DIV)
DMR v DCL (DIV)
DMR v DCL (DIV)
BSK v SPE (DIV)
BSK v SPE (DIV)
BSK v KNF (DIV)
BSK v KNF (DIV)
SPE v KNF (DIV)
SPE v KNF (DIV)
BBC v FLS (DIV)
BBC v FLS (DIV)
BBC v LST (DIV)
BBC v LST (DIV)
FLS v LST (DIV)
FLS v LST (DIV)
EBL v SUC 
EBL v DMR
EBL v DCL
KGB v SUC
KGB v DMR
KGB v DCL
SHK v SUC
SHK v DMR
SHK v DCL
BSK v BBC
BSK v FLS
BSK v LST
SPE v BBC
SPE v FLS
SPE v LST
KNF v BBC
KNF v FLS
KNF v LST
EBL v BSK (ICF)
EBL v BBC (ICF)
KGB v SPE (ICF)
KGB v FLS (ICF)
SHK v KNF (ICF)
SHK v LST (ICF)
SUC v BSK (ICF)
SUC v BBC (ICF)
DMR v SPE (ICF)
DMR v FLS (ICF)
DCL v KNF (ICF)
DCL v LST (ICF)

[Ralphis]

Bump! Cernal Joson please help us! We've been trying to iron out this schedule for a few weeks and have not had any luck, then again none of us are real math wizards. I'm also not entirely opposed to coming to some type of agreement with a programmer who can write something for us to do this schedule every season according to our formula.

[Sharessa]

Ralphis said:

Bump! Cernal Joson please help us!

[crackering]No, Ralph, you are the demons.[/crackering]

[Ralphis]

I changed this up to look a bit easier, still haven't figured anything out though. This makes it easier to look at though:

[code]IDL 2011 DIVISIONAL ALIGNMENT

IDC NORTH
--------
(A)
(B)
(C)

IDC SOUTH
--------
(D)
(E)
(F)

WDC EAST
--------
(1)
(2)
(3)

WDC WEST
--------
(4)
(5)
(6)

--------------------------
DIV - Divisional Game
ICF - Inter-conference Game

A v B (DIV)
A v B (DIV)
A v C (DIV)
A v C (DIV)
B v C (DIV)
B v C (DIV)
D v E (DIV)
D v E (DIV)
D v F (DIV)
D v F (DIV)
E v F (DIV)
E v F (DIV)
1 v 2 (DIV)
1 v 2 (DIV)
1 v 3 (DIV)
1 v 3 (DIV)
2 v 3 (DIV)
2 v 3 (DIV)
4 v 5 (DIV)
4 v 5 (DIV)
4 v 6 (DIV)
4 v 6 (DIV)
5 v 6 (DIV)
5 v 6 (DIV)
A v D 
A v E
A v F
B v D
B v E
B v F
C v D
C v E
C v F
1 v 4
1 v 5
1 v 6
2 v 4
2 v 5
2 v 6
3 v 4
3 v 5
3 v 6
A v 1 (ICF)
A v 4 (ICF)
B v 2 (ICF)
B v 5 (ICF)
C v 3 (ICF)
C v 6 (ICF)
D v 1 (ICF)
D v 4 (ICF)
E v 2 (ICF)
E v 5 (ICF)
F v 3 (ICF)
F v 6 (ICF)

[gggmork]

'against the team that finished in the same rank from the season'

Is it possible to tie? if multiple teams have the same rank, is a pair chosen randomly? I'm no math or programming genius but I did dippy little problems like this with python before and there's a slight chance I'm non-retarded enough to make something.. but its hard to concentrate on such a huge pile of tl;dr.
Does this whole thing serve a real purpose, or is it just some sort of 'puzzle' just for the feck of it with an elaborate fictional first person story attached?

[Creaphis]

There's no such thing as the IDL. Ralphis just likes riddles.

[Ralphis]

gggmork said:

'against the team that finished in the same rank from the season'

Is it possible to tie? if multiple teams have the same rank, is a pair chosen randomly? I'm no math or programming genius but I did dippy little problems like this with python before and there's a slight chance I'm non-retarded enough to make something.. but its hard to concentrate on such a huge pile of tl;dr.
Does this whole thing serve a real purpose, or is it just some sort of 'puzzle' just for the feck of it with an elaborate fictional first person story attached?

Yes, this is for a purpose. I've run a Doom CTF league for almost half a decade called the International Doom League. We've had probably about a total of 150 players sign up since the league's inception in 2006, about 120 players play, and a few hundred great games. We're about to head into our 5th calendar year and 9th season.

---------------------------------------

In the earlier seasons, we ran the league with 12 teams, but in 2009 went to an 8 team format for four seasons. We're now looking to go back and add four more teams again, and teams partially roll over from season to season. We also want to add a 9th game to our current 8 game format. Under these conditions, I came up with a formula for how to determine opponents based on the prior season's standings:

Conference/Divisional Alignment
1. There are two conferences with six teams each.
2. Each conference has two divisions, with three teams each.

How opponents are chosen for each team:
1. A team must face the other two divisional opponents twice each. We refer to these as divisional games. This makes up four games on the schedule.

2. A team must face all three teams from the other division in their conference once each. We refer to these as conference games. This makes up three games on the schedule.

3. A team must face one opponent from each division in the other conference. We refer to these as inter-conference games. These opponents are determined based on rank in standings from the prior season. So, if a team finished 2nd in their division in IDC North, they would face the teams that finished 2nd in the WDC East and WDC South, respectively. This makes up two games on the schedule.

There are only two conditions that have to be met when it comes to breaking down the schedule into nine weeks:

1. No team should ever have three divisional games consecutively.

2. No team should ever play the same divisional opponent two weeks in a row.

Other stuff:

It's not possible to tie in rankings in the IDL because of a series of tie breakers we've established, which include head-to-head records, strength of schedule, and strength of victory.

---------------------------------------

I made up a small spreadsheet to show how the opponents were chosen. It might be easier to see what we're trying to accomplish visually.



The green box signifies the team we're looking at and each red dot represents one game against any marked opponent. As you can see, teams within the division will meet twice (they have two dots). You can also see how those that finished bottom in their division (like Team 6), will play the bottom two teams from the opposite conference (Teams C & F).

A large spreadsheet of the listing of games from next season can be found here: http://ralphis.unidoom.org/stuff/idl/w2011_opp.htm

---------------------------------------

The International Doom League really needs to figure out a way to make this work! We've been trying to figure out how to schedule this for weeks but haven't come up with anything. About 60-70 players are relying on us coming up with this schedule and making it work, so any help would be insanely appreciated!

[Creaphis]

Ralphis, your plight has moved me, so yesterday I decided to tackle this problem. I dusted off a five year old intro-to-Java textbook, spent some frustrating hours trying to remember how anything works and then programmed a schedule generator! - which never actually generated a schedule. Lacking any better ideas, I had tried the brute force method - it randomly assembles possible seasons from your game list and then tests if they're usable afterward. It turns out that randomly coming up with a season that meets all your criteria is about as likely as sorting a deck of cards into its separate suits, each in ascending order, with one shuffle.

So, today I took a pencil and a piece of paper...

Week 1
A v B, DIV
D v E, DIV
1 v 2, DIV
4 v 5, DIV
C v 3, ICF
F v 6, ICF
Week 2
B v C, DIV
E v F, DIV
2 v 3, DIV
5 v 6, DIV
A v 4, ICF
D v 1, ICF
Week 3
A v C, DIV
D v F, DIV
1 v 3, DIV
4 v 6, DIV
B v 5, ICF
E v 2, ICF
Week 4
A v D
B v E
C v F
1 v 4
2 v 5
3 v 6
Week 5
A v E
B v F
C v D
1 v 5
2 v 6
3 v 4
Week 6
A v F
B v D
C v E
1 v 6
2 v 4
3 v 5
Week 7
A v B, DIV
D v E, DIV
1 v 2, DIV
4 v 5, DIV
C v 6, ICF
F v 3, ICF
Week 8
B v C, DIV
E v F, DIV
2 v 3, DIV
5 v 6, DIV
A v 1, ICF
D v 4, ICF
Week 9
A v C, DIV
D v F, DIV
1 v 3, DIV
4 v 6, DIV
B v 2, ICF
E v 5, ICF

[Ralphis]

Creaphis thank you so much! We really appreciate you coming to a solution for our problem as I'm sure it was very time consuming. In thanks, I will now no longer condemn you from finishing your name with "phis" as well. You're now worthy!

Thanks again Creaphis, you saved the IDL!

[dew]

may i be dewphis?

wait. that doesn't sound right.

[Belial]

Where's DomRem when you need him...

[Creaphis]

Ralphis said:

Creaphis thank you so much!

No probs.

Ralphis said:

In thanks, I will now no longer condemn you from finishing your name with "phis" as well.

Ha, I was actually going to suggest this. Thanks a bunch!

Anyways, more about the schedule: I imagine that you'd like to use a different schedule every season, and unfortunately I never came up with a way to produce schedules that are vastly different, but I think you should be able to get some mileage out of this one by just changing the week order each year. I can see a lot of ways that the order could be changed while still keeping any teams from playing too many consecutive division games. That should be a passable solution until a better programmer comes along.

[Ralphis]

Creaphis said:

Anyways, more about the schedule: I imagine that you'd like to use a different schedule every season, and unfortunately I never came up with a way to produce schedules that are vastly different, but I think you should be able to get some mileage out of this one by just changing the week order each year. I can see a lot of ways that the order could be changed while still keeping any teams from playing too many consecutive division games. That should be a passable solution until a better programmer comes along.

This will probably suit us just fine. Along with being able to just move the weeks around, the teams that we slide into the letters/numbers will be different every season most likely. For instance, if a team that finished second and was B last year finishes first this season, they'll become A. It should work out just fine. Thanks dawg!