+{
+ "cells": [
+ {
+ "cell_type": "code",
+ "execution_count": 1,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "{-# LANGUAGE NegativeLiterals #-}\n",
+ "{-# LANGUAGE FlexibleContexts #-}"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 34,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "puzzleKey = \"xlqgujun\""
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 39,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "import Data.List.Split (chunksOf)\n",
+ "import Data.Char (ord)\n",
+ "import Text.Printf (printf)\n",
+ "import Data.Bits (xor)\n",
+ "import qualified Data.Graph as G"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 19,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "knotHash :: String -> [Int]\n",
+ "knotHash input = densify tied\n",
+ " where (tied, _, _) = foldl step ([0..255], 0, 0) hashTerms\n",
+ " hashTerms = mkHashTerms input\n",
+ "\n",
+ "step :: ([Int], Int, Int) -> Int -> ([Int], Int, Int)\n",
+ "step (original, start, skip) len = (replaced, start', skip + 1)\n",
+ " where replaced = tie original start len\n",
+ " start' = (start + len + skip) `mod` (length original)\n",
+ "\n",
+ "tie :: [a] -> Int -> Int -> [a]\n",
+ "tie original start len = replace original replacement start\n",
+ " where replacement = reverse $ extract original start len\n",
+ "\n",
+ "extract :: [a] -> Int -> Int -> [a]\n",
+ "extract items from len = take len $ drop from $ items ++ items\n",
+ "\n",
+ "replace :: [a] -> [a] -> Int -> [a]\n",
+ "replace original replacement from = take (length original) (start ++ replacement ++ remainder)\n",
+ " where excess = drop (length original - from) replacement\n",
+ " stub = drop (length excess) original\n",
+ " start = take from (excess ++ stub)\n",
+ " remainder = drop (length $ start ++ replacement) original \n",
+ "\n",
+ "\n",
+ "mkHashTerms :: String -> [Int]\n",
+ "mkHashTerms text = take (length chunk * 64) $ cycle chunk\n",
+ " where chunk = map ord text ++ [17, 31, 73, 47, 23]\n",
+ "\n",
+ "hexify :: [Int] -> String\n",
+ "hexify = concatMap (printf \"%02x\")\n",
+ "\n",
+ "binify :: [Int] -> String\n",
+ "binify = concatMap (printf \"%08b\")\n",
+ "\n",
+ "densify :: [Int] -> [Int]\n",
+ "densify ns = codes\n",
+ " where chunks = chunksOf 16 ns\n",
+ " compress = foldl1 xor\n",
+ " codes = map compress chunks"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 18,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "\"d4f76bdcbf838f8416ccfa8bc6d1f9e6\""
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "hexify $ knotHash \"flqrgnkx-0\""
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "```\n",
+ "##.#.#..-->\n",
+ ".#.#.#.# \n",
+ "....#.#. \n",
+ "#.#.##.# \n",
+ ".##.#... \n",
+ "##..#..# \n",
+ ".#...#.. \n",
+ "##.#.##.-->\n",
+ "| | \n",
+ "V V \n",
+ "```"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 23,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "\"00001010\""
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "take 8 $ binify $ knotHash \"flqrgnkx-2\""
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 31,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "countSetBits = length . filter (== '1')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 32,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "68"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "countSetBits $ binify $ knotHash \"flqrgnkx-2\""
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 26,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[\"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\"]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "map ((\"flqrgnkx-\" ++) . show) [0..20]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 33,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "rowSpecs key = map (((key ++ \"-\") ++) . show) [0..127]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 36,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "part1 key = sum rowCounts\n",
+ " where hashes = map knotHash $ rowSpecs key\n",
+ " rowCounts = map (countSetBits . binify) hashes"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 37,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "8108"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "part1 \"flqrgnkx\""
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 38,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "8204"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "part1 puzzleKey"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {},
+ "outputs": [],
+ "source": []
+ }
+ ],
+ "metadata": {
+ "kernelspec": {
+ "display_name": "Haskell",
+ "language": "haskell",
+ "name": "haskell"
+ },
+ "language_info": {
+ "codemirror_mode": "ihaskell",
+ "file_extension": ".hs",
+ "name": "haskell",
+ "version": "8.0.2"
+ }
+ },
+ "nbformat": 4,
+ "nbformat_minor": 2
+}