Announcement

Collapse
No announcement yet.

Josephus problem

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • Volker Vanoni
    replied
    Re: Josephus problem

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

    Leave a comment:


  • Michael Mattias
    replied
    Using recursion certainly produces "short" code.

    Leave a comment:


  • Christopher Carroll
    replied
    Recursion

    Chris, interesting link, thanks.

    One of the more elegant solutions on that page used recursion. Here is what the author wrote:
    Code:
    ' 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):
    Code:
    #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

    Leave a comment:


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

    Leave a comment:


  • Michael Mattias
    replied
    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

    Leave a comment:


  • Volker Vanoni
    replied
    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

    Leave a comment:


  • Volker Vanoni
    replied
    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

    Leave a comment:


  • Chris Holbrook
    replied
    Originally posted by John Gleason View Post
    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!

    Leave a comment:


  • John Gleason
    replied
    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.

    Leave a comment:


  • Chris Holbrook
    replied
    Volker, have we just done your prep for you?

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

    Code:
    #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

    Leave a comment:


  • John Gleason
    replied
    Here's a solution to the puzzle, but I don't know how it compares to the linked list technique--probably not too favorably.
    Code:
    #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

    Leave a comment:


  • Mel Bishop
    replied
    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.
    Last edited by Mel Bishop; 12 Oct 2009, 07:49 PM.

    Leave a comment:


  • Chris Holbrook
    replied
    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:

    Code:
    #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

    Leave a comment:


  • Michael Mattias
    replied
    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

    Leave a comment:


  • Volker Vanoni
    started a topic Josephus problem

    Josephus problem

    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
    Attached Files
Working...
X