9 "{-# LANGUAGE NegativeLiterals #-}\n",
10 "{-# LANGUAGE FlexibleContexts #-}"
15 "execution_count": 34,
19 "puzzleKey = \"xlqgujun\""
24 "execution_count": 39,
28 "import Data.List.Split (chunksOf)\n",
29 "import Data.Char (ord)\n",
30 "import Text.Printf (printf)\n",
31 "import Data.Bits (xor)\n",
32 "import qualified Data.Graph as G"
37 "execution_count": 19,
41 "knotHash :: String -> [Int]\n",
42 "knotHash input = densify tied\n",
43 " where (tied, _, _) = foldl step ([0..255], 0, 0) hashTerms\n",
44 " hashTerms = mkHashTerms input\n",
46 "step :: ([Int], Int, Int) -> Int -> ([Int], Int, Int)\n",
47 "step (original, start, skip) len = (replaced, start', skip + 1)\n",
48 " where replaced = tie original start len\n",
49 " start' = (start + len + skip) `mod` (length original)\n",
51 "tie :: [a] -> Int -> Int -> [a]\n",
52 "tie original start len = replace original replacement start\n",
53 " where replacement = reverse $ extract original start len\n",
55 "extract :: [a] -> Int -> Int -> [a]\n",
56 "extract items from len = take len $ drop from $ items ++ items\n",
58 "replace :: [a] -> [a] -> Int -> [a]\n",
59 "replace original replacement from = take (length original) (start ++ replacement ++ remainder)\n",
60 " where excess = drop (length original - from) replacement\n",
61 " stub = drop (length excess) original\n",
62 " start = take from (excess ++ stub)\n",
63 " remainder = drop (length $ start ++ replacement) original \n",
66 "mkHashTerms :: String -> [Int]\n",
67 "mkHashTerms text = take (length chunk * 64) $ cycle chunk\n",
68 " where chunk = map ord text ++ [17, 31, 73, 47, 23]\n",
70 "hexify :: [Int] -> String\n",
71 "hexify = concatMap (printf \"%02x\")\n",
73 "binify :: [Int] -> String\n",
74 "binify = concatMap (printf \"%08b\")\n",
76 "densify :: [Int] -> [Int]\n",
77 "densify ns = codes\n",
78 " where chunks = chunksOf 16 ns\n",
79 " compress = foldl1 xor\n",
80 " codes = map compress chunks"
85 "execution_count": 18,
91 "\"d4f76bdcbf838f8416ccfa8bc6d1f9e6\""
95 "output_type": "display_data"
99 "hexify $ knotHash \"flqrgnkx-0\""
103 "cell_type": "markdown",
122 "execution_count": 23,
132 "output_type": "display_data"
136 "take 8 $ binify $ knotHash \"flqrgnkx-2\""
141 "execution_count": 31,
145 "countSetBits = length . filter (== '1')"
150 "execution_count": 32,
160 "output_type": "display_data"
164 "countSetBits $ binify $ knotHash \"flqrgnkx-2\""
169 "execution_count": 26,
175 "[\"flqrgnkx-0\",\"flqrgnkx-1\",\"flqrgnkx-2\",\"flqrgnkx-3\",\"flqrgnkx-4\",\"flqrgnkx-5\",\"flqrgnkx-6\",\"flqrgnkx-7\",\"flqrgnkx-8\",\"flqrgnkx-9\",\"flqrgnkx-10\",\"flqrgnkx-11\",\"flqrgnkx-12\",\"flqrgnkx-13\",\"flqrgnkx-14\",\"flqrgnkx-15\",\"flqrgnkx-16\",\"flqrgnkx-17\",\"flqrgnkx-18\",\"flqrgnkx-19\",\"flqrgnkx-20\"]"
179 "output_type": "display_data"
183 "map ((\"flqrgnkx-\" ++) . show) [0..20]"
188 "execution_count": 33,
192 "rowSpecs key = map (((key ++ \"-\") ++) . show) [0..127]"
197 "execution_count": 36,
201 "part1 key = sum rowCounts\n",
202 " where hashes = map knotHash $ rowSpecs key\n",
203 " rowCounts = map (countSetBits . binify) hashes"
208 "execution_count": 37,
218 "output_type": "display_data"
227 "execution_count": 38,
237 "output_type": "display_data"
246 "execution_count": null,
254 "display_name": "Haskell",
255 "language": "haskell",
259 "codemirror_mode": "ihaskell",
260 "file_extension": ".hs",