Shaarad Posted May 13, 2011 Posted May 13, 2011 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 EndFuncJailed.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.
cembry90 Posted May 13, 2011 Posted May 13, 2011 (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 May 13, 2011 by cembry90 AutoIt Stuff: UDFs: {Grow}
MrMitchell Posted May 13, 2011 Posted May 13, 2011 Nice problem. Here's a short solution (done manually, and with only 100);73 winsAt the end of round 2 shouldn't #99 kill #1 then round 3 starts with #3?
cembry90 Posted May 13, 2011 Posted May 13, 2011 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}
martin Posted May 13, 2011 Posted May 13, 2011 (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 ) Edited May 13, 2011 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.
UEZ Posted May 13, 2011 Posted May 13, 2011 (edited) 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 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!¯\_(ツ)_/¯ ٩(●̮̮̃•̃)۶ ٩(-̮̮̃-̃)۶ૐ
Shaarad Posted May 14, 2011 Author Posted May 14, 2011 (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 ? 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 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.
Shaarad Posted May 14, 2011 Author Posted May 14, 2011 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. 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.
martin Posted May 14, 2011 Posted May 14, 2011 @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.
guinness Posted May 14, 2011 Posted May 14, 2011 Nice! Shame I missed this post last night. UDF List: _AdapterConnections() • _AlwaysRun() • _AppMon() • _AppMonEx() • _ArrayFilter/_ArrayReduce • _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 parsing • AutoIt Search • AutoIt3 Portable • AutoIt3WrapperToPragma • AutoItWinGetTitle()/AutoItWinSetTitle() • Coding • DirToHTML5 • FileInstallr • FileReadLastChars() • GeoIP database • GUI - Only Close Button • GUI Examples • GUICtrlDeleteImage() • GUICtrlGetBkColor() • GUICtrlGetStyle() • GUIEvents • GUIGetBkColor() • Int_Parse() & Int_TryParse() • IsISBN() • LockFile() • Mapping CtrlIDs • OOP in AutoIt • ParseHeadersToSciTE() • PasswordValid • PasteBin • Posts Per Day • PreExpand • Protect Globals • Queue() • Resource Update • ResourcesEx • SciTE Jump • Settings INI • SHELLHOOK • Shunting-Yard • Signature Creator • Stack() • Stopwatch() • StringAddLF()/StringStripLF() • StringEOLToCRLF() • VSCROLL • WM_COPYDATA • More Examples... Updated: 22/04/2018
Malkey Posted May 14, 2011 Posted May 14, 2011 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 Posted May 14, 2011 Posted May 14, 2011 (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 May 14, 2011 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!¯\_(ツ)_/¯ ٩(●̮̮̃•̃)۶ ٩(-̮̮̃-̃)۶ૐ
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now