Files
MysteryHunt2019/bloomfilter.nb
2020-01-17 04:06:56 -05:00

401 lines
16 KiB
Mathematica

(* Content-type: application/vnd.wolfram.mathematica *)
(*** Wolfram Notebook File ***)
(* http://www.wolfram.com/nb *)
(* CreatedBy='Mathematica 11.0' *)
(*CacheID: 234*)
(* Internal cache information:
NotebookFileLineBreakTest
NotebookFileLineBreakTest
NotebookDataPosition[ 158, 7]
NotebookDataLength[ 16255, 390]
NotebookOptionsPosition[ 15297, 355]
NotebookOutlinePosition[ 15655, 371]
CellTagsIndexPosition[ 15612, 368]
WindowFrame->Normal*)
(* Beginning of Notebook Content *)
Notebook[{
Cell[BoxData[
RowBox[{
RowBox[{"bitVector", "=",
RowBox[{
RowBox[{
RowBox[{"FromDigits", "[",
RowBox[{
RowBox[{"StringTake", "[",
RowBox[{"#", ",",
RowBox[{"3", ";;"}]}], "]"}], ",", "16"}], "]"}], "&"}], "/@",
RowBox[{"StringSplit", "[",
RowBox[{
"\"\<0x3e13e58b,0xb93064dd,0x3b3a13c2,0x43c17b17,0x77c8170f,0x72d684f3,\
0x4e94bde3,0x178ea819,0x9c643453,0xe7e1f598,0x0953e1d4,0xc26a17da,0xb5281dd5,\
0x83fcd020,0xdf5b8585,0x7cfc9c7d,0x4326ebfa,0x44ef1acb,0x5397a9d1,0x541d641b,\
0xf1cc70f0,0xe7debb71,0xfdadfc8d,0x703d5b23,0x91e7b18e,0x6adeb3d1,0x17f2f1da,\
0x66b75403,0xb34d986b,0xcac1c344,0x39b7cd33,0x9a8ea8fc,0x8b3aac29,0xfc4a4997,\
0xf6554b0d,0x4d31de6a,0x7d121515,0xff25b2a3,0xb19185fa,0xfea0fe00,0xc795909a,\
0x3e007be3,0x458562f1,0x5807a052,0xf9edd76e,0x2b912489,0xcc3af4d3,0xec353c96,\
0x319d21b1,0xf4d8d832,0x3737f8a3,0xabc4b4aa,0xedeb3062,0x03faf091,0x75e9879e,\
0xa283f707,0xf1819b7f,0x4ccbfd1b,0xc8e9c576,0x9fea7800,0x095d1f42,0x311af940,\
0xe8ce5b49,0xe46d4fef,0xaabea74a,0x5e9fc668,0xaa0ca532,0xf0902b05,0x165be527,\
0xca9c9474,0xf078def1,0x0663a350,0x62952874,0x40aec582,0x84b07c16,0xa5e772a5,\
0xd72523b7,0xf831cc58,0xce9af317,0xdca9997e,0x5fdf8d2f,0x55cff37e,0xac50b3e1,\
0x217b3a2a,0x9ed334a9,0xb4199163,0x69270573,0xb3c63b38,0xb9e6eb67,0xf67a2cc4,\
0x8b527cfc,0x1b69a598,0x0cd1f9ec,0xd6f0a25b,0x7a6396d8,0xef27d441,0x27d9e083,\
0xb7724e16,0x24939fba,0x4f862321,0x83deba38,0x91a2abb1,0xa16bea81,0xb688aece,\
0x0f6a3764,0x325531cd,0x832c3c30,0x02167d30,0x349314e6,0x29d04e45,0x01eef553,\
0x4587d7c1,0x1ca6f9c3,0x6f1b3f66,0x55faba32,0x4d1b6af3,0x005b3030,0x2c975110,\
0xb3953d5b,0xdce5cfd1,0xfd3f173b,0x2fba9dc0,0xb1108b7b,0x414d78a6,0x7765fbc8,\
0xd2bdb9f1,0x141986df,0xc5c8ec43\>\"", ",", "\"\<,\>\""}], "]"}]}]}],
";"}]], "Input",
CellChangeTimes->{{3.756978287288994*^9, 3.756978312541388*^9}, {
3.7569794009827213`*^9, 3.756979402055189*^9}, {3.756980869434564*^9,
3.7569808719527473`*^9}, 3.756980960523193*^9}],
Cell[BoxData[
RowBox[{
RowBox[{"primes", "=",
RowBox[{"FromDigits", "/@",
RowBox[{"StringSplit", "[",
RowBox[{
"\"\<2196119,2734343,1503683,1126787,2249053,1024921,1444943,2031223,\
2887777,1717099,4111633,1816337,1565261,4990243,2503327,1616827,1968017,\
2816969,3403613,1363717,5012243,1082717,1136717,2621669,3157577,5737961,\
1042523,2188409,1330487,1422923,1047131,1143647,2021629,3838477,3525377,\
4735589,7042933,1801433,2923367,1144399,1594261,2709601,3307609\>\"", ",",
"\"\<,\>\""}], "]"}]}]}], ";"}]], "Input",
CellChangeTimes->{{3.756978463718264*^9, 3.7569784970254507`*^9},
3.756981160220035*^9}],
Cell[BoxData[
RowBox[{
RowBox[{"fnv", "[", "str_", "]"}], ":=",
RowBox[{"Fold", "[",
RowBox[{
RowBox[{
RowBox[{"BitAnd", "[",
RowBox[{
RowBox[{
RowBox[{"BitXor", "[",
RowBox[{"#1", ",", "#2"}], "]"}], "*", "1099511628211"}], ",",
RowBox[{
SuperscriptBox["2", "64"], "-", "1"}]}], "]"}], "&"}], ",",
"14695981039346656037", ",",
RowBox[{"ToCharacterCode", "@", "str"}]}], "]"}]}]], "Input",
CellChangeTimes->{{3.756979083930296*^9, 3.756979206072736*^9}, {
3.756979236842613*^9, 3.756979246577389*^9}}],
Cell[BoxData[
RowBox[{
RowBox[{"hash", "[",
RowBox[{"row_", ",", "column_", ",", "primes_"}], "]"}], ":=",
RowBox[{"With", "[",
RowBox[{
RowBox[{"{",
RowBox[{"s", "=",
RowBox[{"StringReplace", "[",
RowBox[{
RowBox[{"ToUpperCase", "[", "row", "]"}], ",",
RowBox[{
RowBox[{"_", "?",
RowBox[{"(",
RowBox[{
RowBox[{"Not", "[",
RowBox[{"LetterQ", "[", "#", "]"}], "]"}], "&"}], ")"}]}],
"\[Rule]", "\"\<\>\""}]}], "]"}]}], "}"}], ",",
"\[IndentingNewLine]",
RowBox[{"With", "[",
RowBox[{
RowBox[{"{",
RowBox[{"h", "=",
RowBox[{"Mod", "[",
RowBox[{
RowBox[{"fnv", "[", "s", "]"}], ",",
RowBox[{"primes", "[",
RowBox[{"[",
RowBox[{"column", "+", "1"}], "]"}], "]"}]}], "]"}]}], "}"}], ",",
"\[IndentingNewLine]",
RowBox[{"Mod", "[",
RowBox[{"h", ",",
RowBox[{"32", " ", "128"}]}], "]"}]}], "\[IndentingNewLine]", "]"}]}],
"\[IndentingNewLine]", "]"}]}]], "Input",
CellChangeTimes->{{3.756979259272077*^9, 3.756979274906234*^9}, {
3.756979311986095*^9, 3.756979367035007*^9}, {3.756980259652974*^9,
3.7569802876633043`*^9}, {3.756988832758368*^9, 3.756988834093464*^9}}],
Cell[BoxData[
RowBox[{
RowBox[{"bitAt", "[", "pos_", "]"}], ":=",
RowBox[{"Mod", "[",
RowBox[{
RowBox[{"BitShiftRight", "[",
RowBox[{
RowBox[{"bitVector", "[",
RowBox[{"[",
RowBox[{
RowBox[{"BitShiftRight", "[",
RowBox[{"pos", ",", "5"}], "]"}], "+", "1"}], "]"}], "]"}], ",",
RowBox[{"(",
RowBox[{"31", "-",
RowBox[{"(",
RowBox[{"BitAnd", "[",
RowBox[{"pos", ",", "31"}], "]"}], ")"}]}], ")"}]}], "]"}], ",",
"2"}], "]"}]}]], "Input",
CellChangeTimes->{{3.756979393221431*^9, 3.756979457688451*^9}, {
3.756979527877727*^9, 3.756979531612009*^9}, {3.756980420731535*^9,
3.756980427756152*^9}, {3.75698056600744*^9, 3.7569805758300467`*^9}, {
3.75698090293861*^9, 3.756980917632436*^9}, {3.756980988813847*^9,
3.756981012937899*^9}, {3.756981111185359*^9, 3.7569811239056463`*^9}, {
3.756993362526478*^9, 3.756993376566687*^9}}],
Cell[CellGroupData[{
Cell[BoxData[
RowBox[{"allowed", "[", "\"\<kaepernick\>\"", "]"}]], "Input",
CellChangeTimes->{{3.75699100639809*^9, 3.7569910475126877`*^9}}],
Cell[BoxData["False"], "Output",
CellChangeTimes->{{3.756991011492592*^9, 3.756991047790691*^9}}]
}, Open ]],
Cell[CellGroupData[{
Cell[BoxData[
RowBox[{
RowBox[{
RowBox[{"Function", "[",
RowBox[{
RowBox[{"{", "flower", "}"}], ",",
RowBox[{"Mod", "[",
RowBox[{
RowBox[{
RowBox[{
RowBox[{"hash", "[",
RowBox[{"flower", ",", "#"}], "]"}], "&"}], "/@",
RowBox[{"Range", "[",
RowBox[{"0", ",", "42"}], "]"}]}], ",", "2"}], "]"}]}], "]"}], "/@",
RowBox[{"Sort", "@",
RowBox[{"{",
RowBox[{
"\"\<aster\>\"", ",", "\"\<buttercup\>\"", ",", "\"\<carnation\>\"",
",", "\"\<daisy\>\"", ",", "\"\<edelweiss\>\"", ",", "\"\<freesia\>\"",
",", "\"\<geranium\>\"", ",", "\"\<hibiscus\>\"", ",", "\"\<iris\>\"",
",", "\"\<jasmine\>\"", ",", "\"\<kingcup\>\"", ",", "\"\<lotus\>\"",
",", "\"\<magnolia\>\"", ",", "\"\<narcissus\>\"", ",",
"\"\<orchid\>\"", ",", "\"\<primrose\>\""}], "}"}]}]}], "//",
RowBox[{
RowBox[{"ArrayPlot", "[",
RowBox[{"#", ",",
RowBox[{"Mesh", "\[Rule]", "True"}]}], "]"}], "&"}]}]], "Input",
CellChangeTimes->{{3.756989245847426*^9, 3.756989257784947*^9}, {
3.756989352979122*^9, 3.756989406489909*^9}, {3.756989464716695*^9,
3.75698957887539*^9}, {3.756989652192927*^9, 3.756989653545127*^9}, {
3.756989726577818*^9, 3.756989727370398*^9}, {3.756989859861459*^9,
3.756989862605118*^9}, {3.7569899587060747`*^9, 3.756989988920351*^9}, {
3.756990053641925*^9, 3.756990103202651*^9}, {3.756990147650419*^9,
3.7569902613533897`*^9}, {3.7569903031869373`*^9, 3.756990306985496*^9}, {
3.7569905066377487`*^9, 3.756990512720498*^9}, {3.7569905522102327`*^9,
3.756990590405678*^9}, {3.756990638613936*^9, 3.756990644501848*^9}, {
3.756991081747802*^9, 3.756991095561602*^9}}],
Cell[BoxData[
GraphicsBox[{RasterBox[CompressedData["
1:eJxTTMoPSmJiYGAQAGJtIGZkZGQAA0YiAAMcEK+SkGIGNECCUjyqsSjFpRir
UhyKEXIEFaOK41eNIYhbMVbLcCjG7wkGNDGsahmR/YzfWGTlCB4+pWgWE5EE
GRgAj08DxA==
"], {{0, 0}, {43, 16}}, {0, 1}], {
{GrayLevel[
NCache[-1 + GoldenRatio, 0.6180339887498949]],
StyleBox[
LineBox[{{{0, 16}, {43, 16}}, {{0, 15}, {43, 15}}, {{0, 14}, {43,
14}}, {{0, 13}, {43, 13}}, {{0, 12}, {43, 12}}, {{0, 11}, {43, 11}}, {{
0, 10}, {43, 10}}, {{0, 9}, {43, 9}}, {{0, 8}, {43, 8}}, {{0, 7}, {43,
7}}, {{0, 6}, {43, 6}}, {{0, 5}, {43, 5}}, {{0, 4}, {43, 4}}, {{0,
3}, {43, 3}}, {{0, 2}, {43, 2}}, {{0, 1}, {43, 1}}, {{0, 0}, {43, 0}}}],
Antialiasing->False]},
{GrayLevel[
NCache[-1 + GoldenRatio, 0.6180339887498949]],
StyleBox[
LineBox[{{{0, 0}, {0, 16}}, {{1, 0}, {1, 16}}, {{2, 0}, {2, 16}}, {{3,
0}, {3, 16}}, {{4, 0}, {4, 16}}, {{5, 0}, {5, 16}}, {{6, 0}, {6,
16}}, {{7, 0}, {7, 16}}, {{8, 0}, {8, 16}}, {{9, 0}, {9, 16}}, {{10,
0}, {10, 16}}, {{11, 0}, {11, 16}}, {{12, 0}, {12, 16}}, {{13, 0}, {13,
16}}, {{14, 0}, {14, 16}}, {{15, 0}, {15, 16}}, {{16, 0}, {16,
16}}, {{17, 0}, {17, 16}}, {{18, 0}, {18, 16}}, {{19, 0}, {19, 16}}, {{
20, 0}, {20, 16}}, {{21, 0}, {21, 16}}, {{22, 0}, {22, 16}}, {{23,
0}, {23, 16}}, {{24, 0}, {24, 16}}, {{25, 0}, {25, 16}}, {{26, 0}, {26,
16}}, {{27, 0}, {27, 16}}, {{28, 0}, {28, 16}}, {{29, 0}, {29,
16}}, {{30, 0}, {30, 16}}, {{31, 0}, {31, 16}}, {{32, 0}, {32, 16}}, {{
33, 0}, {33, 16}}, {{34, 0}, {34, 16}}, {{35, 0}, {35, 16}}, {{36,
0}, {36, 16}}, {{37, 0}, {37, 16}}, {{38, 0}, {38, 16}}, {{39, 0}, {39,
16}}, {{40, 0}, {40, 16}}, {{41, 0}, {41, 16}}, {{42, 0}, {42,
16}}, {{43, 0}, {43, 16}}}],
Antialiasing->False]}}},
Frame->False,
FrameLabel->{None, None},
FrameTicks->{{None, None}, {None, None}},
GridLinesStyle->Directive[
GrayLevel[0.5, 0.4]],
ImageSize->{523.43359375, Automatic},
Method->{
"DefaultBoundaryStyle" -> Automatic, "DefaultPlotStyle" ->
Automatic}]], "Output",
CellChangeTimes->{
3.756989257974113*^9, {3.756989361549594*^9, 3.756989406716984*^9}, {
3.756989476257662*^9, 3.756989579193232*^9}, 3.7569896538177347`*^9, {
3.7569897276775303`*^9, 3.756989769767002*^9}, 3.756989827461731*^9,
3.756989862967691*^9, {3.7569899612299967`*^9, 3.756989989244811*^9}, {
3.756990048940648*^9, 3.756990058629388*^9}, {3.756990097463891*^9,
3.756990106101871*^9}, {3.756990148775042*^9, 3.75699026171108*^9},
3.756990307689023*^9, 3.756990514308894*^9, {3.756990556914215*^9,
3.756990590730566*^9}, {3.7569906396447277`*^9, 3.756990644733127*^9}, {
3.7569910829916487`*^9, 3.7569910958668747`*^9}}]
}, Open ]],
Cell[BoxData[
RowBox[{
RowBox[{"bitArr", "[", "s_", "]"}], ":=",
RowBox[{
RowBox[{"bitArr", "[", "s", "]"}], "=",
RowBox[{
RowBox[{
RowBox[{"bitAt", "[",
RowBox[{"hash", "[",
RowBox[{"s", ",", "#", ",", "primes"}], "]"}], "]"}], "&"}], "/@",
RowBox[{"Range", "[",
RowBox[{"0", ",",
RowBox[{
RowBox[{"Length", "[", "primes", "]"}], "-", "1"}]}],
"]"}]}]}]}]], "Input",
CellChangeTimes->{{3.756981178485984*^9, 3.756981186773171*^9}, {
3.756982707213051*^9, 3.756982708357205*^9}, {3.756988871788022*^9,
3.756988872556047*^9}}],
Cell[BoxData[
RowBox[{
RowBox[{"allowed", "[", "w_", "]"}], ":=",
RowBox[{"FreeQ", "[",
RowBox[{
RowBox[{"bitArr", "@", "w"}], ",", "0"}], "]"}]}]], "Input",
CellChangeTimes->{{3.756981307682704*^9, 3.756981316472404*^9}, {
3.756981781751648*^9, 3.756981782591955*^9}}],
Cell["The following takes a while to evaluate", "Text",
CellChangeTimes->{{3.7569933089973173`*^9, 3.75699331753244*^9}}],
Cell[BoxData[
RowBox[{"Select", "[",
RowBox[{
RowBox[{"WordData", "[", "]"}], ",", "allowed"}], "]"}]], "Input",
CellChangeTimes->{{3.756981324719595*^9, 3.75698133058766*^9}}],
Cell[BoxData[
RowBox[{
RowBox[{"allowedWords", "=",
RowBox[{"{",
RowBox[{
"\"\<acetone\>\"", ",", "\"\<Aladdin\>\"", ",", "\"\<allegro\>\"", ",",
"\"\<alternation\>\"", ",", "\"\<ambassador\>\"", ",", "\"\<Argo\>\"",
",", "\"\<Aries\>\"", ",", "\"\<arrow\>\"", ",", "\"\<bit\>\"", ",",
"\"\<bloom\>\"", ",", "\"\<boon\>\"", ",", "\"\<Botswana\>\"", ",",
"\"\<briefcase\>\"", ",", "\"\<brownie\>\"", ",", "\"\<chorine\>\"",
",", "\"\<cocktail\>\"", ",", "\"\<collateral\>\"", ",",
"\"\<cornea\>\"", ",", "\"\<damnation\>\"", ",", "\"\<deadeye\>\"", ",",
"\"\<firebase\>\"", ",", "\"\<flame\>\"", ",", "\"\<gale\>\"", ",",
"\"\<genie\>\"", ",", "\"\<hash\>\"", ",", "\"\<Hebe\>\"", ",",
"\"\<holdover\>\"", ",", "\"\<hydra\>\"", ",", "\"\<Iago\>\"", ",",
"\"\<intonation\>\"", ",", "\"\<jackknife\>\"", ",", "\"\<Jafar\>\"",
",", "\"\<jaguar\>\"", ",", "\"\<junior\>\"", ",", "\"\<Lawrence\>\"",
",", "\"\<lens\>\"", ",", "\"\<lowest\>\"", ",", "\"\<malarkey\>\"",
",", "\"\<mini\>\"", ",", "\"\<Morgan\>\"", ",", "\"\<oblivion\>\"",
",", "\"\<odium\>\"", ",", "\"\<Oklahoma\>\"", ",", "\"\<porter\>\"",
",", "\"\<pupil\>\"", ",", "\"\<rates\>\"", ",", "\"\<retina\>\"", ",",
"\"\<rhino\>\"", ",", "\"\<rue\>\"", ",", "\"\<senior\>\"", ",",
"\"\<soliloquy\>\"", ",", "\"\<stagnation\>\"", ",", "\"\<stare\>\"",
",", "\"\<Sunday\>\"", ",", "\"\<swan\>\"", ",", "\"\<tamarin\>\"", ",",
"\"\<tears\>\"", ",", "\"\<tenfold\>\"", ",", "\"\<thresh\>\"", ",",
"\"\<Valkyrie\>\""}], "}"}]}], ";"}]], "Input",
CellChangeTimes->{{3.756983664231471*^9, 3.756983673303623*^9}, {
3.7569837060966043`*^9, 3.75698371509265*^9}, {3.756983787055484*^9,
3.756983790998*^9}, {3.756993319077174*^9, 3.7569933229341*^9}}],
Cell[CellGroupData[{
Cell[BoxData[
RowBox[{
RowBox[{
RowBox[{"bitAt", "[",
RowBox[{"hash", "[",
RowBox[{"\"\<BLOOM\>\"", ",", "#"}], "]"}], "]"}], "&"}], "/@",
RowBox[{"Range", "[",
RowBox[{"0", ",",
RowBox[{
RowBox[{"Length", "[", "primes", "]"}], "-", "1"}]}], "]"}]}]], "Input",
CellChangeTimes->{{3.756980264702359*^9, 3.756980317223325*^9}, {
3.756980377963601*^9, 3.7569804127073183`*^9}, {3.7569805489085283`*^9,
3.7569805489957657`*^9}, {3.7569809197301817`*^9, 3.7569809443145027`*^9}, {
3.756981145523032*^9, 3.756981146034422*^9}}],
Cell[BoxData[
RowBox[{"{",
RowBox[{
"1", ",", "1", ",", "1", ",", "1", ",", "1", ",", "1", ",", "1", ",", "1",
",", "1", ",", "1", ",", "1", ",", "1", ",", "1", ",", "1", ",", "1", ",",
"1", ",", "1", ",", "1", ",", "1", ",", "1", ",", "1", ",", "1", ",", "1",
",", "1", ",", "1", ",", "1", ",", "1", ",", "1", ",", "1", ",", "1", ",",
"1", ",", "1", ",", "1", ",", "1", ",", "1", ",", "1", ",", "1", ",", "1",
",", "1", ",", "1", ",", "1", ",", "1", ",", "1"}], "}"}]], "Output",
CellChangeTimes->{{3.756980413522169*^9, 3.7569804240907927`*^9},
3.756980549668953*^9, {3.756980878905635*^9, 3.756981014562509*^9}, {
3.756981113239396*^9, 3.756981146300156*^9}}]
}, Open ]]
},
WindowSize->{808, 655},
WindowMargins->{{Automatic, 95}, {Automatic, 0}},
FrontEndVersion->"11.0 for Mac OS X x86 (32-bit, 64-bit Kernel) (September \
21, 2016)",
StyleDefinitions->"Default.nb"
]
(* End of Notebook Content *)
(* Internal cache information *)
(*CellTagsOutline
CellTagsIndex->{}
*)
(*CellTagsIndex
CellTagsIndex->{}
*)
(*NotebookFileOutline
Notebook[{
Cell[558, 20, 2010, 34, 453, "Input"],
Cell[2571, 56, 645, 13, 180, "Input"],
Cell[3219, 71, 581, 16, 58, "Input"],
Cell[3803, 89, 1322, 36, 138, "Input"],
Cell[5128, 127, 953, 23, 54, "Input"],
Cell[CellGroupData[{
Cell[6106, 154, 144, 2, 32, "Input"],
Cell[6253, 158, 98, 1, 32, "Output"]
}, Open ]],
Cell[CellGroupData[{
Cell[6388, 164, 1729, 37, 96, "Input"],
Cell[8120, 203, 2816, 51, 223, "Output"]
}, Open ]],
Cell[10951, 257, 599, 17, 32, "Input"],
Cell[11553, 276, 286, 7, 32, "Input"],
Cell[11842, 285, 122, 1, 30, "Text"],
Cell[11967, 288, 184, 4, 32, "Input"],
Cell[12154, 294, 1840, 28, 201, InheritFromParent],
Cell[CellGroupData[{
Cell[14019, 326, 563, 13, 32, "Input"],
Cell[14585, 341, 696, 11, 54, "Output"]
}, Open ]]
}
]
*)
(* End of internal cache information *)