Dinesman's multiple-dwelling problem: Difference between revisions
Content added Content deleted
(→{{header|Python}}: Placeholder.) |
(→{{header|Python}}: Add Python solution.) |
||
Line 282: | Line 282: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
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 and the sentence structure is limited |
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=== |
===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)(?: |
|||
# Multiple names of form n1, n2, n3, ... , and nK |
|||
(?P<namelist> [a-zA-Z]+ (?: , \s+ [a-zA-Z]+)* (?: ,? \s+ and) \s+ [a-zA-Z]+ ) |
|||
# 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* \.) |
|||
# 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* \. )) |
|||
# 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* \. ) |
|||
# 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* \. ) |
|||
# 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* \. ) |
|||
# 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=== |
===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=== |
===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. |
|||
<pre>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 |
|||
</pre> |