Marathon Order of Finish
The first problem about the Brain Basher’s marathon can be found here. We are to find the order of finish for the persons described below:
- Terry Tipton finished after Lisa Limperton and Betty Brent, but before Michael Miller.
- Paul Peterson finished before David Dartford and Lisa Limperton.
- Simone Stevens finished after Paul Peterson and before Jane Jacks and Helen Hall.
- Kenny Kirkpatrick finished after Paul Peterson, Michael Miller and Terry Tipton.
- Lisa Limperton finished after Betty Brent and David Dartford, but before Jane Jacks and Michael Miller.
- Michael Miller finished after Simone Stevens and Betty Brent.
- Betty Brent finished before Jane Jacks, Michael Miller and Paul Peterson.
- David Dartford finished before Kenny Kirkpatrick and Terry Tipton, but after Simone Stevens.
- Jane Jacks finished before Kenny Kirkpatrick, Terry Tipton and Michael Miller, but after Paul Peterson and David Dartford.
- Helen Hall finished before Michael Miller but after Lisa Limperton, Jane Jacks and Terry Tipton.
Each statement actually gives several facts about the order of finish of the contestants. For instance, number one says Lisa Liperton and Betty Brent were ahead of Terry Tipton and he was ahead of Michael Miller. We have already regularized the information from the original statement to ‘ahead’ facts. We can also abbreviate the names to get the CLIPS facts below which can be used by our program:
(ahead LL TT)
(ahead BB TT)
(ahead TT MM)
The complete list of given facts is shown below. You might check it against the statements above:
- (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)
We can first try to solve the puzzle by just counting how many persons each is ahead of. We will need facts that keep the counts. We can start the counts as (count TT 0) for example to make the count for Terry Tipton. We would need one fact for each person involved. We might just simply create a deffacts to assert these too whenever the system is reset to begin inference.
(count TT 0)
(count HH 0)
(count LL 0)
(count JJ 0)
(count DD 0)
(count SS 0)
(count PP 0)
(count BB 0)
(count KK 0)
(count MM 0)
Counting is always minor problem in CLIPS. If we write a rule to add one to the count every time we find a person is ahead of someone. Of course we must retract the old count and assert a new count. But we must also retract the old ‘ahead’ fact, or it could be re-used with the new count fact. The rule below retracts the old count and the ahead fact used and asserts a new count.
(defrule count
?f<-(ahead ?who ?)
?g<-(count ?x ?n)
=>
(retract ?f ?g) ; remove 1) old count for ?who 2) used ahead fact
(assert (count ?x (+ ?n 1))))
Here are the facts that result from a reset and run of our code so far:
CLIPS> (facts)
f-0 (initial-fact)
f-40 (count KK 0)
f-42 (count MM 1)
f-47 (count BB 5)
f-52 (count PP 5)
f-56 (count SS 4)
f-60 (count DD 4)
f-64 (count JJ 4)
f-68 (count LL 4)
f-69 (count HH 1)
f-72 (count TT 3)
For a total of 11 facts.
Now this is obviously not correct. Do you see the problem? Finish order in the race is a linear order. It is antisymmetric - if a is ahead of b then b is not ahead of a. OK. It is irreflexive - a is not ahead of a. OK if I have recorded the facts correctly. But it is also transitive - if a is ahead of b and b is ahead of c then a is ahead of c. So, unless the puzzler poser has been very lenient with us, we will need to find these transitive relationships as well. The rule below does this:
(defrule transitive
(ahead ?a ?b)
(ahead ?b ?c)
=>
(assert (ahead ?a ?c)))
)
The rule simply finds any to facts in the transitive situation and asserts the explicit ahead relationship.
Now what facts do we get by resetting and running? We can see below.
CLIPS> (facts)
f-0 (initial-fact)
f-40 (count KK 0)
f-42 (count MM 1)
f-47 (count BB 5)
f-52 (count PP 5)
f-56 (count SS 4)
f-60 (count DD 4)
f-64 (count JJ 4)
f-68 (count LL 4)
f-69 (count HH 1)
f-72 (count TT 3)
For a total of 11 facts.
It’s as if our transitive rule never ran. In fact it didn't because the current selection regimen did counts before it did transitivity! We need to either force counts after transitivity or we may force transitivity as soon as possible. For that we use salience or importance of using the rule. A positive means earlier and a negative means later. (No salience = 0) Let’s make sure counts occur after the other rules:
(defrule count
(declare (salience -20))
?f<-(ahead ?x ?y)
?g<-(count ?x ?n)
=>
(retract ?f ?g)
(assert (count ?x (+ ?n 1))))
Finally we get a good result (Remember, the count is how many others they are ahead of.):
CLIPS> (facts)
f-0 (initial-fact)
f-40 (count KK 0)
f-64 (count BB 9)
f-71 (count SS 7)
f-79 (count PP 8)
f-84 (count LL 5)
f-86 (count HH 2)
f-92 (count DD 6)
f-93 (count MM 1)
f-97 (count JJ 4)
f-100 (count TT 3)
For a total of 11 facts.
PS.
This puzzle could also be solved manually by the old Traveling Salesman trick.
Create a disc for each runner and attach a rubber band between two for each ahead fact. Now stretch the assembly until all fall into line. Since rubber band are non-directional, you will have to notice that no one is ahead of Betty Brent.
On the other hand you can simulate this with a graph rendering program. I used a GraphViz web version. Below are the marathon relations in GraphViz dot format. Just paste them into the pane,
TT -> MM
PP -> DD
PP -> LL
PP -> SS
SS -> JJ
SS -> HH
PP -> KK
MM -> KK
TT -> KK
BB -> LL
DD -> LL
LL -> JJ
LL -> MM
SS -> MM
BB -> MM
BB -> JJ
BB -> MM
BB -> PP
DD -> KK
DD -> TT
SS -> DD
JJ -> KK
JJ -> TT
JJ -> MM
PP -> JJ
DD -> JJ
HH -> MM
LL -> HH
JJ -> HH
TT -> HH
PS.
This puzzle could also be solved manually by the old Traveling Salesman trick.
Create a disc for each runner and attach a rubber band between two for each ahead fact. Now stretch the assembly until all fall into line. Since rubber band are non-directional, you will have to notice that no one is ahead of Betty Brent.
On the other hand you can simulate this with a graph rendering program. I used a GraphViz web version. Below are the marathon relations in GraphViz dot format. Just paste them into the pane,
LL -> TT
BB -> TTTT -> MM
PP -> DD
PP -> LL
PP -> SS
SS -> JJ
SS -> HH
PP -> KK
MM -> KK
TT -> KK
BB -> LL
DD -> LL
LL -> JJ
LL -> MM
SS -> MM
BB -> MM
BB -> JJ
BB -> MM
BB -> PP
DD -> KK
DD -> TT
SS -> DD
JJ -> KK
JJ -> TT
JJ -> MM
PP -> JJ
DD -> JJ
HH -> MM
LL -> HH
JJ -> HH
TT -> HH
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)
No comments:
Post a Comment