Making a brute-force algorithm viable with a nudge

Brute-force algorithms can be the laughing stock. Sometimes working, but non-optimal, solutions can provoke comments on a code review (or be joked about, like Obama mentioning bubble-sort as the way to go, although to be fair, the question was specifically about sorting a large list).

Still, the problems I solve as a web developer rarely require a sophisticated algorithm. Anything that works is fast enough, and we should optimize code readability and the time taken to implement the feature instead of execution speed.

This post is a story about solving a reasonably complex problem with a surprisingly simple algorithm after I stopped trying to over-engineer a perfect algorithm.

I needed to order elements in a grid in a very specific way, according to many dynamic rules that can affect each other. I generated random orders until a suitable one was found because checking that the result was correct was trivial. The random generation needed a little nudge to go in the right direction to make it feasible.

Here’s what the working end result looks like in action:

In the video, I first click a button to generate a new seating chart. Then, I hover over group names to highlight the group members. I’ll talk more about the groups later.

The problem

I have a simple SaaS for creating classroom seating charts (SeatingChartMaker.app), where I needed to implement a feature that would semi-randomly seat pupils while respecting user-defined rules.

The possible rules are:

• Keep a group of students apart from each other (They don’t need to have the maximum possible distance between them. E.g. the students are known to cause trouble when they sit next to each other, so you might want to keep some distance between them.)
• Keep a group of students next to each other (They really should be next to each other, not just close. E.g. you’d like one student to help the other.)
• Keep selected students in the front of the room (E.g. they cause trouble in backseats or they have poor eyesight)
• Keep selected students in the back of the room

Multiple group instances of the same type can exist, and a student can be in zero, one, or multiple groups.

Implementation problems

Some details to keep in mind:

The random seating chart doesn’t need to be “optimal.” For example, if a group of four students should be kept apart, they don’t need to be placed in the room’s corners. In fact, we want to avoid this kind of recurring optimal solution because we want to generate many different seating charts for the same group of students. It would not be good if the teacher generated new seating charts every month, but some students would always be in the same places.

The group rules affect each other, which will cause problems with the implementation. Here are a couple of examples:

• If we seat a “keep-together” group first and a “keep-in-front” group after that, we might have randomly selected the keep-together to occupy front seats, so there is not enough room for the keep-in-front group.
• On the other hand, if we seat a “keep-together” group after some other group, there might not be enough suitable places next to each other.
• The same students can be in multiple groups. We might have a situation where a student needs to be in front, next to some, but apart from others.

I.e. We can’t solve this by handling the groups one by one in a loop, even if we ordered them in a certain way.

Also, we may have a valid case where all the seating rules can not be satisfied with the given room layout (users can define their own layouts). Given the combination of room layout and student roster the user has created and selected, we don’t even know if there is enough room for all the students.

Trying brute-force

After the “clean” algorithm solution started looking quite complicated, I decided to try a brute-force approach.

1. Generate, e.g., 10 000 completely random seating charts.
2. Score each seating chart.
3. Select the best one.

The idea was to create a simple function to score any seating relative to the given group rules. Unlike the creation, we could handle the groups one by one with scoring. Seating seemed to be quickly checkable (NP) but not quickly solvable (P)

The scoring function in practice is a sum of penalties.

• Keep together: For each pair of students in a group, give a penalty proportional to the distance between them.
• Keep apart: For each pair of students in a group, give a penalty inversely proportional to the distance between them.
• Keep in the front: For each student in a group, give a penalty based on the student’s y-coordinate (distance from the front of the room).
• Keep in the back: For each student in a group, give a penalty equal to the room’s height minus the student’s y-coordinate.

However, this naive brute-force approach wasn’t feasible, especially with complex group setups. The amount of random solutions that could be generated in tolerable time isn’t enough. We usually find a seating chart that is close to a good solution, but especially the keep-together groups seemed to be hard to get right with this approach.

Even if we changed the penalty function from proportional to logarithmic and added weight factors (to give a greater penalty when the students were kind of close but not next to each other), the end result wasn’t good enough.

Why pure randomness wasn’t enough

Rather than scrapping the brute-force approach altogether, I decided to try to fix the shortcomings of it.

Think about what our first approach was really doing—by generating completely random seating charts, we took samples from every possible way students could sit. The problem? The “good” seating arrangements (ones that satisfy our rules) were like tiny needles in a massive haystack of possible arrangements. Even with 10 000 tries, we were unlikely to stumble upon them by pure chance.

This is actually similar to a Monte Carlo simulation, where you use random sampling to generate a distribution of possible outputs based on your inputs. In our case, that distribution of outputs (all possible seating arrangements) was far too wide—most of our samples were landing nowhere near the arrangements we wanted.

What we needed was a way to make our random sampling smarter, similar to how you might modify the input distributions in a Monte Carlo simulation to focus on the outputs you care about. Instead of looking everywhere blindly, we needed to gently push (or “nudge”) our random generation toward areas where we’re more likely to find good solutions. It’s like narrowing down where we look in that haystack.

This realization led me to split the problem into two parts…

1. Function that creates not-entirely-random seating charts.
2. The scoring part described above that selects the best from a set of potential solutions.

Part 2. was already there, so I started implementing small “nudges” to the random seating chart generation.

The nudges are simple seating functions that override the purely random seating chart generation according to some of the group rules. The implemented nudges were based on trial and error to help with the parts that seemed complicated to get right with pure chance. For example, one nudge handles keep-together groups so that it randomly seats the first student of the group and the rest of the students in the closest available seats next to the first one.

We don’t care if the group rule nudges interfere with each other in some unwanted way. For example, if the keep-together groups are seated so that it prevents the front group from being seated properly, we just generate enough potential seating charts with enough randomness and select the best one with the scoring part. Together, the simple seating algorithm with separate scoring is a simpler solution than a perfect seating algorithm without scoring.

The number of seating charts we need to generate is low enough that the UI feels instant. At the moment, I’m using 100, but there’s still a lot of room to increase it, e.g., if we need more group rule types and the current amount isn’t enough to generate at least one good one on most runs. There wouldn’t be any benefit in using a better seating algorithm instead of brute force (with nudges), even though it would probably be about 100 times faster.

Summary

Could the problem you’re facing be solved with simple and naive brute force? For example, Javascript environments in browsers can do a lot of calculations before they affect the UI in any way.

Is it easier to check if the end result is correct than to create a correct result? Could you generate random or semi-random solutions until you find a suitable one with a scoring function?

Starting with a brute-force algorithm and reducing the search can lead to an optimal solution. See “Speeding up brute-force searches” in Wikipedia