Challenge: Solving Josephus problem

[guinness]

Competition closed. Who won? You did!

[mLipok]

Was busy and can't brush up, my third example, so I do it now (for these folks who like to analyze code.):

$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
        $aResult[$iOuter] = (StringMid($sTemp, $iCount, 1)='') ? StringMid($sTemp, $iCount - (UBound($aArray) -$iOuter), 1) : StringMid($sTemp, $iCount, 1)
        $sTemp = StringTrimLeft($sTemp, $iCount) & StringLeft($sTemp, $iCount -1)
    Next
    Return $aResult
EndFunc   ;==>Josephus_mLipok_3

EDIT: Third example will work only to 1 digit number  I mean UBound($aArray) < 11

 

Edited November 18, 2015 by mLipok

[UEZ]

@guinness:

Please use this version (same idea):

#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
    Local $aa[UBound($a)], $i = 0, $k = $p - 1, $c, $cc = 0, $kk, $iUB = UBound($a)
    While $i <> $iUB
        If $a[$k] <> "x" Then
            $aa[$i] = $a[$k]
            $a[$k] = "x"
        EndIf
        $c = 0
        While True
            If $a[$k] <> "x" Then
                $c += 1
                $cc = 0
            Else
                $cc += 1
            EndIf
            If $c = $p Or $cc = $iUB Then ExitLoop
            $k += 1
            If $k = $iUB Then $k = 0
        WEnd
        $i += 1
    WEnd
    Return $aa
EndFunc

Scripting.Dictionary makes no sense here. Why I used it? Because my original idea was different!

Edited November 18, 2015 by UEZ

[UEZ]

Here a little benchmark of the posted scripts:

expandcollapse popup

#include <Array.au3>
Global $iValues = 12345
Global $aArray[$iValues], $i, $fTimer, $fTimer_End
For $i = 1 To $iValues
    $aArray[$i - 1] = $i
Next

$fTimer = TimerInit()
$aResult = Josephus_mLipok2($aArray, 3)
$fTimer_End = TimerDiff($fTimer)
ConsoleWrite("mLipok2: " & @TAB & Round($fTimer_End, 2) & " ms." & @CRLF)
;~ ConsoleWrite(_ArrayToString($aResult) & @CRLF & @CRLF & @CRLF)

If $iValues < 10 Then
    $fTimer = TimerInit()
    $aResult = Josephus_mikell($aArray, 3) ;works only up to 9
    $fTimer_End = TimerDiff($fTimer)
    ConsoleWrite("mikell: " & @TAB & @TAB & Round($fTimer_End, 2) & " ms." & @CRLF)
;~ ConsoleWrite(_ArrayToString($aResult) & @CRLF & @CRLF & @CRLF)
EndIf

$fTimer = TimerInit()
$aResult = Josephus_Chimp($aArray, 3)
$fTimer_End = TimerDiff($fTimer)
ConsoleWrite("Chimp: " & @TAB & @TAB & Round($fTimer_End, 2) & " ms." & @CRLF)
;~ ConsoleWrite(_ArrayToString($aResult) & @CRLF & @CRLF & @CRLF)

$fTimer = TimerInit()
$aResult = Josephus_UEZ($aArray, 3)
$fTimer_End = TimerDiff($fTimer)
ConsoleWrite("UEZ: " & @TAB & @TAB & Round($fTimer_End, 2) & " ms." & @CRLF)
;~ ConsoleWrite(_ArrayToString($aResult) & @CRLF & @CRLF & @CRLF)


Func Josephus_mLipok2($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   ;==>Josephus_mLipok2

Func Josephus_mikell($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   ;==>Josephus_mikell

Func Josephus_Chimp($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_Chimp

Func Josephus_UEZ($a, $p = 3)
    If $p = 1 Then Return $a
    Local $aa[UBound($a)], $i = 0, $k = $p - 1, $c, $cc = 0, $kk, $iUB = UBound($a)
    While $i <> $iUB
        If $a[$k] <> "x" Then
            $aa[$i] = $a[$k]
            $a[$k] = "x"
        EndIf
        $c = 0
        While True
            If $a[$k] <> "x" Then
                $c += 1
                $cc = 0
            Else
                $cc += 1
            EndIf
            If $c = $p Or $cc = $iUB Then ExitLoop
            $k += 1
            If $k = $iUB Then $k = 0
        WEnd
        $i += 1
    WEnd
    Return $aa
EndFunc   ;==>Josephus_UEZ

 

[kylomas]

I am sure all efforts will be in vain!  

(probably only one of you will understand)

Jos

my old, slow assed self is really curious as to what this means...

[guinness]

Thanks for the stats @UEZ. 

Based on the benchmark results and because 3 variations were submitted, I would say @mLipok won! I know @jchd's is quicker, but most posted AutoIt, so this is the common denominator. Well done to everyone who took part.

Let me know if you want more in the near future =)

[Jos]

my old, slow assed self is really curious as to what this means...

It is quite simple:  The first name in my passport is exactly the same as the name in the title....   

 

[mLipok]

Let me know if you want more in the near future =)

I think one per month would be good...... just for relax.

Edited November 19, 2015 by mLipok

[guinness]

I think one per month would be good...... just for relax.

I was thinking once or twice year is enough. Next one I will join in for sure.

[jchd]

Sorry but I was a bit busy at that moment and didn't have much time to wrap the SQL in a clean AutoIt script. Yet I found it interesting and worth noting that sometimes SQL code can reveal significantly more efficient that native script code.

[guinness]

Sorry but I was a bit busy at that moment and didn't have much time to wrap the SQL in a clean AutoIt script. Yet I found it interesting and worth noting that sometimes SQL code can reveal significantly more efficient that native script code.

You definitely won on execution time, just not everyone is familiar with SQL.

[jchd]

Right, that's why de-mystifying it is valuable, even if not for the masses. OTOH there are so many SQL programmers and lines of code everywhere (and for long) that it can't be considered exotic at any rate.