Long stairs
Long stairs is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
An evil wizard has trapped you in the stairwell of his castle. Your only hope of escape is to run up all 100 steps to reach the top, and you can run one step per second. Unfortunately the wizard uses magic to lengthen the staircase by five steps per second. The new steps are inserted randomly between existing steps, so if you're lucky some of them might be beneath you and not ahead of you.
Can you escape, or are you doomed to run up an ever-lengthening staircase forever?
Write a program to simulate your escape attempt. How are you doing after ten minutes? For every second between 600 and 609 seconds inclusive print the number of steps behind you and the number still ahead of you.
If you escaped, run 10,000 tests and print the average time taken and the average final length of the staircase.
11l
V secs_tot = 0
V steps_tot = 0
print(‘Seconds steps behind steps ahead’)
L(trial) 1..10000
V sbeh = 0
V slen = 100
V secs = 0
L sbeh < slen
sbeh++
L 5
I random:(slen) < sbeh
sbeh++
slen++
secs++
I trial == 1 & secs C 600..609
print(‘#. #. #.’.format(secs, sbeh, slen - sbeh))
secs_tot += secs
steps_tot += slen
print(‘Average secs taken: #.6’.format(secs_tot / 10000.0))
print(‘Average final length of staircase: #.6’.format(steps_tot / 10000.0))- Output:
Seconds steps behind steps ahead 600 1906 1194 601 1910 1195 602 1913 1197 603 1918 1197 604 1923 1197 605 1929 1196 606 1934 1196 607 1936 1199 608 1940 1200 609 1943 1202 Average secs taken: 2920.077500 Average final length of staircase: 14700.387500
AppleScript
use AppleScript version "2.5" -- OS X 10.11 (El Capitan) or later.
use framework "Foundation"
use framework "GameplayKit" -- For the random number generator (faster than AppleScript's).
on longStairs()
set output to {"Sample from first run:", "Seconds Steps behind Steps ahead"}
set RNG to current application's class "GKMersenneTwisterRandomSource"'s new()
set {runCount, totalTime, totalLength, firstRun, padding} to {10000, 0, 0, true, " "}
repeat runCount times
set t to 0
set stepsBehind to 0
set stepsAhead to 100
repeat until (stepsAhead = 0)
repeat 5 times
if ((RNG's nextIntWithUpperBound:(stepsBehind + stepsAhead)) > stepsBehind) then
set stepsAhead to stepsAhead + 1
else
set stepsBehind to stepsBehind + 1
end if
end repeat
set t to t + 1
set stepsBehind to stepsBehind + 1
set stepsAhead to stepsAhead - 1
if ((firstRun) and (t < 610) and (t > 599)) then ¬
set end of output to text -5 thru -1 of (padding & t) & ¬
text -13 thru -1 of (padding & stepsBehind) & ¬
text -15 thru -1 of (padding & stepsAhead)
end repeat
set totalTime to totalTime + t
set totalLength to totalLength + stepsBehind
set firstRun to false
end repeat
set {avTime, avLength} to {totalTime / runCount, totalLength / runCount}
set end of output to "Average time taken over " & intToText(runCount, ",") & " runs: " & ¬
(avTime div minutes) & " minutes " & (avTime mod minutes) & " seconds"
set end of output to "Average final staircase length: " & intToText(avLength div 1, ",") & ¬
"." & text 3 thru -1 of ((avLength mod 1) as text) & " steps"
return join(output, linefeed)
end longStairs
on intToText(int, separator)
set groups to {}
repeat while (int > 999)
set groups's beginning to ((1000 + (int mod 1000 as integer)) as text)'s text 2 thru 4
set int to int div 1000
end repeat
set groups's beginning to int
return join(groups, separator)
end intToText
on join(lst, delim)
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to delim
set txt to lst as text
set AppleScript's text item delimiters to astid
return txt
end join
longStairs()
- Output:
"Sample from first run:
Seconds Steps behind Steps ahead
600 2276 824
601 2278 827
602 2282 828
603 2287 828
604 2292 828
605 2296 829
606 2299 831
607 2304 831
608 2310 830
609 2315 830
Average time taken over 10,000 runs: 48 minutes 39.0985 seconds
Average final staircase length: 14,695.4925 steps"
AutoHotkey
result := "Sec steps behind steps ahead"
x := longStairs(609)
for i, s in x.4
result .= "`n" i+599 "`t" s "`t`t" x.2 - s
tests := 10000
loop % tests
{
x := longStairs()
totSteps += x.1
totSec += x.3
}
MsgBox, 262144, , % result .= "`n`nAfter " tests " tests:`nAverage time taken = " totSec/tests " Sec"
. "`nAverage Stair length = " totSteps/tests " steps"
return
longStairs(t:=0){
Stairs := [], last10Steps := [], s := 0
loop 100
Stairs[A_Index] := 0
loop
{
Stairs[++s] := "S" ; take a step forward
if (last10Steps.count()>=10)
last10Steps.RemoveAt(1)
last10Steps.push(s)
loop 5 ; add 5 steps to stairs
{
Random, stp, 1, % Stairs.Count()
Stairs.InsertAt(stp, "x")
s += s > stp ? 1 : 0
}
escT := s = Stairs.Count() ? A_Index : 0
if (A_Index = t || escT) ; reached time limit or Escaped
break
}
return [s, Stairs.Count(), escT, last10Steps]
}
- Output:
Sec steps behind steps ahead 600 1991 1154 601 1993 1152 602 1997 1148 603 2001 1144 604 2004 1141 605 2008 1137 606 2010 1135 607 2013 1132 608 2016 1129 609 2018 1127 After 10000 tests: Average time taken = 3063.260000 Sec Average Stair length = 15416.300000 steps
BASIC
BASIC256
steps_behind = 0
stairs_length = 100
seconds_tot = 0
steps_tot = 0
print "Seconds steps behind steps ahead"
for trial = 1 to 10000 #We'll have the runner try this 10000 times
steps_behind = 0 #runner starts at the bottom
seconds = 0 #reset time taken
stairs_length = 100 #Staircase has 100 steps
while steps_behind < stairs_length #if the runner hasn#t reached the top
steps_behind += 1 #go up one step
for j = 1 to 5 #The evil wizard conjures another five steps
if int(rand*stairs_length) < steps_behind then steps_behind += 1
#there#s a chance that a new step will be behind you
stairs_length += 1 #but either way the staircase is one step longer
next j
seconds += 1 #that all took one second
if trial = 1 and seconds > 599 and seconds < 610 then print seconds, steps_behind, stairs_length - steps_behind
#for the first attempt, see how the runner is doing after ten minutes
end while
seconds_tot += seconds #if the runner escaped, track the time taken and the length of the stairs
steps_tot += stairs_length
next trial
print "Average time taken: "; seconds_tot/10000; " seconds."
print "Average final staircase length: "; steps_tot/10000; " steps."
#if you noticed that last number is about 100*exp(5), that#s no coincidence
- Output:
Similar as FreeBASIC entry.
FreeBASIC
randomize timer
dim as uinteger steps_behind = 0, stairs_length = 100, seconds, j
dim as uinteger seconds_tot, steps_tot
print "Seconds", "steps behind", "steps ahead"
for trial as uinteger = 1 to 10000 'We'll have the runner try this 10000 times
steps_behind = 0 'runner starts at the bottom
seconds = 0 'reset time taken
stairs_length = 100 'Staircase has 100 steps
while steps_behind < stairs_length 'if the runner hasn't reached the top
steps_behind += 1 'go up one step
for j = 1 to 5 'The evil wizard conjures another five steps
if int(rnd*stairs_length) < steps_behind then steps_behind += 1
'there's a chance that a new step will be behind you
stairs_length += 1 'but either way the staircase is one step longer
next j
seconds += 1 'that all took one second
if trial = 1 and seconds >599 and seconds < 610 then print seconds, steps_behind, stairs_length - steps_behind
'for the first attempt, see how the runner is doing after ten minutes
wend
seconds_tot += seconds 'if the runner escaped, track the time taken and the length of the stairs
steps_tot += stairs_length
next trial
print "Average time taken: ";seconds_tot/10000; " seconds."
print "Average final staircase length: ";steps_tot/10000; " steps."
'if you noticed that last number is about 100*exp(5), that's no coincidence
- Output:
Seconds steps behind steps ahead 600 2032 1068 601 2038 1067 602 2042 1068 603 2045 1070 604 2048 1072 605 2053 1072 606 2055 1075 607 2060 1075 608 2064 1076 609 2068 1077 Average time taken: 2921.9457 seconds. Average final staircase length: 14709.7285 steps.
Gambas
Public Sub Main()
Randomize
Dim steps_behind As Integer = 0, stairs_length As Integer = 100, seconds As Integer
Dim seconds_tot As Integer, steps_tot As Integer, j As Integer
Print "Seconds", "steps behind", "steps ahead"
For trial As Integer = 1 To 10000 'We'll have the runner try this 10000 times
steps_behind = 0 'runner starts at the bottom
seconds = 0 'reset time taken
stairs_length = 100 'Staircase has 100 steps
While steps_behind < stairs_length 'if the runner hasn't reached the top
steps_behind += 1 'go up one step
For j = 1 To 5 'The evil wizard conjures another five steps
If Int(Rnd * stairs_length) < steps_behind Then steps_behind += 1
'there's a chance that a new step will be behind you
stairs_length += 1 'but either way the staircase is one step longer
Next
seconds += 1 'that all took one second
If trial = 1 And seconds > 599 And seconds < 610 Then Print seconds, steps_behind, Chr$(9); stairs_length - steps_behind
'for the first attempt, see how the runner is doing after ten minutes
Wend
seconds_tot += seconds 'if the runner escaped, track the time taken and the length of the stairs
steps_tot += stairs_length
Next
Print "Average time taken: "; seconds_tot / 10000; " seconds."
Print "Average final staircase length: "; steps_tot / 10000; " steps."
'if you noticed that last number is about 100*exp(5), that's no coincidence
End
- Output:
Similar as FreeBASIC entry.
GW-BASIC
10 RANDOMIZE TIMER
20 TIMET = 0 : STEPST = 0
30 FOR TRIAL = 1 TO 10000
40 TIME = 0
50 SBEH = 0
60 SLEN = 100
70 SBEH = SBEH + 1
80 IF SBEH >= SLEN THEN GOTO 160
90 FOR WIZ = 1 TO 5
100 IF INT(RND*SLEN)<SBEH THEN SBEH = SBEH + 1
110 SLEN = SLEN + 1
120 NEXT WIZ
130 TIME = TIME + 1
140 IF TRIAL = 1 AND 599<TIME AND TIME <610 THEN PRINT TIME, SBEH, SLEN-SBEH
150 GOTO 70
160 TIMET = TIMET+TIME+1
170 STEPST = STEPST + SLEN
180 NEXT TRIAL
190 PRINT TIMET/10000
200 PRINT STEPST/10000
PureBasic
OpenConsole()
Define.i steps_behind = 0, stairs_length = 100, seconds, j
Define.i seconds_tot, steps_tot
PrintN("Seconds" + #TAB$ + "steps behind" + #TAB$ + "steps ahead")
For trial.i = 1 To 10000 ;We'll have the runner try this 10000 times
steps_behind = 0 ;runner starts at the bottom
seconds = 0 ;reset time taken
stairs_length = 100 ;Staircase has 100 steps
While steps_behind < stairs_length ;if the runner hasn;t reached the top
steps_behind + 1 ;go up one step
For j = 1 To 5 ;The evil wizard conjures another five steps
If Int(Random(1) * stairs_length) < steps_behind:
steps_behind + 1
EndIf
;there;s a chance that a new step will be behind you
stairs_length + 1 ;but either way the staircase is one step longer
Next j
seconds + 1 ;that all took one second
If (trial = 1) And (seconds > 599) And (seconds < 610):
PrintN(Str(seconds) + #TAB$ + #TAB$ + Str(steps_behind) + #TAB$ + Str(stairs_length - steps_behind))
;for the first attempt, see how the runner is doing after ten minutes
EndIf
Wend
seconds_tot + seconds ;if the runner escaped, track the time taken and the length of the stairs
steps_tot + stairs_length
Next trial
PrintN("Average time taken: " + Str(seconds_tot/10000) + " seconds.")
PrintN("Average final staircase length: " + Str(steps_tot/10000) + " steps.")
;if you noticed that last number is about 100*exp(5), that;s no coincidence
PrintN(#CRLF$ + "Press ENTER to exit"): Input()
CloseConsole()
- Output:
Similar as FreeBASIC entry.
QBasic
RANDOMIZE TIMER : REM RANDOMIZE for True BASIC
stepsbehind = 0
stairslength = 100
PRINT "Seconds", "steps behind", "steps ahead"
FOR trial = 1 TO 10000
stepsbehind = 0
seconds = 0
stairslength = 100
DO WHILE stepsbehind < stairslength
stepsbehind = stepsbehind + 1
FOR j = 1 TO 5
IF INT(RND * stairslength) < stepsbehind THEN stepsbehind = stepsbehind + 1
stairslength = stairslength + 1
NEXT j
seconds = seconds + 1
IF trial = 1 AND seconds > 599 AND seconds < 610 THEN PRINT seconds, stepsbehind, stairslength - stepsbehind
LOOP
secondstot = secondstot + seconds
stepstot = stepstot + stairslength
NEXT trial
PRINT "Average time taken: "; secondstot / 10000; " seconds."
PRINT "Average final staircase length: "; stepstot / 10000; " steps."
END
True BASIC
RANDOMIZE ! RANDOMIZE TIME for QBasic
LET stepsbehind = 0
LET stairslength = 100
PRINT "Seconds", "steps behind", "steps ahead"
FOR trial = 1 TO 10000
LET stepsbehind = 0
LET seconds = 0
LET stairslength = 100
DO WHILE stepsbehind < stairslength
LET stepsbehind = stepsbehind + 1
FOR j = 1 TO 5
IF INT(RND * stairslength) < stepsbehind THEN LET stepsbehind = stepsbehind + 1
LET stairslength = stairslength + 1
NEXT j
LET seconds = seconds + 1
IF trial = 1 AND seconds > 599 AND seconds < 610 THEN PRINT seconds, stepsbehind, stairslength - stepsbehind
LOOP
LET secondstot = secondstot + seconds
LET stepstot = stepstot + stairslength
NEXT trial
PRINT "Average time taken: "; secondstot / 10000; " seconds."
PRINT "Average final staircase length: "; stepstot / 10000; " steps."
END
VBScript
Option Explicit
Randomize Timer
Function pad(s,n)
If n<0 Then pad= right(space(-n) & s ,-n) Else pad= left(s& space(n),n) End If
End Function
Sub print(s)
On Error Resume Next
WScript.stdout.WriteLine (s)
If err= &h80070006& Then WScript.Echo " Please run this script with CScript": WScript.quit
End Sub
Function Rounds(maxsecs,wiz,a)
Dim mystep,maxstep,toend,j,i,x,d
If IsArray(a) Then d=True: print "seconds behind pending"
maxstep=100
For j=1 To maxsecs
For i=1 To wiz
If Int(Rnd*maxstep)<=mystep Then mystep=mystep+1
maxstep=maxstep+1
Next
mystep=mystep+1
If mystep=maxstep Then Rounds=Array(j,maxstep) :Exit Function
If d Then
If j>=a(0) And j<=a(1) Then print pad(j,-7) & pad (mystep,-7) & pad (maxstep-mystep,-8)
End If
Next
Rounds=Array(maxsecs,maxstep)
End Function
Dim n,r,a,sumt,sums,ntests,t,maxsecs
ntests=10000
maxsecs=7000
t=timer
a=Array(600,609)
For n=1 To ntests
r=Rounds(maxsecs,5,a)
If r(0)<>maxsecs Then
sumt=sumt+r(0)
sums=sums+r(1)
End if
a=""
Next
print vbcrlf & "Done " & ntests & " tests in " & Timer-t & " seconds"
print "escaped in " & sumt/ntests & " seconds with " & sums/ntests & " stairs"
- Output:
seconds behind pending
600 2123 977
601 2126 979
602 2130 980
603 2134 981
604 2137 983
605 2141 984
606 2145 985
607 2151 984
608 2155 985
609 2159 986
Done 10000 tests in 51.30469 seconds
escaped in 2923.1174 seconds with 14715.587 stairs
Yabasic
steps_behind = 0
stairs_length = 100
print "Seconds", chr$(9), "steps behind", chr$(9), "steps ahead"
for trial = 1 to 10000 //We'll have the runner try this 10000 times
steps_behind = 0 //runner starts at the bottom
seconds = 0 //reset time taken
stairs_length = 100 //Staircase has 100 steps
while steps_behind < stairs_length //if the runner hasn//t reached the top
steps_behind = steps_behind + 1 //go up one step
for j = 1 to 5 //The evil wizard conjures another five steps
if int(ran(1)*stairs_length) < steps_behind steps_behind = steps_behind + 1
//there//s a chance that a new step will be behind you
stairs_length = stairs_length + 1 //but either way the staircase is one step longer
next j
seconds = seconds + 1 //that all took one second
if trial = 1 and seconds > 599 and seconds < 610 print seconds, chr$(9), steps_behind, chr$(9), chr$(9), stairs_length - steps_behind
//for the first attempt, see how the runner is doing after ten minutes
wend
seconds_tot = seconds_tot + seconds //if the runner escaped, track the time taken and the length of the stairs
steps_tot = steps_tot + stairs_length
next trial
print "Average time taken: ", seconds_tot/10000, " seconds."
print "Average final staircase length: ", steps_tot/10000, " steps."
//if you noticed that last number is about 100*exp(5), that//s no coincidence
- Output:
Similar as FreeBASIC entry.
C
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main(void) {
int trial, secs_tot=0, steps_tot=0; //keep track of time and steps over all the trials
int sbeh, slen, wiz, secs; //all the variables related to an individual trial
time_t t;
srand((unsigned) time(&t)); //random number seed
printf( "Seconds steps behind steps ahead\n" );
for( trial=1;trial<=10000;trial++ ) { //10000 attempts for the runner
sbeh = 0; slen = 100; secs = 0; // initialise this trial
while(sbeh<slen) { //as long as the runner is still on the stairs
sbeh+=1; //runner climbs a step
for(wiz=1;wiz<=5;wiz++) { //evil wizard conjures five new steps
if(rand()%slen < sbeh)
sbeh+=1; //maybe a new step is behind us
slen+=1; //either way, the staircase is longer
}
secs+=1; //one second has passed
if(trial==1&&599<secs&&secs<610)
printf("%d %d %d\n", secs, sbeh, slen-sbeh );
}
secs_tot+=secs;
steps_tot+=slen;
}
printf( "Average secs taken: %f\n", secs_tot/10000.0 );
printf( "Average final length of staircase: %f\n", steps_tot/10000.0 );
return 0;
}
- Output:
Seconds steps behind steps ahead 600 2147 953 601 2151 954 602 2156 954 603 2160 955 604 2166 954 605 2169 956 606 2174 956 607 2180 955 608 2184 956 609 2188 957 Average secs taken: 2921.493200 Average final length of staircase: 14707.466000
Dart
import 'dart:math';
void main() {
int secsTot = 0,
stepsTot = 0; // keep track of time and steps over all the trials
Random rand = new Random();
print("Seconds steps behind steps ahead");
for (int trial = 1; trial <= 10000; trial++) {
// 10000 attempts for the runner
int sbeh = 0, slen = 100, secs = 0; // initialise this trial
while (sbeh < slen) {
// as long as the runner is still on the stairs
sbeh += 1; // runner climbs a step
for (int wiz = 1; wiz <= 5; wiz++) {
// evil wizard conjures five new steps
if (rand.nextInt(slen) < sbeh)
sbeh += 1; // maybe a new step is behind us
slen += 1; // either way, the staircase is longer
}
secs += 1; // one second has passed
if (trial == 1 && 599 < secs && secs < 610)
print("$secs $sbeh ${slen - sbeh}");
}
secsTot += secs;
stepsTot += slen;
}
print("Average secs taken: ${secsTot / 10000.0}");
print("Average final length of staircase: ${stepsTot / 10000.0}");
}
- Output:
Similar as C entry.
Factor
USING: combinators.random io kernel math math.order prettyprint ;
: position ( -- n ) 0 ;
: stairs ( -- n ) 100 ;
: new ( -- m n ) position stairs ;
: incd ( m n -- o p ) swap 1 + swap ;
: seconds ( m -- n ) 100 - 5 / ;
: window? ( n -- ? ) seconds 600 609 between? ;
: zap ( m n -- o p ) 2dup / [ incd ] whenp 1 + ;
: barrage ( m n -- o p ) 5 [ zap ] times ;
: .n ( n -- ) pprint 7 [ bl ] times ;
: .stats ( m n -- ) dup seconds .n over .n swap - .n nl ;
: .header ( -- ) "Seconds behind ahead" print ;
: ?.status ( m n -- o p ) dup window? [ 2dup .stats ] when ;
: tick ( m n -- o p ) incd barrage ;
: demo ( m n -- o p ) tick ?.status ;
: sim-with ( q -- n ) new rot [ 2dup < ] swap while drop ; inline
: first ( -- n ) [ demo ] sim-with ;
: sim ( -- n ) [ tick ] sim-with ;
: sims ( -- n ) 0 first + 9999 [ sim + ] times ;
: steps ( m -- n ) "Avg. steps: " write 10000 / dup . ;
: time ( n -- ) "Avg. seconds: " write seconds . ;
: main ( -- ) .header sims nl steps time ;
main
- Output:
Seconds behind ahead 600 2067 1033 601 2073 1032 602 2078 1032 603 2082 1033 604 2087 1033 605 2091 1034 606 2096 1034 607 2099 1036 608 2103 1037 609 2108 1037 Avg. steps: 14731+23/200 Avg. seconds: 2926+223/1000
And for fun, a version without stack effects.
USING: combinators.random effects.parser io kernel math
math.order parser prettyprint stack-checker words ;
<< SYNTAX: .: [ scan-new-word parse-definition dup infer ]
with-definition define-declared ; >>
.: position 0 ;
.: stairs 100 ;
.: new position stairs ;
.: incd swap 1 + swap ;
.: seconds 100 - 5 / ;
.: window? seconds 600 609 between? ;
.: zap 2dup / [ incd ] whenp 1 + ;
.: barrage 5 [ zap ] times ;
.: .n pprint 7 [ bl ] times ;
.: .stats dup seconds .n over .n swap - .n nl ;
.: .header "Seconds behind ahead" print ;
.: ?.status dup window? [ 2dup .stats ] when ;
.: tick incd barrage ;
.: demo tick ?.status ;
.: first new [ 2dup < ] [ demo ] while drop ;
.: sim new [ 2dup < ] [ tick ] while drop ;
.: sims 0 first + 9999 [ sim + ] times ;
.: steps "Avg. steps: " write 10000 / dup . ;
.: time "Avg. seconds: " write seconds . ;
.: main .header sims nl steps time ;
main
Fermat
time_tot:=0; {we'll keep track of the total time and steps across all the trials}
steps_tot:=0;
!!('Seconds ','Steps behind ','Steps ahead');
for trial = 1 to 10 do
s_behind:=0; {initialise staircase and runner for this trial}
stair_len:=100;
time:=0;
while s_behind < stair_len do
s_behind:=s_behind + 1;
for wiz = 1 to 5 do
stair_len:=stair_len + 1; {evil wizard creates a step} {(mwaahahaha)}
if (Rand|stair_len) < s_behind then
s_behind:=s_behind + 1;
fi
od;
time:=time+1; {another second has passed}
if trial = 1 and 599<time and time<610 then
!!(time, ' ', s_behind, ' ',stair_len-s_behind)
fi;
od;
time_tot:=time_tot+time;
steps_tot:=steps_tot+stair_len;
od;
!!(time_tot/10000);
!!(steps_tot/10000);- Output:
Seconds Steps behind Steps ahead
600 2125 975 601 2129 976 602 2132 978 603 2136 979 604 2142 978 605 2146 979 606 2151 979 607 2156 979 608 2162 978 609 2166 979 3697083 / 1250 3722083 / 250
Go
package main
import (
"fmt"
"math/rand"
"time"
)
func main() {
rand.Seed(time.Now().UnixNano())
totalSecs := 0
totalSteps := 0
fmt.Println("Seconds steps behind steps ahead")
fmt.Println("------- ------------ -----------")
for trial := 1; trial < 10000; trial++ {
sbeh := 0
slen := 100
secs := 0
for sbeh < slen {
sbeh++
for wiz := 1; wiz < 6; wiz++ {
if rand.Intn(slen) < sbeh {
sbeh++
}
slen++
}
secs++
if trial == 1 && secs > 599 && secs < 610 {
fmt.Printf("%d %d %d\n", secs, sbeh, slen-sbeh)
}
}
totalSecs += secs
totalSteps += slen
}
fmt.Println("\nAverage secs taken:", float64(totalSecs)/10000)
fmt.Println("Average final length of staircase:", float64(totalSteps)/10000)
}
- Output:
Sample run:
Seconds steps behind steps ahead ------- ------------ ----------- 600 2138 962 601 2143 962 602 2148 962 603 2153 962 604 2159 961 605 2163 962 606 2167 963 607 2172 963 608 2177 963 609 2183 962 Average secs taken: 2917.9058 Average final length of staircase: 14689.519
J
stairsim=:{{
t=. 0 NB. fifths of a second
echo ;_8 _16 _20{.each 'seconds';'steps to top';'steps from bottom'
for_trial. i.1e4 do.
loc=. {.'min max'=. 0 100
while. loc < max do.
if. 0=5|t=.t+1 do.
loc=. loc+1
if. 0=trial do.
if. 1=2999 3046 I.t do.
echo 8 16 20":(t%5),(max-loc),(loc-min)
end.
end.
end.
ins=. min+?max-min
if. ins < loc do. min=. min-1 else. max=. max+1 end.
end.
end.
echo 'Average steps taken: ',":t%5e4
echo 'Average length of staircase: ',":100+t%1e4
}}
Example run:
stairsim''
seconds steps to top steps from bottom
600 1142 1957
601 1142 1962
602 1141 1968
603 1141 1973
604 1142 1977
605 1143 1981
606 1143 1986
607 1143 1991
608 1144 1995
609 1144 2000
Average steps taken: 3026.43
Average length of staircase: 15232.2
jq
Works with gojq, the Go implementation of jq
Neither the C nor the Go-based implmentations of jq currently have a built-in PRNG, so for the present task /dev/urandom is used as a source of entropy by invoking jq as follows:
cat /dev/urandom | tr -cd '0-9' | fold -w 1 | jq -nrf long-stairs.jq
where long-stairs.jq contains the jq program shown below. For simplicity and since the intermediate output has the character of a probe, the program uses `debug` statements to show the intermediate results.
# 0 <= output < $n
def rand($n):
def ntimes(f): range(0; .) | f;
# input: an array of length ($n|tostring|length)
def r:
. as $in
| (join("") | tonumber) as $m
| if $m < $n then $m
else $in[1:] + [input] | r
end;
[$n | tostring | length | ntimes(input)] | r;
# $n specifies the number of iterations
def task($n):
(reduce range(1; $n + 1) as $trial (null;
.sbeh = 0
| .slen = 100
| .secs = 0
| until (.sbeh >= .slen;
.sbeh += 1
| reduce range(1;6) as $wiz (.;
if (rand( .slen) < .sbeh) then .sbeh += 1 else . end
| .slen += 1 )
| .secs += 1
| if ($trial == 1 and .secs > 599 and .secs < 610)
then ([.secs, .sbeh, .slen - .sbeh] | debug) as $debug | .
else .
end )
| .totalSecs += .secs
| .totalSteps += .slen ) ) ;
"Seconds steps behind steps ahead",
"------- ------------ -----------",
(1E4 as $n
| task($n)
| "\nAverage secs taken over \($n) trials: \(.totalSecs/$n)",
"Average final length of staircase: \(.totalSteps/$n)"
)- Output:
Seconds steps behind steps ahead ------- ------------ ----------- ["DEBUG:",[600,1916,1184]] ["DEBUG:",[601,1919,1186]] ["DEBUG:",[602,1920,1190]] ["DEBUG:",[603,1924,1191]] ["DEBUG:",[604,1926,1194]] ["DEBUG:",[605,1931,1194]] ["DEBUG:",[606,1934,1196]] ["DEBUG:",[607,1938,1197]] ["DEBUG:",[608,1942,1198]] ["DEBUG:",[609,1945,1200]] Average secs taken over 10000 trials: 3211.962 Average final length of staircase: 16159.81
Julia
""" https://rosettacode.org/wiki/Long_stairs """
using Statistics
struct LongStairs
startstep::Int
startlength::Int
climbersteps::Int
addsteps::Int
end
Base.length(LongStairs) = typemax(Int)
Base.eltype(ls::LongStairs) = Vector{Int}
function Base.iterate(s::LongStairs, param = (s.startstep, s.startlength))
pos, len = param
pos += s.climbersteps
pos += sum(pos .> rand(1:len, s.addsteps))
len += s.addsteps
return [pos, len], (pos, len)
end
ls = LongStairs(1, 100, 1, 5)
println("Seconds Behind Ahead\n----------------------")
for (secs, (pos, len)) in enumerate(collect(Iterators.take(ls, 609))[600:609])
println(secs + 599, " ", pos, " ", len - pos)
end
println("Ten thousand trials to top:")
times, heights = Int[], Int[]
for trial in 1:10_000
trialstairs = LongStairs(1, 100, 1, 5)
for (sec, (step, height)) in Iterators.enumerate(trialstairs)
if step >= height
push!(times, sec)
push!(heights, height)
break
end
end
end
@show mean(times), mean(heights)
- Output:
Seconds Behind Ahead ---------------------- 601 1938 1167 602 1944 1166 603 1948 1167 604 1952 1168 605 1956 1169 606 1959 1171 607 1963 1172 608 1967 1173 609 1971 1174 Ten thousand trials to top: (mean(times), mean(heights)) = (2927.0853, 14735.4265)
Nim
import std/[random, strformat]
randomize()
proc simulate(verbose: bool): (int, int) =
if verbose:
echo "Seconds Steps behind Steps ahead"
var curr = 1 # Number of current step.
var last = 100 # Number of last step.
var t = 0
while true:
inc t
inc curr
if curr > last:
return (t, last) # Escaped!
# Add new steps.
for i in 1..5:
let n = rand(1..last)
if n < curr: inc curr # Behind current step.
inc last
if verbose and t in 600..609:
echo &"{t:^7} {curr:^12} {last - curr:^12}"
if t == 609: return # This part is terminated.
# First part of the task.
discard simulate(true)
echo()
# Second part of the task.
var tSum, stepSum = 0
for _ in 1..10_000:
let (t, n) = simulate(false)
tSum += t
stepSum += n
echo &"Average seconds taken: {tSum / 10_000}"
echo &"Average final length of staircase: {stepSum / 10_000}"
- Output:
Seconds Steps behind Steps ahead 600 2031 1069 601 2034 1071 602 2038 1072 603 2043 1072 604 2046 1074 605 2050 1075 606 2055 1075 607 2061 1074 608 2066 1074 609 2070 1075 Average seconds taken: 2924.1551 Average final length of staircase: 14715.7755
Pascal
Free Pascal
Trying to calculate results of multiple random rounds.Now a partial step forward 1/CntOfSpellStairs for every spell stair.
Now results are much closer.
program WizardStaircase;
const
StartStairLength = 100;
StairsPerSpell = 5;
rounds = 10000;
procedure OutActual(trials,behind,infront:longword);
begin
writeln(trials:5,infront+behind:12,behind:10,inFront:9);
end;
function OneRun(StairsPerSpell:Cardinal;WithOutput:boolean):longword;
var
inFront,behind,total,i,trials: Cardinal;
begin
trials := 0;
total := StartStairLength;
inFront := total;
behind := 0;
repeat
inc(trials);
inc(behind);
dec(infront);
//spell
i := StairsPerSpell;
repeat
if random(total) < behind then
inc(behind)
else
inc(infront);
inc(total);
dec(i);
until i=0;
if WithOutput then
begin
if (trials <= 609)AND(trials>=600) then
OutActual(trials,behind,infront);
end;
until infront = 0;
OneRun := total;
end;
procedure CheckDouble(StairsPerSpell:Cardinal);
var
behind,infront,relpos,total,One,relSpell : double;
i : LongInt;
begin
write(StairsPerSpell:3);
One := 1.0;
behind := 0.0;
inFront := StartStairLength;
total := StartStairLength;
relSpell := One/StairsPerSpell;
repeat
i := StairsPerSpell;
//doing a partial move per one stair per spell
repeat
relpos := (behind+relSpell)/total;
behind := behind + relpos +relSpell;
inFront := inFront+(One-relpos)-relSpell;
total := total+One;
dec(i);
until i= 0;
until infront < One;
writeln((total-StartStairLength)/StairsPerSpell:10:0,total:14:0);
end;
var
i,
mySpell,
attempt,
minStairs,
maxStairs,
total : longword;
begin
randomize;
writeln('Seconds steps total behind ahead');
total := OneRun(StairsPerSpell,true);
writeln(' average stairs needed steps minimum maximum');
for mySpell := 1 to 7 do
begin
write(mySpell:3,' ');
total := 0;
minStairs := High(minStairs);
maxStairs := low(maxStairs);
For i := rounds-1 downto 0 do
begin
attempt:= OneRun(mySpell,false);
if minStairs>attempt then
minstairs := attempt;
if maxStairs<attempt then
maxstairs := attempt;
inc(total,attempt);
end;
writeln((total-StartStairLength)/rounds/mySpell:12:3,total/rounds:14:3,minStairs:9,maxStairs:10);
end;
writeln;
writeln(' calculated ');
For i := 1 to 10 do
CheckDouble(i);
end.
- @ TIO.RUN:
Seconds steps total behind ahead
600 3100 2260 840
601 3105 2264 841
602 3110 2269 841
603 3115 2275 840
604 3120 2281 839
605 3125 2285 840
606 3130 2291 839
607 3135 2295 840
608 3140 2300 840
609 3145 2302 843
average stairs needed steps minimum maximum
1 271.090 271.100 239 313
2 367.570 735.150 540 954
3 663.998 1992.003 1234 2911
4 1353.416 5413.674 2748 8980
5 2933.418 14667.099 6715 27210
6 6648.557 39891.354 18394 80050
7 15550.874 108856.130 42380 218892
calculated
1 170 270
2 317 734
3 633 1999
4 1333 5432
5 2933 14765
6 6673 40138
7 15573 109111
8 37063 296604
9 89573 806257
10 219154 2191640
Real time: 55.269 s
Phix
with javascript_semantics -- (nb expect blank screen for ~30s) integer total_seconds = 0, total_steps = 0 printf(1,"time behind ahead\n") printf(1,"---- ------ -----\n") for trial=1 to 10_000 do integer stairs_length = 100, steps_behind = 0, seconds = 0 while steps_behind < stairs_length do steps_behind += 1 for wizard=1 to 5 do steps_behind += (rnd()*stairs_length < steps_behind) stairs_length += 1 end for seconds += 1 if trial=1 and seconds>=600 and seconds<=609 then printf(1,"%4d %7d %6d\n", {seconds, steps_behind, stairs_length-steps_behind}) end if end while total_seconds += seconds total_steps += stairs_length if trial=1 then printf(1,"\n") end if end for printf(1,"Average seconds: %f, average steps: %f\n", {total_seconds/10000,total_steps/10000})
- Output:
time behind ahead ---- ------ ----- 600 1978 1122 601 1980 1125 602 1986 1124 603 1990 1125 604 1995 1125 605 1999 1126 606 2002 1128 607 2004 1131 608 2008 1132 609 2012 1133 Average seconds: 2913.609300, average steps: 14668.046500
Perl
#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Long_stairs
use warnings;
my $sumseconds = my $sumsizes = my $runs = 0;
for ( 1 .. 1e4 )
{
$runs++;
my $behind = 0;
my $ahead = 100;
my $seconds = 0;
while( $ahead > 0 )
{
rand() <= ($ahead / ($behind + $ahead)) ? $ahead++ : $behind++ for 1 .. 5;
$behind++; # one step up
$ahead--;
$seconds++;
$_ == 1 and 600 <= $seconds <= 609 and
print "step $seconds: $behind behind, $ahead ahead\n";
}
$sumsizes += $behind;
$sumseconds += $seconds;
}
printf "\naverage stair length %d average seconds %d\n",
$sumsizes / $runs, $sumseconds / $runs;
- Output:
step 600: 2233 behind, 867 ahead step 601: 2237 behind, 868 ahead step 602: 2241 behind, 869 ahead step 603: 2247 behind, 868 ahead step 604: 2249 behind, 871 ahead step 605: 2254 behind, 871 ahead step 606: 2258 behind, 872 ahead step 607: 2262 behind, 873 ahead step 608: 2268 behind, 872 ahead step 609: 2273 behind, 872 ahead average stair length 15438 average seconds 3067
Python
""" https://rosettacode.org/wiki/Long_stairs """
from numpy import mean
from random import sample
def gen_long_stairs(start_step, start_length, climber_steps, add_steps):
secs, behind, total = 0, start_step, start_length
while True:
behind += climber_steps
behind += sum([behind > n for n in sample(range(total), add_steps)])
total += add_steps
secs += 1
yield (secs, behind, total)
ls = gen_long_stairs(1, 100, 1, 5)
print("Seconds Behind Ahead\n----------------------")
while True:
secs, pos, len = next(ls)
if 600 <= secs < 610:
print(secs, " ", pos, " ", len - pos)
elif secs == 610:
break
print("\nTen thousand trials to top:")
times, heights = [], []
for trial in range(10_000):
trialstairs = gen_long_stairs(1, 100, 1, 5)
while True:
sec, step, height = next(trialstairs)
if step >= height:
times.append(sec)
heights.append(height)
break
print("Mean time:", mean(times), "secs. Mean height:", mean(heights))
- Output:
Seconds Behind Ahead ---------------------- 600 2122 978 601 2127 978 602 2130 980 603 2135 980 604 2139 981 605 2144 981 606 2149 981 607 2153 982 608 2157 983 609 2162 983 Ten thousand trials to top: Mean time: 2780.502 secs. Mean height: 14002.51
Quackery
[ 0 100 0
[ 5 times
[ 2dup swap
random > +
dip 1+ ]
1+
rot 1+ unrot
2dup < until ]
drop ] is test ( --> n n )
( and again, with progress report )
[ 0 100 0
[ rot dup dip unrot
dup 600 610 within iff
[ say "After " echo
say " seconds, "
2dup dup
say "Behind: "
echo
say " Ahead: "
- echo cr ]
else drop
5 times
[ 2dup swap
random > +
dip 1+ ]
1+
rot 1+ unrot
2dup < until ]
drop 2drop ] is progress ( --> )
progress
cr
0 0 10000 times
[ test rot +
unrot + swap ]
swap
say "Mean time: "
number$ char . swap -4 stuff echo$ cr
say "Mean stairs: "
number$ char . swap -4 stuff echo$ cr- Output:
After 600 seconds, Behind: 2187 Ahead: 913 After 601 seconds, Behind: 2191 Ahead: 914 After 602 seconds, Behind: 2197 Ahead: 913 After 603 seconds, Behind: 2200 Ahead: 915 After 604 seconds, Behind: 2204 Ahead: 916 After 605 seconds, Behind: 2208 Ahead: 917 After 606 seconds, Behind: 2211 Ahead: 919 After 607 seconds, Behind: 2214 Ahead: 921 After 608 seconds, Behind: 2218 Ahead: 922 After 609 seconds, Behind: 2224 Ahead: 921 Mean time: 3063.7808 Mean stairs: 15418.9040
Raku
my ($trials, $t-total, $s-total) = 10000;
say 'Seconds steps behind steps ahead';
race for ^$trials {
my $stairs = 100;
my $location = 0;
my $seconds = 0;
loop {
++$seconds;
++$location;
last if $location > $stairs;
for (1..$stairs).roll(5) {
++$location if $_ <= $location;
++$stairs;
}
say " $seconds $location {$stairs-$location}" if !$_ && (599 < $seconds < 610);
}
$t-total += $seconds;
$s-total += $stairs;
}
say "Average seconds: {$t-total/$trials}, Average steps: {$s-total/$trials}";
- Sample output:
Seconds steps behind steps ahead 600 2143 957 601 2149 956 602 2153 957 603 2158 957 604 2164 956 605 2170 955 606 2175 955 607 2178 957 608 2183 957 609 2187 958 Average seconds: 2716.0197, Average steps: 13677.143
RPL
« 0 (100,100)
DO SWAP 1 +
SWAP 1 -
1 5 START
RAND OVER RE LASTARG IM / <
1 R→C +
NEXT
IF OVER 599 > 3 PICK 610 < AND THEN OVER 1 DISP DUP 2 DISP END
UNTIL DUP RE NOT END
IM "steps" →TAG SWAP "secs" →TAG
» 'STAIRS' STO
- Output:
2: steps:16135 1: secs:3207
Executing 10,000 tests is far beyond the computing power of a basic calculator.
V (Vlang)
import rand
fn main() {
mut total_secs := 0
mut total_steps := 0
println("Seconds steps behind steps ahead")
println("------- ------------ -----------")
for trial in 1..10000 {
mut sbeh := 0
mut slen := 100
mut secs := 0
for sbeh < slen {
sbeh++
for _ in 1..5 {
if rand.intn(slen) or {0} < sbeh {
sbeh++
}
slen++
}
secs++
if trial == 1 && secs > 599 && secs < 610 {
println("$secs $sbeh ${slen-sbeh}")
}
}
total_secs += secs
total_steps += slen
}
println("\nAverage secs taken: ${total_secs/10000}")
println("Average final length of staircase: ${total_steps/10000}")
}- Output:
Sample run:
Seconds steps behind steps ahead ------- ------------ ----------- 600 2112 988 601 2115 990 602 2121 989 603 2126 989 604 2130 990 605 2135 990 606 2141 989 607 2146 989 608 2150 990 609 2155 990 Average secs taken: 2914.465 Average final length of staircase: 14672.325
Wren
import "random" for Random
import "./fmt" for Fmt
var totalSecs = 0
var totalSteps = 0
var rand = Random.new()
System.print("Seconds steps behind steps ahead")
System.print("------- ------------ -----------")
for (trial in 1..10000) {
var sbeh = 0
var slen = 100
var secs = 0
while (sbeh < slen) {
sbeh = sbeh + 1
for (wiz in 1..5) {
if (rand.int(slen) < sbeh) sbeh = sbeh + 1
slen = slen + 1
}
secs = secs + 1
if (trial == 1 && secs > 599 && secs < 610) {
Fmt.print("$d $d $d", secs, sbeh, slen - sbeh)
}
}
totalSecs = totalSecs + secs
totalSteps = totalSteps + slen
}
Fmt.print("\nAverage secs taken: $h", totalSecs/10000)
Fmt.print("Average final length of staircase: $h", totalSteps/10000)
- Output:
Sample run:
Seconds steps behind steps ahead ------- ------------ ----------- 600 2112 988 601 2115 990 602 2121 989 603 2126 989 604 2130 990 605 2135 990 606 2141 989 607 2146 989 608 2150 990 609 2155 990 Average secs taken: 2914.465 Average final length of staircase: 14672.325
XPL0
include xpllib; \for Print
int Trial, SecsTotal, StepsTotal; \keep track of time and steps over all trials
int SBehind, SLen, Wiz, Secs; \all variables related to individual trial
[SecsTotal:= 0; StepsTotal:= 0;
Print("Seconds steps behind steps ahead\n");
for Trial:= 1 to 10000 do \10000 attempts for the runner
[SBehind:= 0; SLen:= 100; Secs:= 0; \initialise this Trial
while SBehind < SLen do \as long as runner is still on stairs
[SBehind:= SBehind+1; \runner climbs a step
for Wiz:= 1 to 6 do \evil Wizard conjures five new steps
[if Ran(SLen) < SBehind then
SBehind:= SBehind+1; \maybe a new step is behind us
SLen:= SLen+1; \either way, the staircase is longer
];
Secs:= Secs+1; \one second has passed
if Trial=1 & 599<Secs & Secs<610 then
Print("%d %d %d\n", Secs, SBehind, SLen-SBehind);
];
SecsTotal:= SecsTotal + Secs;
StepsTotal:= StepsTotal + SLen;
];
Print("Average seconds taken: %f\n", float(SecsTotal)/10000.0);
Print("Average final length of staircase: %f\n", float(StepsTotal)/10000.0);
]- Output:
Seconds steps behind steps ahead 600 2275 1425 601 2278 1428 602 2283 1429 603 2289 1429 604 2294 1430 605 2299 1431 606 2304 1432 607 2306 1436 608 2311 1437 609 2316 1438 Average seconds taken: 6625.81730 Average final length of staircase: 39854.90380