Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #13050 > unrolled thread

Euro's and Dollars.

Back to article view | Back to comp.lang.forth

Contents

  Euro's and Dollars. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-06-18 19:00 +0000
    Re: Euro's and Dollars. "A. K." <akk@nospam.org> - 2012-06-18 23:18 +0200
      Re: Euro's and Dollars. Mark Wills <markrobertwills@yahoo.co.uk> - 2012-06-19 00:20 -0700
        Re: Euro's and Dollars. "Elizabeth D. Rather" <erather@forth.com> - 2012-06-18 21:51 -1000
    Re: Euro's and Dollars. vandys@vsta.org - 2012-06-19 00:49 +0000
      Re: Euro's and Dollars. Spam@ControlQ.com - 2012-06-18 21:43 -0400
        Re: Euro's and Dollars. "A. K." <akk@nospam.org> - 2012-06-19 07:20 +0200
          Re: Euro's and Dollars. Ecki <ecki@intershop.de> - 2012-06-19 09:26 +0200
            Re: Euro's and Dollars. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-06-19 15:58 +0000
              Re: Euro's and Dollars. "A. K." <akk@nospam.org> - 2012-06-19 19:58 +0200
                Re: Euro's and Dollars. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-06-20 01:31 +0000
                  Re: Euro's and Dollars. "A. K." <akk@nospam.org> - 2012-06-20 07:15 +0200
              Re: Euro's and Dollars. Ecki <ecki@intershop.de> - 2012-06-20 10:15 +0200
              Re: Euro's and Dollars. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-06-20 10:46 +0000
                Re: Euro's and Dollars. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-06-20 17:39 +0000
                  Re: Euro's and Dollars. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-06-21 16:21 +0000
                    Re: Euro's and Dollars. Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-06-21 11:58 -0500
                      Re: Euro's and Dollars. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-06-22 14:57 +0000
                    Re: Euro's and Dollars. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-06-21 20:38 +0000
        Re: Euro's and Dollars. vandys@vsta.org - 2012-06-19 15:49 +0000
      Re: Euro's and Dollars. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-06-19 15:43 +0000
        Re: Euro's and Dollars. vandys@vsta.org - 2012-06-19 15:51 +0000
    Re: Euro's and Dollars. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-06-19 15:41 +0000
      Re: Euro's and Dollars. Paul Rubin <no.email@nospam.invalid> - 2012-06-19 10:26 -0700
        Re: Euro's and Dollars. Paul Rubin <no.email@nospam.invalid> - 2012-06-19 23:34 -0700
      Re: Euro's and Dollars. Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-06-19 12:41 -0500
        Re: Euro's and Dollars. Paul Rubin <no.email@nospam.invalid> - 2012-06-19 11:10 -0700
          Re: Euro's and Dollars. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-06-20 03:12 +0000
            Re: Euro's and Dollars. Paul Rubin <no.email@nospam.invalid> - 2012-06-19 23:51 -0700
          Re: Euro's and Dollars. Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-06-20 03:15 -0500

Page 2 of 2 — ← Prev page 1 [2]

#13064

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

[toc] | [prev] | [next] | [standalone]

#13068

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

[toc] | [prev] | [next] | [standalone]

#13063

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

[toc] | [prev] | [next] | [standalone]

#13073

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 . ;

[toc] | [prev] | [next] | [standalone]

#13096

Paul Rubin <no.email@nospam.invalid> writes:
> : dollar ( -- )  dollarcoins TO coins  100 5 cc . ;
> : euro ( -- )  eurocoins TO coins  100 6 cc . ;

Should say

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

of course.  

[toc] | [prev] | [next] | [standalone]

#13074

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.

[toc] | [prev] | [next] | [standalone]

#13077

Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>> The explanation why the lisp program worked runs several pages.
> Interesting.  Where is that example from?

A little web searching finds:

 http://mitpress.mit.edu/sicp/full-text/sicp/book/node16.html

[toc] | [prev] | [next] | [standalone]

#13091

In article <7x4nq7tbpa.fsf@ruckus.brouhaha.com>,
Paul Rubin  <no.email@nospam.invalid> wrote:
>Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>>> The explanation why the lisp program worked runs several pages.
>> Interesting.  Where is that example from?
>
>A little web searching finds:
>
> http://mitpress.mit.edu/sicp/full-text/sicp/book/node16.html

Right
Structure and interpretation of computer programs
Abelson Sussman and Sussman

A classic course about scheme. It is quite to my liking, but
some may find it too math oriented.

The book shows its age (1990) with sentences like:
     "It will take quite a while for that 292 to be computed."

(Actually more like 2 mS in Forth, I don't know yet how
to measure it in Scheme, but it is not noticeable.)

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

[toc] | [prev] | [next] | [standalone]

#13098

Albert van der Horst <albert@spenarnc.xs4all.nl> writes:
> The book shows its age (1990) with sentences like:
>      "It will take quite a while for that 292 to be computed."
>
> (Actually more like 2 mS in Forth, I don't know yet how
> to measure it in Scheme, but it is not noticeable.)

Here is a memoized python version.  With the memoization turned off, the
euro calculation takes a noticable time (maybe 0.2 sec).  With
memoization there's no noticable pause.
================================================================

def memoize(f, sentinel=object()):
    memo = {}
    def m(*args):
        if args in memo:
            return memo[args]
        memo[args] = v = f(*args)
        return v
    return m

@memoize
def cc(amount, coins):
    if not(coins) or amount < 0: return 0
    if amount == 0: return 1
    return cc(amount-coins[0],coins) + cc(amount,coins[1:])

print 'dollar',cc(100,(1,5,10,25,50))
print 'euro',cc(100,(1,2,5,10,20,50))

[toc] | [prev] | [next] | [standalone]

#13101

Paul Rubin <no.email@nospam.invalid> wrote:
> Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>>> The explanation why the lisp program worked runs several pages.
>> Interesting.  Where is that example from?
> 
> A little web searching finds:
> 
> http://mitpress.mit.edu/sicp/full-text/sicp/book/node16.html

Ah thanks, it's from SICP.  I looked in the index but couldn't find
it.

Andrew.

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.forth

csiph-web