Day 14 part 1

diff --git a/src/advent14/advent14.hs b/src/advent14/advent14.hs
new file mode 100644 (file)
index 0000000..940fe7b
--- /dev/null
+++ b/src/advent14/advent14.hs
@@ -0,0 +1,60 @@
+import Data.List.Split (chunksOf)
+import Data.Char (ord)
+import Text.Printf (printf)
+import Data.Bits (xor)
+
+puzzleKey = "xlqgujun"
+
+
+part1 :: String -> Int
+part1 key = sum rowCounts
+    where hashes = map knotHash $ rowSpecs key
+          rowCounts = map (countSetBits . binify) hashes
+
+rowSpecs :: String -> [String]
+rowSpecs key = map (((key ++ "-") ++) . show) [0..127]
+
+countSetBits :: String -> Int
+countSetBits = length . filter (== '1')
+
+
+knotHash :: String -> [Int]
+knotHash input = densify tied
+    where (tied, _, _) = foldl step ([0..255], 0, 0) hashTerms
+          hashTerms = mkHashTerms input
+
+step :: ([Int], Int, Int) -> Int -> ([Int], Int, Int)
+step (original, start, skip) len = (replaced, start', skip + 1)
+    where replaced = tie original start len
+          start' = (start + len + skip) `mod` (length original)
+
+tie :: [a] -> Int -> Int -> [a]
+tie original start len = replace original replacement start
+    where replacement = reverse $ extract original start len
+
+extract :: [a] -> Int -> Int -> [a]
+extract items from len = take len $ drop from $ items ++ items
+
+replace :: [a] -> [a] -> Int -> [a]
+replace original replacement from = take (length original) (start ++ replacement ++ remainder)
+    where excess = drop (length original - from) replacement
+          stub = drop (length excess) original
+          start = take from (excess ++ stub)
+          remainder = drop (length $ start ++ replacement) original 
+
+
+mkHashTerms :: String -> [Int]
+mkHashTerms text = take (length chunk * 64) $ cycle chunk
+    where chunk = map ord text ++ [17, 31, 73, 47, 23]
+
+hexify :: [Int] -> String
+hexify = concatMap (printf "%02x")
+
+binify :: [Int] -> String
+binify = concatMap (printf "%08b")
+
+densify :: [Int] -> [Int]
+densify ns = codes
+    where chunks = chunksOf 16 ns
+          compress = foldl1 xor
+          codes = map compress chunks
\ No newline at end of file

diff --git a/src/advent14/advent14.ipynb b/src/advent14/advent14.ipynb
new file mode 100644 (file)
index 0000000..c4d69b6
--- /dev/null
+++ b/src/advent14/advent14.ipynb
@@ -0,0 +1,267 @@
+{
+ "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
+}