# Challenge: Solving Josephus problem

## Recommended Posts

##### Share on other sites

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 by mLipok

Signature beginning:
Please remember: "AutoIt"..... *  Wondering who uses AutoIt and what it can be used for ? * *
IE on Windows 11 * How to ask ChatGPT for AutoIt Codefor other useful stuff click the following button:

Spoiler

Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind.

My contribution to others projects or UDF based on  others projects: * _sql.au3 UDF  * POP3.au3 UDF *  RTF Printer - UDF * XML.au3 UDF * SMTP Mailer UDF * Dual Monitor resolution detection * * 2GUI on Dual Monitor System * _SciLexer.au3 UDF * SciTE - Lexer for console pane

Wiki: Expand your knowledge - AutoIt Wiki * Collection of User Defined Functions * How to use HelpFile * Good coding practices in AutoIt *

OpenOffice/LibreOffice/XLS Related: WriterDemo.au3 * XLS/MDB from scratch with ADOX

"Homo sum; humani nil a me alienum puto" - Publius Terentius Afer
"Program are meant to be read by humans and only incidentally for computers and execute" - Donald Knuth, "The Art of Computer Programming"
, be   and       \\//_.

Anticipating Errors :  "Any program that accepts data from a user must include code to validate that data before sending it to the data store. You cannot rely on the data store, ...., or even your programming language to notify you of problems. You must check every byte entered by your users, making sure that data is the correct type for its field and that required fields are not empty."

Signature last update: 2023-04-24

##### Share on other sites

@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 by UEZ

The own fart smells best!
Her 'sikim hıyar' diyene bir avuç tuz alıp koşma!
¯\_(ツ)_/¯  ٩(●̮̮̃•̃)۶ ٩(-̮̮̃-̃)۶ૐ

##### Share on other sites

Here a little benchmark of the posted scripts:

```#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```

The own fart smells best!
Her 'sikim hıyar' diyene bir avuç tuz alıp koşma!
¯\_(ツ)_/¯  ٩(●̮̮̃•̃)۶ ٩(-̮̮̃-̃)۶ૐ

##### Share on other sites

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

Forum Rules         Procedure for posting code

"I like pigs.  Dogs look up to us.  Cats look down on us.  Pigs treat us as equals."

- Sir Winston Churchill

##### Share on other sites

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 =)

##### Share on other sites

• Developers

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

Live for the present,
Dream of the future,
Learn from the past.

##### Share on other sites

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

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

Edited by mLipok

Signature beginning:
Please remember: "AutoIt"..... *  Wondering who uses AutoIt and what it can be used for ? * *
IE on Windows 11 * How to ask ChatGPT for AutoIt Codefor other useful stuff click the following button:

Spoiler

Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind.

My contribution to others projects or UDF based on  others projects: * _sql.au3 UDF  * POP3.au3 UDF *  RTF Printer - UDF * XML.au3 UDF * SMTP Mailer UDF * Dual Monitor resolution detection * * 2GUI on Dual Monitor System * _SciLexer.au3 UDF * SciTE - Lexer for console pane

Wiki: Expand your knowledge - AutoIt Wiki * Collection of User Defined Functions * How to use HelpFile * Good coding practices in AutoIt *

OpenOffice/LibreOffice/XLS Related: WriterDemo.au3 * XLS/MDB from scratch with ADOX

"Homo sum; humani nil a me alienum puto" - Publius Terentius Afer
"Program are meant to be read by humans and only incidentally for computers and execute" - Donald Knuth, "The Art of Computer Programming"
, be   and       \\//_.

Anticipating Errors :  "Any program that accepts data from a user must include code to validate that data before sending it to the data store. You cannot rely on the data store, ...., or even your programming language to notify you of problems. You must check every byte entered by your users, making sure that data is the correct type for its field and that required fields are not empty."

Signature last update: 2023-04-24

##### Share on other sites

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.

##### Share on other sites

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.

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

##### Share on other sites

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.

##### Share on other sites

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.

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

## Create an account

Register a new account

• ### Similar Content

• #### Mixed Base Conversion (coding challenge)

By Gianni,

• 5 replies
• 680 views
• #### Trim text in a file without storing the contents of anywhere 1 2

By TheDcoder,

• 22 replies
• 3,676 views
• #### Hey Everyone (please VOTE in Challenge)

By TheSaint,

• 3 replies
• 2,057 views
• #### Lottery - Challenge 1 2 3 4

By guinness,

• 74 replies
• 11,535 views
×

• Wiki

• Back

• #### Beta

• Git
• FAQ
×
• Create New...