Skip to content

Instantly share code, notes, and snippets.

# orlp/rc2maze.py

Last active August 4, 2020 00:42
Show Gist options
• Save orlp/0c5fc7264f02e3d211d42da643163bb7 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 import numpy as np def expected_time_to_solve(N): A = np.zeros((4*(N+2), 4*(N+2))) # (n, forward) => (4n + 0), (n, backward) => (4n + 1), (n, inside) => (4n + 2), (n, facewall) => (4n + 3) for i in range(4*(N+2)): if i < 4: A[i,4] = 1 elif i >= 4*(N+1): A[i,i] = 1 elif i % 4 == 0: A[i,i+2] = 3/4 A[i,i+4] = 1/4 elif i % 4 == 1: A[i,i+1] = 1/4 A[i,i-4] = 3/4 elif i % 4 == 2: A[i,i+1] = 1 elif i % 4 == 3: A[i, i+1] = 1/2 A[i, i+2-8] = 1/2 else: raise RuntimeError("non-exhaustive Markov chain") Q = A[:4*(N+1),:4*(N+1)] x = np.linalg.inv(np.eye(4*(N+1)) - Q) return np.sum(x[0]) last = 1 for N in range(1,200): tts = expected_time_to_solve(N) ratio_with_last = tts/last print(N, tts, ratio_with_last) last = tts
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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 51 574056577.6473218 1.4000001809577964 52 803679284.3062508 1.4000001316943367 53 1125151075.0287511 1.4000000958093626 54 1575211583.4402516 1.4000000696795316 55 2205296296.6163526 1.4000000506598613 56 3087414896.462894 1.4000000368204493 57 4322380937.648049 1.400000026753773 58 6051333396.707272 1.4000000194337343 59 8471866840.790177 1.4000000141125917 60 11860613663.906248 1.4000000102456756
to join this conversation on GitHub. Already have an account? Sign in to comment