Josephus Circle problem

From	Paul Rubin <no.email@nospam.invalid>
Newsgroups	comp.lang.forth
Subject	Josephus Circle problem
Date	2013-12-23 19:12 -0800
Organization	Nightsong/Fort GNOX
Message-ID	<7x61qfuel8.fsf@ruckus.brouhaha.com> (permalink)

Show all headers | View raw

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

Back to comp.lang.forth | Previous | Next — 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