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

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

coin changer --- a challenge for novices

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

Contents

  coin changer --- a challenge for novices Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-11-04 17:57 -0800
    Re: coin changer --- a challenge for novices "Paul E. Bennett" <Paul_E.Bennett@topmail.co.uk> - 2012-11-05 07:47 +0000
      Re: coin changer --- a challenge for novices Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-11-05 21:26 -0800
        Re: coin changer --- a challenge for novices "Paul E. Bennett" <Paul_E.Bennett@topmail.co.uk> - 2012-11-06 19:00 +0000
    Re: coin changer --- a challenge for novices Steve Graham <jsgrahamus@yahoo.com> - 2012-11-06 17:09 -0700
      Re: coin changer --- a challenge for novices jfong <jfong@ms4.hinet.net> - 2012-11-06 17:57 -0800
      Re: coin changer --- a challenge for novices Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-11-07 05:13 -0600
      Re: coin changer --- a challenge for novices awegel@arcor.de (Alex Wegel) - 2012-11-07 16:04 +0100
      Re: coin changer --- a challenge for novices Brad Eckert <hwfwguy@gmail.com> - 2012-11-07 08:11 -0800
        Re: coin changer --- a challenge for novices "Ed" <invalid@nospam.com> - 2012-11-08 19:12 +1100
    Re: coin changer --- a challenge for novices Ian Osgood <iano@quirkster.com> - 2012-11-08 07:19 -0800
      Re: coin changer --- a challenge for novices anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-11-08 17:27 +0000
        Re: coin changer --- a challenge for novices Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-11-08 19:56 -0800
      Re: coin changer --- a challenge for novices "Ed" <invalid@nospam.com> - 2012-11-09 15:37 +1100
      Re: coin changer --- a challenge for novices albert@spenarnc.xs4all.nl (Albert van der Horst) - 2012-11-14 10:59 +0000
    Re: coin changer --- a challenge for novices jfong <jfong@ms4.hinet.net> - 2012-11-08 17:04 -0800
      Re: coin changer --- a challenge for novices Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-11-08 20:10 -0800
        Re: coin changer --- a challenge for novices "Ed" <invalid@nospam.com> - 2012-11-09 16:17 +1100
          Re: coin changer --- a challenge for novices Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-11-08 23:17 -0800
    Re: coin changer --- a challenge for novices arc <arc.deletethis@vorsicht-bissig.de> - 2012-11-11 17:53 +1300
      Re: coin changer --- a challenge for novices Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-11-13 20:29 -0800
        Re: coin changer --- a challenge for novices John Rible <google@sandpipers.com> - 2012-11-13 22:39 -0800
          Re: coin changer --- a challenge for novices Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-11-13 22:54 -0800

Page 1 of 2  [1] 2  Next page →

#17049 — coin changer --- a challenge for novices

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

[toc] | [next] | [standalone]

#17056

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.Bennett@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..
********************************************************************

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

#17081

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

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

#17091

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

-- 
********************************************************************
Paul E. Bennett...............<email://Paul_E.Bennett@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..
********************************************************************

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

#17095

Hugh Aguilar wrote:
> 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).
>

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.

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

#17099

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!

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

#17110

Steve Graham <jsgrahamus@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.

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

#17120

Steve Graham <jsgrahamus@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?).

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

#17127

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.

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

#17141

Brad Eckert wrote:
> 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.

One can never be too cynical  :)

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

#17163

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

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

#17172

Ian Osgood <iano@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/

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

#17186

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.

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

#17189

Ian Osgood 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 .
>
> (The CTMWiki was at http://codepoetics.com/wiki/ but seems to have disappeared in the last
> few years.)

Your routine appears to have made its way to RosettaCode:

http://rosettacode.org/wiki/Count_the_coins

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

#17265

In article <4f03fcc6-545f-4415-98c8-7da152fc86ed@googlegroups.com>,
Ian Osgood  <iano@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

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

#17184

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?

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

#17188

On Nov 8, 6:04 pm, jfong <jf...@ms4.hinet.net> wrote:
> 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?

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)

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

#17190

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.

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

#17192

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.

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

#17219

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

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web