Jump to content

Recommended Posts

Posted (edited)

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 by guinness
Fixed wrong comment style

UDF List:

  Reveal hidden contents

Updated: 22/04/2018

Posted (edited)

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

Edited by mLipok
typo

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

  Reveal hidden contents

Signature last update: 2023-04-24

Posted
  On 11/16/2015 at 9:49 PM, mLipok said:

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

Link fixed. Thanks

(It was because I was logged in)

UDF List:

  Reveal hidden contents

Updated: 22/04/2018

Posted

Question <Array.au3> can be used ?

 

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

  Reveal hidden contents

Signature last update: 2023-04-24

Posted (edited)
  On 11/16/2015 at 10:00 PM, TouchOdeath said:

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

Post here.

  On 11/16/2015 at 10:01 PM, mLipok said:

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

UDF List:

  Reveal hidden contents

Updated: 22/04/2018

Posted

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

 

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

  Reveal hidden contents

Signature last update: 2023-04-24

Posted

Clever solution @mLipok

UDF List:

  Reveal hidden contents

Updated: 22/04/2018

Posted

Working with non UDF solution.

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

  Reveal hidden contents

Signature last update: 2023-04-24

Posted (edited)

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

Please don't send me any personal message and ask for support! I will not reply!

Selection of finest graphical examples at Codepen.io

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

Posted

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

 

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

  Reveal hidden contents

Signature last update: 2023-04-24

Posted

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

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

  Reveal hidden contents

Signature last update: 2023-04-24

Posted (edited)
  On 11/16/2015 at 11:13 PM, mLipok said:

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

UDF List:

  Reveal hidden contents

Updated: 22/04/2018

Posted (edited)

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 by mikell
Posted

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

 

 

image.jpeg.9f1a974c98e9f77d824b358729b089b0.jpeg Chimp

small minds discuss people average minds discuss events great minds discuss ideas.... and use AutoIt....

Posted

Here's an SQLite version:

/*
  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).

  Reveal hidden contents

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
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)

Posted

Here my approach:

#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

 

Please don't send me any personal message and ask for support! I will not reply!

Selection of finest graphical examples at Codepen.io

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

Posted

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

 

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

  Reveal hidden contents

Signature last update: 2023-04-24

Posted (edited)
  On 11/18/2015 at 4:01 PM, Jos said:

(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 by guinness

UDF List:

  Reveal hidden contents

Updated: 22/04/2018

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...