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

Groups > comp.lang.forth > #53554

Re: Challenge for Christmas

Newsgroups comp.lang.forth
Date 2016-12-26 11:45 -0800
References <26197516-a481-4262-a604-5cae2c7dc49a@googlegroups.com> <o3rg8d$7q0$1@cherry.spenarnc.xs4all.nl>
Message-ID <30f7aeeb-e32b-4a17-855e-a9595af047be@googlegroups.com> (permalink)
Subject Re: Challenge for Christmas
From lehs <skydda.barnen@gmail.com>

Show all headers | View raw

Den måndag 26 december 2016 kl. 17:14:08 UTC+1 skrev Albert van der Horst:
> In article <26197516-a481-4262-a604-5cae2c7dc49a@googlegroups.com>,
> lehs  <skydda.barnen@gmail.com> wrote:
> >Given a buffer of increasing unsigned integers beginning at addr1 and ending at addr2-cell. I want a routine
> >
> >is_a_product  ( u addr2 addr1 -- flag )
> >
> >answering the question wether u is a product of some numbers in the field or not.
> >
> >Example: if the field contains the integers 2,3,4 then 2,6,9,12
> should give true flag while 7,10,21 should give false flag. Unless I'm
> wrong there is a lot of different strategies, but I can't see an
> obvious one.
> 
> I made it a challenge to have it right the first time, i.e. the first
> test must succeed. That didn't happen because in the specification
> only the examples make clear that each number may be used more than once.
> Then the modified program accepted the test cases.
> Note that I tightened the specs.
> 
> This ask for a program that does recursion on several levels,
> much like the infamous coin change program. These programs are
> notoriously inefficient. With recursion you don't want three items
> on the stack. But the end of the array is fortunately always the
> same, which saves one parameter.
> 
> ------------------------------------------------
> WANT TRUE
> VARIABLE high
> : (is_a_product)   ( n,a)
>    OVER 1 = IF 2DROP TRUE EXIT THEN    ( n,a)
>    2DUP @ < IF 2DROP FALSE EXIT THEN   ( n,a)    \ * note
>    BEGIN DUP high @ <> WHILE           ( n,a)
>       2DUP @ /MOD                      ( n,a, rem, n')
>       SWAP IF DROP ELSE
>          OVER RECURSE IF 2DROP TRUE EXIT THEN
>       THEN                             ( n,a)
>    CELL+ REPEAT                        ( n,a')
>    2DROP FALSE EXIT ;
> 
> \ For  n  and a non-inclusive range  adr1  adr2  ,return
> \ "n  can  be written as a product of numbers in the range, where
> \ each number can be used zero or more times"
> : is_a_product   SWAP high ! (is_a_product) ;
> 
> HERE 2 , 3 , 4 , HERE
> CONSTANT adr2   CONSTANT adr1
> 
> : q adr2 adr1 is_a_product ;
> 
> "Expect false " TYPE 7 q . 10 q . 21 q . CR
> "Expect true " TYPE 2 q . 6 q . 9 q . 12 q . CR
>  ---------------------------------------------------
> 
> Expect false 0 0 0
> Expect true -1 -1 -1 -1
> 
> You can leave out the line with the star. That is an optimisation,
> based on the given that the factors are in increasing order.
> 
> Note the Moore convention for parameters: and extra space around
> the names. My convention to replace -- by `` : ''  `` leaves ''
> or `` returns '' complements that.
> 
> 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

Very nice! I'm convinced this is the simplest possible approach. With your permission I will use the code on my blog http://forthmath.blogspot.se to study integer monoids, sets of natural numbers that are closed under multiplication (i.e. if two numbers belong to a certain monoid, then also their product do that). 

All such monoids are infinite, but are determed by its generators. With is_a_product it's possible to decide whether a natural number is a member of a finitely generated integer  monoid or not.

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-24 06:10 -0800
  Re: Challenge for Christmas november.nihal@gmail.com - 2016-12-24 14:17 -0800
    Re: Challenge for Christmas mhx@iae.nl - 2016-12-24 15:37 -0800
    Re: Challenge for Christmas mhx@iae.nl - 2016-12-24 15:43 -0800
    Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-25 01:25 -0800
      Re: Challenge for Christmas november.nihal@gmail.com - 2016-12-25 06:59 -0800
        Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-25 07:26 -0800
          Re: Challenge for Christmas november.nihal@gmail.com - 2016-12-25 07:57 -0800
            Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-25 08:07 -0800
              Re: Challenge for Christmas november.nihal@gmail.com - 2016-12-25 08:25 -0800
  Challenge for Christmas Ilya Tarasov <ilya74.tarasov@gmail.com> - 2016-12-25 07:39 -0800
  Re: Challenge for Christmas anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-12-25 16:52 +0000
    Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-25 09:33 -0800
      Re: Challenge for Christmas Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2016-12-25 18:15 +0000
        Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-25 13:21 -0800
          Re: Challenge for Christmas november.nihal@gmail.com - 2016-12-25 16:51 -0800
            Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-26 00:48 -0800
              Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-26 01:36 -0800
              Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-26 01:39 -0800
                Re: Challenge for Christmas november.nihal@gmail.com - 2016-12-26 04:36 -0800
                Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-26 07:40 -0800
                Re: Challenge for Christmas anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-12-26 15:53 +0000
                Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-26 08:57 -0800
                Re: Challenge for Christmas anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-12-27 13:12 +0000
                Re: Challenge for Christmas albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-12-27 16:58 +0100
                Re: Challenge for Christmas anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-12-27 16:01 +0000
                Re: Challenge for Christmas albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-12-27 19:10 +0100
                Re: Challenge for Christmas anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-12-27 18:08 +0000
                Re: Challenge for Christmas albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-12-27 20:13 +0100
                Re: Challenge for Christmas anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-12-28 08:19 +0000
                Re: Challenge for Christmas albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-12-28 12:49 +0100
                Re: Challenge for Christmas anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-12-28 14:26 +0000
                Re: Challenge for Christmas anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-12-29 13:13 +0000
                Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-27 12:29 -0800
                Re: Challenge for Christmas albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-12-27 22:25 +0100
                Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-27 14:19 -0800
                Re: Challenge for Christmas november.nihal@gmail.com - 2016-12-27 14:14 -0800
                Re: Challenge for Christmas anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-12-28 11:06 +0000
                Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-28 04:22 -0800
              Re: Challenge for Christmas john <anon@example.com> - 2016-12-26 13:05 +0000
                Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-26 07:45 -0800
          Re: Challenge for Christmas Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2016-12-26 07:44 +0000
        Re: Challenge for Christmas anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-12-26 13:21 +0000
          Re: Challenge for Christmas anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-12-26 13:57 +0000
            Re: Challenge for Christmas anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-12-26 14:58 +0000
  Re: Challenge for Christmas albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-12-26 17:24 +0100
    Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-26 09:15 -0800
    Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-26 11:45 -0800
    Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-30 10:47 -0800
      Re: Challenge for Christmas albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-12-31 15:31 +0100
        Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-31 10:53 -0800

csiph-web