Applied Engineering: Functional Languages and the Dinner Table Problem

[latexpage]
This will be the first post in a series called “applied engineering”. It will feature small tutorials on engineering problems as well as gentle introductions into the art of software engineering. Even non-tech people should be able to follow the series.

My first post in the series considers functional languages, a class of programming languages. Functional languages are mostly used in scientific environments but are now gaining traction in industry applications as well. I will add a couple of posts on functional languages to get the interested reader started.

As with all language paradigma, there is a bunch of concrete realisations that we can use. For our purposes here, we use Ocaml – so if you want to try our little snippets, go ahead and install Ocaml on your own machine.

Now what exactly are language paradigma and what are the different programming languages? Language paradigma are based on the same idea as language families in natural languages – you group languages together that share the same roots. The main language paradigma that we have in computer science are imperative languages, functional languages, markup languages, logic languages and object orientation, although object orientation could be seen as a “language topping”. It is mostly but not exclusively used in combination with imperative languages though.

So we are using the functional language called OCaml. We could also use Haskell – we would stay in the same language family (like Germanic languages). In other words, once you’ve understood the concepts of functional languages using Ocaml, you can easily adapt to Haskell in case you want to.

Let’s start with a real-world problem to see how we could solve it using Ocaml. Assume that you host a dinner party and you’re having a hard time assigning people to your table as some people want to sit right next to each other while others cannot without ruining your evening. After a couple of minutes writing down some possible seatings on a piece of paper, you give up – there are just too many combinations.

Hence let the computer solve the problem for us by using our Ocaml program – because that’s what programs are all about: you give them some well-structured data – in our case whether people want or not want to sit next to each other – and let them compute a solution to the data – in our case a favourable dinner table seating assignment.

Before starting to write a single line of code, let us structure the data. For the purpose of this example, we need to add a bunch of people, a bunch of constraints (who wants to sit or not sit next to whom) and some table configuration (i.e. what seats are next to each other).

First, let us start with the people. We will assign consecutive natural numbers starting from 0 to all people:

0 Hank
1 Karen
2 Becka
3 Mia
4 Julian
5 Trixi

Second, let us add some constraints. A constraint will be of the following form:

Person A likes Person B by +/-p%

This means that person A would like to sit next to person B by a specific rating – ranging from 0% – 100%. If person A would rather not sit next to person B, we let p% range from -100% to 0%. Note that person A wanting to sit next to person B does not necessarily imply the converse. Let us assume the following constraints:

Hank likes Karen by 100%
Hank likes Becka by 100%
Hank likes Mia by -50%
Hank likes Julian by -100%
Karen likes Hank by 75%
Karen likes Becka by 100%
Karen likes Mia by 50%
Karen likes Julian by 50%
Karen likes Trixi by -75%
Becka likes Hank by 50%
Becka likes Karen by 50%
Becka likes Mia by 75%
Becka likes Julian by -75%
Mia likes Hank by 100%
Mia likes Trixi by 50%
Julian likes Karen by 50%
Trixi likes Hank by 100%
Trixi likes Karen by -50%

This for instance tells us that while Hank isn’t too eager to sit next to Mia, she, on the other hand, would like so very much.

Third, let us add some table configuration. We do this be specifying the proximity between seats while no proximity specification means that these two seats are so distant from each other that the two people sitting there could not be considered next to each other. For our purposes, we assume a small dinner table with one seat on each end and two seats on each side. We will give every seat a number again, assigning 0 and 3 to the left resp. the right end, and 1-2 resp. 4-5 to the bottom resp. top side. We will give the proximity specification by such lines:

i j p%

This means that seat $i$ is in $p%$-proximity of $j$ where $100%$ means directly next to each other and $50%$ for instance means that these two chairs are near each other but not exactly next to each other. For our table, the specification could look as follows:

0 1 100%
0 4 100%
1 0 100%
1 4 100%
1 2 100%
1 5 50%
2 3 100%
2 1 100%
2 5 100%
2 4 50%
3 2 100%
3 5 100%
4 0 100%
4 1 100%
4 5 100%
4 2 50%
5 3 100%
5 4 100%
5 3 100%
5 1 50%

This table tells us, for instance, that the bottom left seat 1 is right next to left head seat 0, bottom right seat 2 and top left seat 2, while it is only “near” top right seat 5 and not at all next to the right head seat 3.

A dinner table seating assignment is now an identification like “Hank sits on seat number 3 and Karen sits on seat number 0”. And our program will search for such an assignment that optimizes all given constraints. We will use a mathematical formulation to explain what we mean by optimal – intuitively, we want to maximize the accumulated satisfaction of constraints.

More formally, let $assign: People \rightarrow Seat$ be a table seating assignment, $proximity: Seat \times Seat \rightarrow Precentage$ be the proximity configuration between two seats and let $constraint: People \times People \rightarrow Percentage$ be the constraint of two people. We then want to maximize the value of
\[
\sum_{p,q \in People} constraint(p,q) \cdot proximity(assign(p), assign(q))
\]
with respect to the table seating assignment. In other words we build the sum over all pairs of people, where the value of a pair is given by the product of its proximity and its constraint, i.e. the further away two people are the less relevant the constraint is.

Are we still on the same page? You had this or similar problems before? Great! You have just seen how you model a real-world problem in terms of mathematics and processable structures. In the next post, we will write our first Ocaml program and integrate this data.

Leave a Reply