Path: csiph.com!usenet.pasdenom.info!aioe.org!.POSTED!not-for-mail From: "Rod Pemberton" 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: References: <7x61qfuel8.fsf@ruckus.brouhaha.com> <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 On Tue, 24 Dec 2013 04:13:15 -0500, Paul Rubin wrote: > "Rod Pemberton" 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