LupSeat: a smart seat assignment generator
This article was co-written by Hiroya Gojo
This work will soon be presented at the 32nd Annual UC Davis Undergraduate Research, Scholarship & Creative Activities Conference.
Introduction
When students are allowed to sit next to whoever they want in an exam, it may increase the chance of plagiarism and cheating. On the other hand, assigning random seats to students prior to exams is time-consuming, especially for large classes, since instructors have to assign seats by hand. There are also risks of clerical errors, such as forgetting to assign a student. Existing software solutions unfortunately only focus on relatively small classrooms.
The goal of our project, LupSeat, is to automate the seat assignment process in an easy way to solve this problem. Using an algorithmic approach simplifies the process of spacing out students and minimizes the chance of errors. LupSeat is easy for instructors to use and instructors only need to provide student information and the representation of the room layout.
Seating algorithms
From a programming point of view, the most interesting part of this project is the seating algorithm. Given a number of students in a class and a number of seats in a classroom, the main goal is to maximize the number of empty seats between students, while still being able to sit all students.
In other words, if we call a “chunk” a block of students who are seating next to one another without any empty seats between them, then the goal is to minimize the size of chunks when assigning seats.
While developing LupSeat, two fundamentally different algorithms were compared, which we called chunk increase and consecutive divide. The former is a bottom up algorithm, with the latter is a top down algorithm.
The idea behind the chunk increase algorithm is to first start off with a chunk size of 1, which means that each student would have an empty seat (or an aisle or a wall) on each side. If all the students do not fit in the room with this chunk size, then the algorithm is repeatedly run again while progressively incrementing the chunk size is increased by 1. We stop once all students fit in the room.
The idea behind the consecutive divide algorithm is that the room initially starts out with the largest chunk size possible. It’s then likely that the number of available seats is larger than the number of students. So, we repeatedly take the current biggest chunk and split in two smaller chunks (with an empty seat in the middle), until we the number of seats is equal to the number of students. The empty seats should be evenly distributed across the room. Since splitting a chunk into two can lead to imbalanced chunk sizes, we use a backtracking algorithm which patches together split chunks and divides them again but evenly.
By creating a heuristic score to rank a room layout (i.e., computing the average size of chunk in a room), and running a script to run each algorithm many times on different configurations, the consecutive divide algorithm was shown to consistently outperform the others.
User interfaces
Two user interfaces were developed: a command-line interface, and a multiplatform graphical user interface.
The user needs to specify the list of students as a CSV file, and the layout of the classroom in YAML format.
Seating chart generation
LupSeat is very customizable in its output. Several files are created including a graphical room layout image, a CSV file with all the student/seat information, and the graphical student to seat assignment image.
The image sizes are customizable according to standard paper sizes, and the order of the students can be sorted based on their name, or their ID, or their seat position.
Example of a graphical room layout:
Example of a graphical student to seat assignment, ordered by seat position:
Future work
Because of the pandemic, this project has not yet been tested in real conditions. We are hoping that we will be able to use LupSeat in 2021/2022!
More work is also being planned, for example:
- More output possibilities.
- A database of all UC Davis lecture halls.
- More documentation.
Drop us a line if you’re interested in using our tool!