Who Killed Agatha

The Who Killed Agatha example can be found at the DMCommunity website.

Who killed Agatha

Someone in Dreadsbury Mansion killed Aunt Agatha. Agatha, the butler, and Charles live in Dreadsbury Mansion, and are the only ones to live there. A killer always hates, and is no richer than his victim. Charles hates noone that Agatha hates. Agatha hates everybody except the butler. The butler hates everyone not richer than Aunt Agatha. The butler hates everyone whom Agatha hates. Noone hates everyone. Who killed Agatha?

We can convert the challenge description into the following six clear rules:

  1. A killer always hates, and is no richer than it’s victim.
  2. Charles hates noone that Agatha hates.
  3. Agatha hates everybody but the butler.
  4. The butler hates everyone not richer than Agatha.
  5. The butler hates everyone whom Agatha hates.
  6. Noone hates everyone.

The first step when designing a cDMN solution, is creating the glossary. In our glossary, we define all the elements which we’ll use in our cDMN implementations.

After having read the description of the challenge, it should be clear that we need at least a Person type. This type will serve as the domain containing all the people’s names.

Type
Name Type Values
Person string Agatha, Butler, Charles

We also need a way to declare whether or not a person is hated by another. Since a person can hate multiple people, it is not possible to use a function in this situation. Thus, we introduce a relation instead: Person hates Person. The same goes for declaring whether or not a person is richer than another. For this, we introduce the relation Person richer than Person.

Relation
Name
Person hates Person
Person richer than Person

Lastly, we also need a way to find out who our killer is. A constant lends itself perfectly for this, since there is exactly one killer.

Constant
Name Type
Killer Person

Assuming that our glossary is finished, we can start modeling each of the rules.

Rule 1

A killer always hates, and is no richer than its victim.

Here we need to specify that a killer hates its victim as well as isn’t richer than the victim. This can easily be done using a constraint table. We state that the Killer has to hate Agatha, and cannot be richer than her. Note how it is possible to construct a constraint table without input variables. In this case, the outputs are always applicable.

Rule 1
E* Killer hates Agatha Killer richer than Agatha
1 Yes No

“Killer hates Agatha” and “Killer richer than Agatha” need to be true.

Rule 2

Charles hates noone that Agatha hates.

This rule is also best implemented using a constraint table. We can state that for every person, if Agatha hates them, then Charles doesn’t.

Charles hates no one that Agatha hates
E* Person Agatha hates Person Charles hates Person
1 - Yes No

For every person for whom “Agatha hates Person” is true, “Charles hates Person” is false.

Rule 3

Agatha hates everybody but the butler.

This can again be modeled using a constraint table. We evaluate each person, and if they are not the butler, Agatha hates them (row 1). If they are the butler, Agatha doesn’t hate them (row 2).

Agatha hates everybody but the butler
E* Person Agatha hates Person
1 Butler No
2 not(Butler) Yes

Rule 4

The butler hates everyone not richer than Agatha.

We use another constraint table for this rule. We evaluate each person not richer than Agatha, and have the Butler hate that person.

The butler hates everyone not richer than Agatha
E* Person Person richer than Agatha Butler hates Person
1 - No Yes

Rule 5

The butler hates everyone whom Agatha hates.

Here we quantify over each person whom Agatha hates, and make “Butler hates Person” true. Coincidentally, we already have a table which has the same input. We can add an extra output column to “Charles hates noone that Agatha hates” and save a table this way.

Charles hates no one that Agatha hates
E* Person Agatha hates Person Charles hates Person Butler hates Person
1 - Yes No Yes

Rule 6

Noone hates everyone.

For this rule, we need to define a way to know who “everyone” is, and how to model this. A possible solution is to introduce a new function, which will keep track of how many people are hated by one person.

Function
Name Type
number hated persons of Person Int

This would then allow us to create two tables: one counting how many persons are hated, and one putting a constraint on that amount. To count how many are hated, we can make use of the C# hitpolicy. We need to evaluate every p1, and count the amount of p2 whom p1 hates. Afterwards, we use a E* table to make sure nobody hates more than 3 people. In cDMN, the #Type operator can be used to count the number of elements in a type. In this case, we use #Person to denote the number of people in the problem.

Count enemies
C# Person called p1 Person called p2 p1 hates p2 number hated persons of p1
1 - - yes p2

Noone hates all
E* Person number hated persons of Person
1 - < #Person

The end

Run the example.

Now that all the rules are encoded in tables, we can run the example and discover the mystery of Dreadsbury mansion! Running the solver on our created model results in the following:

Model 1
==========
hated_persons_of_Person := {Agatha->2, Butler->2, Charles->1}.
Killer := Agatha.
Person_hates_Person := {(Agatha,Agatha), (Agatha,Charles), (Butler,Agatha), (Butler,Charles), (Charles,Butler)}.
Person_richer_than_Person := {(Butler,Agatha)}.

Elapsed Time:
0.863

It turns out Agatha hates herself, and was her own killer!