# Dinesman's Multiple Dwelling Problem

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

-----------------------

### [The Task](https://rosettacode.org/wiki/Dinesman%27s_multiple-dwelling_problem)

> 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](https://picolisp-blog.hashnode.dev/who-owns-the-zebra-a-logic-puzzle): We have to translate the statements to our knowledge base so that it can be solved with [Pilog](https://picolisp-blog.hashnode.dev/series/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](https://gitlab.com/picolisp-blog/single-plage-scripts/-/tree/main/rosetta).


---------------------------

# Sources
https://illustrain.com/?p=29325   
http://rosettacode.org/wiki/Dinesman%27s_multiple-dwelling_problem#PicoLisp