Valentines
Now we begin a second problem from the same site. The problem is to figure out the first name, thw color of valentine each of three young ladies received and from whom they thought it came. The full problem is here. Below we list the relevant constraints from the web site:
1. Unluckily for Freddie, when Miss Jetson received her card, she thought it was from Adam.
2. When Molly received her blue coloured card, she told Miss Hanson and together they worked out who the card was from. It didn't occur to either of them that it was from Freddie!
3. The girl who received the red card was convinced it came from Ethan.
4. Neither Millie nor Miss Motson received a pink card.
Note that poor Fred nevers figures at at in our deduction! The girls, their first names. the card colors and the senders can be represented by a few facts.
(domain last Hanson Jetson Motson)
(domain first Lilly Millie Molly)
(domain color blue pink red)
(domain sender Adam Dylan Ethan)
Since there are but three ladies, three first names, three colors and three senders, the number of possibilities are few. If we let the order of last names of the ladies be fixed, then any order of the other domains can represent a choice for the ladies first name, card color or her beau. The possible orders are just the permutation of the domain’s values. The code below permutes domain values as long as the name of the domain is not last. (note that the phrase “&~last“ tells CLIPS not to match the foregoing variable with the word last.):
(defrule permuteDom
(domain ?dom&~last $?X ?x ?y $?Y)
=>
(assert (domain ?dom $?X ?y ?x $?Y)))
The result of running our code so far gives all possible orders or domain values relative to the last names:
CLIPS> (facts)
f-0 (initial-fact)
f-1 (domain last Hanson Jetson Motson)
f-2 (domain first Lilly Millie Molly)
f-3 (domain color blue pink red)
f-4 (domain sender Adam Dylan Ethan)
f-5 (domain sender Dylan Adam Ethan)
f-6 (domain sender Dylan Ethan Adam)
f-7 (domain sender Ethan Dylan Adam)
f-8 (domain sender Ethan Adam Dylan)
f-9 (domain sender Adam Ethan Dylan)
f-10 (domain color pink blue red)
f-11 (domain color pink red blue)
f-12 (domain color red pink blue)
f-13 (domain color red blue pink)
f-14 (domain color blue red pink)
f-15 (domain first Millie Lilly Molly)
f-16 (domain first Millie Molly Lilly)
f-17 (domain first Molly Millie Lilly)
f-18 (domain first Molly Lilly Millie)
f-19 (domain first Lilly Molly Millie)
A possible world now is represented by one choice of order for each of first, color and guy. The rule below below creates a world by assembling one order of first name, one of color and one of sender into a single world fact.
(defrule makeWorld
(domain last $?L)
(domain first $?F)
(domain color $?C)
(domain sender $?S)
=>
(assert (world L: $?L F: $?F C: $?C S: $?S)))
But the basic operation of a rule based system is to apply the rule every way possible so all combinations will get tried.
In fact there are 6x6x6 or 216 distinct possible worlds. A lot of facts for a person, but few for a computer.Each world represents a choice of values in a standard logic problem like a solving grid. That’s too many to show them all, but we give two examples below for reference:
CLIPS> (facts 100 101)
f-100 (world L: Hanson Jetson Motson F: Molly Millie Lilly C: red blue pink S: Ethan Dylan Adam)
f-101 (world L: Hanson Jetson Motson F: Molly Millie Lilly C: red blue pink S: Dylan Ethan Adam)
Fact 101 is interpreted as
- Hanson …. Molly … red … Dylan
- Jetson … Milly … blue ... Ethan
- Motson ... Lilly … pink … Adam
Now we need to eliminate the unreal possible worlds given the constraints. We will use rules this time rather than facts. Rules let one use the full matching, logical and arithmetic powers of the language. We consider rules to enforce the implicit constraints given to reject worlds one by one until (hopefully) one is left as the only possible world.
1. Unluckily for Freddie, when Miss Jetson received her card, she thought it was from Adam.
We know Miss Jetson’s place so we match the corresponding place in the sender information. If Adam is not there, we retract the world. Notice how we ask CLIPS to remember the fact’s index so we may retract it later:
(defrule JetsonFromAdam
?f<-(world L: $? F: $? C: $? S: ? ~Adam ?)
=>
(retract ?f))
We could have used an even simpler pattern (world $? ~Adam ?) but the different pieces of the world fact will be useful later.
Now consider the second constraint of the problem: “When Molly received her blue coloured card, she told Miss ;Hanson and together they worked out who the card was from….”Ffrom this we know:
- Molly’s card is blue
- Hanson is not Molly
- Hanson’s card is not blue
We know just where to find Hansons data values. They are first in each tupple. We can use the nth$ CLIPS function to pick out the first value in any list. So if we just get the correcct value out of a list, we test to see whether is is Molly or blue. For constraint two we test the value retrieved from the list to see if it is Molly - a reject. For constraint 3 we do the same but with colors.
(defrule HansonNotMolly
?f<-(world L: $?L F: $?F C: $?C S: $?S)
(test (eq (nth$ 1 $?F) Molly))
=>
(retract ?f))
(defrule HansonNotBlue
?f<-(world L: $?L F: $?F C: $?C S: $?S)
(test (eq (nth$ 1 $?C) blue))
=>
(retract ?f))
Constraint 1 is a little more complex. Worlds have Molly in different places but they cannot have blue in the same place. So we have to find where in the first names list has Molly. Then we can look at the corresponding value in the colors list. The (member$ ?what $?list) function looks in the list a tells a what location (1,2 …) it first found the ?what value. Since Molly must be there somewhere, we don’t have to worry about member$ answering FALSE. We will reject worlds where the color value in Molly’s place is not blue. This more complex rule looks like this:
(defrule MollyBlue
?f<-(world L: $?L F: $?F C: $?C S: $?S)
(test (neq (nth$ (member$ Molly $?F) $?C) blue))
=>
(retract ?f))
Now we need to fill out the constraint. However the means we have used so far will work. If a constraint uses a last name, where know where its values are. Check the value in the corresponding place. If the constraint requires something other than last name, find the first value and use its location to get and inspect the second domain value.
My complete list of rules is in this section notes. However it might be more fun to write them yourself first. Here are the rules I wrote for constraints 3 & 4. Be careful about when to use eq and when to use neq!:
;3. The girl who received the red card was convinced it came ;from Ethan.
(defrule RedMustBeEthan ...
;4. Neither Millie nor Miss Motson received a pink card.
(defrule MotsonNotMillie ...
(defrule MillieNotPink ...
(defrule MotsonNotPink ...
Running all my rules, the only world fact that remained was the correct answer. The last fact remaining was: f-213 (world L: Hanson Jetson Motson F: Millie Lilly Molly C: red pink blue S: Ethan Adam Dylan) Of course, you can now read the answers tight off the fact!
Notes
Marathon
Here is the complete set of facts gleaned directly from the Brain Basher’s marathon information:
- (ahead LL TT)(ahead BB TT)(ahead TT MM)
- (ahead PP DD) (ahead PP LL)
- (ahead PP SS)(ahead SS JJ)(ahead SS HH)
- (ahead PP KK)(ahead MM KK)(ahead TT KK)
- (ahead BB LL)(ahead DD LL)(ahead LL JJ)(ahead LL MM)
- (ahead SS MM)(ahead BB MM)
- (ahead BB JJ) (ahead BB MM) (ahead BB PP)
- (ahead DD KK)(ahead DD TT)(ahead SS DD)
- (ahead JJ KK)(ahead JJ TT)(ahead JJ MM)(ahead PP JJ)(ahead DD JJ)
- (ahead HH MM)(ahead LL HH)(ahead JJ HH)(ahead TT HH)
Valentine Constraint Rules Notes
;3. The girl who received the red card was convinced it came ;from Ethan.
(defrule RedMustBeEthan
?f<-(world L: $?L F: $?F C: $?C S: $?S)
(test (neq (nth$ (member$ red $?C) $?S) Ethan))
=>
(retract ?f))
;4. Neither Millie nor Miss Motson received a pink card.
(defrule MotsonNotMillie
?f<-(world L: $?L F: $?F C: $?C S: $?S)
(test (eq (nth$ 3 $?F) Millie))
=>
(retract ?f))
(defrule MillieNotPink
?f<-(world L: $?L F: $?F C: $?C S: $?S)
(test (eq (nth$ (member$ Millie $?F) $?C) pink))
=>
(retract ?f))
(defrule MotsonNotPink
?f<-(world L: $?L F: $?F C: $?C S: $?S)
(test (eq (nth$ 3 $?C) pink))
=>
(retract ?f))
No comments:
Post a Comment