Challenge: Solving Josephus problem

[guinness]

I have been known in the past to do these kind of challenges and thought it was that time once again that I present the AutoIt community with a new challenge. I suggest you first go and read the link below as to what is the purpose of the challenge, as I would only repeat what was already said.

Anyway, once you've read the challenge, try and fill in the missing code to solve Josephus problem. Good luck.

Local $aArray = [1,2,3,4,5,6,7]
Josephus($aArray, 3) ; Returns [3,6,2,7,5,1,4]
Josephus($aArray, 1) ; Returns [1,2,3,4,5,6,7]

Func Josephus($aArray, $iCount)
    ; Code here

    ; Returns an array
EndFunc

Source: http://www.codewars.com/kata/josephus-permutation

Edited November 16, 2015 by guinness
Fixed wrong comment style

[mLipok]

link is saying to me: "Uh oh! Something went wrong! (500)"

Edited November 16, 2015 by mLipok
typo

[guinness]

link is saying to me: "Uh oh! Something went wrong! (500)"

Link fixed. Thanks

(It was because I was logged in)

[TouchOdeath]

so then what.. do we PM you the answer or post here?

[mLipok]

Question <Array.au3> can be used ?

 

[guinness]

so then what.. do we PM you the answer or post here?

Post here.

Question <Array.au3> can be used ?

 

Yeah you can, though of course this can be done without Array,au3.

I am not going to join in on this one.

Edited November 16, 2015 by guinness

[mLipok]

Here is my proposal:

#include <Array.au3>

Local $aArray = [1, 2, 3, 4, 5, 6, 7]

Local $aResult1 = Josephus($aArray, 3) ; Returns [3,6,2,7,5,1,4]
_ArrayDisplay($aResult1)

Local $aResult2 = Josephus($aArray, 1) ; Returns [1,2,3,4,5,6,7]
_ArrayDisplay($aResult2)

Func Josephus($aArray, $iCount)
    Local $aResult[UBound($aArray)]

    For $iOuter = 0 To UBound($aArray) - 1
        For $iInner = 1 To $iCount - 1
            _ArrayPush($aArray, $aArray[0])
        Next
        $aResult[$iOuter] = $aArray[0]
        _ArrayDelete($aArray, 0)
    Next

    Return $aResult
EndFunc   ;==>Josephus

 

[guinness]

Clever solution @mLipok

[mLipok]

Working with non UDF solution.

[UEZ]

Shouldn't it be for

Josephus($aArray, 3) ; Returns [3,6,2,5,1,4,7]

?

If so, then here my version:

#include <Array.au3>

Local $aArray = [1,2,3,4,5,6,7]
$aResult = Josephus($aArray, 5) ; Returns [1,2,3,4,5,6,7]
_ArrayDisplay($aResult)

Func Josephus($a, $p = 3)
    If $p = 1 Then Return $a
    Local $aa[UBound($a)], $i, $k = $p, $iUB = UBound($a)
    For $i = 0 To $iUB - 1
        $aa[$i] = $a[$k - 1]
        $k += $p
        $k = $k > $iUB ? $k - $iUB : $k
    Next
    Return $aa
EndFunc

 

Forget it, the link is now working and the number is deleted from array - my assumption was wrong. I've to rethink my solution!

Edited November 16, 2015 by UEZ

[mLipok]

No UDF solution:

#include <Array.au3>

Local $aArray = [1, 2, 3, 4, 5, 6, 7]

Local $aResult1 = Josephus2($aArray, 3) ; Returns [3,6,2,7,5,1,4]
_ArrayDisplay($aResult1)

Local $aResult2 = Josephus2($aArray, 1) ; Returns [1,2,3,4,5,6,7]
_ArrayDisplay($aResult2)

Func Josephus2($aArray, $iCount)
    Local $aResult[UBound($aArray)]

    Local $iPosition = -1
    For $iOuter = 1 To UBound($aArray)
        For $iInner = 1 To $iCount
            Do
                $iPosition += 1
                If $iPosition > UBound($aArray) - 1 Then $iPosition = 0
            Until $aArray[$iPosition] <> ''
        Next
        $aResult[$iOuter-1] = $aArray[$iPosition]
        $aArray[$iPosition] = ''
    Next
    Return $aResult
EndFunc   ;==>Josephus2

 

[mLipok]

@guinness you do not set end time.
Can you set the clock ?

[guinness]

@guinness you do not set end time.
Can you set the clock ?

Well there is no deadline per say, as this was just a bit of fun and kind of good for understanding the language. I know it helped me with ES2015! But lets say 2015/11/18 18:00 UTC.

@UEZ, you had me worried for a second that I have provided incorrect information. The result is correct for anyone else wondering.

Edited November 17, 2015 by guinness

[mikell]

A (dirty) String* route

#Include <Array.au3>

Local $aArray = [1,2,3,4,5,6,7]
$aRes = Josephus($aArray, 3) ; Returns [3,6,2,7,5,1,4]
;$aRes = Josephus($aArray, 1) ; Returns [1,2,3,4,5,6,7]
_ArrayDisplay($aRes)

Func Josephus($aArray, $iCount)
   Local $n = UBound($aArray), $aRes[$n], $k = 0, $sStr
   For $i = 0 to $n-1
      $sStr &= $aArray[$i]
   Next

   Local $sTmp = $sStr
   While $sTmp <> ""
        $k += $iCount
        While $k > StringLen($sStr)
             $sStr &= $sTmp  
        Wend
        $aRes[$k/$iCount-1] = StringMid($sStr, $k, 1)
        $sTmp = StringReplace($sTmp, $aRes[$k/$iCount-1], "")
   Wend
   Return $aRes
EndFunc

 

Edited November 17, 2015 by mikell

[Gianni]

....I crashed and hit my head, when I got up I had this vision:

#include <array.au3>
Local $aArray[7] = [1, 2, 3, 4, 5, 6, 7]
$a = Josephus($aArray, 3) ; Returns [3,6,2,7,5,1,4]
_ArrayDisplay($a)
$a = Josephus($aArray, 1) ; Returns [1,2,3,4,5,6,7]
_ArrayDisplay($a)

Func Josephus($aArray, $iCount)
    ; Code here
    Local $iUbound = UBound($aArray), $aResult[$iUbound], $aTemp[$iUbound], $iCounter = $iCount, $iIndex = 0, $iFound = 0
    Do
        Do
            $iNDX = $iIndex - (Int($iIndex / $iUbound) * $iUbound)
            $iCounter -= $aTemp[$iNDX] = ""
            $iIndex += 1
        Until $iCounter = 0
        $aResult[$iFound] = $aArray[$iNDX]
        $aTemp[$iNDX] = $aArray[$iNDX]
        $iFound += 1
        $iCounter = $iCount
    Until $iFound = $iUbound
    Return $aResult
    ; Returns an array
EndFunc   ;==>Josephus

 

[jchd]

Here's an SQLite version:

expandcollapse popup

/*
  Compute Josephus(count, step)  
  In the example below, we compute Josephus(754, 123)  

  Note that standard SQLite DLL fixes a limit of only 1000 recursions in triggers.
  This limit can be raised as much as needed at compile time. 
*/

pragma recursive_triggers=1;
create table ii as 
              with recursive ints(i) as (
                   select 0
                          union all
                   select i+1
                   from ints
                   where i < 753   /* here put count-1 */
              )       
              select i from ints
;

create table Josephus (i int);

create trigger rest
after delete on ii
      begin
           insert into josephus values (old.i + 1);           
           delete from ii where i = (
                  select i from ii limit 1 offset                  
                         (
                          select ((122  /* here put step - 1*/
                                 + (select count() from ii where i < old.i)) % (select count() from ii))
                          from ii
                  )
           );
      end      
;

delete from ii where i = (select i from ii limit 1 offset 122       /* here put step - 1 again */
);

On my old PC, this SQL Josephus(754, 123) example takes 250 ms on average (on a disk-based database!), while code in, for instance post #11 takes 2.6 s, essentially 10 times more, even if it works only in memory.

You don't need to write Autoit code for running it: use either the sqlite3.exe command-line tool or a good SQLite manager (like SQLite Expert).

[Jos]

I am sure all efforts will be in vain!  

(probably only one of you will understand)

Jos

[UEZ]

Here my approach:

expandcollapse popup

#include <Array.au3>

Global $aArray = [1,2,3,4,5,6,7]

Global $fTimer = TimerInit()
Global $aResult = Josephus($aArray, 3) ; Returns [3,6,2,7,5,1,4]
Global $fTimer_End = TimerDiff($fTimer)

ConsoleWrite("Runtime: " & Round($fTimer_End, 2) & " ms." & @CRLF)

_ArrayDisplay($aResult)


Func Josephus($a, $p = 3)
    If $p = 1 Then Return $a
    $oSD = ObjCreate("Scripting.Dictionary")
    For $i = 0 To UBound($a) - 1
        $oSD.Add($i + 1, $a[$i]) ;key, item
    Next
    Local $aa[UBound($a)], $i = 0, $k = $p, $c, $cc = 0, $kk
    While $oSD.Count > 1
        If $oSD.Item($k) <> "x" Then
            $aa[$i] = $oSD.Item($k)
            $oSD.Item($k) = "x"
        EndIf
        $c = 0
        $kk = $k
        While True
            If $oSD.Item($kk) <> "x" Then
                $c += 1
                $cc = 0
            Else
                $cc += 1
            EndIf
            If $c = $p Or $cc = $oSD.Count Then ExitLoop
            $kk += 1
            If $kk > $oSD.Count Then $kk = 1
        WEnd
        $k = $kk
        $i += 1
        If $i = UBound($aa) Then ExitLoop
    WEnd
    $oSD.RemoveAll()
    $oSD = Null
    Return $aa
EndFunc

 

[mLipok]

My third example:

$aResult1 = Josephus_mLipok_3($aArray, 3) ; Returns [3,6,2,7,5,1,4]
_ArrayDisplay($aResult1, 'Josephus_mLipok_3')
$aResult2 = Josephus_mLipok_3($aArray, 1) ; Returns [1,2,3,4,5,6,7]
_ArrayDisplay($aResult2, 'Josephus_mLipok_3')

Func Josephus_mLipok_3($aArray, $iCount)
    Local $aResult[UBound($aArray)], $sTemp = ''
    For $iOuter = 0 To UBound($aArray) - 1
        $sTemp &= $aArray[$iOuter]
    Next
    For $iOuter = 0 To UBound($aArray) - 1
        $sTemp = StringTrimLeft($sTemp, $iCount - 1) & StringLeft($sTemp, $iCount - 1)
        $aResult[$iOuter] = StringLeft($sTemp, 1)
        $sTemp = StringTrimLeft($sTemp, 1)
    Next
    Return $aResult
EndFunc   ;==>Josephus_mLipok_3

 

[guinness]

(probably only one of you will understand)

Yerp =)

Nice idea with the string, @mikell

Great @Chimp

Classic @jchd with SQL and excellent on the execution speed.

Great @UEZ

Very concise @mLipok

About 8 minutes to go by my watch.

Edited November 18, 2015 by guinness