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

Groups > comp.lang.forth > #27437

Re: Josephus Circle problem

Path csiph.com!usenet.pasdenom.info!aioe.org!.POSTED!not-for-mail
From "Rod Pemberton" <dont_use_email@xnohavenotit.cnm>
Newsgroups comp.lang.forth
Subject Re: Josephus Circle problem
Date Tue, 24 Dec 2013 17:05:49 -0500
Organization Aioe.org NNTP Server
Lines 53
Message-ID <op.w8mabzfq5zc71u@localhost> (permalink)
References <7x61qfuel8.fsf@ruckus.brouhaha.com> <op.w8k6n9wa5zc71u@localhost> <7xsiti628k.fsf@ruckus.brouhaha.com>
NNTP-Posting-Host CNsg4fVcCsvs3UaOgZtQCw.user.speranza.aioe.org
Mime-Version 1.0
Content-Type text/plain; charset=us-ascii; format=flowed; delsp=yes
Content-Transfer-Encoding 7bit
X-Complaints-To abuse@aioe.org
User-Agent Opera Mail/12.16 (Linux)
X-Notice Filtered by postfilter v. 0.8.2
Xref csiph.com comp.lang.forth:27437

Show key headers only | View raw

On Tue, 24 Dec 2013 04:13:15 -0500, Paul Rubin <no.email@nospam.invalid>  
wrote:
> "Rod Pemberton" <dont_use_email@xnohavenotit.cnm> writes:

>> [link]
>> Understand it?
>
> That's in C and it's ugly!

Yes, it is, both.

Unfortunately, as the OP requested it, it would've been
much larger and uglier if it had used linked lists.

> Here it is in Haskell:
>
>     josephus n [] = []
>     josephus n ds = f:josephus n (fs++es) where
>       (es,f:fs) = splitAt n' ds
>       n' = (n-1) `mod` length ds
>
>     main = print (josephus 3 [1..40])
>
> It's interesting that Knuth (actually probably vol. 1 rather than
> vol. 2) gave this problem a difficulty rating suggesting a few hours
> of work in MIX assembly language.

Hours?

> I remember implementing it in Lisp long
> ago, using a circular list mutated with rplacd, ugh.  The Lisp hacking
> took just a few minutes and I remember thinking that yeah, it might
> actually take a few hours to get it working in assembler, so the quick
> Lisp solution showed how much times had changed since the book was
> written in the 1960's.
>

I seem to recall the C solution I posted being just a few minutes too,
but passage of time, posted some years ago, and my recollection may
be glorifying that a bit...

> My Forth solution probably took me about an hour, though a real Forther
> could probably have done it better/faster.  My first Haskell solution
> (using unfoldr) took a few minutes, and the direct recursive version
> above took just a minute or two.  In retrospect, unfoldr was a little
> too fancy.

While a bit ugly, AIR, the C code is quite simple, just using some loops
with skip counters.  That could be re-implemented in Forth since they're
just acting like a sieve, much like the sieve of Eratosthenes for primes.


Rod Pemberton

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

Thread

Josephus Circle problem Paul Rubin <no.email@nospam.invalid> - 2013-12-23 19:12 -0800
  Re: Josephus Circle problem "Rod Pemberton" <dont_use_email@xnohavenotit.cnm> - 2013-12-24 02:49 -0500
    Re: Josephus Circle problem Paul Rubin <no.email@nospam.invalid> - 2013-12-24 01:13 -0800
      Re: Josephus Circle problem mhx@iae.nl - 2013-12-24 02:17 -0800
        Re: Josephus Circle problem ForthFreak <forthfreak@gmail.com> - 2013-12-24 03:45 -0800
          Re: Josephus Circle problem Paul Rubin <no.email@nospam.invalid> - 2013-12-24 04:25 -0800
            Re: Josephus Circle problem ForthFreak <forthfreak@gmail.com> - 2013-12-24 04:25 -0800
              Re: Josephus Circle problem Paul Rubin <no.email@nospam.invalid> - 2013-12-24 04:52 -0800
            Re: Josephus Circle problem albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-12-24 14:57 +0000
            Re: Josephus Circle problem "Ed" <invalid@invalid.com> - 2013-12-25 20:15 +1100
          Re: Josephus Circle problem mhx@iae.nl - 2013-12-24 04:36 -0800
      Re: Josephus Circle problem "Rod Pemberton" <dont_use_email@xnohavenotit.cnm> - 2013-12-24 17:05 -0500
      Re: Josephus Circle problem "WJ" <w_a_x_man@yahoo.com> - 2014-03-10 07:11 +0000
    Re: Josephus Circle problem mhx@iae.nl - 2013-12-24 02:59 -0800
  Re: Josephus Circle problem ForthFreak <forthfreak@gmail.com> - 2013-12-24 01:53 -0800
    Re: Josephus Circle problem Paul Rubin <no.email@nospam.invalid> - 2013-12-24 04:06 -0800
      Re: Josephus Circle problem ForthFreak <forthfreak@gmail.com> - 2013-12-24 04:24 -0800
  Re: Josephus Circle problem ForthFreak <forthfreak@gmail.com> - 2013-12-24 04:30 -0800
    Re: Josephus Circle problem ForthFreak <forthfreak@gmail.com> - 2013-12-24 04:35 -0800
  Re: Josephus Circle problem ForthFreak <forthfreak@gmail.com> - 2013-12-24 05:01 -0800
    Re: Josephus Circle problem Paul Rubin <no.email@nospam.invalid> - 2013-12-24 05:34 -0800
      Re: Josephus Circle problem ForthFreak <forthfreak@gmail.com> - 2013-12-24 05:22 -0800
      Re: Josephus Circle problem "Elizabeth D. Rather" <erather@forth.com> - 2013-12-24 13:25 -1000
        Re: Josephus Circle problem "Ed" <invalid@invalid.com> - 2013-12-25 20:40 +1100
          Re: Josephus Circle problem "Elizabeth D. Rather" <erather@forth.com> - 2013-12-25 09:37 -1000
            Re: Josephus Circle problem ForthFreak <forthfreak@gmail.com> - 2013-12-26 03:19 -0800
              Re: Josephus Circle problem "Elizabeth D. Rather" <erather@forth.com> - 2013-12-26 12:01 -1000
            Re: Josephus Circle problem "Ed" <invalid@invalid.com> - 2013-12-27 12:33 +1100
              Re: Josephus Circle problem Elizabeth D Rather <erather@forth.com> - 2013-12-26 17:41 -1000
                Re: Josephus Circle problem "Ed" <invalid@invalid.com> - 2013-12-27 18:46 +1100
                Re: Josephus Circle problem Mark Wills <markrobertwills@yahoo.co.uk> - 2013-12-27 02:46 -0800
                Re: Josephus Circle problem albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-12-27 13:16 +0000
                Re: Josephus Circle problem mhx@iae.nl - 2013-12-27 05:27 -0800
                Re: Josephus Circle problem albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-12-27 14:15 +0000
                Re: Josephus Circle problem "Ed" <invalid@invalid.com> - 2013-12-29 21:56 +1100
                Re: Josephus Circle problem albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-12-29 12:37 +0000
                Re: Josephus Circle problem "Ed" <invalid@invalid.com> - 2013-12-30 00:47 +1100
                Re: Josephus Circle problem "Ed" <invalid@invalid.com> - 2013-12-29 14:08 +1100
              Re: Josephus Circle problem Mark Wills <markrobertwills@yahoo.co.uk> - 2013-12-27 02:35 -0800
                Re: Josephus Circle problem Mark Wills <markrobertwills@yahoo.co.uk> - 2013-12-27 02:43 -0800
                Re: Josephus Circle problem albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-12-27 19:00 +0000
    Re: Josephus Circle problem albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-12-24 15:59 +0000
  Re: Josephus Circle problem Gerry Jackson <spam@qlikz.org> - 2013-12-24 20:07 +0000
    Re: Josephus Circle problem albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-12-24 20:31 +0000
    Re: Josephus Circle problem mhx@iae.nl - 2013-12-25 04:38 -0800
      Re: Josephus Circle problem mhx@iae.nl - 2013-12-25 06:04 -0800
      Re: Josephus Circle problem mhx@iae.nl - 2013-12-25 06:06 -0800
        Re: Josephus Circle problem Paul Rubin <no.email@nospam.invalid> - 2013-12-25 23:08 -0800
          Re: Josephus Circle problem ForthFreak <forthfreak@gmail.com> - 2013-12-26 03:31 -0800
        Re: Josephus Circle problem Gerry Jackson <spam@qlikz.org> - 2013-12-26 10:52 +0000
          Re: Josephus Circle problem Tristan Plumb <firth@trstn.net> - 2013-12-26 14:37 +0000
            Re: Josephus Circle problem Paul Rubin <no.email@nospam.invalid> - 2013-12-26 07:12 -0800
          Re: Josephus Circle problem Gerry Jackson <spam@qlikz.org> - 2013-12-26 17:31 +0000
        Re: Josephus Circle problem Ron Aaron <rambamist@gmail.com> - 2013-12-26 21:39 +0200
    Re: Josephus Circle problem anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-12-26 17:33 +0000

csiph-web