Algorithm for adding students to a color group

Question

I'm developing a system where students are added to color groups (RED,BLUE,GREEN,YELLOW). They need to be added evenly. Here is a picture of the logic for adding a student to a group

Here is the logic I have so far (purely based on number of students in each group):

var studentsByColorGroup={"GREEN":[], "BLUE":[], "RED":[], "YELLOW":[]};
var gradeCountsByColorGroup={
  "GREEN" :{3:0, 4:0, 5:0, 6:0},
  "BLUE"  :{3:0, 4:0, 5:0, 6:0},
  "RED"   :{3:0, 4:0, 5:0, 6:0},
  "YELLOW":{3:0, 4:0, 5:0, 6:0}
};
for(var student of students) {
  studentsByColorGroup[student.color].push(student);
  gradeCountsByColorGroup[student.color][student.grade]++;
}
var greenCount =studentsByColorGroup["GREEN" ].length;
var blueCount  =studentsByColorGroup["BLUE"  ].length;
var redCount   =studentsByColorGroup["RED"   ].length;
var yellowCount=studentsByColorGroup["YELLOW"].length;
var list={
  "GREEN" :this.greenCount,
  "BLUE"  :this.blueCount,
  "RED"   :this.redCount,
  "YELLOW":this.yellowCount
};
var keysSorted:string[]=Object.keys(list).sort((a, b) => list[a]-list[b]);
// The first element in the list of sorted keys should 
// be the color with the LEAST students in it
newStudent.color=keysSorted[0];

Now, I need to add the part that makes sure that students are balanced as much as possible with respect to grade. Please see the image for details.

How would you alter the above algorithm to programmatically determine the new student's color group?

By the way, this is a real-world problem (not just for student algorithm assignment) for a system I'm developing which goes live next Wednesday

user_2328165 · Answer

First, pick the elements with the lowest count and then pick the one with the lowest count of the colour of the student. A greedy algorithm will suffice.


const groups = new Map();

// initialize your groups
map.add("red", { ... });

function findGroup(grade) {
    const min = "red";

    map.forEach((group, color) => {
        const groupLength = length(group);
        const minLength = length(min[0]);

        if(groupLength < minLength) {
            min = [color]
        } else if(groupLength == minLength && group[grade] < map.get(min)[grade]) {
            min = color;
        }
    });

    return min;
}

user_9348534 · Answer

Lots of editing to make a runable snippet... Key Features though are the following functions:

getEligibleColorsByCounts

accepts an object whose keys are colors and values are numbers
sorts colors by value
populates array by starting with lowest sorted color then adding each additional color that has same value
returns array of colors

getEligibleColorsByTotals

builds object whose keys are colors and values are from studentsByColorGroup
calls getEligibleColorsByCounts passing in object
returns array of colors whose counts are all equal

getEligibleColorsByGrade

builds object whose keys are colors and values are from gradeCountsByColorGroup
calls getEligibleColorsByCounts passing in object
returns array of colors whose counts are all equal

getNewStudentColorGroup

calls getEligibleColorsByTotals
if only one possible color, returns that color
otherwise calls getEligibleColorsByGrade and passes in results of getEligibleColorsbyTotals
returns a single color

addStudent

gets color for new student from getNewStudentColorGroup
adds student to color group array
increments number of students of newStudent.grade in color group

var students = [];
students.push({name: "student1", grade:4});
students.push({name: "student2", grade:6});
students.push({name: "student3", grade:5});
students.push({name: "student4", grade:3});
students.push({name: "student5", grade:6});
students.push({name: "student6", grade:3});
students.push({name: "student7", grade:3});
students.push({name: "student8", grade:3});

var studentsByColorGroup = {
  "GREEN": [],
  "BLUE": [],
  "RED": [],
  "YELLOW": []
};

var gradeCountsByColorGroup = {
  "GREEN": {
    3: 0,
    4: 0,
    5: 0,
    6: 0
  },
  "BLUE": {
    3: 0,
    4: 0,
    5: 0,
    6: 0
  },
  "RED": {
    3: 0,
    4: 0,
    5: 0,
    6: 0
  },
  "YELLOW": {
    3: 0,
    4: 0,
    5: 0,
    6: 0
  }
};

var getEligibleColorsByCounts = function(counts) {
  var colors = Object.keys(counts);
  colors.sort(function(a, b) {
    return (counts[a] - counts[b]);
  });

  var returnArray = [];
  for (var index = 0; index < colors.length; index++) {
    returnArray.push(colors[index]);
    if (index != colors.length - 1) {
      if (counts[colors[index]] != counts[colors[index + 1]]) {
        break;
      }
    }
  }
  return (returnArray);
};

var getEligibleColorsByTotals = function() {
  var colorCounts = {
    "GREEN": studentsByColorGroup["GREEN"].length,
    "BLUE": studentsByColorGroup["BLUE"].length,
    "RED": studentsByColorGroup["RED"].length,
    "YELLOW": studentsByColorGroup["YELLOW"].length
  };
  var returnArray = getEligibleColorsByCounts(colorCounts);
  return (returnArray);
};

var getEligibleColorsByGrade = function(colors, grade) {
  var colorCounts = {};
  colors.forEach(function(color) {
    colorCounts[color] = gradeCountsByColorGroup[color][grade];
  });
  var returnArray = getEligibleColorsByCounts(colorCounts);
  return (returnArray);
};

var getNewStudentColorGroup = function(grade) {
  var returnColor = '';
  var totalsColors = getEligibleColorsByTotals();
  if (totalsColors.length == 1) {
    returnColor = totalsColors[0];
  } else {
    var gradeColors = getEligibleColorsByGrade(totalsColors, grade);
    returnColor = gradeColors[0];
  }
  return (returnColor);
};

var addStudent = function(student, grade) {
  var color = getNewStudentColorGroup(grade);
  studentsByColorGroup[color].push(student);
  gradeCountsByColorGroup[color][grade]++;
};

students.forEach(function(student){
  addStudent(student, student.grade);
});

console.log(studentsByColorGroup);
var newStudent = {};

console.log("Adding Student9");
newStudent = {name: "student9", grade:6}; 
students.push(newStudent);
addStudent(newStudent, newStudent.grade);
console.log(studentsByColorGroup);

console.log("Adding Student10");
newStudent = {name: "student10", grade:3};
students.push(newStudent);
addStudent(newStudent, newStudent.grade);
console.log(studentsByColorGroup);

console.log("Adding Student11");
newStudent = {name: "student11", grade:4}; 
students.push(newStudent);
addStudent(newStudent, newStudent.grade);
console.log(studentsByColorGroup);

console.log("Adding Student12");
newStudent = {name: "student12", grade:6}; 
students.push(newStudent);
addStudent(newStudent, newStudent.grade);
console.log(studentsByColorGroup);

console.log("Adding Student13");
newStudent = {name: "student13", grade:5}; 
students.push(newStudent);
addStudent(newStudent, newStudent.grade);
console.log(studentsByColorGroup);

Algorithm for adding students to a color group

2 Answers