Just for fun - getting started on a tricky PHP logic problem

Question

As a means of improving my skill as a PHP developer I often challenge myself with problems from the site Programming Praxis. 99% of the time I can solve the riddles myself, but I'm jammed on this one and need some guidance on how to get started. The riddle is called "Multiple Dwellings". Here is the 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?

My basic trouble is this: I do not understand how to test and evaluate different logical situations. So for example, if we want to test if Baker belongs on the first floor, how best to "fill in" the test positions for each of the 4 remaining people? My (many) attempts have all ended in frustration at the bottoms of massive If/else if/else trees.

This isn't for homework, money, or fame - just a riddle I could use a little help getting started on!

Updated - Here is my solution! Thanks for all the input everyone, not necessarily optimized but at least now I understand it:

<?php

    function testThisOne ($testList) {
        $MillerFloor = "";
        $CooperFloor = "";
        $SmithFloor = "";
        $FletcherFloor = "";

        foreach ($testList as $key => $person) if ($person == "Miller") $MillerFloor = $key;
        foreach ($testList as $key => $person) if ($person == "Cooper") $CooperFloor = $key;
        foreach ($testList as $key =>$person) if ($person == "Smith") $SmithFloor = $key;
        foreach ($testList as $key => $person) if ($person == "Fletcher") $FletcherFloor = $key;

        if ($testList[4] == "Baker") return false;
        if ($testList[0] == "Cooper") return false;
        if ($testList[0] == "Fletcher" || $testList[4] == "Fletcher") return false;
        if ($MillerFloor < $CooperFloor) return false;
        if (abs($SmithFloor - $FletcherFloor) == 1 || abs($CooperFloor - $FletcherFloor) == 1) return false;

        return true;
    }

    function puzzleSolve1() {
        $people = array("Baker","Cooper","Fletcher","Miller","Smith");
        do {
            shuffle($people);
        } while (!testThisOne($people));
        return $people;
    }

?>

Answer 1

So let's call the persons B C F M S.

Basically everyone can live anywhere, so we have this starting situation:

[BCFMS] [BCFMS] [BCFMS] [BCFMS] [BCFMS]

Now you do say

Baker does not live on the top floor.

So We'll have

[BCFMS] [BCFMS] [BCFMS] [BCFMS] [CFMS]

Cooper does not live on the bottom floor.

So we end up with:

[BFMS] [BCFMS] [BCFMS] [BCFMS] [CFMS]

Fletcher does not live on either the top or the bottom floor.

Ookay:

[BMS] [BCFMS] [BCFMS] [BCFMS] [CMS]

Miller lives on a higher floor than does Cooper.

Ok, so M cannot be on a lower position than C:

[BS] [BCFS] [BCFMS] [BCFMS] [CMS]

And also, C cannot be on the last floor, because M must be above him:

[BS] [BCFS] [BCFMS] [BCFMS] [MS]

(A): Smith does not live on a floor adjacent to Fletcher’s.

(B): Fletcher does not live on a floor adjacent to Cooper’s.

So there's no S-F, F-S, F-C or C-F on adjacent "boxes" (floors).

And we also know that

(C): live on different floors of an apartment house

Conforming to (C), we have two possible situations, the first floor being B's or S's

Let's take the second case (because we know (A) about him)

[S] [BCFS] [BCFMS] [BCFMS] [MS]

According to (A):

[S] [BC] [BCF] [BCF] [M]

So we also know that M lives above C (the previous step is true already, as we know M for sure being on the last floor by now):

[S] [BC] [BCF] [BCF] [M]

According to (B), neither F nor C can be on the 3rd floor, and under the influence of (C), we ultimately get the only one possible permutation because of further reductions (only one person per floor):

[S] [C] [B] [F] [M]

So here is the solution:

Smith, Cooper, Baker, Fletcher, Miller

Answer 2

Interesting problem. Since it's a programming challenge, I think the best way to do it is just going to be generating all the possible arrangements of the people, and testing whether they're right.

Since you just wanted a starting point, I'm not going to write any actual code, I'll just outline the way I'd approach solving it:

1. Since all the tenants live on different floors, you need to use a "permutation" algorithm to generate all their different possible arrangements. That is, you're starting with a set like {1, 2, 3, 4, 5}, with each element representing one person's floor number, say in the order of Baker, Cooper, Fletcher, Miller, Smith. You need to find every other possible arrangement. The algorithm on wikipedia is fairly straightforward and should be easy to implement.

2. For every permutation you generate, you need to test if all the conditions are true. If any of the conditions are false, stop testing and go on to the next permutation. If all the conditions are satisfied, you're done. All the conditions are fairly easy to test, for example:

   "Baker does not live on the top floor." >> $baker != 5

   "Miller lives on a higher floor than does Cooper." >> $miller > $cooper

   And so on.

Answer 3

I guess you could format this a a set of linear (in)equations.

B < 5
C > 1
F < 5
F > 1
M > C
|S - F| > 1
|F - C| > 1

These plus: B != C != F != S != M

Now feed this into simplex algorithm and you are done :)

EDIT: But if you want to solve this programatically, I guess testing all permutations for these conditions would be much simpler - there is only 5! of them.