Re: JESS: Newbie question (Coin puzzle-SOLVED)

Win Carus Thu, 14 Aug 2003 11:56:29 -0700

Ernest's approach reduces matching time substantially and does make it possible in a realistic time to compute the $2.00 change combinations using a version of your script modified as he suggest.

However ... the "generate-and-test" approach is still very memory-intensive and a still-better alternative would be to use the CCP approach implemented by Futtersack and Labat (http://www.droit.univ-paris5.fr/futtersack/english/research/CCP/). Although the approach discussed refers only to a CLIPS implementation, Jess code is also available for download. The basic idea behind CCP is to assert facts only as needed; and backtrack only to sensible alternative search paths. This can reduce memory use substantially and make some problems possible to solve (or possible to solve in reasonable times).

Win

Solutions to $2.00 variant:

Jess, the Java Expert System Shell
Copyright (C) 2001 E.J. Friedman Hill and the Sandia Corporation
Jess Version 6.1p4 7/8/2003

Solution : 15 pennies, 33 nickels, 2 dimes, 0 quarters, 0 half-dollars
Solution : 45 pennies, 1 nickels, 0 dimes, 2 quarters, 2 half-dollars
Solution : 40 pennies, 7 nickels, 0 dimes, 1 quarters, 2 half-dollars
Solution : 40 pennies, 5 nickels, 1 dimes, 3 quarters, 1 half-dollars
Solution : 40 pennies, 4 nickels, 4 dimes, 0 quarters, 2 half-dollars
Solution : 40 pennies, 3 nickels, 2 dimes, 5 quarters, 0 half-dollars
Solution : 40 pennies, 2 nickels, 5 dimes, 2 quarters, 1 half-dollars
Solution : 40 pennies, 0 nickels, 6 dimes, 4 quarters, 0 half-dollars
Solution : 35 pennies, 13 nickels, 0 dimes, 0 quarters, 2 half-dollars
Solution : 35 pennies, 11 nickels, 1 dimes, 2 quarters, 1 half-dollars
Solution : 35 pennies, 9 nickels, 2 dimes, 4 quarters, 0 half-dollars
Solution : 35 pennies, 8 nickels, 5 dimes, 1 quarters, 1 half-dollars
Solution : 35 pennies, 6 nickels, 6 dimes, 3 quarters, 0 half-dollars
Solution : 35 pennies, 5 nickels, 9 dimes, 0 quarters, 1 half-dollars
Solution : 35 pennies, 3 nickels, 10 dimes, 2 quarters, 0 half-dollars
Solution : 35 pennies, 0 nickels, 14 dimes, 1 quarters, 0 half-dollars
Solution : 30 pennies, 17 nickels, 1 dimes, 1 quarters, 1 half-dollars
Solution : 30 pennies, 15 nickels, 2 dimes, 3 quarters, 0 half-dollars
Solution : 30 pennies, 14 nickels, 5 dimes, 0 quarters, 1 half-dollars
Solution : 30 pennies, 12 nickels, 6 dimes, 2 quarters, 0 half-dollars
Solution : 30 pennies, 9 nickels, 10 dimes, 1 quarters, 0 half-dollars
Solution : 30 pennies, 6 nickels, 14 dimes, 0 quarters, 0 half-dollars
Solution : 25 pennies, 23 nickels, 1 dimes, 0 quarters, 1 half-dollars
Solution : 25 pennies, 21 nickels, 2 dimes, 2 quarters, 0 half-dollars
Solution : 25 pennies, 18 nickels, 6 dimes, 1 quarters, 0 half-dollars
Solution : 25 pennies, 15 nickels, 10 dimes, 0 quarters, 0 half-dollars
Solution : 20 pennies, 27 nickels, 2 dimes, 1 quarters, 0 half-dollars
Solution : 20 pennies, 24 nickels, 6 dimes, 0 quarters, 0 half-dollars

[EMAIL PROTECTED] wrote:

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]
--------------------------------------------------------------------


--------------------------------------------------------------------
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]
--------------------------------------------------------------------

Re: JESS: Newbie question (Coin puzzle-SOLVED)

Reply via email to