Dinesman's Multiple Dwelling Problem

Dinesman's Multiple Dwelling Problem

Mia Temma's photo
Mia Temma
·

4 min read

The original task is from the book "Superior Mathematical Puzzles" from Howard P. Dinesman.

The Task

Baker, Cooper, Fletcher, Miller, and Smith live on different floors of an apartment house that contains only five floors.

  • Baker does not live on the top floor.
  • Cooper does not live on the bottom floor.
  • Fletcher does not live on either the top or the bottom floor.
  • Miller lives on a higher floor than does Cooper.
  • Smith does not live on a floor adjacent to Fletcher's.
  • Fletcher does not live on a floor adjacent to Cooper's.

Where does everyone live?

This task is kind of similar to the Zebra riddle: We have to translate the statements to our knowledge base so that it can be solved with Pilog.

Defining the Knowledge Base

Let's define a predicate dwelling that returns a list of tenants, where the first list item corresponds to the first floor and the fifth item to the last floor. We know that the list is a permutation of the five names, although we don't know the order. We can use the permute predicate for that:

(be dwelling (@Tenants)
   (permute (Baker Cooper Fletcher Miller Smith) @Tenants)
   ...

The topFloor and bottomFloor predicate

Reading the rules closely, we can identify four rules: "top floor", "bottom floor", "higher floor" and "adjacent floor". Let's implement them in Prolog. The topFloor tenant is the fifth entry in the @Tenants list, while the bottomFloor tenant is the first item:

(be topFloor (@Tenant @Lst)
   (equal (@ @ @ @ @Tenant) @Lst) )

(be bottomFloor (@Tenant @Lst)
   (equal (@Tenant @ @ @ @) @Lst) )

Now we can add the corresponding rules ot the main dwelling predicate:

  • Baker does not live on the top floor.
  • Cooper does not live on the bottom floor.
  • Fletcher does not live on either the top or the bottom floor.
(be dwelling (@Tenants)
   (permute (Baker Cooper Fletcher Miller Smith) @Tenants)
   (not (topFloor Baker @Tenants))
   (not (bottomFloor Cooper @Tenants))
   (not (or ((topFloor Fletcher @Tenants)) ((bottomFloor Fletcher @Tenants))))

The higherFloor predicate

Next, we have the following statement:

  • Miller lives on a higher floor than does Cooper.

We define a predicate higherFloor that takes three arguments: two tenants and the full tenant list.

(be higherFloor (@Tenant1 @Tenant2 @Lst)
   ...

where @Tenant1 is the person living in the higher floor.

Let's assume that we have a sublist @Rest of the tenants list which starts with @Tenant2. In this case, we could split the list into @Tenant2 and the people living above:

(equal (@Tenant2 . @Higher) @Rest)

And we know that @Tenant1 must then be a member of the @Higher sublist:

(equal (@Tenant2 . @Higher) @Rest)
(member @Tenant1 @Higher)

So the only thing we need is a smart way to define @Rest. Luckily, we have the built-in append predicate for this kind of purpose. It takes three arguments: the "first part" of the list, the "second part" of the list, and the full list.

Let's test it to understand what it's doing. Since we're only interested in the "Rest", we can treat the first part as "don't care" using the anonymous variable @:

: (? (append @ @Rest (Baker Cooper Fletcher Miller Smith)))
 @Rest=(Baker Cooper Fletcher Miller Smith)
 @Rest=(Cooper Fletcher Miller Smith)
 @Rest=(Fletcher Miller Smith)
 @Rest=(Miller Smith)
 @Rest=(Smith)
 @Rest=NIL

Given a specific tenant list, append generates for us five sublists that we can use for our higherFloor check.

So our final predicate definition is as follows:

(be higherFloor (@Tenant1 @Tenant2 @Lst)
   (append @ @Rest @Lst)
   (equal (@Tenant2 . @Higher) @Rest)
   (member @Tenant1 @Higher) )

The adjacentFloor predicate

Similarly, we can define the adjacentFloor predicate. Two floors are adjacent if they directly follow each other in the list.

Again we can define the @Rest predicate iteratively with append. After that, we simply need to check if the list starts with @Tenant1 and is followed by @Tenant2, or the other way around.

(be adjacentFloor (@Tenant1 @Tenant2 @Lst)
   (append @ @Rest @Lst)
   (or
      ((equal (@Tenant1 @Tenant2 . @) @Rest))
      ((equal (@Tenant2 @Tenant1 . @) @Rest)) ) )

Querying the solution

Now the last step is easy: We save everything to a file multipleDwelling.l and execute it with

$ pil multipleDwelling.l +``
: (? (dwelling @Result))
 @Result=(Smith Cooper Baker Fletcher Miller) 
-> NIL

There is only one solution.

You can download the final script here.

Sources

illustrain.com/?p=29325
rosettacode.org/wiki/Dinesman%27s_multiple-..

logicFunctional Programmingalgorithms