Things that make me go hmm...

As I'm re-writing the RuleCompiler I've been trying to think about more situations that the current implementation can't handle. For example, the SEND + MORE = MONEY problem can't be expressed at all at the moment.

Not that solving it using pyRete would be more natural or efficient than any other way of doing it, but still...

The reason it can't be expressed is because the variables have no connection to each other. It could be fixed by having a lot of dummy JoinNodes that just chain variables together. This would be, sort of, the same as generating all possible combinations of variables.

The only test that would have to be performed (after generating the values send, more and money) are:

>>> if send + more == money: pass
I keep thinking that the whole thing could be written as:
>>> import pyRete
>>> @pyRete.Rule
... def solve(s=int,e=int,n=int,d=int,m=int,o=int,r=int,y=int):
... send = int("%s%s%s%s" % (s,e,n,d)) # s *1000 + e *100 + n *10 + d
... more= int("%s%s%s%s" % (m,o,r,e)) # m *1000 + o *100 + r *10 + e
... money= int("%s%s%s%s%s" % (m,o,n,e,y)) # m *10000 + o *1000 + n *100 + e *10 + y
... if send + more == money:
... print "send %04d + more %04d = money %05d" % (send, more, money)
Unfortunately this violates quite a few of the things that I've decided shouldn't be allowed. For example, you can't assign to a local variable.

This type of situation might not be very common and/or useful but I'd like to have support for it anyway. I'll try to re-write the problem using CLIPS. I think that's going to be completely unneccessary, but most of all... lots of fun.

[2006-11-08] Since I have now written the CLIPS solution I've also noted that the code above won't work. It would, eventually, spit out the correct answer but it would also generate a lot more "solutions" than there actually are. The reason is that there's no constraint saying that a number cannot be bound to more than one variable at the same time.
The code below works fine though, because the generator getCombinations takes care of that constraint...

BTW, here's a brute force Python solution to the problem:

>>> def getCombinations(lst, n):
... if n== 0:
... yield []
... else:
... for i in range(len(lst)):
... for j in getCombinations(lst[:i]+ lst[i+1:], n- 1):
... yield [lst[i]]+ j
>>> variables = ['s', 'e', 'n', 'd', 'm', 'o', 'r', 'y']
>>> numbers = range(10)
>>> values = {}
>>> for combination in getCombinations(numbers, len(variables)):
... for n in combination:
... values[variables[combination.index(n)]] = n
... send = int("%(s)s%(e)s%(n)s%(d)s" % (values))
... more = int("%(m)s%(o)s%(r)s%(e)s" % (values))
... money = int("%(m)s%(o)s%(n)s%(e)s%(y)s" % (values))
... if send + more == money:
... print "send %04d + more %04d = money %05d" % (send, more, money)
It takes about a minute to run on my laptop. I wonder what the equivalent pyRete implementation would take.

Note that both of the above implementations are spitting out several solutions. There's actually one additional constraint saying that the first digit in either of the numbers can't be 0. But implementing that is left as an exersice to the reader :-)

Inga kommentarer: