Dinesman's multiple-dwelling problem

From Rosetta Code
Dinesman's multiple-dwelling problem is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

The task is to solve Dinesman's multiple dwelling problem but in a way that most naturally follows the problem statement given below. Solutions are allowed (but not required) to parse and interpret the problem text, but should remain flexible and should state what changes to the problem text are allowed. Flexibility and ease of expression are valued.

Examples may be be split into "setup", "problem statement", and "output" sections where the ease and naturalness of stating the problem and getting an answer, as well as the ease and flexibility of modifying the problem are the primary concerns.

Example output should be shown here, as well as any comments on the examples flexibility.

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?

C

<lang C>#include <stdio.h>

  1. include <stdlib.h>

int verbose = 0;

  1. define COND(a, b) int a(int *s) { return (b); }

typedef int(*condition)(int *);

/* BEGIN problem specific setup */

  1. define N_FLOORS 5
  2. define TOP (N_FLOORS - 1)

int solution[N_FLOORS] = { 0 }; int occupied[N_FLOORS] = { 0 };

enum tenants { baker = 0, cooper, fletcher, miller, smith, phantom_of_the_opera, };

char *names[] = { "baker", "cooper", "fletcher", "miller", "smith", };

COND(c0, s[baker] != TOP); COND(c1, s[cooper] != 0); COND(c2, s[fletcher] != 0 && s[fletcher] != TOP); COND(c3, s[miller] > s[cooper]); COND(c4, abs(s[smith] - s[fletcher]) != 1); COND(c5, abs(s[cooper] - s[fletcher]) != 1);

  1. define N_CONDITIONS 6

condition cond[] = { c0, c1, c2, c3, c4, c5 };

/* END of problem specific setup */


int solve(int person) { int i, j; if (person == phantom_of_the_opera) { /* check condition */ for (i = 0; i < N_CONDITIONS; i++) { if (cond[i](solution)) continue;

if (verbose) { for (j = 0; j < N_FLOORS; j++) printf("%d %s\n", solution[j], names[j]); printf("cond %d bad\n\n", i); } return 0; }

printf("Found arrangement:\n"); for (i = 0; i < N_FLOORS; i++) printf("%d %s\n", solution[i], names[i]); return 1; }

for (i = 0; i < N_FLOORS; i++) { if (occupied[i]) continue; solution[person] = i; occupied[i] = 1; if (solve(person + 1)) return 1; occupied[i] = 0; } return 0; }

int main() { verbose = 0; if (!solve(0)) printf("Nobody lives anywhere\n"); return 0; }</lang>Output<lang>Found arrangement: 2 baker 1 cooper 3 fletcher 4 miller 0 smith</lang>C, being its compiled self, is not terribly flexible in dynamically changing runtime code content. Parsing some external problem specification would be one way, but for a small problem, it might as well just recompile with conditions hard coded. For this program, to change conditions, one needs to edit content between BEGIN and END of problem specific setup. Those could even be setup in an external file and gets #included if need be.

D

Works with: D version 2

<lang d>import std.stdio, std.range, std.math;

auto permutations(size_t n) { 

   auto seq = array(iota(n));
   size_t[][] res;

   void perms(size_t[] s, size_t[] pre = []) {
       if (s.length) {
           foreach (i, c; s) {
              perms(s[0 .. i] ~ s[i + 1 .. $], pre ~ c);
           }
       } else res ~= pre;
   }

   perms(seq);
   return res;

}

size_t[] solve(T...)(size_t len, T fun) { 

   auto perms = permutations(len);
   outer:
   foreach (p; perms) {
       foreach (fn; fun)
           if (!fn(cast(int[])p)) 
               continue outer;
       return p;
   }
   return null;

}

void main() { 

   enum Floors = 5u;
   enum {Baker, Cooper, Fletcher, Miller, Smith};
   
   auto c1 = (int[] s){ return s[Baker] != s.length-1; }; 
   auto c2 = (int[] s){ return s[Cooper] != 0; }; 
   auto c3 = (int[] s){ return s[Fletcher] != 0 && s[Fletcher] != s.length-1; }; 
   auto c4 = (int[] s){ return s[Miller] > s[Cooper]; }; 
   auto c5 = (int[] s){ return abs(s[Smith] - s[Fletcher]) != 1; };
   auto c6 = (int[] s){ return abs(s[Cooper] - s[Fletcher]) != 1; };
   
   if (auto sol = solve(Floors, c1, c2, c3, c4, c5, c6))
       writeln(sol);

}</lang> 

[2, 1, 3, 4, 0]

Icon and Unicon

This solution uses string invocation to call operators and the fact the Icon/Unicon procedures are first class values. The procedure names could also be given as strings and it would be fairly simple to read the names and all the rules directly from a file. Each name and rule recurses and relies on the inherent backtracking in the language to achieve the goal.

The rules explicitly call stop() after showing the solution. Removing the [stop] would cause the solver to try all possible cases and report all possible solutions (if there were multiple ones).

<lang Icon>invocable all global nameL, nameT, rules

procedure main() # Dinesman

nameT := table() nameL := ["Baker", "Cooper", "Fletcher", "Miller", "Smith"] rules := [ [ distinct ], 

          [ "~=",        "Baker",    top()      ],
          [ "~=",        "Cooper",   bottom()   ],
          [ "~=",        "Fletcher", top()      ],  
          [ "~=",        "Fletcher", bottom()   ],
          [ ">",         "Miller",   "Cooper"   ],
          [ notadjacent, "Smith",    "Fletcher" ],
          [ notadjacent, "Fletcher", "Cooper"   ],
          [ showsolution ],
          [ stop ] ]

if not solve(1) then 

  write("No solution found.")

end

procedure dontstop() # use if you want to search for all solutions end

procedure showsolution() # show the soluton 

  write("The solution is:")
  every write("   ",n := !nameL, " lives in ", nameT[n])
  return

end

procedure eval(n) # evaluate a rule 

  r := copy(rules[n-top()])
  every r[i := 2 to *r] := rv(r[i])
  if get(r)!r then suspend

end

procedure rv(x) # return referenced value if it exists return \nameT[x] | x end

procedure solve(n) # recursive solver 

  if n > top() then {         # apply rules
     if n <= top() + *rules then 
        ( eval(n) & solve(n+1) ) | fail   
     }
  else                        # setup locations
     (( nameT[nameL[n]] := bottom() to top() ) & solve(n + 1)) | fail
  return

end

procedure distinct(a,b) # ensure each name is distinct 

  if nameT[n := !nameL] = nameT[n ~== key(nameT)] then fail
  suspend

end

procedure notadjacent(n1,n2) # ensure n1,2 are not adjacent 

  if not adjacent(n1,n2) then suspend

end

procedure adjacent(n1,n2) # ensure n1,2 are adjacent 

  if abs(n1 - n2) = 1 then suspend

end

procedure bottom() # return bottom 

  return if *nameL > 0 then 1 else 0

end

procedure top() # return top 

  return *nameL

end</lang>

Output:

The solution is:
   Baker lives in 3
   Cooper lives in 2
   Fletcher lives in 4
   Miller lives in 5
   Smith lives in 1

J

This problem asks us to pick from one of several possibilities. We can represent these possibilities as a permutation of the residents' initials, arranged in order from lowest floor to top floor:

<lang j>possible=: ((i.!5) A. i.5) { 'BCFMS'</lang>

Additionally, we are given a variety of constraints which eliminate some possibilities:

<lang j>possible=: (#~ 'B' ~: {:"1) possible NB. Baker not on top floor possible=: (#~ 'C' ~: {."1) possible NB. Cooper not on bottom floor possible=: (#~ 'F' ~: {:"1) possible NB. Fletcher not on top floor possible=: (#~ 'F' ~: {."1) possible NB. Fletcher not on bottom floor possible=: (#~ </@i."1&'CM') possible NB. Miller on higher floor than Cooper possible=: (#~ 0 = +/@E."1~&'SF') possible NB. Smith not immediately below Fletcher possible=: (#~ 0 = +/@E."1~&'FS') possible NB. Fletcher not immediately below Smith possible=: (#~ 0 = +/@E."1~&'CF') possible NB. Cooper not immediately below Fletcher possible=: (#~ 0 = +/@E."1~&'FC') possible NB. Fletcher not immediately below Cooper</lang>

The answer is thus:

<lang j> possible SCBFM</lang>

(bottom floor) Smith, Cooper, Baker, Fletcher, Miller (top floor)

PureBasic

<lang PureBasic>Prototype cond(Array t(1))

Enumeration #Null 

 #Baker
 #Cooper
 #Fletcher
 #Miller
 #Smith

EndEnumeration

Procedure checkTenands(Array tenants(1), Array Condions.cond(1)) 

 Protected i, j
 Protected.cond *f 
 j=ArraySize(Condions())
 For i=0 To j
   *f=Condions(i)              ; load the function pointer to the current condition
   If *f(tenants()) = #False
     ProcedureReturn  #False
   EndIf 
 Next
 ProcedureReturn #True

EndProcedure

Procedure C1(Array t(1)) 

 If Int(Abs(t(#Fletcher)-t(#Cooper)))<>1
   ProcedureReturn #True
 EndIf

EndProcedure

Procedure C2(Array t(1)) 

 If t(#Baker)<>5
   ProcedureReturn #True
 EndIf

EndProcedure

Procedure C3(Array t(1)) 

 If t(#Cooper)<>1
   ProcedureReturn #True
 EndIf

EndProcedure

Procedure C4(Array t(1)) 

 If t(#Miller) >= t(#Cooper)
   ProcedureReturn #True
 EndIf

EndProcedure

Procedure C5(Array t(1)) 

 If t(#Fletcher)<>1 And t(#Fletcher)<>5
   ProcedureReturn #True
 EndIf

EndProcedure

Procedure C6(Array t(1)) 

 If Int(Abs(t(#Smith)-t(#Fletcher)))<>1
   ProcedureReturn #True
 EndIf

EndProcedure

Procedure main() 

 If OpenConsole()
   Dim People(4)
   Dim Conditions(5)
   Protected  a, b, c, d, e, i
   ;
   ;- Load pointers to all conditions
   Conditions(i)=@C1(): i+1
   Conditions(i)=@C2(): i+1
   Conditions(i)=@C3(): i+1
   Conditions(i)=@C4(): i+1
   Conditions(i)=@C5(): i+1
   Conditions(i)=@C6()
   ;
   ; generate and the all legal combinations
   For a=1 To 5
     For b=1 To 5
       If a=b: Continue: EndIf
       For c=1 To 5
         If a=c Or b=c: Continue: EndIf
         For d=1 To 5
           If d=a Or d=b Or d=c : Continue: EndIf
           For e=1 To 5 
             If e=a Or e=b Or e=c Or e=d: Continue: EndIf
             People(#Baker)=a
             People(#Cooper)=b
             People(#Fletcher)=c
             People(#Miller)=d
             People(#Smith)=e
             If checkTenands(People(), Conditions())
               PrintN("Solution found;")
               PrintN("Baker="+Str(a)+#CRLF$+"Cooper="+Str(b)+#CRLF$+"Miller="+Str(c))
               PrintN("Fletcher="+Str(d)+#CRLF$+"Smith="+Str(e)+#CRLF$) 
             EndIf
           Next
         Next
       Next
     Next
   Next
   Print("Press ENTER to exit"): Input()
 EndIf

EndProcedure

main()</lang> 

Solution found;
Baker=3
Cooper=2
Miller=4
Fletcher=5
Smith=1

Python

By parsing the problem statement

This example parses the statement of the problem as given and allows some variability such as the number of people, floors and constraints can be varied although the type of constraints allowed and the sentence structure is limited

Setup

Parsing is done with the aid of the multi-line regular expression at the head of the program.

<lang python>import re from itertools import product

problem_re = re.compile(r"""(?msx)(?:

  1. Multiple names of form n1, n2, n3, ... , and nK

(?P<namelist> [a-zA-Z]+ (?: , \s+ [a-zA-Z]+)* (?: ,? \s+ and) \s+ [a-zA-Z]+ )

  1. Flexible floor count (2 to 10 floors)

| (?: .* house \s+ that \s+ contains \s+ only \s+ 

 (?P<floorcount> two|three|four|five|six|seven|eight|nine|ten ) \s+ floors \s* \.)
  1. Constraint: "does not live on the n'th floor"

|(?: (?P<not_live> \b [a-zA-Z]+ \s+ does \s+ not \s+ live \s+ on \s+ the \s+ 

 (?: top|bottom|first|second|third|fourth|fifth|sixth|seventh|eighth|ninth|tenth) \s+ floor \s* \. ))
  1. Constraint: "does not live on either the I'th or the J'th [ or the K'th ...] floor

|(?P<not_either> \b [a-zA-Z]+ \s+ does \s+ not \s+ live \s+ on \s+ either 

 (?: \s+ (?: or \s+)? the \s+       
   (?: top|bottom|first|second|third|fourth|fifth|sixth|seventh|eighth|ninth|tenth))+ \s+ floor \s* \. )
  1. Constraint: "P1 lives on a higher/lower floor than P2 does"

|(?P<hi_lower> \b [a-zA-Z]+ \s+ lives \s+ on \s+ a \s (?: higher|lower) 

  \s+ floor \s+ than (?: \s+ does)  \s+  [a-zA-Z]+ \s* \. )
  1. Constraint: "P1 does/does not live on a floor adjacent to P2's"

|(?P<adjacency> \b [a-zA-Z]+ \s+ does (?:\s+ not)? \s+ live \s+ on \s+ a \s+ 

  floor \s+ adjacent \s+ to \s+  [a-zA-Z]+ (?: 's )? \s* \. )
  1. Ask for the solution

|(?P<question> Where \s+ does \s+ everyone \s+ live \s* \?)

) """)

names, lennames = None, None floors = None constraint_expr = 'len(set(alloc)) == lennames' # Start with all people on different floors

def do_namelist(txt): 

   " E.g. 'Baker, Cooper, Fletcher, Miller, and Smith'"
   global names, lennames
   names = txt.replace(' and ', ' ').split(', ')
   lennames = len(names)

def do_floorcount(txt): 

   " E.g. 'five'"
   global floors
   floors = '||two|three|four|five|six|seven|eight|nine|ten'.split('|').index(txt)

def do_not_live(txt): 

   " E.g. 'Baker does not live on the top floor.'"
   global constraint_expr
   t = txt.strip().split()
   who, floor = t[0], t[-2]
   w, f = (names.index(who),
           ('|first|second|third|fourth|fifth|sixth|' +
            'seventh|eighth|ninth|tenth|top|bottom|').split('|').index(floor)
           )
   if f == 11: f = floors
   if f == 12: f = 1
   constraint_expr += ' and alloc[%i] != %i' % (w, f)

def do_not_either(txt): 

   " E.g. 'Fletcher does not live on either the top or the bottom floor.'"
   global constraint_expr
   t = txt.replace(' or ', ' ').replace(' the ', ' ').strip().split()
   who, floor = t[0], t[6:-1]
   w, fl = (names.index(who),
            [('|first|second|third|fourth|fifth|sixth|' +
              'seventh|eighth|ninth|tenth|top|bottom|').split('|').index(f)
             for f in floor]
            )
   for f in fl:
       if f == 11: f = floors
       if f == 12: f = 1
       constraint_expr += ' and alloc[%i] != %i' % (w, f)

def do_hi_lower(txt): 

   " E.g. 'Miller lives on a higher floor than does Cooper.'"
   global constraint_expr
   t = txt.replace('.', ).strip().split()
   name_indices = [names.index(who) for who in (t[0], t[-1])]
   if 'lower' in t:
       name_indices = name_indices[::-1]
   constraint_expr += ' and alloc[%i] > alloc[%i]' % tuple(name_indices)

def do_adjacency(txt): 

    E.g. "Smith does not live on a floor adjacent to Fletcher's."
   global constraint_expr
   t = txt.replace('.', ).replace("'s", ).strip().split()
   name_indices = [names.index(who) for who in (t[0], t[-1])]
   constraint_expr += ' and abs(alloc[%i] - alloc[%i]) > 1' % tuple(name_indices)

def do_question(txt): 

   global constraint_expr, names, lennames

   exec_txt =

for alloc in product(range(1,floors+1), repeat=len(names)): 

   if %s:
       break

else: 

   alloc = None

 % constraint_expr 

   exec(exec_txt, globals(), locals())
   a = locals()['alloc']
   if a:
       output= ['Floors are numbered from 1 to %i inclusive.' % floors]
       for a2n in zip(a, names):
           output += ['  Floor %i is occupied by %s' % a2n]
       output.sort(reverse=True)
       print('\n'.join(output))
   else:
       print('No solution found.')
   print()

handler = { 

   'namelist': do_namelist,
   'floorcount': do_floorcount,
   'not_live': do_not_live,
   'not_either': do_not_either,
   'hi_lower': do_hi_lower,
   'adjacency': do_adjacency,
   'question': do_question,
   }

def parse_and_solve(problem): 

   p = re.sub(r'\s+', ' ', problem).strip()
   for x in problem_re.finditer(p):
       groupname, txt = [(k,v) for k,v in x.groupdict().items() if v][0]
       #print ("%r, %r" % (groupname, txt))
       handler[groupname](txt)</lang>
Problem statement

This is not much more than calling a function on the text of the problem! <lang python>if __name__ == '__main__': 

   parse_and_solve("""
       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?""")

   print('# Add another person with more constraints and more floors:')
   parse_and_solve("""
       Baker, Cooper, Fletcher, Miller, Guinan, and Smith
       live on different floors of an apartment house that contains
       only seven floors. Guinan does not live on either the top or the third or the fourth floor.
       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?""")</lang>
Output

This shows the output from the original problem and then for another, slightly different problem to cover some of the variability asked for in the task. 

Floors are numbered from 1 to 5 inclusive.
  Floor 5 is occupied by Miller
  Floor 4 is occupied by Fletcher
  Floor 3 is occupied by Baker
  Floor 2 is occupied by Cooper
  Floor 1 is occupied by Smith

# Add another person with more constraints and more floors:
Floors are numbered from 1 to 7 inclusive.
  Floor 7 is occupied by Smith
  Floor 6 is occupied by Guinan
  Floor 4 is occupied by Fletcher
  Floor 3 is occupied by Miller
  Floor 2 is occupied by Cooper
  Floor 1 is occupied by Baker

By using the Amb operator

In this example, the problem needs to be turned into valid Python code for use with the Amb operator. Setup is just to import Amb.

The second set of results corresponds to this modification to the problem statement: 

Baker, Cooper, Fletcher, Miller, Guinan, and Smith
live on different floors of an apartment house that contains
only seven floors. Guinan does not live on either the top or the third or the fourth floor.
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

<lang python>from amb import Amb

if __name__ == '__main__': 

   amb = Amb()

   maxfloors = 5
   floors = range(1, maxfloors+1)
   # Possible floors for each person
   Baker, Cooper, Fletcher, Miller, Smith = (amb(floors) for i in range(5))
   for _dummy in amb( lambda Baker, Cooper, Fletcher, Miller, Smith: (
                        len(set([Baker, Cooper, Fletcher, Miller, Smith])) == 5  # each to a separate floor
                        and Baker != maxfloors
                        and Cooper != 1
                        and Fletcher not in (maxfloors, 1)
                        and Miller > Cooper
                        and (Smith - Fletcher) not in (1, -1)  # Not adjacent
                        and (Fletcher - Cooper) not in (1, -1) # Not adjacent
                        ) ):

       print 'Floors are numbered from 1 to %i inclusive.' % maxfloors
       print '\n'.join(sorted('  Floor %i is occupied by %s'
                                  % (globals()[name], name)
                              for name in 'Baker, Cooper, Fletcher, Miller, Smith'.split(', ')))
       break
   else:
       print 'No solution found.'
   print



   print '# Add another person with more constraints and more floors:'
   # The order that Guinan is added to any list of people must stay consistant
   
   amb = Amb()

   maxfloors = 7
   floors = range(1, maxfloors+1)
   # Possible floors for each person
   Baker, Cooper, Fletcher, Miller, Guinan, Smith = (amb(floors) for i in range(6))
   for _dummy in amb( lambda Baker, Cooper, Fletcher, Miller, Guinan, Smith: (
                        len(set([Baker, Cooper, Fletcher, Miller, Guinan, Smith])) == 6  # each to a separate floor
                        and Guinan not in (maxfloors, 3, 4)
                        and Baker != maxfloors
                        and Cooper != 1
                        and Fletcher not in (maxfloors, 1)
                        and Miller > Cooper
                        and (Smith - Fletcher) not in (1, -1)  # Not adjacent
                        and (Fletcher - Cooper) not in (1, -1) # Not adjacent
                        ) ):

       print 'Floors are numbered from 1 to %i inclusive.' % maxfloors
       print '\n'.join(sorted('  Floor %i is occupied by %s'
                                  % (globals()[name], name)
                              for name in 'Baker, Cooper, Fletcher, Miller, Guinan, Smith'.split(', ')))
       break
   else:
       print 'No solution found.'
   print

</lang>

Output
Floors are numbered from 1 to 5 inclusive.
  Floor 1 is occupied by Smith
  Floor 2 is occupied by Cooper
  Floor 3 is occupied by Baker
  Floor 4 is occupied by Fletcher
  Floor 5 is occupied by Miller

# Add another person with more constraints and more floors:
Floors are numbered from 1 to 7 inclusive.
  Floor 1 is occupied by Baker
  Floor 2 is occupied by Cooper
  Floor 3 is occupied by Miller
  Floor 4 is occupied by Fletcher
  Floor 5 is occupied by Guinan
  Floor 6 is occupied by Smith
Retrieved from "https://rosettacode.org/wiki/Dinesman%27s_multiple-dwelling_problem?oldid=189906"