Last updated on January 26, 2021
Talking with a teacher in a local school district, they were about to start hybrid learning. Previously all students were doing distance learning, but starting in about a week, they will go into class two days a week. Half the students will go in something like Monday and Wednesday and the other half will go in Tuesday and Thursday.
Some families have multiple children who go to the school. One of the bigger concerns is making sure parents don’t have to go to the school all four days a week in-person learning is done. They’ve basically taken all students whose last name begins with a letter in the first half of the alphabet and assigned them to one group, then assigned the rest to the other group. This works well enough for the parents, but some of the teachers have fairly unbalanced groups, with way more students in one group than the other.
At first, my thought was that we could just try different combinations until we found one that worked. Grouping students by their last names and working from the largest group to the smallest, recursively work the combinations sort of like the 8 queens problem.
Working that out, I figured I’d have to check through all the teachers at the end to see if they were balanced, if not, reject the solution, go back an iteration, and try again. As I was mulling that about, I figured that that would be a lot of checking. And we’re also looking at
GROUPN! number of possible combinations.
So, could I do it as I go? Well, at the end of the day, there will be a number of students with no other siblings attending the school. So we should wind up with a decent number of singles we can just use to fill gaps. Then it’s just a matter of not filling up either day too much. I could still work from largest group to smallest, but how I allocate the students would require finesse.
My biggest concern is keeping the days as balanced as possible across all teachers. So if I could dump the group of students on the day that needed it most, I could keep the days balanced as I go. Which day needs it most? Well, not every teacher will have students with a certain last name. Between all those teachers, we know how many students were assigned to be on day 1 and day 2 for each teacher. From there we find the highest day 1 total and the highest day 2 total. The day we want is the day represented by the lower of those two totals. The min of maxes. This also happens to work all the way down the line. The single student groups will just be placed in the day needed by that teacher.
def findLowerDay(teacherList): #current maxes for teachers on day1 and day2 mday1 = 0 mday2 = 0 for currentTeacher in teacherList: #get this teacher's counts and set them to the max if greater cday1 = sum(1 for y in currentTeacher.students if y.day == 1) if cday1 > mday1: mday1 = cday1 cday2 = sum(1 for y in currentTeacher.students if y.day == 2) if cday2 > mday2: mday2 = cday2 #now we know the most students any of these teachers have on either day #we choose the day with fewer students #tie goes to day2 if mday1 < mday2: return 1 else: return 2
The link to the repository is below