Sign in to follow this  
Followers 0
Shaarad

A riddle....

14 posts in this topic

So guys, I will first share the riddle with you. Here it goes.

There are 1000 prisoners in a prison. Only one of them is to be released from prison. So, the officers arrange all the 1000 prisoners in a circle, give 1st prisoner a gun. 1st prisoner shoots 2nd prisoner and hands the gun over to the 3rd prisoner. 3rd prisoner shoots 4th and hands the gun over to the 5th....this continues...999th prisoner shoots 1000th and hands the gun again to 1st. NOW 1st kills 3rd prisoner (as 2nd is already dead!) and gives the gun to 5th....

AND SO ON....

so the question is...after many such rounds, what is the lucky last prisoner guy number who is released from the prison ? :unsure:

Though it seems simple, it is not that much. So I tried to AutoIt ! :>

Here is the program which I made and it works well for small number of prisoners (eg. 100 or even 200) but it takes much time to find the answer for 1000 prisoners...(I am typing this and simultaneously the program is running...it has been 20 minutes but still I have not got the answer) ;)

So, guys please tell me a simple algorithm to shorten the time and find the answer quickly ! :D

Thanks.

#Include <File.au3>
Global $total,$startwith,$tocken,$readperistalsis,$solution
$solution="FALSE"
call ("startup")

func startup()
    $total=inputbox ("","Total number")
    $startwith=inputbox ("","Start with")
    call ("filemaker",$total,$startwith)
EndFunc

func filemaker($total,$startwith)
    $initialwrite=fileopen ("JAILED.txt",1)
    $writeno=1
    Do
        filewriteline ($initialwrite,"ALIVE" & @CRLF)
        $writeno=$writeno+1
    Until $writeno>$total
    FileClose ($initialwrite)
call ("inisolver")
EndFunc

func inisolver ()
    _FileWriteToLine ("JAILED.txt",$startwith+1,"DEAD",1)

    $readperistalsis=$startwith+2
    $tocken=0

call ("regularsolver")
EndFunc

Func regularsolver()
    Do
        $currentstat=filereadline ("JAILED.txt",$readperistalsis)
        if $currentstat="ALIVE" and $tocken =1 Then
                call ("killit")
            EndIf
        If $currentstat="ALIVE" and $tocken=0 Then
            $tocken=1
        EndIf
        
        if $readperistalsis=$total Then
            $readperistalsis=1
        Else
            $readperistalsis=$readperistalsis+1
        EndIf
        
        call ("checkforsolution")
    Until $solution="TRUE"
    
    if $solution="TRUE" Then
        Exit
    EndIf
    
EndFunc

Func killit()
    _filewritetoline ("JAILED.txt",$readperistalsis,"DEAD",1)
    $tocken=0
    call ("regularsolver")
EndFunc

func checkforsolution()
    $i=0
    $no=0
    Do
        $line=FilereadLine ("JAILED.txt",$i)
        if $line="ALIVE" Then
            $no=$no+1
        EndIf
        $i=$i+1
    until $i>$total
    if $no=1 Then
        msgbox (64,"","solved")
        $i2=1
        Do
        $line2=FilereadLine ("JAILED.txt",$i2)
        if $line2="ALIVE" Then
            $resultfile=fileopen ("RESULT.txt",1)
            filewrite ($resultfile,$i2)
            fileclose ($resultfile)
        EndIf
        $i2=$i2+1
    until $i2>$total
    Exit
    Else
        call ("regularsolver")
    EndIf
EndFunc

Jailed.au3


Common sense plays a role in the basics of understanding AutoIt... If you're lacking in that, do us all a favor, and step away from the computer.

Share this post


Link to post
Share on other sites



What were your results with 100 or 200 prisoners?

Share this post


Link to post
Share on other sites

#3 ·  Posted (edited)

Nice problem. Here's a short solution (done manually, and with only 100)

;1->2, 3->4, 5->6, 7->8, 9->10, 11->12, 13->14, 15->16, 17->18, 19->20, 21->22, 23->24, 25->26, 27->28, 29->30, 31->32, 33->34, 35->36, 37->38, 39->40, 41->42, 43->44, 45->46, 47->48, 49->50, 51->52, 53->54, 55->56, 57->58, 59->60, 61->62, 63->64, 65->66, 67->68, 69->70, 71->72, 73->74, 75->76, 77->78, 79->80, 81->82, 83->84, 85->86, 87->88, 89->90, 91->92, 93->94, 95->96, 97->98, 99->100
;1->3, 5->7, 9->11, 13->15, 17->19, 21->23, 25->27, 29->31, 33->35, 37->39, 41->43, 45->47, 49->51, 53->55, 57->59, 61->63, 65->67, 69->71, 73->75, 77->79, 81->83, 85->87, 89->91, 93->95, 97->99
;1->5, 9->13, 17->21, 25->29, 33->37, 41->45, 49->53, 57->61, 65->69, 73->77, 81->85, 89->93, 97->1
;9->17, 25->33, 41->49, 57->65, 73->81, 89->97
;9->25, 41->57, 73->89
;9->41, 73->9
;73 wins

I'll work on the script to do this later.. Gotta go to class. :-)

Edited by cembry90

AutoIt Stuff:

 

UDFs: {Grow}

Share this post


Link to post
Share on other sites

Nice problem. Here's a short solution (done manually, and with only 100)

;73 wins

At the end of round 2 shouldn't #99 kill #1 then round 3 starts with #3?

Share this post


Link to post
Share on other sites

At the end of round 2 shouldn't #99 kill #1 then round 3 starts with #3?

No because 97 killed 99

AutoIt Stuff:

 

UDFs: {Grow}

Share this post


Link to post
Share on other sites

Ahh got it

Share this post


Link to post
Share on other sites

#7 ·  Posted (edited)

Maybe this works

$start = 1000; or whatever number
$loops = 1
$step = 2
$first = 1
$standing = $start
$lastStanding = $start

While $standing > 1
    $standing = Ceiling($lastStanding / 2)

    If $standing = 1 Then ExitLoop
    $step = 2 ^ $loops

    If Mod($lastStanding, 2) = 1 Then;the last person shot the first
        If $first + $step <= $start Then $first = $first + $step
        $standing = $standing - 1;because the first was shot
    EndIf

    $lastStanding = $standing
    $loops += 1
Wend

ConsoleWrite("Last man standing is number " & $first & @CRLF)

EDIT:

There is no option in there to set the number of the person who fires first. But all you would need to do is shift the numbers round the circle by some amount so it wouldn't really affect the method. (Assuming the method works :unsure: )

Edited by martin

Serial port communications UDF Includes functions for binary transmission and reception.printing UDF Useful for graphs, forms, labels, reports etc.Add User Call Tips to SciTE for functions in UDFs not included with AutoIt and for your own scripts.Functions with parameters in OnEvent mode and for Hot Keys One function replaces GuiSetOnEvent, GuiCtrlSetOnEvent and HotKeySet.UDF IsConnected2 for notification of status of connected state of many urls or IPs, without slowing the script.

Share this post


Link to post
Share on other sites

#8 ·  Posted (edited)

Here my solution (I don't know whether it is working properly!):

;solution (brute force and formular) for the riddle here: http://www.autoitscript.com/forum/topic/128609-a-riddle/
;coded by UEZ 2011
#include <Array.au3>
#include <GUIConstantsEx.au3>
#include <WindowsConstants.au3>
$w = @DesktopWidth
$h = @DesktopHeight
Global $prisoners = "."
Do
    $prisoners = InputBox("Lucky Prisoner", "Please enter the amount of prisoners:", 100, " M4", -1, 130)
Until StringRegExp($prisoners, "[\D]+", 3)
$prisoners = Int($prisoners)
If Not $prisoners Then Exit
Sleep(100)
#region calculate lucky prisoner through a formular much faster
$formular = $prisoners - 2 ^ (Floor(LN($prisoners) / LN(2) - 1) + 1) + $prisoners -  2^(Floor(LN($prisoners) / LN(2) - 1) + 1) + 1
ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $formular = ' & $formular & @crlf & '>Error code: ' & @error & @crlf) ;### Debug Console

$formular2 = 2 * $prisoners - 2 ^ (Floor(LN($prisoners) / LN(2) - 1) + 2) + 1 ;formular is shorten from above
ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $formular2 = ' & $formular2 & @crlf & '>Error code: ' & @error & @crlf) ;### Debug Console

$formular3 = 2 * $prisoners - 2 ^ (Floor(Log($prisoners) / Log(2) - 1) + 2) + 1
ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $formular3 = ' & $formular3 & @crlf & '>Error code: ' & @error & @crlf) ;### Debug Console
#endregion

Const $round = 360 / $prisoners ;calculate angle for displaying the squares
Const $s = Min(Max(Ceiling(($h + $w) / ($prisoners)), 3), ($w + $h) / 16) ;squre size
Const $w2 = $w / 2 - $s / 2 ;screen center width
Const $h2 = $h / 2 - $s / 2 ;screen center height
Const $r1 = $w2 - 1 ;radius x
Const $r2 = $h2 - 1 ;radius y
Const $rad = ACos(-1) / 180 ; pi / 180
Const $hGUI = GUICreate ("Lucky Prisoner", $w, $h, 0 , 0,  $WS_POPUP)
GUISetBkColor(0, $hGUI)
Dim $aChkb[$prisoners][3]

$j = 0
$i = 0
Do ;fill up the array with prisoner's information -> control id|neighbor|alive or dead (1 is alive)
        $aChkb[$j][0] = GUICtrlCreateGraphic($w2 + Cos($i * $rad) * $r1, $h2 + Sin($i * $rad) * $r2, $s, $s) ;caculate square position
        GUICtrlSetBkColor(-1, 0xFFFFFF)
        GUICtrlSetGraphic(-1, $GUI_GR_RECT, 0, 0, $s, $s) ;print square to screen
        $aChkb[$j][1] = $j + 1
        $aChkb[$j][2] = 1
        $j += 1
        $i += $round ;next angle
Until $j = $prisoners
$aChkb[$j-1][1] = 0
GUICtrlSetBkColor($aChkb[0][0], 0x00FF00)
GUISetState()

MsgBox(0, "Information", "Prisoner in green is the first who starts out of " & $prisoners & " prisoners!")
$z = 0
$p = 0
While 1
    For $i = 0 To UBound($aChkb) - 1 ;prisoner shoots his neighbor
        If $aChkb[$i][2] Then
            GUICtrlSetBkColor($aChkb[$aChkb[$i][1]][0], 0x400000) ;dead prisoner is marked in dark red
            $aChkb[$aChkb[$i][1]][2] = 0 ;mark as dead
            $j = $i + 1
            While 1 ;find next neighbor
                If $j = UBound($aChkb) Then $j = 0
                If $j = $i  Or $aChkb[$j][2] = 1 Then ExitLoop
                $j += 1
            WEnd
            $aChkb[$i][1] = $j ;save next neighbor
            $z += 1
            $p = $i
        EndIf
    Next
    $i = 0
    While $aChkb[$i][2] = 0 ;find next neighbor over the array border starting from 0
        $i += 1
    WEnd
    $j = UBound($aChkb) - 1
    While $aChkb[$j][2] = 0 ;find next neighbor over the array border backwards from the end
        $j -= 1
    WEnd
    $aChkb[$j][1] = $i
    If $z = 1 Or $j <= $i Then ExitLoop ;if one prisoner left exit loop
WEnd

MsgBox(0, "Lucky Prisoner", "Prisoner " & $p + 1 & " is the lucky one!")

While 1
    $msg = GUIGetMsg()
    If $msg = $GUI_EVENT_CLOSE Then ExitLoop
WEnd
GUIDelete()
Exit

Func Max($a, $b)
    If $a = "" Or $b = "" Then Return SetError(1, 0, 0)
    If Not IsNumber($a) Or Not IsNumber($b) Then Return SetError(2, 0, 0)
    If $a < $b Then Return $b
    Return $a
EndFunc

Func Min($a, $b)
    If $a = "" Or $b = "" Then Return SetError(1, 0, 0)
    If Not IsNumber($a) Or Not IsNumber($b) Then Return SetError(2, 0, 0)
    If $a > $b Then Return $b
    Return $a
EndFunc

Func LN($x)
    Local Const  $e = 2.71828182845904523536
    If Not IsString($x) And $x > 0 Then
        If $x = 1 Then Return 0
        Return Log($x) / Log($e)
    EndIf
    Return 0
EndFunc

But not proven...

Br,

UEZ

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!
¯\_(ツ)_/¯

Share this post


Link to post
Share on other sites

#9 ·  Posted (edited)

With 100 prisoners and the 1st one firing the gun, I got the answer as 73.

With 200 prisoners and the 1st one firing the gun, I got the answer as 145.

Are those correct ?

:unsure:

This one is getting more and more complicated now ! :>

As we are concerned about the speed of calculations, and if we are unable to shorten the method, which type of program will run faster ? compiled .exe version of 'running .au3 script' ?

Edited by Shaarad

Common sense plays a role in the basics of understanding AutoIt... If you're lacking in that, do us all a favor, and step away from the computer.

Share this post


Link to post
Share on other sites

To UEZ,

Your program works as efficiently for 1000 prisoners as it works for 100 prisoners ! Great work

and that too with GUI !

Thanks.

My program is too slow but I will confirm the answer for 1000 prisoners and tell you all. If our answers match, then that's it. :unsure:


Common sense plays a role in the basics of understanding AutoIt... If you're lacking in that, do us all a favor, and step away from the computer.

Share this post


Link to post
Share on other sites

@UEZ,

that's amazing!

and it can be shortened a little which makes it even faster.

$formular = 2*$prisoners - 2 ^ (FLOOR(LN($prisoners) / LN(2) - 1) + 2) + 1


Serial port communications UDF Includes functions for binary transmission and reception.printing UDF Useful for graphs, forms, labels, reports etc.Add User Call Tips to SciTE for functions in UDFs not included with AutoIt and for your own scripts.Functions with parameters in OnEvent mode and for Hot Keys One function replaces GuiSetOnEvent, GuiCtrlSetOnEvent and HotKeySet.UDF IsConnected2 for notification of status of connected state of many urls or IPs, without slowing the script.

Share this post


Link to post
Share on other sites

Nice! Shame I missed this post last night.


_AdapterConnections()_AlwaysRun()_AppMon()_AppMonEx()_BinaryBin()_CheckMsgBox()_CmdLineRaw()_ContextMenu()_ConvertLHWebColor()/_ConvertSHWebColor()_DesktopDimensions()_DisplayPassword()_DotNet_Load()/_DotNet_Unload()_Fibonacci()_FileCompare()_FileCompareContents()_FileNameByHandle()_FilePrefix/SRE()_FindInFile()_GetBackgroundColor()/_SetBackgroundColor()_GetConrolID()_GetCtrlClass()_GetDirectoryFormat()_GetDriveMediaType()_GetFilename()/_GetFilenameExt()_GetHardwareID()_GetIP()_GetIP_Country()_GetOSLanguage()_GetSavedSource()_GetStringSize()_GetSystemPaths()_GetURLImage()_GIFImage()_GoogleWeather()_GUICtrlCreateGroup()_GUICtrlListBox_CreateArray()_GUICtrlListView_CreateArray()_GUICtrlListView_SaveCSV()_GUICtrlListView_SaveHTML()_GUICtrlListView_SaveTxt()_GUICtrlListView_SaveXML()_GUICtrlMenu_Recent()_GUICtrlMenu_SetItemImage()_GUICtrlTreeView_CreateArray()_GUIDisable()_GUIImageList_SetIconFromHandle()_GUIRegisterMsg()_GUISetIcon()_Icon_Clear()/_Icon_Set()_IdleTime()_InetGet()_InetGetGUI()_InetGetProgress()_IPDetails()_IsFileOlder()_IsGUID()_IsHex()_IsPalindrome()_IsRegKey()_IsStringRegExp()_IsSystemDrive()_IsUPX()_IsValidType()_IsWebColor()_Language()_Log()_MicrosoftInternetConnectivity()_MSDNDataType()_PathFull/GetRelative/Split()_PathSplitEx()_PrintFromArray()_ProgressSetMarquee()_ReDim()_RockPaperScissors()/_RockPaperScissorsLizardSpock()_ScrollingCredits_SelfDelete()_SelfRename()_SelfUpdate()_SendTo()_ShellAll()_ShellFile()_ShellFolder()_SingletonHWID()_SingletonPID()_Startup()_StringCompact()_StringIsValid()_StringRegExpMetaCharacters()_StringReplaceWholeWord()_StringStripChars()_Temperature()_TrialPeriod()_UKToUSDate()/_USToUKDate()_WinAPI_Create_CTL_CODE()_WinAPI_CreateGUID()_WMIDateStringToDate()/_DateToWMIDateString()Au3 script parsingAutoIt SearchAutoIt3 PortableAutoIt3WrapperToPragmaAutoItWinGetTitle()/AutoItWinSetTitle()CodingDirToHTML5FileInstallrFileReadLastChars()GeoIP databaseGUI - Only Close ButtonGUI ExamplesGUICtrlDeleteImage()GUICtrlGetBkColor()GUICtrlGetStyle()GUIEventsGUIGetBkColor()Int_Parse() & Int_TryParse()IsISBN()LockFile()Mapping CtrlIDsOOP in AutoItParseHeadersToSciTE()PasswordValidPasteBinPosts Per DayPreExpandProtect GlobalsQueue()Resource UpdateResourcesExSciTE JumpSettings INISHELLHOOKShunting-YardSignature CreatorStack()Stopwatch()StringAddLF()/StringStripLF()StringEOLToCRLF()VSCROLLWM_COPYDATAMore Examples...

Updated: 04/09/2015

Share this post


Link to post
Share on other sites

To manually check the results, I have added to martin's example so that cembry90's notation of Post #3 is returned.

That is "a->b, c->d," where "a" kills "b" then "a" hands gun to next person in line alive "c". Then, "c" kills the next person in line alive "d".

#include <Misc.au3>

Local $start = 100; or whatever number
Local $startOrig = $start, $Res
Local $loops = 1
Local $step = 2
Local $first = 1
Local $standing = $start
Local $lastStanding = $start

While $standing > 1
    $standing = Ceiling($lastStanding / 2)

    If $standing = 1 Then ExitLoop
    $step = 2 ^ $loops

    For $i = $first To $startOrig Step $step
        $Res &= $i & "->" & _Iif($i + $step / 2 > $startOrig, $first, $i + $step / 2) & ", "
        ConsoleWrite($i & "->" & _Iif($i + $step / 2 > $startOrig, $first, $i + $step / 2) & ", ")
    Next
    $Res &= @CRLF
    ConsoleWrite(@CRLF)

    If Mod($lastStanding, 2) = 1 Then;the last person shot the first
        If $first + $step <= $start Then $first = $first + $step
        $standing = $standing - 1;because the first was shot
    EndIf

    $lastStanding = $standing
    $loops += 1
WEnd

ConsoleWrite("Last man standing is number " & $first & @CRLF)
MsgBox(0, "Results", $Res & $first & " Wins" & @CRLF)

#cs
    ;1->2, 3->4, 5->6, 7->8, 9->10, 11->12, 13->14, 15->16, 17->18, 19->20, 21->22, 23->24, 25->26, 27->28, 29->30, 31->32, 33->34, 35->36, 37->38, 39->40, 41->42, 43->44, 45->46, 47->48, 49->50, 51->52, 53->54, 55->56, 57->58, 59->60, 61->62, 63->64, 65->66, 67->68, 69->70, 71->72, 73->74, 75->76, 77->78, 79->80, 81->82, 83->84, 85->86, 87->88, 89->90, 91->92, 93->94, 95->96, 97->98, 99->100
    ;1->3, 5->7, 9->11, 13->15, 17->19, 21->23, 25->27, 29->31, 33->35, 37->39, 41->43, 45->47, 49->51, 53->55, 57->59, 61->63, 65->67, 69->71, 73->75, 77->79, 81->83, 85->87, 89->91, 93->95, 97->99
    ;1->5, 9->13, 17->21, 25->29, 33->37, 41->45, 49->53, 57->61, 65->69, 73->77, 81->85, 89->93, 97->1
    ;9->17, 25->33, 41->49, 57->65, 73->81, 89->97
    ;9->25, 41->57, 73->89
    ;9->41, 73->9
    ;73 wins
#ce

@UEZ

Note: The FN() function is converting to a ,natural logarithm (base e).

So this works

$prisoners = 1000
ConsoleWrite((2 * $prisoners - 2 ^ (Floor(Log($prisoners) / Log(2) - 1) + 2) + 1) & @CRLF)

Share this post


Link to post
Share on other sites

#14 ·  Posted (edited)

The for next loop calculation is not precise enough for higher numbers! The result for 1000 prisoners was wrong due to rounding problems!

I changed the code! Now it should calculate also properly in brute force mode.

@martin: it was too late to shorten the function!

@Malkey: thanks for the hint but long time I did not work with log respectively ln functions. There are many ways to Rome...

Further my math knowledge is not the best....

Br,

UEZ

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!
¯\_(ツ)_/¯

Share this post


Link to post
Share on other sites

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
Sign in to follow this  
Followers 0