in reply to Perl for Adjudication

I'm sorry, but your problem just isn't very clear. Having read your question and the discussion I am not sure that I understand a number of basic things. The cause of this is that you have created a private language from familiarity with the problem, and are not aware that you have not communicated what this language is clearly to bystanders. Unfortunately this means that nobody can help you because they don't understand you.

But I think I have puzzled out your real question. Please correct this description if it is wrong.

Many schools register many particpants (a participant can be one person, or a team of 2-3 people) for many different competitions. A participant is also called a competitor. Each competition takes place in 3 rounds. In each round the participants are divided into a series of panels. The members of a panel all compete in front of some judge who scores the round. For logistical reasons panels should be around the same size as each other, and their size should not exceed 6. For resource reasons you would like to do this with as few judges as possible for the competition.

The maximally flexible situation is one where your program gets information about how many schools are in a given competition, how many participants each provides, and optionally the number of judges that you need. It is then supposed to devise up the best schedule that it can for the 3 rounds of competition. It appears from running your code that you have set the number of students per school to 3, and you decide the number of judges according to some rule that I didn't look up.

And there are two additional complex requirements. First you don't want to ever have 2 participants from the same school on the same panel. You would also like to avoid having pairs of participants appear in different rounds on the same panel as each other.

Is this right? If so then a few observations.

You claim to have found that setting this up by hand for a small number of participants is fairly easy. But you can't always satisfy all of the rules. My guess is that when you went to the math people asking to find the perfect solution, they taught you factorials to show you how many different possible solutions you had to search through to find the perfect answer. (You might have even written code that should work, but it didn't finish?)

My first suggestion is that if you really can assume that there are always 3 competitors per school then you should pre-build a set of optimal solutions in a data file, and then have your CGI script just return the one that matches the size that you have handled. That leaves the problem of generating those optimal solutions..once.

My suggestion for that is that you write a program to look for good solutions, but not worry about perfection. Here is a possible algorithm that I would try writing for the absolutely general problem (arbitrary number of schools, arbitrary number of participants per school, fixed number of judges handed to me).

  1. Decide the sizes of each panel so that they are as close to even as possible (we are not worrying about your "6 participants" rule here - just break them up as evenly as you can).
  2. Randomly assign participants to panels, taking care not to assign 2 people from the same school to the same panel.
  3. Calculate how many undesired "collisions" you have (2 people from the same school on the same panel, people meeting in different rounds).
  4. Go through each round and pair of participants (I would do this in random order), and decide whether to switch them. You won't switch if it puts two people from the same school on the same panel. You won't switch if it increases the number of times that 2 people meet multiple times on the same panel. You will if it reduces number of pairs that meet twice. When it is a wash, randomly choose whether or not to flip them.
  5. Repeat the previous step while there are any collisions left and you managed to reduce the number of collisions any time in the last 3 passes. (3 is an arbitrary number.)
  6. Write out your "best I could do" solution.
Then I would work out your optimal solutions to your original problem by, for each number of schools, starting with as few judges as you can, and apply the above program to find the best solution that it finds. Stop with the number of judges that gives you the first perfect solution.

Replies are listed 'Best First'.
Re: Re: Perl for Adjudication
by dejoha (Novice) on Sep 28, 2003 at 02:47 UTC

    I'm sorry about the ambiguity -- you're right about the jargon I am using. Let me try to clarify a few things as best I can.

    For simplicity in the program, I make the assumption that each school registers the maximum number of students as competitors. Let's say we have 10 schools register monologues. The maximum a school can enter in this category is 3. This would give us a maximum total of 30 competitors (in this case, 30 students). Let "A1" stand for school A, entry 1, and so on:

    A1  B1  C1  D1  E1  F1  G1  H1  I1  J1
A2  B2  C2  D2  E2  F2  G2  H2  I2  J2
A3  B3  C3  D3  D3  F3  G3  H3  I3  J3

    [download]

    There are 3 rounds. Each competitor must compete in each round. In order to accomplish this, we divide the total number of competitors into groups and send them into separate rooms, each one adjudicated by a single judge. These are the panels. Panels = Rooms. We want to keep the number of competitors in each room under six for timing purposes (each competitor performs between 3 - 5 minutes).

    At this point, we do not need to worry about the number of judges needed. In the example above, we have 30 competitors. We could use 6 rooms and 6 judges with 5 competitors in each room. Round one might look like this:

    Round 1
---+----+----+----+----+----
A1 | A2 | A3 | B1 | B2 | B3
C1 | C2 | C3 | D1 | D2 | D3
E1 | E2 | E3 | F1 | F2 | F3
G1 | G2 | G3 | H1 | H2 | H3
I1 | I2 | I3 | J1 | J2 | J3

    [download]

    One thing that I think would be most valuable, would be to find out if it is even possible to make round 2 and 3 work without breaking the competitions "rules." I think this is the reason I was told about factorials. If I could find out whether or not a certain set would or would not work, I could modify the program to work only when the number of schools is > X (for example).

    Factorials only tell you the possible matches. It doesn't factor in if a match fits my criteria. Does that make sense?

    This was why I tried to illustrate using a diagram. I was tying to see if there was a mathematical solution to figure out "how many matches are left." In my illustration, I stated that for competitor A1, after round one, his possible matches are reduced by 4. I'm not a math major, so I don't really know how to state this very clearly, but it seems like it should be some kind of simple algebra. Maybe?

    I thought that if I could figure out the "number of matches left", I might be able to use that information to find out what matches are left and use them for the next round (instead of iterating through a random list over and over). Doing it randomly seems like it would take a very long time to compute. However, if I knew mathematically what matches wouldn't work, I wouldn't have to do the randomness, per se.

    Since the possible matches is reduced each round, it is like an intricate puzzle --- the pieces can only fit a certain way.

    I hope this helps someone. I keep wanting to have a mathematical solution I can use with Perl that would help take some of the guesswork out of it. I don't mind putting Perl to work in a random recursive subroutine, but it seems like that breaks the Perl laziness rule :)

    It would be great if there were a pattern in the way you assign competitors into panels. Anyone see a pattern?

[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom