4 ms·
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 instan
by nightcracker 6y ago
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_articles/probability_book/Chapter11.pdf 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/0c5fc7264f02e3d211d42da643163bb7 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-hitting-time-of-infinite-markov-chain-in-the-limit https://math.stackexchange.com/questions/3779234/mean-first-....