coin changer --- a challenge for novices

[Hugh Aguilar]

I'm working my way through SICP. There is nothing like that available
for Forth!

An example program in SICP is a program to calculate how many ways it
is possible to provide change (pennies, nickles, dimes, quarters and
half-dollars) for a specific amount. For example, how many ways can
$1.00 be provided in coins? (it is 292, according to their program).
As a bonus challenge --- display all of the combinations.

So, the challenge for those who have never posted any Forth code on
comp.lang.forth (Gavino, Elizabeth Rather, John Passaniti, etc.), is
to provide code to solve this puzzle. I've made challenges like this
in the past (the alien-alphabet program
https://groups.google.com/group/comp.lang.forth/browse_thread/thread/dd8e30fcc7589749)
but received only responses from people who are already known Forth
programmers. This coin-changer is an easier problem though, so
hopefully those who don't program can solve it as their first-ever
Forth program. Please everybody wait for one week to give the three
non-programmers mentioned above plenty of time to write their program
and post it (I'm hoping to see Gavino come in first --- Go, Go,
Gavino!).

As a slightly more advanced challenge (still pretty easy), solve the N-
Queens problem. I don't think this appears anywhere in SICP, but I
have a solution in my novice package (
http://www.forth.org/novice.html). As a bonus challenge --- make your
program non-recursive as I did (the N-Queens problem is a classic
example of recursive-descent searching in many textbooks).

[Paul E. Bennett]

Hugh Aguilar wrote:

[%X]

I am certain that I have seen code from Elizabeth on here before. Then I
have been on this ng a long time.

> Please everybody wait for one week to give the three
> non-programmers mentioned above plenty of time to write their program
> and post it (I'm hoping to see Gavino come in first --- Go, Go,
> Gavino!).

Yes, I would be interested to see some code from Gavino too.

--
********************************************************************
Paul E. Bennett...............<email://Paul_E....@topmail.co.uk>
Forth based HIDECS Consultancy
Mob: +44 (0)7811-639972
Tel: +44 (0)1235-510979
Going Forth Safely ..... EBA. www.electric-boat-association.org.uk..
********************************************************************

[Hugh Aguilar]

On Nov 5, 12:48 am, "Paul E. Bennett" <Paul_E.Benn...@topmail.co.uk>
wrote:

> I am certain that I have seen code from Elizabeth on here before. Then I
> have been on this ng a long time.

Please provide a link.

I've never seen any code from E.R. on comp.lang.forth. Her two books
are also very light on code. Actually, all of the Forth Inc. books are
light on code --- I've never seen an implementation of FIELD for
example --- because of this, there are a lot of people in the world
who will say dismissively, "Forth is just a toy language like QBasic;
it doesn't support structs, which are the basis of all data
structures." Trying to tell the person that it is possible for him to
implement FIELD himself is an uphill battle --- the guy has already
dismissed Forth and adopted C --- there are a lot of programmers like
this who spent a few weeks reading "Starting Forth" and learning Forth
back in the 1980s, and who have never touched Forth since that time.
The book does have cute cartoons though --- it was just the right
speed for me when I was 18 and my experience primarily involved line-
number BASIC, and a smattering of Pascal and 6502 assembly-language
(if I hadn't already had a Pascal class in H.S. though, I would never
have thought of structs (records) on my own).

[Paul E. Bennett]

Hugh Aguilar wrote:

> On Nov 5, 12:48 am, "Paul E. Bennett" <Paul_E.Benn...@topmail.co.uk>
> wrote:
>> I am certain that I have seen code from Elizabeth on here before. Then I
>> have been on this ng a long time.
>
> Please provide a link.

As just one would prove your statement wrong, this link should help. It was
a thread that you also took part in (about arrays).

<https://groups.google.com/group/comp.lang.forth/browse_thread/thread/1d235f674d6076e7/ab015f1cd4db415a?hl=en-
GB#ab015f1cd4db415a>

> I've never seen any code from E.R. on comp.lang.forth. Her two books
> are also very light on code. Actually, all of the Forth Inc. books are
> light on code --- I've never seen an implementation of FIELD for
> example --- because of this, there are a lot of people in the world
> who will say dismissively, "Forth is just a toy language like QBasic;
> it doesn't support structs, which are the basis of all data
> structures." Trying to tell the person that it is possible for him to
> implement FIELD himself is an uphill battle --- the guy has already
> dismissed Forth and adopted C --- there are a lot of programmers like
> this who spent a few weeks reading "Starting Forth" and learning Forth
> back in the 1980s, and who have never touched Forth since that time.
> The book does have cute cartoons though --- it was just the right
> speed for me when I was 18 and my experience primarily involved line-
> number BASIC, and a smattering of Pascal and 6502 assembly-language
> (if I hadn't already had a Pascal class in H.S. though, I would never
> have thought of structs (records) on my own).

[Steve Graham]

I fail to see why we have to be rude on this newsgroup. My mother
didn't teach me to act this way nor did I teach my children thus.

[jfong]

Steve Graham 2012/11/7 PM 8:09:06 wrote：
> Hugh Aguilar wrote:
>
> > I'm working my way through SICP. There is nothing like that available

> > .......

>
> I fail to see why we have to be rude on this newsgroup. My mother
> didn't teach me to act this way nor did I teach my children thus.

I don't see why you are disturbed? Maybe you are comfortable in the cage(should do this, don't do that) given by the society(parent, priest, moralist, politician). We are not live in a machinary world yet, so enjoy it!

[Andrew Haley]

Steve Graham <jsgra...@yahoo.com> wrote:

> I fail to see why we have to be rude on this newsgroup. My mother
> didn't teach me to act this way nor did I teach my children thus.

We generally aren't, and you shouldn't treat this as representative.

Andrew.

[Alex Wegel]

Steve Graham <jsgra...@yahoo.com> wrote:

> My mother
> didn't teach me to act this way

You see - here on clf you can still learn from people which were more
lucky in this respect.

Another thing you can learn here is: How to not understand what others
mean and still win the argument.

And: Which 10% of reality to replace in order to not having to admit to
have failed.

Yes, i did use rude words here in clf too, but maybe not enough (are
there enough anyway?).

[Brad Eckert]

On Tuesday, November 6, 2012 5:09:06 PM UTC-7, Steve Graham wrote:
>
> I fail to see why we have to be rude on this newsgroup. My mother
> didn't teach me to act this way nor did I teach my children thus.

My daughter perfected sarcasm totally without my help.

[Ed]

One can never be too cynical :)

[Ian Osgood]

On Sunday, November 4, 2012 5:57:44 PM UTC-8, Hugh Aguilar wrote:
> I'm working my way through SICP. There is nothing like that available
>
> for Forth!

There was a wiki devoted to solving SICP problems in Oz, which also included many other programming languages. I had added Forth solutions to problems in the early chapters -- including this one -- before lack of automatic memory management became a burden. Here was my recursive solution to the change counting problem:

: table create does> swap cells + @ ;
table coin-value 0 , 1 , 5 , 10 , 25 , 50 ,

: count-change ( total coin -- n )
over 0= if
2drop 1
else over 0< over 0= or if
2drop 0
else
2dup coin-value - over recurse
>r 1- recurse r> +
then then ;

100 5 count-change .

(The CTMWiki was at http://codepoetics.com/wiki/ but seems to have disappeared in the last few years.)

[Anton Ertl]

Ian Osgood <ia...@quirkster.com> writes:
>There was a wiki devoted to solving SICP problems in Oz, which also include=
>d many other programming languages. I had added Forth solutions to problems=
> in the early chapters -- including this one -- before lack of automatic me=
>mory management became a burden.

Was not releasing the memory not an option? Have you looked at using
my garbage collector?

- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2012: http://www.euroforth.org/ef12/

[jfong]

Hugh Aguilar 2012/11/5 wrote：
> An example program in SICP is a program to calculate how many ways it
> is possible to provide change (pennies, nickles, dimes, quarters and
> half-dollars) for a specific amount. For example, how many ways can
> $1.00 be provided in coins? (it is 292, according to their program).
> As a bonus challenge --- display all of the combinations.

Here is my non-recursive version:

DECIMAL
VARIABLE CNT
0 VALUE #50C 0 VALUE #25C 0 VALUE #10C 0 VALUE #5C

VARIABLE SHOW? \ a flag to control the display of combination
: ?SHOW ( n--) SHOW? @ IF CR #50C . #25C . #10C . #5C . . ELSE DROP THEN ;

: 1CENT ( n--) ?SHOW 1 CNT +! ;
: 5CENT ( n--) DUP 5 / 1+ 0 DO I TO #5C DUP 1CENT 5 - LOOP DROP ;
: 10CENT ( n--) DUP 10 / 1+ 0 DO I TO #10C DUP 5CENT 10 - LOOP DROP ;
: 25CENT ( n--) DUP 25 / 1+ 0 DO I TO #25C DUP 10CENT 25 - LOOP DROP ;
: 50CENT ( n--N) 0 CNT !
DUP 50 / 1+ 0 DO I TO #50C DUP 25CENT 50 - LOOP DROP
CR CNT @ U. ;

Here is the result:
100 50CENT
292 ok
0 50CENT
1 ok

1 SHOW? !
7 50CENT
0 0 0 0 7
0 0 0 1 2
2 ok

Any comment?

[Hugh Aguilar]

On Nov 8, 10:28 am, an...@mips.complang.tuwien.ac.at (Anton Ertl)
wrote:

> Ian Osgood <i...@quirkster.com> writes:
> >There was a wiki devoted to solving SICP problems in Oz, which also include=
> >d many other programming languages. I had added Forth solutions to problems=
> > in the early chapters -- including this one -- before lack of automatic me=
> >mory management became a burden.
>
> Was not releasing the memory not an option?  Have you looked at using
> my garbage collector?
>
> - anton

I generally don't bother to release memory. This is only an issue for
programs that run indefinitely --- if they have a leak, then they will
eventually run out of memory. If a program runs once and is done, as
most of my programs do, then it is not necessary to release memory,
but it is okay to just terminate the program and let the OS clean up
any allocated memory that is left hanging.

In my novice package I think I have all my programs cleaning up after
themselves. It is example code for novices, so I want to be neat and
tidy, even if this isn't strictly necessary.

I don't intend to support GC in Straight Forth --- I consider GC to be
totally un-Forth-like.

[Hugh Aguilar]

This looks pretty good. I haven't written my program yet, but this is
essentially how I was going to do it. I wanted a non-recursive
solution so that it wouldn't be a direct port of the Scheme program in
SICP that was recursive (pretty much everything in Scheme is
recursive). I hinted about this earlier when I mentioned that my N-
Queens program is non-recursive, whereas this is almost always done
recursively and is often assigned in school to specifically to teach
recursion.

Is this correct? It looks like a bug, as the result should be 0 not 1.
> 0 50CENT
> 1  ok
Just off the top of my head, I think this could be fixed by using ?DO
rather than DO --- but I haven't examined your program carefully
enough to know. I'm at a restaurant right now, so I don't really have
time --- I'll look at it more closely later. I don't think I will
write a program of my own --- I will just examine yours, as I doubt
that I could write one that would be significantly better (this is a
pretty easy problem, so there is not all that much opportunity for
cleverness).

Good job! (although I wish Gavino could have stepped up and done it)

[Ed]

Your routine appears to have made its way to RosettaCode:

http://rosettacode.org/wiki/Count_the_coins

[Ed]

Hugh Aguilar wrote:
> ...

> Good job! (although I wish Gavino could have stepped up and done it)

AFAIK Gavino has never claimed to be a Forth programmer/expert.
He just wants to know if anything substantial has been done in Forth.
Full marks for persistence.

BTW this was more aptly a challenge for maths novices. Programmers
only need to know where to steal and how to adapt routines that someone
else has already written.

[Hugh Aguilar]

On Nov 8, 10:20 pm, "Ed" <inva...@nospam.com> wrote:
> Hugh Aguilar wrote:
> > ...
> > Good job! (although I wish Gavino could have stepped up and done it)
>
> AFAIK Gavino has never claimed to be a Forth programmer/expert.
> He just wants to know if anything substantial has been done in Forth.
> Full marks for persistence.

I agree that it is unfair to put Gavino in the same category as the
dynamic duo of Elizabeth Rather and John Passaniti. Gavino isn't a bad
person; he has never claimed to be a Forth expert or even a Forth
programmer. He is somewhat annoying with all those questions about
whether Forth could be used for such-and-such application (the answer
is: "Yes, but only with a lot of work.")

> BTW this was more aptly a challenge for maths novices.  Programmers
> only need to know where to steal and how to adapt routines that someone
> else has already written.

I wouldn't describe this as a challenge for mathematics folks. There
is no math here except simple arithmetic. It is a challenge for
programmers, as it involves developing an algorithm. It is pretty well-
known though, so it is possible for a script-kiddie to steal an
already-written program off the internet without understanding how it
works. Also, it is not a very difficult algorithm --- a person could
solve the puzzle for specific cases by hand, working with a big pile
of coins on the kitchen table.

[arc]

>
> As a slightly more advanced challenge (still pretty easy), solve the N-
> Queens problem. I don't think this appears anywhere in SICP, but I
> have a solution in my novice package (
> http://www.forth.org/novice.html). As a bonus challenge --- make your
> program non-recursive as I did (the N-Queens problem is a classic
> example of recursive-descent searching in many textbooks).

Here is my non-recursive n-queens solution.

I'm still pretty green with forth, so comments welcome.

-arc.

\ \\\\\\\\\\
\ nqueens.fs

( basic usage:
create-queens dup n-queens
dup .board \ displays a chessboard
dup .queens \ displays coordinates of queens
set N to solve for Ns other than 8. )

variable N
8 N !

: 3dup
dup 2over rot ;

\ \\\\\\\\\\\\\\\\\\\\\\
\ RNG

( Fast Random Number Generator
algorithm by George Marsaglia "Xorshift RNGs"

Arnold Doray's version posted to comp.lang.forth Sat, 17 Dec 2011
message id: <jch8b0$d5h$1...@dont-email.me>
)

\ Xorshift (13,17,5)
: xorshift ( n -- n )
dup 13 lshift xor
dup 17 rshift xor
dup 5 lshift xor ;

variable (rnd) \ seed
2463534242 (rnd) ! \ initialize seed

: rnd ( -- n )
(rnd) @ xorshift dup (rnd) ! ;

: random-index
rnd n @ mod ;

\ \\\\\\\\\\\\\\\\\\\\
\ Queens and their operations

2 cells constant QUEEN-SIZE

: create-queens ( - queens-addr )
here
N @ QUEEN-SIZE * allot ;

: queen.x ( queen-addr - x )
@ ;

: queen.x! ( x queen-addr - )
! ;

: queen.y ( queen-addr - y )
1 cells + @ ;

: queen.y! ( y queen-addr - )
1 cells + ! ;

: queen.xy! ( x y queen-addr - )
2dup queen.y!
swap drop queen.x! ;

: queens.queen-i ( queens-addr n - queen-addr )
queen-size * + ;

: queens-bounds ( queens-addr - upper-bound lower-bound)
N @ QUEEN-SIZE * bounds ;


: .queens ( queens-addr - )
cr
queens-bounds ?do
i dup . [char] : emit space
dup queen.x .
queen.y . cr
queen-size +loop ;

: clear-queens ( queens-addr - )
queens-bounds ?do
-1 i queen.x!
-1 i queen.y!
queen-size +loop ;


: queen-there ( x y queens-addr - f )
queens-bounds ?do
over i queen.x =
over i queen.y =
and
if 2drop -1 unloop exit then
queen-size +loop
2drop 0 ;



: setup-queens ( queens-addr - )
dup queens-bounds ?do ( queens-addr )
begin
random-index random-index ( queens-addr x y )
3dup rot
queen-there ( queens-addr x y f )
while 2drop repeat ( queens-addr x y )
i queen.xy!
queen-size +loop drop ;

\ \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
\ board display

: .board-rowborder ( n - )
[char] + emit
0 ?do
[char] - emit [char] + emit
loop cr ;


: .board ( queens-addr - )
cr
space space space N @ 0 ?do i . loop cr
space space N @ .board-rowborder
N @ 0 ?do i .
[char] | emit
N @ 0 ?do
dup j i rot queen-there if [char] Q emit else space then
[char] | emit
loop cr
space space N @ .board-rowborder
loop drop ;

\ \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
\ attack detection

: on-same-col ( queens-addr queens-addr - f )
queen.y swap queen.y = ;

: on-same-row ( queens-addr queens-addr - f)
queen.x swap queen.x = ;

: on-same-diagonal ( queen-addr queen-addr - f )
2dup queen.x swap queen.x - abs -rot ( xdiff queen-addr queen-addr )
queen.y swap queen.y - abs ( xdiff ydiff)
= ;

: queen-attack ( queen-addr queen-addr - f )
2dup = if 2drop 0 exit then
2dup on-same-row if 2drop -1 exit then
2dup on-same-col if 2drop -1 exit then
2dup on-same-diagonal if 2drop -1 exit then
2drop 0
;

: queen-attacked ( queens-addr queen-addr - f )
swap queens-bounds ?do
dup i queen-attack if drop -1 unloop exit then
queen-size +loop
drop 0
;

: any-queens-attacked ( queens-addr - f )
dup queens-bounds ?do
dup i queen-attacked if drop -1 unloop exit then
queen-size +loop
drop 0
;

\ \\\\\\\\\\\\\\\\\\
\ nqueens

variable iterations

: n-queens ( queens-addr )
0 iterations !
begin
iterations @ 1 + iterations !
dup clear-queens
dup setup-queens
dup any-queens-attacked
invert
until
drop
;


\ uncomment this to get an explicit solution example
\ create explicit-solution 0 , 3 , 1 , 5 , 2 , 7 , 3 , 1 , 4 , 6 , 5 , 0 , 6 , 2 , 7 , 4 ,

[Hugh Aguilar]

On Nov 10, 9:53 pm, arc <arc.deletet...@vorsicht-bissig.de> wrote:
> > As a slightly more advanced challenge (still pretty easy), solve the N-
> > Queens problem. I don't think this appears anywhere in SICP, but I
> > have a solution in my novice package (
> >http://www.forth.org/novice.html). As a bonus challenge --- make your
> > program non-recursive as I did (the N-Queens problem is a classic
> > example of recursive-descent searching in many textbooks).
>
> Here is my non-recursive n-queens solution.
>
> I'm still pretty green with forth, so comments welcome.
>
> -arc.

I glanced over it. I don't think that a Monte Carlo search is
necessary. That is only done when you don't know how to search
completely, or a complete search is so gigantic as to be intractable,
so you just fire at random until you hit something that works. Neither
is true of the N-Queens problem --- you do know how to search
completely (just iterate down the rows), and the search is pretty
small (my program takes a matter of seconds to run).

You are factoring a lot, which is good. The only thing I would suggest
is that you use a record for your queen's coordinates, rather than use
a double and then manually write code to assign one cell to .x and the
other to .y as you did. This will become especially important later on
if you write a program in which your record has more than two fields
in it. You can use FIELD which is provided in the novice package:
http://www.forth.org/novice.html

Your Forth style is pretty good. The only thing I would suggest is
that you indent all of the loop at the same level, rather than have
the last line indented at the same level as the previous code. For
example, you have this:

: queen-there ( x y queens-addr - f )
queens-bounds ?do
over i queen.x =
over i queen.y =
and
if 2drop -1 unloop exit then
queen-size +loop
2drop 0 ;

I would indent the +LOOP line like this:

: queen-there ( x y queens-addr - f )
queens-bounds ?do
over i queen.x =
over i queen.y =
and
if 2drop -1 unloop exit then
queen-size +loop
2drop 0 ;

Also, I generally put the IF on the same line as the code that
generated the conditional:

: queen-there ( x y queens-addr - f )
queens-bounds ?do
over i queen.x =
over i queen.y =
and if 2drop -1 unloop exit then
queen-size +loop
2drop 0 ;

Also, use TRUE and FALSE for better readability (generally, you always
want to use constants rather than "magic numbers" in your code):

: queen-there ( x y queens-addr - f )
queens-bounds ?do
over i queen.x =
over i queen.y =

and if 2drop true unloop exit then
queen-size +loop
2drop false ;

All in all, it looked like pretty good Forth style. I didn't actually
test the program though.

[John Rible]

On Tuesday, November 13, 2012 8:29:31 PM UTC-8, Hugh Aguilar wrote:

> ...snip... I didn't actually test the program though.

With apologies to Pete Seeger: when will you ever learn?

[Hugh Aguilar]

Probably never, as I don't understand your criticism.

I don't really have time to test/debug other people's programs. I can
see that the algorithm (a Monte Carlo search) is inappropriate, so the
whole program has to be rewritten anyway, so there isn't all that much
point in testing this one. I helped the guy a little, in that I
steered him away from an inappropriate algorithm and I critiqued his
coding style. That wasn't a lot of help, but it was more than you have
done for him, which is nothing.

[Albert van der Horst]

In article <4f03fcc6-545f-4415...@googlegroups.com>,

Ian Osgood <ia...@quirkster.com> wrote:
>On Sunday, November 4, 2012 5:57:44 PM UTC-8, Hugh Aguilar wrote:
>> I'm working my way through SICP. There is nothing like that available
>>
>> for Forth!
>
>There was a wiki devoted to solving SICP problems in Oz, which also
>included many other programming languages. I had added Forth solutions
>to problems in the early chapters -- including this one -- before lack
>of automatic memory management became a burden. Here was my recursive
>solution to the change counting problem:
>
>: table create does> swap cells + @ ;
>table coin-value 0 , 1 , 5 , 10 , 25 , 50 ,
>
>: count-change ( total coin -- n )
> over 0= if
> 2drop 1
> else over 0< over 0= or if
> 2drop 0
> else
> 2dup coin-value - over recurse
> >r 1- recurse r> +
> then then ;
>
>100 5 count-change .
>

Isn't that horse dead already?

From a recent thread:
"
WANT MARK-TIME
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 ;

MARK-TIME 100 count-change "Dollars :" TYPE . ELAPSED .uS CR
"

There is an interesting difference. This code splits the recursion
part in two branches 2-->1 introduced by a 2DUP.

Your code splits the data path, then uses OVER to borrow some
data from the other data path.

Despite the extra return stack manipulation I prefer the second
solution. You will understand what I mean if you try yo port this
to Factor.

>(The CTMWiki was at http://codepoetics.com/wiki/ but seems to have
>disappeared in the last few years.)

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