## Tuesday, March 20, 2007

### Solving the "Mr.S and Mr.P" puzzle by John McCarthy in Python

I have found recently an interesting article on reddit, about solving a logic puzzle in Haskel:
While the technique presented is interesting itself, I find it transferable to Python with even improved readability.
And here is the original statement:

`Formalization of two Puzzles Involving Knowledge McCarthy, John (1987). http://www-formal.stanford.edu/jmc/puzzles.htmlWe pick two numbers a and b, so that a>=b and both numbers are withinthe range [2,99]. We give Mr.P the product a*b and give Mr.S the suma+b.The following dialog takes place: Mr.P: I don't know the numbers Mr.S: I knew you didn't know. I don't know either. Mr.P: Now I know the numbers Mr.S: Now I know them tooCan we find the numbers a and b?`

Follows the solution written in Python 2.5.

`# all pairs of a,bpairs = [ (a,b) for a in range(2,99+1) for b in range(2,99+1) if a>=b ]# calculates map of solutionsdef calc_map(oper):    M={}    for a,b in pairs:        m = oper(a,b)        if not m in M:            M[m] = []        M[m].append( (a,b) )    return M# function that tests for single solutionsingle = lambda lx: len(lx) == 1# maps that hold the sum and the product solutions, # dictionaries with list valuesS = calc_map(lambda a,b: a+b)P = calc_map(lambda a,b: a*b)# Rules listrule_MrP_dont_know      = lambda p: not single (P[p])rule_MrS_dont_know      = lambda s: not single (S[s])rule_MrS_knew_MrP_doesnt_know = lambda s: all( [rule_MrP_dont_know( a*b )                                                         for a,b in S[s] ] )        rule_MrP_now_knows      = lambda p: single( [ (a,b) for a,b in P[p]                                         if rule_MrS_knew_MrP_doesnt_know(a+b) ])rule_MrS_knows_MrP_now_know = lambda s: single([ (a,b) for a,b in S[s]                                             if rule_MrP_now_knows(a*b) ])# Solve itfor a, b in pairs:    s,p = a+b, a*b    if rule_MrP_dont_know(p) \            and rule_MrS_dont_know(s) \            and rule_MrS_knew_MrP_doesnt_know(s)\            and rule_MrP_now_knows(p) \            and rule_MrS_knows_MrP_now_know(s):        print "Answer is:" , a,b`

And if we run the program the answer we get is:

`Answer is: 13 4`

I used the "all" function to increase readability and this is the only reason a 2.5 version is needed. Use own "all" function for a 2.4 version.

Now what we have here is almost a short implementation of a rule engine with forward-chaining. It certainly misses a lot of functionality of a real rule engine, but the actual process of rules execution is probabbly the same. Is Python a good language for this kind of tasks? I think it is.

The Python solution does not follow exactly the Haskell route neither the the paper by McCarthy. MsCarthy I find rather difficult to read and Haskel has its own oddity that makes me screem sometimes in the middle of the night.

The Python rules try to be more directly mapped to the conditions in the task. Readability counts and of course beautiful is better than ugly.

#### 1 comment:

Anonymous said...

I agree that (x,y) = (4,13) is a
solution. I also believe that
when Mr. P sees a 76 and Mr. S seen a 23, they can deduce that
(4,19) is a solution. Where have
I gone wrong??