Seating Chart Optimizer

Introduction

Welcome to EduCorp, The nation's leading purveyor of educational support software! You will be joining the team tasked with developing EduCorp's latest classroom support application: SitRite3K. Recent education research suggests that seating arrangements are the single most important factor in student learning. Students who are seated near friends exhibit better concentration, perform better on tests, and express greater satisfaction with the classroom experience.

SitRite3K will automate the tedious process of developing seating charts to maximize learning outcomes. After a teacher enters a list of students, along with each student's seating preferences, the program will display an optimized seating chart that places students near their preferred classmates.

The user interface group has already completed a cutting-edge GUI front-end for the SitRite3K system. It will be your responsibility to program the optimization logic.

This assignment will have two stages with two separate deadlines. For the first stage you will complete a Student class that encodes the preferences of an individual student. For the second stage you will complete a SeatingChart class that represents a rectangular seating arrangement and provides the functionality for optimizing seating assignments.

Part A - The Student Class

The Student class must conform to the following UML diagram:

You are free to add additional private helper methods, but the public methods must match the UML specification exactly.

Detailed Requirements

Constructors

As usual, the constructors must appropriately initialize each of the instance variables. The single-argument constructor must initialize both the row and the column values to 0. (Don't forget to avoid code repetition by using the this keyword.) Note that the constructors for the Student class do not need to perform any data validation. For example, it is not necessary to ensure that the row and column values are non-negative.

Accessors and Mutators

These methods must perform the obvious operations. Again, no data validation is required.

addFriend

This method must add the provided Student object to the end of the friends ArrayList.

getUnhappiness

A student's unhappiness is defined to be the summed Euclidean distance from the student to each of the student's friends, assuming that the seats are arranged in a uniform grid with one meter of separation between adjacent seats. More formally, a student's unhappiness is defined to be: \[\sum_{f \in friends} \sqrt{(row - f_{row})^2 + (column - f_{column})^2}\] Where \(row\) and \(column\) represent the location of the student and \(f_{row}\) and \(f_{column}\) represent the location of friend \(f\).

Implementation Advice

While not a requirement, I strongly suggest that you create a driver class to facilitate testing and debugging. It is generally a good idea to write a quick test for each method before moving on to the next one. This allows you to catch problems early and prevents you from making the same mistakes over and over again in your code. By "driver class", I mean something like the following: 

public class TestDriver
{
    public static void main(String[] args)
    {
        Student pete = new Student("Peter", 3, 4);
        
        System.out.println("Name (should be Peter): " + pete.getName()); 
    }

}

Don't delete the tests when you finish a method! You may be able to reuse them if you need to modify the method later. They also provide a useful reference if you need to get help from the instructor or a TA.

We will discuss more formal approaches to testing later in the semester.

Part B - The SeatingChart Class

The SeatingChart class represents a grid of seating locations as a two-dimensional array of Student objects. It is not necessary for every entry to contain a Student: null entries are used to represent empty seats.

The SeatingChart class must conform to the following UML diagram:

Again, you are free to add additional private helper methods.

Detailed Requirements

Constructor

The constructor must instantiate the two dimensional array seats. It is not the responsibility of the constructor to populate seats with Student objects. Initially, all entries should be null, representing an empty seating chart. No data validation is required for the constructor arguments.

getRows, getColumns

These methods should return the number of rows and columns in the SeatingChart.

getStudent

This method must return a reference to the student at the indicated location. If the location is invalid, this method must return null.

placeStudent

This method must place the provided student into seats at the indicated location.

getTotalUnhappiness

This method must return the sum of the unhappiness values of all Student objects stored in the seating chart.

swap

This method must swap the students at the two indicated locations. If either location is invalid, then this method must have no effect.

stepGreedy

This method must iterate once through the entire seating chart, performing local seating changes where those changes will decrease the total unhappiness of the classroom. This method must conform to the following pseudocode: 

for each row in the seating chart, starting with row 0, do:
    for each column in the seating chart, starting with column 0, do:

         Swap the student at the current location with the student
         sitting behind her if that swap would reduce the total
         unhappiness.

         Swap the student at the current location with the student
         sitting in front of her if that swap would reduce the total
         unhappiness.

         Swap the student at the current location with the student to
         her left if that swap would reduce the total unhappiness.

         Swap the student at the current location with the student to
         her right if that swap would reduce the total unhappiness.

This logic is guaranteed to decrease the total unhappiness of the classroom, or to leave the total unchanged if there are no local swaps that would help.

The positional descriptions above ("right", "left", "in front", "behind") assume that row 0 represents the front row of the classroom and column 0 represents the leftmost column.

Note that your implementation must match this pseudocode exactly. The order that the seats are accessed and the order of the swaps are both arbitrary: any other ordering would be equally valid. However, the order of operations will impact the final arrangement. If your code doesn't match the description above, it may appear to work correctly, but it won't pass the automated submission tests.

solveGreedy

It may be necessary to call the stepGreedy method multiple times before the students reach a configuration where no further improvements are possible. The solveGreedy method must repeatedly call stepGreedy until no additional improvements occur.

Note that the seating chart optimization algorithm expressed in the stepGreedy and solveGreedy methods is not guaranteed to find the best possible arrangement of students. It is easy for this algorithm to get stuck in a sub-optimal configuration that cannot be improved through local swaps. See the "Going Further" section below for more information.

Provided Code and Configuration Files

The jar file SitRite3K_V2.jar may be used to visualize the operation of your completed code. This file provides the following two classes:

Submitting

Part A (10%)

Submit your completed Student.java file through Web-CAT by the first deadline. The grading for this submission will be all or nothing: you will receive full credit if your code passes the submission tests and 0 otherwise. You have unlimited submissions for this deadline.

Part B (90%)

Submit completed versions of both Student.java and SeatingChart.java. You are not required to submit the same version of Student.java as you submitted for part A.

Code that fails any of the Web-CAT submission tests will receive at most 50% of the possible credit for part B. This includes both the functionality tests and the Checkstyle tests.

Keep in mind that passing the Web-CAT functionality tests does not guarantee that your code is correct. I will write the tests to catch the errors I anticipate, but it is impossible to develop tests that will catch every possible coding error. Your grade will be based on my evaluation of your submission: it is possible to lose points for incorrect code, even if that code passes the submission tests.

Similarly, passing the Checkstyle submission tests does not guarantee that your code conforms to the course style guide. Checkstyle only considers the low-level formatting of your code; it won't tell you if your code is badly organized or badly documented. Again, your final grade will be based on my evaluation of your submission.

Part B will include a penalty for excessive Web-CAT submissions. You are allowed five submissions with no penalty. There will be a one point deduction for each submission beyond five.

Going Further

As stated above, the optimization algorithm we are implementing for this assignment is not guaranteed to find the best possible seating arrangement. You may be wondering why we are bothering with this imperfect algorithm. In fact, it may be that there is no efficient algorithm that is guaranteed to find the best possible solution for this problem.

There are certainly inefficient algorithms that can find the best solution. For example, we could simply try every possible arrangement of students and keep the arrangement with the lowest total unhappiness. Unfortunately, for a classroom containing 30 students there are \(30! \approx 2.65 \times 10^{32}\) possible arrangements. This calculation would take trillions of years to complete.

I won't present a formal proof, but I suspect that this problem is in the class NP-Hard. (It bears some similarity to the quadratic assignment problem, which is known to be NP-Hard). Such problems probably don't have efficient algorithms: no matter how hard we try we will never be able to find an algorithm that can solve the problem in a reasonable amount of time.

Of course, just because we can't develop an algorithm to find the best answer doesn't necessarily mean that we can't develop an algorithm to find a pretty good answer in a reasonable amount of time. The algorithm that you implemented for this assignment is known as a "greedy" algorithm. Greedy algorithms make local improvements until no more improvements are possible. Such algorithms may find decent solutions quickly, but they tend to get stuck in "local minima": solutions that are not optimal, but that can't be improved through purely local changes.

Your challenge, if you choose to accept it, is to implement a better algorithm than the greedy algorithm described above. Some version of simulated annealling would probably work well and wouldn't be too difficult to implement. You may be able to think of something even better.

On the challenge.txt input, the greedy algorithm generally finds an arrangement in the range of 4500-5000. Eternal glory will be yours if you can beat this mark by a significant margin.

If you choose to work on this portion of the project, you should not include the code in your Web-CAT submission. The Web-CAT tests will be configured to test that the greedy algorithm is operating as expected.