I think Mitch Christensen wrote:
> Thanks for the help.
>
> In the interest of understanding (and optimization), I've included my
> solution.
>
> I'd appreciate any feedback anyone can to provide (for instance, finding 50
> coins that add up to $2.00 throws an OutOfMemory exception with standard JVM
> settings).
The LHS of your rule makes a list every possible combination of coins,
valid or not. It's this long list of combinations that causes the
OutOfMemoryError. This is kind of the "procedural programmer" approach
to writing the rule. Don't be scared of pattern-matching -- it's what
makes rule engines useful!
What you want to do is to move the filtering from the right-hand-side
of the rule (where it's done *after* the list is made) to the
left-hand-side (where it is done during pattern-matching, *while* the
list is made, resulting in a much shorter list and better
performance. So, for example
(defrule find-solution-2
(coin (denomination penny) (count ?cp) (amount ?ap))
(coin (denomination nickel)
(count ?cn&:(<= (+ ?cn ?cp) 50))
(amount ?an&:(<= (+ ?an ?ap) 100)))
(coin (denomination dime)
(count ?cd&:(<= (+ ?cd ?cn ?cp) 50))
(amount ?ad&:(<= (+ ?ad ?an ?ap) 100)))
... [use '=' instead of '<=' for the last pattern]
=>
(printout t "Solution : " ?cp " pennies, " ?cn " nickels, " ?cd " dimes, " ?cq
" quarters, " ?ch " half-dollars" crlf))
will be faster and use much less memory.
>
> -Mitch
>
> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
> ;; Find a set of 50 coins that add up to $1.00
> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
> ;; prepare working memory
> (clear)
> (reset)
>
> ;; define the parameters (play with these for different results)
> (bind ?coinCount 50)
> (bind ?totalAmt 100)
>
> ;; define the coin fact template
> (deftemplate coin (slot denomination) (slot count) (slot amount))
>
> ;; assert all possible coin facts
> (foreach ?denom (create$ half-dollar quarter dime nickel penny)
> (bind ?count 0)
> (bind ?total 0)
>
> ;; assign the appropriate amounts
> (if (eq ?denom half-dollar) then (bind ?amount 50) else
> (if (eq ?denom quarter) then (bind ?amount 25)) else
> (if (eq ?denom dime) then (bind ?amount 10)) else
> (if (eq ?denom nickel) then (bind ?amount 5)) else
> (if (eq ?denom penny) then (bind ?amount 1)))
>
> ;; assert the necessary coin facts
> (while (and (<= ?total ?totalAmt) (<= ?count ?coinCount)) do
> ;; add the fact
> (assert (coin (denomination ?denom) (count ?count) (amount ?total)))
>
> ;; tally the total amount
> (bind ?total (+ ?total ?amount))
> (bind ?count (+ ?count 1))
> )
> )
>
> ;; define the rules to find the combination of facts such that
> ;; the coin count equals ?coinCount and the amount equals ?totalAmt.
> ;;
> ;; ?cX - # of coins, ?aX amount of currency
> (defrule find-solution
> (coin (denomination penny) (count ?cp) (amount ?ap))
> (coin (denomination nickel) (count ?cn) (amount ?an))
> (coin (denomination dime) (count ?cd) (amount ?ad))
> (coin (denomination quarter) (count ?cq) (amount ?aq))
> (coin (denomination half-dollar) (count ?ch) (amount ?ah))
> =>
> (if (and (eq (+ ?cp ?cn ?cd ?cq ?ch) ?coinCount)
> (eq (+ ?ap ?an ?ad ?aq ?ah) ?totalAmt)) then
> (printout t "Solution : " ?cp " pennies, " ?cn " nickels, " ?cd " dimes, "
> ?cq " quarters, " ?ch " half-dollars" crlf)))
>
> ;; solve...
> (run)
>
>
> -----Original Message-----
> From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]
> Behalf Of [EMAIL PROTECTED]
> Sent: Monday, August 11, 2003 8:27 AM
> To: [EMAIL PROTECTED]
> Subject: Re: JESS: Newbie question (Coin puzzle)
>
>
> I think Mitch Christensen wrote:
> [Charset iso-8859-1 unsupported, filtering to ASCII...]
> >
> > PROBLEM: Define a set of coins amounting to exactly $1.00 using exactly 50
> > coins.
> >
> > APPROACH: I thought I'd assert he following facts,
> >
> > 2 Half dollar facts
> > 4 Quarter facts
> > 10 Dime facts
> > 20 Nickel facts
> > 100 Penny facts
> >
> > Then define a rule to print the facts such that the number of facts
> (coins)
> > is 50 and the value of the 50 facts equals 100 ($1.00).
>
> Since the problem isn't to determine -which- of the 100 pennies to
> use, for example, it's really unnecessary to represent each one
> individually. If it -were- necessary, then you'd want to be able to
> distinguish them, somehow, so you'd give them an identifier:
>
> (deftemplate coin (slot type) (slot id (default-value (gensym*))))
> (deftemplate coin-type (slot type) (slot value))
>
> (bind ?count 50)
> (while (> ?count 0)
> (assert (coin (type penny))))
>
> Each penny would then be unique.
>
> But I don't think I would do it this way. What if you had facts like
>
> (penny-count 0)
> (penny-count 1)
> (penny-count 2)
> ...
> (penny-count 50)
>
> (nickel-count 0)
> (nickel-count 1)
> (nickel-count 2)
> ...
>
>
> And then wrote a rule that matched one penny-count fact, one
> nickel-count fact, etc, such that the counts summed to 50, and the
> amounts summed to $1.00?
>
> ---------------------------------------------------------
> Ernest Friedman-Hill
> Distributed Systems Research Phone: (925) 294-2154
> Sandia National Labs FAX: (925) 294-2234
> PO Box 969, MS 9012 [EMAIL PROTECTED]
> Livermore, CA 94550 http://herzberg.ca.sandia.gov
>
> --------------------------------------------------------------------
> To unsubscribe, send the words 'unsubscribe jess-users [EMAIL PROTECTED]'
> in the BODY of a message to [EMAIL PROTECTED], NOT to the list
> (use your own address!) List problems? Notify [EMAIL PROTECTED]
> --------------------------------------------------------------------
>
> --------------------------------------------------------------------
> To unsubscribe, send the words 'unsubscribe jess-users [EMAIL PROTECTED]'
> in the BODY of a message to [EMAIL PROTECTED], NOT to the list
> (use your own address!) List problems? Notify [EMAIL PROTECTED]
> --------------------------------------------------------------------
>
---------------------------------------------------------
Ernest Friedman-Hill
Distributed Systems Research Phone: (925) 294-2154
Sandia National Labs FAX: (925) 294-2234
PO Box 969, MS 9012 [EMAIL PROTECTED]
Livermore, CA 94550 http://herzberg.ca.sandia.gov
--------------------------------------------------------------------
To unsubscribe, send the words 'unsubscribe jess-users [EMAIL PROTECTED]'
in the BODY of a message to [EMAIL PROTECTED], NOT to the list
(use your own address!) List problems? Notify [EMAIL PROTECTED]
--------------------------------------------------------------------
