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

Groups > comp.lang.forth > #27411

Re: Josephus Circle problem

From "Rod Pemberton" <dont_use_email@xnohavenotit.cnm>
Newsgroups comp.lang.forth
Subject Re: Josephus Circle problem
Date 2013-12-24 02:49 -0500
Organization Aioe.org NNTP Server
Message-ID <op.w8k6n9wa5zc71u@localhost> (permalink)
References <7x61qfuel8.fsf@ruckus.brouhaha.com>

Show all headers | View raw

On Mon, 23 Dec 2013 22:12:35 -0500, Paul Rubin <no.email@nospam.invalid>  
wrote:

> This is an oldie that was in Knuth vol 2 though I don't have the
> reference handy.  Also at:
>
> http://thedailywtf.com/Articles/Programming-Praxis-Josephus-Circle.aspx
> http://mathworld.wolfram.com/JosephusProblem.html
>
> From the first url: "In order to decide who would die in which order,
> the soldiers stood in a circle and, starting with the top of the circle
> and continuing clockwise, counted to three. The third man got the ax and
> the counting resumed at one. The process continued until there was no
> one left. Josephus, who didn't quite agree with the whole "we should all
> kill ourselves" idea, figured out the perfect way to avoid death: be the
> last man standing."
>
> Problem: There are 40 soldiers to start with, number 1,2,3,... .
> Calculate the order in which they are killed.
>
> A solution:
> ================================================================
>
> 40 constant ring-size
> 3 constant jump-size
> jump-size 1- constant jump-size-1
>
> create ring  ring-size cells allot
> does> ( i -- addr ) swap cells + ;
>
> variable remaining                      \ number of men still alive
> variable p                              \ place to start counting from
> : decr-remaining ( -- ) remaining @ 1- remaining ! ;
>
> : init-ring ( -- ) ring-size 0 do i 1+ i ring ! loop ;
> : init-vars ( -- ) ring-size remaining !   0 p ! ;
> : init ( -- ) init-ring init-vars ;
> : next-p ( -- ) p @ jump-size-1 + remaining @ mod p ! ;
>
> : cells-to-move ( -- n ) remaining @ p @ - 1- ;
> : remove ( -- ) p @ 1+ ring  p @ ring  cells-to-move cells  move ;
>
> : show ( n -- ) ring @ . ;
> : iteration ( -- ) next-p p @ dup show remove decr-remaining ;
> : run ( -- ) cr init begin remaining @ while iteration repeat cr ;
>
> run
> ================================================================


https://groups.google.com/d/msg/comp.lang.c/k9YQ7kmnRsE/saqlkO2Si60J

Understand it?


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