Friday, August 31, 2012

First Kittendome meeting in PyCon 2013 Program Committee

Yesterday marked the first Kittendome meeting in preparation for US PyCon 2013.

I attended the meeting in #pycon-pc on Freenode. It went surprisingly well. This is all thanks to the hard work that the committee has put in over the years and the enormous energy that the chairs have spent ensuring the facilities are in good shape.

The pycon_bot was very helpful, too. In fact, it was kinda neat to have a bot tally all votes and organize the meeting. It even pestered voters who had not voted! I would absolutely consider using the IRC bot if I ever hold any meeting over IRC.

Sunday, August 26, 2012

Pair work in a classroom

Problem statement

You’re in charge of teaching a classroom of students and in the next assessment, each student has the option to work either in pairs or alone. As it turns out, the students are seated in an M x N rectangular grid, and each student can work with up to one adjacent classmate -- a student in the center of the classroom has up to 4 choices of partners, while those at the corners have up to 2.

We assume that the productivity of each student (when working alone) is represented by a positive integer. When two adjacent students work as a pair, their combined productivity is equal to the product of their individual productivities. For example, if two adjacent students have productivities of 3 and 5 each, then their total productivity would be 8 when working separately, but 15 when working together as a pair. Students with productivity 1 always prefer to work alone and should never be placed in a pair.

Task: Given the productivity for each individual in the class (as a grid of positive integers), design an algorithm that computes the maximum total productivity achievable by pairing students in the class. Note that the total productivity consists of the summed productivities of all pairs and students working alone; note also that productivity scores should only be counted once per pairing, not once for each individual in the pairing.

Solution

Based on a checker pattern, students can be divided into two groups: those on the white spots, and those on the black spots. Position (0, 0) is the first white spot; next position (0, 1) is the first black spot and so on, as illustrated in figure below.

(0, 0)(0, 1)(0, 2)
(1, 0)(1, 1)(1, 2)
(2, 0)(2, 1)(2, 2)

Observation: students on the white spots can only pair with students on the black spots and vice versa.

The maximum productivity value is attained when we can pair all students up in a way that the sum of their productivity values is greatest. And this problem can be easily solved with min-cost bipartie matching algorithm such as Hungarian algorithm.

With the input below, I got 1859 as the answer. What do you get?

inp = [
 '7 5 9 2 3 1 9 3 3 6 2 1 5 3 4',
 '1 2 7 1 5 2 8 6 1 3 4 3 4 7 3',
 '2 9 5 4 4 2 5 1 1 6 1 8 9 5 2',
 '1 8 2 2 4 3 8 8 8 9 6 7 3 6 7',
 '8 1 4 2 4 7 9 9 1 5 4 7 7 6 2',
 '4 3 6 3 2 3 8 9 5 2 7 4 7 1 1',
 '2 7 2 6 1 2 3 3 3 6 5 6 1 1 7',
 '4 6 2 3 6 2 6 4 3 2 1 1 5 7 7',
 '6 5 9 6 4 1 2 3 6 2 4 9 8 4 7',
 '5 9 6 8 5 2 3 5 1 7 2 8 5 7 5',
]