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:
A killer always hates, and is no richer than it’s victim.
Charles hates noone that Agatha hates.
Agatha hates everybody but the butler.
The butler hates everyone not richer than Agatha.
The butler hates everyone whom Agatha hates.
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!