Announcement

Collapse
No announcement yet.

Josephus problem

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

  • 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:wave:
    Attached Files

  • #2
    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
    Michael Mattias
    Tal Systems Inc. (retired)
    Racine WI USA
    [email protected]
    http://www.talsystems.com

    Comment


    • #3
      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

      Comment


      • #4
        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, 08:49 PM.
        There are no atheists in a fox hole or the morning of a math test.
        If my flag offends you, I'll help you pack.

        Comment


        • #5
          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

          Comment


          • #6
            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

            Comment


            • #7
              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.

              Comment


              • #8
                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!

                Comment


                • #9
                  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:wavey:

                  Comment


                  • #10
                    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:wavey:

                    Comment


                    • #11
                      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
                      Michael Mattias
                      Tal Systems Inc. (retired)
                      Racine WI USA
                      [email protected]
                      http://www.talsystems.com

                      Comment


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

                        Comment


                        • #13
                          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

                          Comment


                          • #14
                            Using recursion certainly produces "short" code.
                            Michael Mattias
                            Tal Systems Inc. (retired)
                            Racine WI USA
                            [email protected]
                            http://www.talsystems.com

                            Comment


                            • #15
                              Re: Josephus problem

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

                              Comment

                              Working...
                              X