A riddle....

[Shaarad]

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 ?

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 !

Thanks.

expandcollapse popup

#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

[MrMitchell]

What were your results with 100 or 200 prisoners?

[cembry90]

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 May 13, 2011 by cembry90

[MrMitchell]

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?

[cembry90]

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

No because 97 killed 99

[MrMitchell]

Ahh got it

[martin]

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 )

Edited May 13, 2011 by martin

[UEZ]

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

expandcollapse popup

;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 May 14, 2011 by UEZ

[Shaarad]

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 ?

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 May 14, 2011 by Shaarad

[Shaarad]

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.

[martin]

@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

[guinness]

Nice! Shame I missed this post last night.

[Malkey]

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

expandcollapse popup

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

[UEZ]

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 May 14, 2011 by UEZ