Liz Douglass

Frenzy Fixtures in Scala

leave a comment »

Following on from my post about Friday Feedback Frenzies, Mark, Ben and I looked at how to work out frenzy pairs. The idea with the frenzies is that you exchange feedback with two people each week, and that you rotate the people that you do this with. When I have organised these previously I have generally just picked people at random. Mark, Ben and I decided to generate a frenzy fixture (if you will).

Mark came up with the idea of using something like a football/tennis game scheduling algorithm. We found a Round Robin cyclic algorithm to get us started. Our first step was to get this algorithm working in Scala:

      val numberOfPlayers = 12
      for (round <- 1 to 11) {
        for (court <- 1 to 6) {
          print((if(court == 1) 1 else (round + court - 2) % (numberOfPlayers - 1) + 2),
                (numberOfPlayers - 1 + round - court) % (numberOfPlayers - 1) + 2)
        }
        println()
      }

The output from this is below. Each row represents a round and each bracketed pair in a row represents a match-up of two players on a court.

(1,2)(3,12)(4,11)(5,10)(6,9)(7,8)
(1,3)(4,2)(5,12)(6,11)(7,10)(8,9)
(1,4)(5,3)(6,2)(7,12)(8,11)(9,10)
(1,5)(6,4)(7,3)(8,2)(9,12)(10,11)
(1,6)(7,5)(8,4)(9,3)(10,2)(11,12)
(1,7)(8,6)(9,5)(10,4)(11,3)(12,2)
(1,8)(9,7)(10,6)(11,5)(12,4)(2,3)
(1,9)(10,8)(11,7)(12,6)(2,5)(3,4)
(1,10)(11,9)(12,8)(2,7)(3,6)(4,5)
(1,11)(12,10)(2,9)(3,8)(4,7)(5,6)
(1,12)(2,11)(3,10)(4,9)(5,8)(6,7)

Next we moved from everything being 1 indexed to being 0 indexed. We also changed the fixed player, who always plays on court 0, to be the last one in the player list. This was done only because it made the loops more readable:

      val numberOfPlayers = 12
      for (round <- 0 to 10) {
        for (court <- 0 to numberOfPlayers/2 - 1) {
          print(((if(court == 0) numberOfPlayers - 1 else (court + round) % (numberOfPlayers - 1))),
                (((numberOfPlayers - 1) - court + round) % (numberOfPlayers - 1)))
        }
        println()
      }

Then the output was:

(11,0)(1,10)(2,9)(3,8)(4,7)(5,6)
(11,1)(2,0)(3,10)(4,9)(5,8)(6,7)
(11,2)(3,1)(4,0)(5,10)(6,9)(7,8)
(11,3)(4,2)(5,1)(6,0)(7,10)(8,9)
(11,4)(5,3)(6,2)(7,1)(8,0)(9,10)
(11,5)(6,4)(7,3)(8,2)(9,1)(10,0)
(11,6)(7,5)(8,4)(9,3)(10,2)(0,1)
(11,7)(8,6)(9,5)(10,4)(0,3)(1,2)
(11,8)(9,7)(10,6)(0,5)(1,4)(2,3)
(11,9)(10,8)(0,7)(1,6)(2,5)(3,4)
(11,10)(0,9)(1,8)(2,7)(3,6)(4,5)

Our next step was to switch domains from sports to feedback frenzies:

val participants = 12
val weeks = 10
for (frenzy <- 0 until weeks) {
  for (pair <- 0 until participants/2) {
    print(((if(pair == 0) participants - 1 else (pair + frenzy) % (participants - 1))),
          (((participants - 1) - pair + frenzy) % (participants - 1)))
  }
  println()
}

Then we changed to creating a collection of all the pairs:

      val participants = 12
      val weeks = 10
      val frenzyPairs = for {
        frenzy <- 0 until weeks
        pair <- 0 until participants/2
      } yield (((if(pair == 0) participants - 1 else (pair + frenzy) % (participants - 1))),
                (((participants - 1) - pair + frenzy) % (participants - 1)))
      frenzyPairs.foreach(print)
    }

And the output…

RangeM((11,0), (1,10), (2,9), (3,8), (4,7), (5,6))
RangeM((11,1), (2,0), (3,10), (4,9), (5,8), (6,7))
RangeM((11,2), (3,1), (4,0), (5,10), (6,9), (7,8))
RangeM((11,3), (4,2), (5,1), (6,0), (7,10), (8,9))
RangeM((11,4), (5,3), (6,2), (7,1), (8,0), (9,10))
RangeM((11,5), (6,4), (7,3), (8,2), (9,1), (10,0))
RangeM((11,6), (7,5), (8,4), (9,3), (10,2), (0,1))
RangeM((11,7), (8,6), (9,5), (10,4), (0,3), (1,2))
RangeM((11,8), (9,7), (10,6), (0,5), (1,4), (2,3))
RangeM((11,9), (10,8), (0,7), (1,6), (2,5), (3,4))

As Ben quite rightly pointed out if we take two rows a time, then each person will exchange feedback with two people in the same frenzy. Our final step was to group each pair of successive rows. To do this we first moved to having two nested for loops. We thought that this would make it easier to do the grouping, but it ended up being redundant. Here our final version of the frenzy fixture generator:

      val participants = 12
      val rounds = 10
      val frenzyPairs = for (frenzy <- 0 until rounds)
                      yield for(pair <- 0 until participants/2)
                            yield (((if(pair == 0) participants - 1 else (pair + frenzy) % (participants - 1))),
                                  (((participants - 1) - pair + frenzy) % (participants - 1)))

      val (evenOnes,oddOnes) = frenzyPairs.toList.zipWithIndex.partition(_._2%2 == 0)
      evenOnes.zip(oddOnes).foreach(println)

Our final output was:

((RangeM((11,0), (1,10), (2,9), (3,8), (4,7), (5,6)),0),(RangeM((11,1), (2,0), (3,10), (4,9), (5,8), (6,7)),1))
((RangeM((11,2), (3,1), (4,0), (5,10), (6,9), (7,8)),2),(RangeM((11,3), (4,2), (5,1), (6,0), (7,10), (8,9)),3))
((RangeM((11,4), (5,3), (6,2), (7,1), (8,0), (9,10)),4),(RangeM((11,5), (6,4), (7,3), (8,2), (9,1), (10,0)),5))
((RangeM((11,6), (7,5), (8,4), (9,3), (10,2), (0,1)),6),(RangeM((11,7), (8,6), (9,5), (10,4), (0,3), (1,2)),7))
((RangeM((11,8), (9,7), (10,6), (0,5), (1,4), (2,3)),8),(RangeM((11,9), (10,8), (0,7), (1,6), (2,5), (3,4)),9))

The end result could be tidied up a little but it does provide us with a frenzy fixture for a given number of participants. Given more time we would have used names for participants rather than just numbers.

Advertisements

Written by lizdouglass

November 18, 2009 at 11:52 am

Posted in Uncategorized

Tagged with ,

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: