Long stairs: Difference between revisions

Content added Content deleted

Inline

Revision as of 19:04, 16 November 2021

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.

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;

}</lang>

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

Factor

<lang 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</lang>

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. <lang factor>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</lang>

Fermat

<lang 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);</lang>

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

FreeBASIC

<lang 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</lang>

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.

GW-BASIC

<lang gwbasic> 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</lang>

Julia

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

</lang>

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)

Pascal

Free Pascal

<lang pascal>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(WithOutput:boolean):longword; var

 inFront,behind,total,i,trials: longword;

begin

 trials := 0;
 total := StartStairLength;
 inFront := total;
 behind := 0;
 repeat
   inc(trials);
   inc(behind);
   dec(infront);
   //spell
   for i := 1 to StairsPerSpell do
   begin
     if random(total)+1 <= behind then
       inc(behind)
     else
       inc(infront);
     inc(total)
   end;
   if WithOutput then
   begin
     if (trials <= 609)AND(trials>=600) then
       OutActual(trials,behind,infront);
   end;
 until infront = 0;
 OneRun := total;

end;

procedure CheckDouble; //instead of random use ratio behind/total var //xmm in freepascal using SSE

 behind,infront,relpos,total,One : double;
 i : nativeInt;

begin

 One := 1.0;
 behind := 0.0;
 inFront := StartStairLength;
 total := StartStairLength;
 repeat
   //first: doing the step
   behind  += One;
   inFront -= One;
   //second: doing the spell
   For i := StairsPerSpell-1 downto 0 do
   begin
     relpos  := behind/total;
     behind  += relpos;
     inFront += (One-relpos);
     total   += One;
   end;
 until infront < One;
 writeln(total:10:2);

end;

var

 i,
 attempt,
 minStairs,
 maxStairs,
 total : longword;

begin

 minStairs := High(minStairs);
 maxStairs := low(maxStairs);
 randomize;
 writeln('Seconds  steps total  behind    ahead');
 total := OneRun(true);
 total := 0;
 For i := rounds-1 downto 0 do
 begin
   attempt:= OneRun(false);
   if minStairs>attempt then
     minstairs := attempt;
   if maxStairs<attempt then
     maxstairs := attempt;
   inc(total,attempt);
 end;
 writeln(' average stairs  minimum   maximum');
 writeln(total/rounds:14:3,minStairs:9,maxStairs:10);
 writeln;
 writeln((total-StartStairLength)/rounds/StairsPerSpell:10:3,' average needed seconds');
 writeln;
 writeln(' stairs without random ');
 CheckDouble;

end. </lang>

@ TIO.RUN:

Seconds  steps total  behind    ahead
  600        3100      2021     1079
  601        3105      2027     1078
  602        3110      2031     1079
  603        3115      2036     1079
  604        3120      2039     1081
  605        3125      2043     1082
  606        3130      2048     1082
  607        3135      2052     1083
  608        3140      2055     1085
  609        3145      2059     1086
 average stairs  minimum   maximum
     14691.605     7655     26770

  2938.319 average needed seconds

 stairs without random
  14470.00

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

Raku

<lang perl6>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}";</lang>

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

Wren

Translation of: C

Library: Wren-fmt

<lang ecmascript>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)</lang>

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