trjhtr

I decided to solve a problem posted on Stack Overflow as a bit of fun. (I wouldn't post it there as they should attempt it themselves)

The basic idea is to find the exam schedule which uses the fewest number of slots for a set of students. Students take a selection of different modules each and should be able to attend all of their exams without any clashes.

Here's the input data:

John takes Modules A, G, F and C

Ben takes Modules E, F, B, and A

Clare takes Modules D, A, G, and E

And this should result in

Time slot 1: Modules D and F

Time slot 2: Modules B and G

Time slot 3: Modules C and E

Time slot 4: Module A

(I've taken the names/order of the time slots to be arbitrary, not sure whether that was the original intent)

I have 3 classes which are basically data holders: Module, TimeSlot and Student and a Main class which does the actual calculation.

The code is written in Java 8. I used streams and lambdas in a few places. I did consider using Java 10 for var but it didn't seem to add much value in many places.

Any advice is appreciated. I'm not concerned about performance, really. Readability and maintainability are the most important code quality metrics in my opinion. In particular, I'm almost certain modulesToStudents can be rewritten using streams. Whether or not it would be more readable, I don't know.

Please note that I'm already aware that, because this a greedy implementation, it will will not give the optimum solution in all cases.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.stream.Collectors;

class Module

 private final char name;

 Module(final char name)
 
 this.name = name;
 

 @Override
 public boolean equals(final Object o)
 getClass() != o.getClass()) return false;
 final Module module = (Module) o;
 return name == module.name;
 

 @Override
 public int hashCode()
 
 return Objects.hash(name);
 

 @Override
 public String toString()
 
 return "Module " + name;
 


class TimeSlot

 private final int id;
 private final List<Module> modules = new ArrayList<>();

 TimeSlot(final int id)
 
 this.id = id;
 

 void addModule(final Module module)
 
 modules.add(module);
 

 boolean containsAny(final List<Module> modules)
 
 return modules.stream().anyMatch(this.modules::contains);
 

 @Override
 public String toString()
 
 return "TimeSlotmodules=" + modules + ", id=" + id + '';
 


class Student

 private final String name;
 private final List<Module> modules;

 Student(final String name, final List<Module> modules)
 
 this.name = name;
 this.modules = modules;
 

 List<Module> getModules()
 
 return modules;
 

 @Override
 public String toString()
 
 return name;
 


public class Main

 public static void main(final String... args)
 
 System.out.println(calculateSchedule(data()));
 

 private static List<Student> data()
 
 return Arrays.asList(
 new Student("John", Arrays.asList(new Module('A'), new Module('G'), new Module('F'), new Module('C'))),
 new Student("Ben", Arrays.asList(new Module('E'), new Module('F'), new Module('B'), new Module('A'))),
 new Student("Clare", Arrays.asList(new Module('D'), new Module('A'), new Module('G'), new Module('E')))
 );
 

 private static String calculateSchedule(final List<Student> students)
 
 final List<TimeSlot> slots = new ArrayList<>();
 final Map<Module, List<Student>> modulesToStudentsByPopularity = sortLargestFirst(
 modulesToStudents(students)
 );
 for (final Map.Entry<Module, List<Student>> entry : modulesToStudentsByPopularity.entrySet())
 
 final Module module = entry.getKey();
 final List<Student> modulesStudents = entry.getValue();
 boolean isSlotAvailable = false;
 for (final TimeSlot slot : slots)
 
 isSlotAvailable = isSlotAvailable(slot, modulesStudents);
 if (isSlotAvailable)
 
 slot.addModule(module);
 break;
 
 
 if (!isSlotAvailable)
 
 final TimeSlot newSlot = new TimeSlot(slots.size());
 newSlot.addModule(module);
 slots.add(newSlot);
 
 
 return slots.toString();
 

 private static Map<Module, List<Student>> modulesToStudents(final List<Student> students)
 
 final Map<Module, List<Student>> modulesToStudents = new HashMap<>();
 for (final Student student : students)
 
 for (final Module module : student.getModules())
 
 modulesToStudents.putIfAbsent(module, new ArrayList<>());
 modulesToStudents.get(module).add(student);
 
 
 return modulesToStudents;
 

 private static <K, V> Map<K, List<V>> sortLargestFirst(final Map<K, List<V>> input)
 
 return input.entrySet().stream()
 .sorted((a, b) -> b.getValue().size() - a.getValue().size()) // Sort by size, descending
 .collect(
 Collectors.toMap(
 Map.Entry::getKey,
 Map.Entry::getValue,
 (a, b) -> throw new AssertionError(); ,
 LinkedHashMap::new
 )
 );
 

 private static boolean isSlotAvailable(final TimeSlot slot, final List<Student> students)
 
 return students.stream().noneMatch(student -> slot.containsAny(student.getModules()));
 

Some tips:

• Java conventions dictate the opening brace should be on the same line.


• Always try to use braces, also when you only have single line statement/expressions in a block. It prevents potential bugs due to formatting, and it makes it easier to change or add code later on without worrying too much.


• Perhaps make your classes final. You could opt for using instanceof in your equals method (which also removed the need for a null check). For more information, see e.g. instanceof vs getClass
  


• 
  Object.hash will unnecessarily autobox the character. Just return (int) name (taking the value as an unsigned 16-bit int), or for better clarity, Character.hashCode(name).


• 
  return modules.stream().anyMatch(this.modules::contains);, you should not use contains like this on a list. Each contains will iterate the list in order to find the value. Use a Set instead, e.g. HashSet. Of course, you may need the list as state in order to keep the same order (or use an ordered set).


• With the Student class, you are directly assigning the value of the modules reference to a field. This means, any changes outside to this passed list will be visible here as well. Use a safe copy to prevent any nastiness.


• Something a bit like this, you are returning a direct reference to the list. Users can mutate the internal state of the student by modyfing this list. Use e.g. Collections.unmodifiableList(modules). Because you can not update the students state, you can cache this value.


• 
  

  Extremely minor, but I personally think this is a tad more clear:

  
  
  

  boolean isSlotAvailable = false;
  for (final TimeSlot slot : slots) 
   if (isSlotAvailable(slot, modulesStudents)) 
   slot.addModule(module);
   isSlotAvailable = true;
   break;
   
  
  

  
  



• I'd let calculateSchedule return the time slots, not a string. Let the client decide what to do with it.



• 
  

  You could write the isSlotAvailable as:

  
  
  

  return students.stream()
   .map(Student::getModules)
   .noneMatch(slot::containsAny);
  

  
  


• 
  

  I tried to create a Java 8 version for modulesToStudents. My current solution is using an extra method on student. I do not really prefer it though. I wanted to try it with a groupingBy, but I do not know how to do it with a list property. I'll add my other solution just for reference:

  
  
  

  return students.stream()
   .flatMap(student -> student.getModules().stream())
   .distinct()
   .collect(
   toMap(
   identity(),
   module -> students.stream().filter(student -> student.isEnscribedToModule(module)).collect(toList())));