Josephus problem

[Volker Vanoni]

Hi,
I am a newbie not to Basic in general but to Powerbasic. The attached file
contains a solution of the Josephus problem. I used a string like a list in functual languages. This is not the usual way. Can anyone show me how to do it with a linked list?
greetings
Volker

[Michael Mattias]

I have a (old!) linked list demo:
Dynamic Allocation and Linked Lists for both PB/DOS and PB/CC
Public Domain, as appeared in April 1999 issue of BASICally Speaking

I think someone else recently did a linked list demo, right here. Try a search of source code forum using "linked" in thread title.

As far as USING a linked list to solve the problem you are on your own. (I like your current solution, assuming it works).

MCM

[Chris Holbrook]

two ways to do it

first method
just translate a C solution using pointers and allocating the nodes dynamically. If you post source here someone may translate it, or parts of it, for you. Another flavour of this would be to use strings (automatic dynamic allocation done for you) instead of UDTs.

second method
declare a UDT to be a node, declare a circle as an array of nodes, and the previous and next "linked list pointers" are then array subscripts.

The result of the second method will look a bit like this - undebugged because it is past my bedtime:

#compile exe
#dim all
#break on
#debug display
  type Jonode
    Number as long
    nxt as dword
    Prev as dword
  end type
global circle() as jonode
'----------------------------------------------
sub makecircle ( n as long)
    local i as long
    local s as string
    
    redim circle(0 to n-1) as global jonode
    for i = 1 to n-2
        circle(i).nxt = i + 1
        circle(i).prev = i - 1
    next
    circle(0).nxt = 1
    circle(0).prev = n -1
    circle(n-1).nxt = 0
    circle(n-1).prev = n - 2
'    for i = lbound(circle()) to ubound(circle())
'        ? str$(i) + str$(circle(i).prev) + str$(circle(i).nxt)
'    next
        
end sub
'--------------------------------------------
function Josephus(Number as long, skip as long) as string
      local  current, l as long

      makecircle( number)
      do until circle(current).nxt = current
          for l = 1 to Skip
              current = circle(current).nxt
          next
          current = destry(current)
      loop
      Josephus = str$(circle(current).number)
      current = destry(current)
end function
'--------------------------------------------
function destry(deaded as long) as long

  circle(circle(deaded).prev).nxt = circle(deaded).nxt

  circle(circle(deaded).nxt).prev = circle(deaded).Prev

  function = circle(Deaded).nxt

  circle(deaded).nxt = -1

  circle(deaded).prev = -1

end function
'-------------------------------------------
function pbmain () as long
    local n, s as long
    input "How many warriors? ",n
    input "Counting modus? ",s
    print "The warrior with position " + Josephus(n,s) + " in the circle is remaining "
    sleep 12000
end function

[Mel Bishop]

Well, Volker, since no one else has, let me be the first to welcome you to the board.

Got a Question/Problem? DO NOT hesitate to ask!!! 9,999 times out of ten thousand, you will get a prompt, accurate answer.

Could you do us a favor? Please update your personal profile so we can all know where you are from. We have posters from all over the world here and your location would be most appreciative. Thanks.

You know, to be honest, I didn't have a clue as to what your puzzle is. I had to go to Wikipedia to find out.

[John Gleason]

Here's a solution to the puzzle, but I don't know how it compares to the linked list technique--probably not too favorably.

#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN () AS LONG
    DIM n AS LONG
    LOCAL a, warrPos, cMod, ii, lastWarr AS LONG

    INPUT "How many warriors? ",n
    INPUT "Counting modus? ",a
    DIM circ(1 TO n) AS LONG
    FOR ii = 1 TO n
       circ(ii) = 49
    NEXT
    
    DO
       INCR warrPos
       IF warrPos > n THEN warrPos = 1
       IF circ(warrPos) = 49 THEN
          INCR cMod
          IF cMod = a THEN
             circ(warrPos) = 48
             cMod = 0
             INCR lastWarr
             IF n - lastWarr = 1 THEN
                FOR ii = 1 TO n
                   IF circ(ii) = 49 THEN
                      PRINT "The warrior with position"+ STR$(ii)+ " in the circle is remaining "
                      WAITKEY$
                      EXIT FUNCTION
                   END IF
                NEXT
             END IF
          END IF
       END IF
    LOOP
       
END FUNCTION

[Chris Holbrook]

Volker, have we just done your prep for you?

Just a little tweak to make it report the number correctly:

#compile exe
#dim all
#break on
#debug display
  type Jonode
    Number as long
    nxt as dword
    Prev as dword
  end type
global circle() as jonode
'----------------------------------------------
sub makecircle ( n as long)
    local i as long
    local s as string

    redim circle(0 to n-1) as global jonode
    for i = 1 to n-2
        circle(i).nxt = i + 1
        circle(i).prev = i - 1
        circle(i).number = i
    next
    circle(0).nxt = 1
    circle(0).prev = n -1
    circle(0).number = 0
    circle(n-1).nxt = 0
    circle(n-1).prev = n - 2
    circle(n-1).number = n-1
end sub
'--------------------------------------------
function Josephus(Number as long, skip as long) as string
      local  current, l as long

      makecircle( number)
      do
          for l = 1 to Skip
              current = circle(current).nxt
          next
          current = destry(current)
      loop until circle(current).nxt = current
      function = str$(circle(current).number)
      current = destry(current)
end function
'--------------------------------------------
function destry(deaded as long) as long

  circle(circle(deaded).prev).nxt = circle(deaded).nxt

  circle(circle(deaded).nxt).prev = circle(deaded).Prev

  function = circle(Deaded).nxt

  circle(deaded).nxt = -1

  circle(deaded).prev = -1

end function
'-------------------------------------------
function pbmain () as long
    local n, s as long
    input "How many warriors? ",n
    input "Counting modus? ",s
    print "The warrior with position " + Josephus(n,s) + " in the circle is remaining "
    sleep 12000
end function

[John Gleason]

Chris, I tried 100,000 warriors and a 455 modus, and got a different answer than with your code. I don't know how to check which is right.

[Chris Holbrook]

Chris, I tried 100,000 warriors and a 455 modus, and got a different answer than with your code. I don't know how to check which is right.

John, are you sure you weren't using a byte array? Only kidding. I admire your thoroughness. My code is just a hack of a Pascal source I found on the web. I don't think we should investigate until Volker tells us what marks we got for his homework!

[Volker Vanoni]

Re: Josephus problem

To my advisors
I thank you for your help.
Chris' first version has indeed a little bug. The socond version seems to work correctly. Linked list look very complicated in C and Powerbasic. I doubt whether I shall work with them. My first language was Scheme, a Lisp dialect.
It is built on lists which are easy to use and lead to short code. Therfore I always trie to fake list with strings. Maybe I can achieve the same with dynamic arrays. John' s code is something like that, I think.
Thanks again. I was really suprised that I got so many responds.
Best wishes
Volker

[Volker Vanoni]

Re: Josephus problem

To my advisors
I thank you for your help.
Chris' first version has indeed a little bug. The second seems to work correctly. Linked list look very complicated in C and Powerbasic. I doubt whether I shall work with them. My first language was Scheme, a Lisp dialect.
It is built on lists which are easy to use and lead to short code. Therfore I always trie to fake list with strings. Maybe I can achieve the same with dynamic arrays. John' s code is something like that, I think.
Thanks again. I was really suprised that I got so many responds.
Best wishes
Volker

[Michael Mattias]

My first language was Scheme, a Lisp dialect.
It is built on lists which are easy to use and lead to short code

Your problem looks like it should be solvable with recursion.

Recursion results in 'short code.' It can also be a real bear to debug.

MCM

[Chris Holbrook]

There are a few different approaches in this collection of source code: http://thedailywtf.com/Comments/Prog...us-Circle.aspx

[Christopher Carroll]

Recursion

Chris, interesting link, thanks.

One of the more elegant solutions on that page used recursion. Here is what the author wrote:

' Ref: 2009-07-29 09:47 • by Alex Mont.
' http://thedailywtf.com/Comments/Programming-Praxis-Josephus-Circle.aspx

' Consider the function J(n,k) which is the position of the surviving soldier
' relative to the current starting point of the count, where n is the number of
' remaining soldiers and k is the interval (3 in the example).
' (Note that counting 3 at a time actually means you're only skipping 2
' at a time.) Note that "position" is counting only currently alive soldiers.

' If n=1 then clearly we are done, and J(1,k) = 0 for any k.
' Now consider the case of n>1. We have something like this:

' * * * * * * * * * *
'       ^

' Where the caret marks where the count starts.
' Now at the next step (assuming again k=3)

' * * * * * X * * * *
'             ^

' So now suppose that J(n-1,k) = x. That means that the surviving soldier is
' X positions after the caret in the second diagram. But the caret in the
' second diagram is 3 positions after the caret in the first diagram, so the
' surviving soldier is X+3 positions after the caret in the first diagram. Of
' course you have to take the mod of that by n to account for wrap around.

' Thus our formula is (code in Python):

'   def J(n,k):
'       if(n==1)
'           return 0
'       else
'           return (J(n-1,k)+k)%n

' Note that because of the way the recursion is set up, at no point do you
' have to keep track of which positions of soldiers are dead already.
' And it is an O(n) algorithm.

And here is it in PowerBASIC. Note that I take no credit for this (it belongs to Alex Mont):

#Compile Exe
#Dim All

Function J(n As Long, ByVal k As Long) As Long
' Purpose:      Josephus problem with recursion
' Parameters:   I/O: n - number of remaining soldiers
'               I:   k - interval
    J = IIf&(n = 1, 0, (J(n - 1, k) + k) Mod n)
End Function

Function PbMain()
    ? Str$(J(41, 3))        ' J(41, 3) --> 30
End Function

[Michael Mattias]

Using recursion certainly produces "short" code.

[Volker Vanoni]

Re: Josephus problem

The recursive solution is elegant and I would have chosen it if I would have thought about it.
Volker