{
 "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
}