 # Lexico rank calculation for an MMH 2016 puzzle

Jan 16th, 2016
472
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #!/usr/bin/perl
2. #                                               Robert Munafo
3. #                                        Test Solution Please Ignore
4. #                                         MIT IAP Mystery Hunt, 2016
5. #      MMH 2016 "Huntception" (aka "Muttstery Hunt") : Sleeping Beauty : Identify, SORT, Index, Solve
6.
7. \$| = 1;
8.
9. # In the first line, "27" means it was line 27 in the original puzzle (the "original position" before sorting the 29 clues)
10. # then we have an "-LLION" pun (a word that sounds like it could be a million-trillion-zillion number) not all of which actually end in "LLION"
11. # then the description of the big number in each clue plus my (Robert Munafo) conversion to something making it easier to compare to its neighbors
12. \$dat1 = q`
13.     27  EMILLEON    BIG FOOT + 1   ~ BB(BB(BB(BB(BB(BB(BB(BB(BB(BB(googol))))))))))
14.     18  ECTHELION   BB(100)
15.     26  BRAZILLIAN  A(BB(99), BB(99))
16.     20  SCALLION    Loader's number   (some believe it's bigger than BB(100+), see googology.wikia.com/wiki/Talk:Loader's_number )
17.     5   MEDALLION   3→2→3→3
18.     9   PYGMALION   2→3→3→3
19.     7   BULLION     Graham's number   (3→3→64→2 < Graham < 3→3→65→2)
20.     28  RAPSCALLION Moser's number    ~ 2↑(Mega) 3  ~ 2↑(255PT1.99x10^619)3
21.     16  REBELLION   A(10^100,10^100)    = 2↑(googol+1) googol = 2→googol→(googol+1)
22.     29  FILLION     3↑10^100 3    ~ 3→3→googol
23.     22  NAPOLEON    A(5,1)   = 2↑↑↑↑↑3-3  (Ackermann function, use Wikipedia article's definition)
24.     15  ORWELLIAN   2→10^100→2     = 2→googol→2 = 2↑↑googol
25.     8   PERIHELION  3^(4^(5^(6^... (10^100)     ~ 3↑↑100 = 3→100→2
26.     25  SMULLYAN    (10^100)... 6^(5^(4^3))    (note that googol^..^4^3 is smaller than 3^4^...^googol)
27.     4   HYLIAN       (full square around a 6)   ~ 4 PT ( 7.701054 x 10 ^ 217837 )
28.     11  JULIAN      (((10^100!)!)!)!    ~ 4 PT ( 9.3326215443948 x 10 ^ 157 )
29.     6   COTILLION   3^(2^(2^(4^(35^15))))    ~ 4 PT ( 8.722890751664 x 10 ^ 22 )
30.     24  STALLION    2^(38^(64^(20^(57^13))))   ~ 4 PT ( 8.7228907507447 x 10 ^ 22 )
31.     23  CHAMELEON   68^(75^(96^(92^(39^3))))   ~ 3 PT ( 1.6876927 x 10 ^ 116490 )
32.     3   GILLIAN     43^(45^(47^(49^(41^3))))   ~ 3 PT ( 1.6876925 x 10 ^ 116490 )
33.     17  PAVILLION   2↑↑8   ~ 3 PT ( 6.03122606 x 10 ^ 19727 )
34.     14  VERMILLION  A(4,5)    = 2↑↑8-3  (Ackermann function, use Wikipedia article's definition)
35.     10  AUSTRALIAN  Largest named number in the Avatamsaka Sutra   ~ 10 ^ ( 1.0149329261031 x 10 ^ 32 )
36.     12  SICILIAN    13^315760124882724518   ~ 1.0883338209710305866135010120769 x 10 ^ 351738892036687573  ~ 10 ^ ( 3.5173889203668 x 10 ^ 17 )
37.     13  TRISKELION  20^270354175698445357   ~ 1.0883338209710305866113067575128 x 10 ^ 351738892036687573  ~ 10 ^ ( 3.5173889203668 x 10 ^ 17 )
38.     21  REGELLIAN   Largest named number in The Sand Reckoner   = 10 ^ ( 8 x 10 ^ 16 )
39.     2   REPTILIAN   Number of particles in the known Universe   ~ 10^97
40.     19  APHELION    Number of permutations of these numbers   = 29! ~ 8.8417619937398 x 10 ^ 30
41.     1   TRILLIAN    2↑10^100 2    = 4  (because 2↑↑↑....↑2 is always 4 no matter how many ↑'s)
42. `;
43.
44. \$i = 0;
45. \$rank = 29; # In the big text chunk above, the biggest number (29th lexicographically) is given first and then the 28th, 27th, etc.
46. foreach \$s (split(/\n/, \$dat1)) {
47.   if (\$s ne '') {
48.     print " \$i \$s\n";
49.     @dat2 = split(/\t/, \$s);  # now dat2 contains: blank , original position , "-ILLION" pun , description of big number
50.     print "  '\$dat2', '\$dat2', \$rank, '\$dat2'\n";
51.     \$oo = \$dat2;
52.     \$wrd[\$oo] = \$dat2; # "word" e.g. medlallion
53.     \$lex[\$oo] = \$rank;    # lexicographical rank after sorting by size of number (1=smallest, 29=largest)
54.     \$dsc[\$oo] = \$dat2; # "description"
55.     \$rank--; # The next line in the text block is the next-smaller number
56.   }
57.   \$i++;
58. }
59.
60. # Use iterative formula for lexicographic rank.
61. # e.g. for the example at http://www.geeksforgeeks.org/lexicographic-rank-of-a-string/
62. # we would output "0+4*5!+4*4!+3*3!+1*2!+1*1!+0*0!+1
63. \$ans = "";
64. \$rf = 29;
65. for(\$i=1; \$i<=29; \$i++) {
66.   print "\$i   \$wrd[\$i]   \$lex[\$i]   \$dsc[\$i]\n";
67.   \$coeff = \$lex[\$i] - 1; \$rf--;
68.   \$ans = \$ans . "+\$coeff*\$rf!";
69.   # Now that this item is out of the running, remote the rank of any remaining item whose rank was higher
70.   for(\$j=\$i+1; \$j<29; \$j++) {
71.     if (\$lex[\$j] > \$lex[\$i]) {
72.       \$lex[\$j]--;
73.      }
74.   }
75. }
76. \$ans = \$ans . "+1";
77. print "\n \$ans\n";
78. # this gives something like "+0*28!+3*27!+9*26!+14*25!+24*24!+12*23!+22*22!+16*21!+23*20!+7*19!+13*18!+6*17!+5*16!+18*15!+17*14!+20*13!+8*12!+26*11!+2*10!+25*9!+4*8!+1*7!+10*6!+11*5!+15*4!+27*3!+28*2!+21*1!+19*0!+1"
79. # which we cut and paste into http://www.wolframalpha.com/
80. # to get 36528615030208447864573605853 or similar
81.
82. # The ordering of BB() vs. Leader is still debated, I've tried a few options, and got other similar numbers:
83. #   36528615030208447864573605851
84. #   36528615030208447864494498011
85. #   36528615030208447864533689059
86. #   36528615030208447864573605853
87. # The initial digits of this big number depend only on us getting the right answer for the rank of the clues near the beginning of the puzzle's 29 clues in the order presented in the puzzle.
88. # e.g. as long as we're certain "Trillian 2^(10^100) 2 = 4" is the smallest, this "36528..." number will never be more than "1*28!" and the initial digits 365... are determined solely by our guess that "Reptilian number of particles in universe" is the 4th-smallest and "Gillian 43^(45..." is the 10th-smallest, etc.
89. # all of the digits of the "36528..." number are determined solely by the puzzle author's choice of what order to give the 29 clues, it could be anything from 1 to 29! = 8841761993739701954543616000000