Just for fun - start with a complex logical PHP problem

Question

As a means of improving my skills as a PHP developer, I often challenge myself from the Praxis Programming site. In 99% of cases, I myself can solve puzzles, but I'm stuck in this, and I need to be guided by how to start. The riddle is called "Several living quarters." Here is the problem:

Baker, Cooper, Fletcher, Miller and Smith live on different floors of a residential building, which consists of only five floors. Baker does not live on the top floor. Cooper doesn't live on the ground floor. Fletcher does not live on the upper or lower floor. Miller lives on a higher floor than Cooper. Smith does not live on the floor next to Fletchers. Fletcher doesn't live on the floor next to Coopers. Where does everyone live?

My main problem is this: I do not understand how to test and evaluate various logical situations. So, for example, if we want to check whether Baker is on the first floor, what is the best way to “fill out” test positions for each of the 4 remaining people? My (many) attempts all ended in disappointment at the bottom of the massive If / else if / else trees.

This is not for homework, money or fame - just a mystery that I could use a little to get started!

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

<?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

An interesting problem. Since this is a programming problem, I think the best way to do this is to simply create all possible mechanisms of people and check if they are correct.

Since you just need a starting point, I am not going to write any actual code, I will just describe the way that I approach its solution:

• Since all tenants live on different floors, you need to use the "permutation" algorithm to generate all of their various possible options. That is, you start with a set, such as {1, 2, 3, 4, 5} , with each element representing the number of one person, for example, in the order of Baker, Cooper, Fletcher, Miller, Smith. You need to find all possible options. The wikipedia algorithm is pretty simple and should be easy to implement.

• For each permutation that you create, you need to check to see if all the conditions are true. If any of the conditions is false, stop testing and continue to the next permutation. If all conditions are met, everything is ready. All conditions are quite simple to test, for example:

  "Baker doesn't live on the top floor." → $baker != 5

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

  And so on.

Answer 2

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

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

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

Now submit this to the simplex algorithm , and you're done :)

EDIT: But if you want to solve this problem programmatically, I think testing all permutations for these conditions would be much easier - only 5! of them.

Answer 3

So call people BCFM S.

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

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

Now you speak

Baker does not live on the top floor.

So we will have

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

Cooper doesn't live on the ground floor.

So, in the end we get:

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

Fletcher does not live on the upper or lower floor.

Ookay:

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

Miller lives on a higher floor than Cooper.

So, M cannot be in a lower position than C:

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

And also, C cannot be on the top floor, because M must be above it:

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

(A): Smith does not live on the floor next to Fletchers.

(B): Fletcher doesn't live on the floor next to Coopers.

Thus, there are no SF, FS, FC or CF on adjacent “drawers” ​​(floors).

And we also know that

(C): live on different floors of a residential building.

According to (C), we have two possible situations: the first floor is B or S

Take the second case (because we know (A) about it)

 [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 already right, since we know that M is probably on the top floor):

 [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 possible permutation due to further reductions (only one person per floor):

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

So here is the solution:

Smith, Cooper, Baker, Fletcher, Miller