src/advent14/advent14.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "code",
   5    "execution_count": 1,
   6    "metadata": {},
   7    "outputs": [],
   8    "source": [
   9     "{-# LANGUAGE NegativeLiterals #-}\n",
  10     "{-# LANGUAGE FlexibleContexts #-}"
  11    ]
  12   },
  13   {
  14    "cell_type": "code",
  15    "execution_count": 34,
  16    "metadata": {},
  17    "outputs": [],
  18    "source": [
  19     "puzzleKey = \"xlqgujun\""
  20    ]
  21   },
  22   {
  23    "cell_type": "code",
  24    "execution_count": 39,
  25    "metadata": {},
  26    "outputs": [],
  27    "source": [
  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"
  33    ]
  34   },
  35   {
  36    "cell_type": "code",
  37    "execution_count": 19,
  38    "metadata": {},
  39    "outputs": [],
  40    "source": [
  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",
  45     "\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",
  50     "\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",
  54     "\n",
  55     "extract :: [a] -> Int -> Int -> [a]\n",
  56     "extract items from len = take len $ drop from $ items ++ items\n",
  57     "\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",
  64     "\n",
  65     "\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",
  69     "\n",
  70     "hexify :: [Int] -> String\n",
  71     "hexify = concatMap (printf \"%02x\")\n",
  72     "\n",
  73     "binify :: [Int] -> String\n",
  74     "binify = concatMap (printf \"%08b\")\n",
  75     "\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"
  81    ]
  82   },
  83   {
  84    "cell_type": "code",
  85    "execution_count": 18,
  86    "metadata": {},
  87    "outputs": [
  88     {
  89      "data": {
  90       "text/plain": [
  91        "\"d4f76bdcbf838f8416ccfa8bc6d1f9e6\""
  92       ]
  93      },
  94      "metadata": {},
  95      "output_type": "display_data"
  96     }
  97    ],
  98    "source": [
  99     "hexify $ knotHash \"flqrgnkx-0\""
 100    ]
 101   },
 102   {
 103    "cell_type": "markdown",
 104    "metadata": {},
 105    "source": [
 106     "```\n",
 107     "##.#.#..-->\n",
 108     ".#.#.#.#   \n",
 109     "....#.#.   \n",
 110     "#.#.##.#   \n",
 111     ".##.#...   \n",
 112     "##..#..#   \n",
 113     ".#...#..   \n",
 114     "##.#.##.-->\n",
 115     "|      |   \n",
 116     "V      V   \n",
 117     "```"
 118    ]
 119   },
 120   {
 121    "cell_type": "code",
 122    "execution_count": 23,
 123    "metadata": {},
 124    "outputs": [
 125     {
 126      "data": {
 127       "text/plain": [
 128        "\"00001010\""
 129       ]
 130      },
 131      "metadata": {},
 132      "output_type": "display_data"
 133     }
 134    ],
 135    "source": [
 136     "take 8 $ binify $ knotHash \"flqrgnkx-2\""
 137    ]
 138   },
 139   {
 140    "cell_type": "code",
 141    "execution_count": 31,
 142    "metadata": {},
 143    "outputs": [],
 144    "source": [
 145     "countSetBits = length . filter (== '1')"
 146    ]
 147   },
 148   {
 149    "cell_type": "code",
 150    "execution_count": 32,
 151    "metadata": {},
 152    "outputs": [
 153     {
 154      "data": {
 155       "text/plain": [
 156        "68"
 157       ]
 158      },
 159      "metadata": {},
 160      "output_type": "display_data"
 161     }
 162    ],
 163    "source": [
 164     "countSetBits $ binify $ knotHash \"flqrgnkx-2\""
 165    ]
 166   },
 167   {
 168    "cell_type": "code",
 169    "execution_count": 26,
 170    "metadata": {},
 171    "outputs": [
 172     {
 173      "data": {
 174       "text/plain": [
 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\"]"
 176       ]
 177      },
 178      "metadata": {},
 179      "output_type": "display_data"
 180     }
 181    ],
 182    "source": [
 183     "map ((\"flqrgnkx-\" ++) . show) [0..20]"
 184    ]
 185   },
 186   {
 187    "cell_type": "code",
 188    "execution_count": 33,
 189    "metadata": {},
 190    "outputs": [],
 191    "source": [
 192     "rowSpecs key = map (((key ++ \"-\") ++) . show) [0..127]"
 193    ]
 194   },
 195   {
 196    "cell_type": "code",
 197    "execution_count": 36,
 198    "metadata": {},
 199    "outputs": [],
 200    "source": [
 201     "part1 key = sum rowCounts\n",
 202     "    where hashes = map knotHash $ rowSpecs key\n",
 203     "          rowCounts = map (countSetBits . binify) hashes"
 204    ]
 205   },
 206   {
 207    "cell_type": "code",
 208    "execution_count": 37,
 209    "metadata": {},
 210    "outputs": [
 211     {
 212      "data": {
 213       "text/plain": [
 214        "8108"
 215       ]
 216      },
 217      "metadata": {},
 218      "output_type": "display_data"
 219     }
 220    ],
 221    "source": [
 222     "part1 \"flqrgnkx\""
 223    ]
 224   },
 225   {
 226    "cell_type": "code",
 227    "execution_count": 38,
 228    "metadata": {},
 229    "outputs": [
 230     {
 231      "data": {
 232       "text/plain": [
 233        "8204"
 234       ]
 235      },
 236      "metadata": {},
 237      "output_type": "display_data"
 238     }
 239    ],
 240    "source": [
 241     "part1 puzzleKey"
 242    ]
 243   },
 244   {
 245    "cell_type": "code",
 246    "execution_count": null,
 247    "metadata": {},
 248    "outputs": [],
 249    "source": []
 250   }
 251  ],
 252  "metadata": {
 253   "kernelspec": {
 254    "display_name": "Haskell",
 255    "language": "haskell",
 256    "name": "haskell"
 257   },
 258   "language_info": {
 259    "codemirror_mode": "ihaskell",
 260    "file_extension": ".hs",
 261    "name": "haskell",
 262    "version": "8.0.2"
 263   }
 264  },
 265  "nbformat": 4,
 266  "nbformat_minor": 2
 267 }