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, often, the problems that I solve as a web developer, rarely require a sophisticated algorithm. Anything that works is fast enough, and we should optimize code readability, and time taken to implement the feature (instead of execution speed).

This is a story of how I solved a fairly complex problem with a surprisingly simple piece of code, when I stopped trying to over engineer a perfect algorithm for it.

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

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

In the video, I first click a button to generate a new seating chart. Then I’m hovering over group names to highlight the persons in the group. 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 front of the room (E.g. they cause trouble in backseats or they have poor eyesight)
• Keep selected students in back of the room

There can be multiple group instances of the same type, 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”. E.g. if we have a group of 4 students that should be kept apart, they don’t need to be placed on the corners of the room. In fact, we even want to avoid this kind of recurring optimal solutions, because we want to be able to generate many different seating charts for the same group of students. It would be bad, if the teacher generated new seating charts every month, but some students would always be in the exact same places.

The group rules affect each other, which will cause problems with the implementation. Couple of examples:

• If we seat a keep-together group first, and keep-in-front after that, we might have randomly selected the keep-togethers to occupy front seats so that there is not enough room for the keep-in-front-group.
• On the other hand, if we seat keep-together group after some other group, there might not be enough suitable places next to each other left.
• 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 might well have a valid case, where all the seating rules can not be satisfied with the given room layout (users can define their own layouts). We don’t even know, if there is enough room for all the students, with the combination of room layout and student roster the user has created and selected.

Trying brute-force

After the “clean” algorithm solution started looking quite complicated, I had an idea 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. With scoring, unlike the creation, we could handle the groups one by one. 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 that is proportional to the distance between the students.
• Keep apart: for each pair of students in a group, give a penalty that is inversely proportional to the distance between the students.
• Keep in front: for each student in a group, give a penalty that is the y-coordinate (distance from front of the room) of the student.
• Keep in back: for each student in a group, give a penalty that is the height of the room minus y-coordinate of the student.

However, especially with complex group setups, this naive brute-force approach wasn’t feasible. 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-togethers 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 a give greater penalty when the students were kind of close, but not next to each other), the end result wasn’t good enough.

Helping the brute-force solution

Rather than scrapping the brute-force approach all together, I decided to try to fix the short comings of it. I divided the problem in 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 random seating chart generation according to some parts of the group rules. The implemented nudges were implemented based on trial and error to help with the parts that seemed hard to get right with pure change. E.g. one nudge handles keep-togethers so that it randomly seats the first student of the group, and the rest of the students to 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. E.g. if keep-togethers are seated so that it prevents front-group 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 simpler solution than just a perfect seating algorithm without scoring.

The amount 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 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 a simple and naive brute-force? E.g. Javascript environments in browsers can do a lot of calculations before it affects 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?

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