News for hackers. Stuff that matters.
Re:A ride that takes 10^20k years to complete in Roller Coas... by nightcracker on Monday August 03, 2020 @08:04PM (#24045006)
A precise analysis of how many steps it takes to solve this maze. I am assuming that each step takes exactly as long as any other, and that the character instantaneously turns at the start of its step. Analyzing the video this seems about right.

For each 'dead end unit' there are four states the character can be in after having just taken a step, s = {forward, backward, inside, facewall}. Let us look at the Markov chain transition probabilities if we are in state (n,s).

  - (n,forward) has a 3/4 chance of going to (n,inside) and 1/4 chance of going to (n+1,forward).
  - (n,backward) has a 1/4 chance of going to (n,inside) and a 3/4 chance of going to (n-1,backward).  
  - (n,inside) has a 100% chance to go to (n,facewall).  
  - (n,facewall) has a 50/50 chance of going to (n+1,forward) and (n-1,backward).
Assuming that big N indicates how many 'dead end units' we have, there are two exceptions:

  - (0,s) always goes to (1,forward) for any s.  
  - (N+1,forward) always goes to itself, it is an absorbing state.
Without going into details too much, we can now apply some results from Markov chain theory (see here for more: https://www.dartmouth.edu/~chance/teaching_aids/books_articl...).

If we build up the transition matrix of the above, ensuring that any absorbing state is at the end (we only have one absorbing state), we can take matrix Q as the rows/columns that don't interact with the absorbing state. Then the sum of the first row of (I - Q)^(-1) gives us our mean absorption times.

The code: https://gist.github.com/orlp/0c5fc7264f02e3d211d42da643163bb...

The results (in format N, expected time to solve, ratio with last):

    1 5.6 5.6
    2 13.439999999999998 2.4
    3 25.816000000000003 1.9208333333333338
    4 44.542400000000015 1.725379609544469
    5 72.15936000000002 1.6200150867488055
    6 112.22310400000002 1.555212019618799
    7 169.71234560000005 1.5122763455197248
    8 251.59728384000005 1.4824925255172479
    9 367.63619737600015 1.4612089278745692
    10 531.4906763264004 1.445697350043086
    11 762.2869468569604 1.4342433100158898
    12 1086.8017255997447 1.4257121023530763
    13 1542.5224158396427 1.4193227518003906
    14 2181.9313821754995 1.4145216690337734
    15 3078.503935045701 1.4109077674002157
    16 4335.105509063981 1.408185794311686
    17 6095.747712689574 1.406135952157193
    18 8562.046797765406 1.404593365952747
    19 12016.265516871565 1.4034337583867995
    20 16853.571723620193 1.4025631923626152
    21 23627.200413068273 1.4019105742407632
    22 33111.68057829557 1.4014220897699503
    23 46391.35280961381 1.401057028800373
    24 64984.29393345935 1.400784628983539
    25 91015.8115068431 1.4005816790136818
    26 127461.33610958033 1.400430694396402
    27 178486.4705534125 1.4003185279649442
    28 249923.05877477748 1.4002353119531679
    29 349935.6822846886 1.4001736534444356
    30 489954.75519856386 1.4001280235262301
    31 685982.8572779896 1.4000942944210868
    32 960423.6001891854 1.400069389489103
    33 1344642.0402648596 1.4000510191544548
    34 1882549.2563708038 1.400037482094484
    35 2635620.7589191245 1.400027515880301
    36 3689922.2624867745 1.4000201849980958
    37 5165945.767481486 1.4000147970596988
    38 7232380.0744740805 1.4000108402222013
    39 10125389.504263714 1.4000079365298022
    40 14175604.1059692 1.4000058071840076
    41 19845905.94835688 1.4000042467325944
    42 27784329.92769964 1.4000031039147403
    43 38898124.898779504 1.4000022674651564
    44 54457439.25829131 1.4000016556067978
    45 76240480.76160783 1.400001208283035
    46 106736740.266251 1.4000008814215148
    47 149431504.9727514 1.400000642702783
    48 209204176.96185198 1.4000004684420466
    49 292885919.1465928 1.4000003412933768
    50 410040359.6052299 1.4000002485609422

This makes me conjecture that modulo small effects at the start/end (and I've completely ignored the long middle piece), we have that the number of steps taken to solve a N 'dead end unit' maze is Ө(1.4^N). I've asked a question on the math stackexchange to see if someone can prove it formally: https://math.stackexchange.com/questions/3779234/mean-first-....

There are no comments on this comment yet.