Euro's and Dollars.

In studying Scheme I came across the example program to count
in how many ways one dollar can be changed.
Of much more interest is the same problem for the Euro.

This can be even shorter in Forth.
Translating the Lisp source is probably easier then debugging a
Forth version. :-(
-----------8< --------------------------------
CREATE kind-of-coins 0 , 1 , 5 , 10 , 25 , 50 ,
: first-denomination kind-of-coins SWAP CELLS + @ ;

( amount kinds-of-coins -- count )
: cc OVER 0= IF 2DROP 1 ELSE OVER 0< OVER 0= OR IF 2DROP 0 ELSE
2DUP 1- RECURSE >R >R R@ first-denomination - R> RECURSE R> +
THEN THEN ;

( amount -- count )
: count-change 5 cc ;

100 count-change "Dollars :" TYPE . CR

-----------8< --------------------------------

For euro's you need:

-----------8< --------------------------------
CREATE euro-change 0 , 1 , 2 , 5 , 10 , 20 , 50 ,
: count-change 6 cc ;
-----------8< --------------------------------


Dollars : 292

Euro's : 4562

The Euro wins. (As long as you use cents and tuppences,
which will be over shortly.)

Now for the $100 question.
If we order the coins in descending order then :

A. It gives a wrong result
B. It runs faster
C. It runs slower but not by an order of magnitude
D. It runs so slow that you may loose your patience, or risk
a stack overflow

Groetjes Albert

--
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

On 18.06.2012 21:00, Albert van der Horst wrote:
> In studying Scheme I came across the example program to count
> in how many ways one dollar can be changed.
> Of much more interest is the same problem for the Euro.
>
> This can be even shorter in Forth.
> Translating the Lisp source is probably easier then debugging a
> Forth version. :-(
> -----------8< --------------------------------
> CREATE kind-of-coins 0 , 1 , 5 , 10 , 25 , 50 ,
> : first-denomination kind-of-coins SWAP CELLS + @ ;
>
> ( amount kinds-of-coins -- count )
> : cc OVER 0= IF 2DROP 1 ELSE OVER 0< OVER 0= OR IF 2DROP 0 ELSE
> 2DUP 1- RECURSE >R >R R@ first-denomination - R> RECURSE R> +
> THEN THEN ;
>
> ( amount -- count )
> : count-change 5 cc ;
>
> 100 count-change "Dollars :" TYPE . CR
>
> -----------8< --------------------------------
>
> For euro's you need:
>
> -----------8< --------------------------------
> CREATE euro-change 0 , 1 , 2 , 5 , 10 , 20 , 50 ,
> : count-change 6 cc ;
> -----------8< --------------------------------
>
>
> Dollars : 292
>
> Euro's : 4562
>
> The Euro wins. (As long as you use cents and tuppences,
> which will be over shortly.)
>
> Now for the $100 question.
> If we order the coins in descending order then :
>
> A. It gives a wrong result
> B. It runs faster
> C. It runs slower but not by an order of magnitude
> D. It runs so slow that you may loose your patience, or risk
> a stack overflow
>
> Groetjes Albert
>
> --
>

Thank you for this piece of code as absolutely bad coding example.
;-)

Albert van der Horst <albert@spenarnc.xs4all.nl> wrote:
> In studying Scheme I came across the example program to count
> in how many ways one dollar can be changed.

From: vandys@vsta.org
To: Albert van der Horst <albert@spenarnc.xs4all.nl>
Subject: Re: Euro's and Dollars.
In-Reply-To: <m5tu4r.9ba@spenarnc.xs4all.nl>
X-Newsgroups: comp.lang.forth

In article <m5tu4r.9ba@spenarnc.xs4all.nl> you wrote:
> In studying Scheme I came across the example program to count
> in how many ways one dollar can be changed.

Here's the search in Prolog, FWIW (not tested, just wanted to play with
the idea):

% A solution
change(_, 0, _, Solve) :- debug("solve", Solve), !, fail.

% No solution
change([], _, _) :- !, fail.
change([Coin|_], Balance, _) :-
Coin > Balance, !, fail.

% Apply current coin
change(Coins, Balance, Solve) :-
[Coin|_]=Coins,
Balance2 is Balance-Coin,
change(Coins, Balance2, [Coin|Solve]).

% Step down to next coin
change([_|Coins], Balance, Solve) :- change(Coins, Balance, Solve).

Invocation for US money WRT one dollar:

change([1, 5, 10, 25, 50], 100, []).

--
Andy Valencia
Home page: http://www.vsta.org/andy/
To contact me: http://www.vsta.org/contact/andy.html

On Mon, 19 Jun 2012, vandys@vsta.org wrote:
>
> Here's the search in Prolog, FWIW (not tested, just wanted to play with
> the idea):
>
> % A solution
> change(_, 0, _, Solve) :- debug("solve", Solve), !, fail.

Is anyone still using Prolog? Are there problem domains where Prolog is
still viable?? I haven't heard of anyone using it since the 1980's when
the AI fad was fresh, and backtracking all the rage ...

On 19.06.2012 03:43, Spam@ControlQ.com wrote:
> On Mon, 19 Jun 2012, vandys@vsta.org wrote:
>>
>> Here's the search in Prolog, FWIW (not tested, just wanted to play with
>> the idea):
>>
>> % A solution
>> change(_, 0, _, Solve) :- debug("solve", Solve), !, fail.
>
> Is anyone still using Prolog? Are there problem domains where Prolog is
> still viable?? I haven't heard of anyone using it since the 1980's when
> the AI fad was fresh, and backtracking all the rage ...
>

Unknown to the "masses" it is used in many professional applications,
although not as elementary Prolog, but as its successor Constraint
Programming.

Typical application fields are
- production planning
- transportation optimization
- crew rotation
- network design
- time tabling
- military applications
- financial applications
-

Someone said, CP is the most underestimated area in the software industry.

On Jun 18, 10:18*pm, "A. K." <a...@nospam.org> wrote:
> On 18.06.2012 21:00, Albert van der Horst wrote:
>
>
>
>
>
> > In studying Scheme I came across the example program to count
> > in how many ways one dollar can be changed.
> > Of much more interest is the same problem for the Euro.
>
> > This can be even shorter in Forth.
> > Translating the Lisp source is probably easier then debugging a
> > Forth version. :-(
> > -----------8< --------------------------------
> > CREATE kind-of-coins 0 , 1 , *5 , *10 , *25 , *50 ,
> > : first-denomination kind-of-coins SWAP CELLS + @ ;
>
> > ( amount kinds-of-coins -- count )
> > : cc * OVER 0= IF 2DROP 1 ELSE * OVER 0< OVER 0= OR IF 2DROP 0 ELSE
> > * * 2DUP 1- RECURSE >R *>R R@ first-denomination - R> RECURSE *R> +
> > * * THEN THEN ;
>
> > ( amount -- count )
> > : count-change * 5 cc ;
>
> > 100 count-change "Dollars :" TYPE . CR
>
> > -----------8< --------------------------------
>
> > For euro's you need:
>
> > -----------8< --------------------------------
> > CREATE euro-change 0 , 1 , *2 , 5 , *10 , *20 , *50 ,
> > : count-change * 6 cc ;
> > -----------8< --------------------------------
>
> > Dollars : 292
>
> > Euro's : 4562
>
> > The Euro wins. (As long as you use cents and tuppences,
> > * which will be over shortly.)
>
> > Now for the $100 question.
> > If we order the coins in descending order then :
>
> > A. It gives a wrong result
> > B. It runs faster
> > C. It runs slower but not by an order of magnitude
> > D. It runs so slow that you may loose your patience, or risk
> > * * *a stack overflow
>
> > Groetjes Albert
>
> > --
>
> Thank you for this piece of code as absolutely bad coding example.
> ;-)- Hide quoted text -
>
> - Show quoted text -

What, specifically, is wrong with his code? You call his code a "bad
coding example" and then give no justification at all for your
comment.

Please clarify.

> Someone said, CP is the most underestimated area in the software
> industry.

For Prolog, it's IMHO somehow the missing part, as it allows one to
"semi-bind" a variable, in contrast to either have it bound or
full-free. That in turn heavily reduces the possible search tree for
many problems, making them solvable with much less effort or at all --
think of how Sudoku is solved.

E.

On 6/18/12 9:20 PM, Mark Wills wrote:
> On Jun 18, 10:18 pm, "A. K."<a...@nospam.org> wrote:
>> On 18.06.2012 21:00, Albert van der Horst wrote:
>>
>>
>>
>>
>>
>>> In studying Scheme I came across the example program to count
>>> in how many ways one dollar can be changed.
>>> Of much more interest is the same problem for the Euro.
>>
>>> This can be even shorter in Forth.
>>> Translating the Lisp source is probably easier then debugging a
>>> Forth version. :-(
>>> -----------8< --------------------------------
>>> CREATE kind-of-coins 0 , 1 , 5 , 10 , 25 , 50 ,
>>> : first-denomination kind-of-coins SWAP CELLS + @ ;
>>
>>> ( amount kinds-of-coins -- count )
>>> : cc OVER 0= IF 2DROP 1 ELSE OVER 0< OVER 0= OR IF 2DROP 0 ELSE
>>> 2DUP 1- RECURSE>R>R R@ first-denomination - R> RECURSE R> +
>>> THEN THEN ;
>>
>>> ( amount -- count )
>>> : count-change 5 cc ;
>>
>>> 100 count-change "Dollars :" TYPE . CR
>>
>>> -----------8< --------------------------------
>>
>>> For euro's you need:
>>
>>> -----------8< --------------------------------
>>> CREATE euro-change 0 , 1 , 2 , 5 , 10 , 20 , 50 ,
>>> : count-change 6 cc ;
>>> -----------8< --------------------------------
>>
>>> Dollars : 292
>>
>>> Euro's : 4562
>>
>>> The Euro wins. (As long as you use cents and tuppences,
>>> which will be over shortly.)
>>
>>> Now for the $100 question.
>>> If we order the coins in descending order then :
>>
>>> A. It gives a wrong result
>>> B. It runs faster
>>> C. It runs slower but not by an order of magnitude
>>> D. It runs so slow that you may loose your patience, or risk
>>> a stack overflow
>>
>>> Groetjes Albert
>>
>>> --
>>
>> Thank you for this piece of code as absolutely bad coding example.
>> ;-)- Hide quoted text -
>>
>> - Show quoted text -
>
> What, specifically, is wrong with his code? You call his code a "bad
> coding example" and then give no justification at all for your
> comment.
>
> Please clarify.

Insane stack thrashing and recursion. No stack comments. Can't untangle
his algorithm enough to try to improve. I think the recursion is to
blame for #D.

Cheers,
Elizabeth

--
==================================================
Elizabeth D. Rather (US & Canada) 800-55-FORTH
FORTH Inc. +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

In article <m5tu4r.9ba@spenarnc.xs4all.nl>,
Albert van der Horst <albert@spenarnc.xs4all.nl> wrote:
>In studying Scheme I came across the example program to count
>in how many ways one dollar can be changed.
>Of much more interest is the same problem for the Euro.
>
>This can be even shorter in Forth.
>Translating the Lisp source is probably easier then debugging a
>Forth version. :-(

Elizabeth has called this insane stacktrashing, let's see.
The explanation why the lisp program worked runs several pages.

>-----------8< --------------------------------
>CREATE kind-of-coins 0 , 1 , 5 , 10 , 25 , 50 ,
>: first-denomination kind-of-coins SWAP CELLS + @ ;
>
>( amount kinds-of-coins -- count )
>: cc OVER 0= IF 2DROP 1 ELSE OVER 0< OVER 0= OR IF 2DROP 0 ELSE
> 2DUP 1- RECURSE >R >R R@ first-denomination - R> RECURSE R> +
> THEN THEN ;

( amount kinds-of-coins -- same same flag )
: zero-amount OVER 0= ;
( amount kinds-of-coins -- same same flag )
: negative-amount-or-no-coins?
OVER 0< OVER 0= OR ;

( amount kinds-of-coins -- amount lesser-kinds-of-coins )
: one-less-kind 1- ;

( amount kinds-of-coins -- new-amount kinds-of-coins )
: one-less-large-coin >R R@ first-denomination - R> ;
\ Personally prefer this over :
: one-less-large-coin DUP first-denomination NEGATE ROT + SWAP ;

( amount kinds-of-coins -- count )
: cc [ RECURSIVE ( so we can call cc from within ) ]
\ We can compose an amount of zero in exactly one way, regardless of
\ the coins available. (or is this nanny-granny comment?)
zero-amount? IF 2DROP 1 ELSE
\ We cannot realize a negative amount, or any amount using no
\ coins (except zero, but that has already been take into account.)
negative-amount-or-no-coins? IF 2DROP 0 ELSE
\ Possibility one: don't use largest denomination
2DUP one-less-kind 2>R ( a k -- a k )
\ Possibility two: do use largest denomination so at least one of it.
one-less-coin 2>R ( a k -- )
( empty stack, all arguments on return stack )
2R> cc 2R> cc +
THEN THEN ;

Disclaimer : above code for illustration purposes. It has not been
tested.

>
>( amount -- count )
>: count-change 5 cc ;
>
>100 count-change "Dollars :" TYPE . CR
>
>-----------8< --------------------------------
>
>For euro's you need:
>
>-----------8< --------------------------------
>CREATE euro-change 0 , 1 , 2 , 5 , 10 , 20 , 50 ,
>: count-change 6 cc ;
>-----------8< --------------------------------
>
>
>Dollars : 292
>
>Euro's : 4562
>
>The Euro wins. (As long as you use cents and tuppences,
> which will be over shortly.)
>
>Now for the $100 question.
>If we order the coins in descending order then :
>
>A. It gives a wrong result
>B. It runs faster
>C. It runs slower but not by an order of magnitude
>D. It runs so slow that you may loose your patience, or risk
> a stack overflow
>
>Groetjes Albert
>

P.S. the worst trashing occurred by a news reader that changed

2DUP 1- RECURSE >R >R R@ first-denomination - R> RECURSE R> +
into
2DUP 1- RECURSE>R>R R@ first-denomination - R> RECURSE R> +


--
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

In article <a4a0kpFeidU1@mid.individual.net>, <vandys@vsta.org> wrote:
>Albert van der Horst <albert@spenarnc.xs4all.nl> wrote:
>> In studying Scheme I came across the example program to count
>> in how many ways one dollar can be changed.
>
>From: vandys@vsta.org
>To: Albert van der Horst <albert@spenarnc.xs4all.nl>
>Subject: Re: Euro's and Dollars.
>In-Reply-To: <m5tu4r.9ba@spenarnc.xs4all.nl>
>X-Newsgroups: comp.lang.forth
>
>In article <m5tu4r.9ba@spenarnc.xs4all.nl> you wrote:
>> In studying Scheme I came across the example program to count
>> in how many ways one dollar can be changed.
>
>Here's the search in Prolog, FWIW (not tested, just wanted to play with
>the idea):
>
>% A solution
>change(_, 0, _, Solve) :- debug("solve", Solve), !, fail.
>
>% No solution
>change([], _, _) :- !, fail.
>change([Coin|_], Balance, _) :-
> Coin > Balance, !, fail.
>
>% Apply current coin
>change(Coins, Balance, Solve) :-
> [Coin|_]=Coins,
> Balance2 is Balance-Coin,
> change(Coins, Balance2, [Coin|Solve]).
>
>% Step down to next coin
>change([_|Coins], Balance, Solve) :- change(Coins, Balance, Solve).
>
>Invocation for US money WRT one dollar:
>
>change([1, 5, 10, 25, 50], 100, []).

Correct me if I'm wrong, but doesn't this generate all solutions,
instead of counting them?

>
>--
>Andy Valencia
>Home page: http://www.vsta.org/andy/
>To contact me: http://www.vsta.org/contact/andy.html


--
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

Spam@controlq.com wrote:
> Is anyone still using Prolog? Are there problem domains where Prolog is
> still viable?? I haven't heard of anyone using it since the 1980's when
> the AI fad was fresh, and backtracking all the rage ...

Very much so, just google with the terms ibm, watson, and prolog. The IBM
team's observations very much match our own experience.

--
Andy Valencia
Home page: http://www.vsta.org/andy/
To contact me: http://www.vsta.org/contact/andy.html

Albert van der Horst <albert@spenarnc.xs4all.nl> wrote:
> Correct me if I'm wrong, but doesn't this generate all solutions,
> instead of counting them?

Yes, I guess I should've just bumped a counter when I hit the solution.
The way I wrote it you'd "wc -l" afterwards and get a count of the number
of debug output lines.

--
Andy Valencia
Home page: http://www.vsta.org/andy/
To contact me: http://www.vsta.org/contact/andy.html

In article <20120619092656.0d5cc45a@tiger.support.j.intershop .de>,
Ecki <ecki@intershop.de> wrote:
>> Someone said, CP is the most underestimated area in the software
>> industry.
>
>For Prolog, it's IMHO somehow the missing part, as it allows one to
>"semi-bind" a variable, in contrast to either have it bound or
>full-free. That in turn heavily reduces the possible search tree for
>many problems, making them solvable with much less effort or at all --
>think of how Sudoku is solved.

The most natural way to solve a Sudoku is:
for all unsolved squares find out how many possibilities it has.
for all squares with 1 possibility fill it in
repeat

so that is probably a bad example.
(Officially a sudoku must not require backtracking to solve it.)

>
>E.

Groetjes Albert

--
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

Albert van der Horst <albert@spenarnc.xs4all.nl> writes:
> Elizabeth has called this insane stacktrashing, let's see.
> The explanation why the lisp program worked runs several pages.

Here's a more verbose version using gforth locals.

================================================== ==============

CREATE dollarcoins 1 , 5 , 10 , 25 , 50 ,
CREATE eurocoins 1 , 2 , 5 , 10 , 20 , 50 ,
VALUE coins

: coin-at { n } coins n cells + @ ;

: cc { amount coin-index -- n }
amount 0=
if 1
else
coin-index 0< amount 0< or
if 0
else
amount coin-index 1- recurse
amount coin-index coin-at -
coin-index recurse
+
then
then
;

: dollar ( -- ) dollarcoins TO coins 100 5 cc . ;
: euro ( -- ) eurocoins TO coins 100 6 cc . ;

Albert van der Horst <albert@spenarnc.xs4all.nl> wrote:
> Elizabeth has called this insane stacktrashing, let's see.
> The explanation why the lisp program worked runs several pages.

Interesting. Where is that example from?

Andrew.