src/advent06/advent06.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": 2,
  16    "metadata": {},
  17    "outputs": [],
  18    "source": [
  19     "import qualified Data.Vector as V\n",
  20     "import Data.Vector ((//), (!))\n",
  21     "import Data.List (unfoldr)\n",
  22     "import qualified Data.Map.Strict as M"
  23    ]
  24   },
  25   {
  26    "cell_type": "code",
  27    "execution_count": 3,
  28    "metadata": {},
  29    "outputs": [],
  30    "source": [
  31     "type Memory = V.Vector Int\n",
  32     "type Redist = (Int, Int, Memory)\n",
  33     "type History = M.Map Memory Int"
  34    ]
  35   },
  36   {
  37    "cell_type": "code",
  38    "execution_count": 4,
  39    "metadata": {},
  40    "outputs": [
  41     {
  42      "data": {
  43       "text/plain": [
  44        "[0,2,7,0]"
  45       ]
  46      },
  47      "metadata": {},
  48      "output_type": "display_data"
  49     }
  50    ],
  51    "source": [
  52     "vec0 = V.fromList [0, 2, 7, 0]\n",
  53     "vec0"
  54    ]
  55   },
  56   {
  57    "cell_type": "code",
  58    "execution_count": 5,
  59    "metadata": {},
  60    "outputs": [],
  61    "source": [
  62     "redistStart :: Memory -> Redist\n",
  63     "redistStart vec0 = (current, toDistribute, startVec)\n",
  64     "    where origin = V.maxIndex vec0\n",
  65     "          toDistribute = vec0!origin\n",
  66     "          current = (origin + 1) `mod` (length vec0)\n",
  67     "          startVec = vec0 // [(origin, 0)]"
  68    ]
  69   },
  70   {
  71    "cell_type": "code",
  72    "execution_count": 6,
  73    "metadata": {},
  74    "outputs": [
  75     {
  76      "data": {
  77       "text/plain": [
  78        "(3,7,[0,2,0,0])"
  79       ]
  80      },
  81      "metadata": {},
  82      "output_type": "display_data"
  83     }
  84    ],
  85    "source": [
  86     "redistStart $ V.fromList [0, 2, 7, 0]"
  87    ]
  88   },
  89   {
  90    "cell_type": "code",
  91    "execution_count": 7,
  92    "metadata": {},
  93    "outputs": [],
  94    "source": [
  95     "redistR :: Redist -> Memory\n",
  96     "redistR (_, 0, vec) = vec\n",
  97     "redistR (i, n, vec) = redistR (i', n', vec')\n",
  98     "    where n' = n - 1\n",
  99     "          i' = (i + 1) `mod` (length vec)\n",
 100     "          vec' = vec // [(i, vec!i + 1)]"
 101    ]
 102   },
 103   {
 104    "cell_type": "code",
 105    "execution_count": 8,
 106    "metadata": {},
 107    "outputs": [],
 108    "source": [
 109     "redist = redistR . redistStart"
 110    ]
 111   },
 112   {
 113    "cell_type": "code",
 114    "execution_count": 9,
 115    "metadata": {},
 116    "outputs": [
 117     {
 118      "data": {
 119       "text/plain": [
 120        "[2,4,1,2]"
 121       ]
 122      },
 123      "metadata": {},
 124      "output_type": "display_data"
 125     }
 126    ],
 127    "source": [
 128     "redist $ V.fromList [0, 2, 7, 0]"
 129    ]
 130   },
 131   {
 132    "cell_type": "code",
 133    "execution_count": 10,
 134    "metadata": {},
 135    "outputs": [
 136     {
 137      "data": {
 138       "text/plain": [
 139        "[3,1,2,3]"
 140       ]
 141      },
 142      "metadata": {},
 143      "output_type": "display_data"
 144     }
 145    ],
 146    "source": [
 147     "redist $ redist $  V.fromList [0, 2, 7, 0]"
 148    ]
 149   },
 150   {
 151    "cell_type": "code",
 152    "execution_count": 11,
 153    "metadata": {},
 154    "outputs": [],
 155    "source": [
 156     "redistSeq = unfoldr redistU\n",
 157     "    where redistU vec = Just (redist vec, redist vec)"
 158    ]
 159   },
 160   {
 161    "cell_type": "code",
 162    "execution_count": 12,
 163    "metadata": {},
 164    "outputs": [
 165     {
 166      "data": {
 167       "text/plain": [
 168        "[(0,[2,4,1,2]),(1,[3,1,2,3]),(2,[0,2,3,4]),(3,[1,3,4,1]),(4,[2,4,1,2]),(5,[3,1,2,3]),(6,[0,2,3,4]),(7,[1,3,4,1])]"
 169       ]
 170      },
 171      "metadata": {},
 172      "output_type": "display_data"
 173     }
 174    ],
 175    "source": [
 176     "take 8 $ zip [0..] $ redistSeq $ V.fromList [0, 2, 7, 0]"
 177    ]
 178   },
 179   {
 180    "cell_type": "code",
 181    "execution_count": 13,
 182    "metadata": {},
 183    "outputs": [],
 184    "source": [
 185     "findRepeat :: History -> [(Int, Memory)] -> Int\n",
 186     "findRepeat h ((n, x) : nxs) = if x `M.member` h \n",
 187     "                              then n + 1\n",
 188     "                              else findRepeat (M.insert x n h) nxs\n",
 189     "    where n0 = (M.!) h x"
 190    ]
 191   },
 192   {
 193    "cell_type": "code",
 194    "execution_count": 26,
 195    "metadata": {},
 196    "outputs": [],
 197    "source": [
 198     "findRepeatB :: History -> [(Int, Memory)] -> Int\n",
 199     "findRepeatB h ((n, x) : nxs) = if x `M.member` h \n",
 200     "                              then n - n0\n",
 201     "                              else findRepeatB (M.insert x n h) nxs\n",
 202     "    where n0 = (M.!) h x"
 203    ]
 204   },
 205   {
 206    "cell_type": "code",
 207    "execution_count": 27,
 208    "metadata": {},
 209    "outputs": [
 210     {
 211      "data": {
 212       "text/plain": [
 213        "5"
 214       ]
 215      },
 216      "metadata": {},
 217      "output_type": "display_data"
 218     }
 219    ],
 220    "source": [
 221     "findRepeat M.empty $ zip [0..] $ redistSeq $ V.fromList [0, 2, 7, 0]"
 222    ]
 223   },
 224   {
 225    "cell_type": "code",
 226    "execution_count": 28,
 227    "metadata": {},
 228    "outputs": [],
 229    "source": [
 230     "part1 :: [Int] -> Int\n",
 231     "-- part1 memlist = findRepeat M.empty $ zip [0..] $ redistSeq $ V.fromList memlist\n",
 232     "part1 = (findRepeat M.empty) . (zip [0..]) . redistSeq . V.fromList"
 233    ]
 234   },
 235   {
 236    "cell_type": "code",
 237    "execution_count": 29,
 238    "metadata": {},
 239    "outputs": [],
 240    "source": [
 241     "part2 :: [Int] -> Int\n",
 242     "-- part1 memlist = findRepeat M.empty $ zip [0..] $ redistSeq $ V.fromList memlist\n",
 243     "part2 = (findRepeatB M.empty) . (zip [0..]) . redistSeq . V.fromList"
 244    ]
 245   },
 246   {
 247    "cell_type": "code",
 248    "execution_count": 30,
 249    "metadata": {},
 250    "outputs": [],
 251    "source": [
 252     "main :: IO ()\n",
 253     "main = do \n",
 254     "        text <- readFile \"../../data/advent06.txt\"\n",
 255     "--         text0 <- readFile \"../../data/advent06.txt\"\n",
 256     "--         let text = \"0 2 7 0\"\n",
 257     "        let memory = map read $ words text\n",
 258     "        print $ part1 memory\n",
 259     "        print $ part2 memory"
 260    ]
 261   },
 262   {
 263    "cell_type": "code",
 264    "execution_count": 31,
 265    "metadata": {},
 266    "outputs": [
 267     {
 268      "data": {
 269       "text/plain": [
 270        "7864\n",
 271        "1695"
 272       ]
 273      },
 274      "metadata": {},
 275      "output_type": "display_data"
 276     }
 277    ],
 278    "source": [
 279     "main"
 280    ]
 281   },
 282   {
 283    "cell_type": "code",
 284    "execution_count": null,
 285    "metadata": {},
 286    "outputs": [],
 287    "source": []
 288   }
 289  ],
 290  "metadata": {
 291   "kernelspec": {
 292    "display_name": "Haskell",
 293    "language": "haskell",
 294    "name": "haskell"
 295   },
 296   "language_info": {
 297    "codemirror_mode": "ihaskell",
 298    "file_extension": ".hs",
 299    "name": "haskell",
 300    "version": "8.0.2"
 301   }
 302  },
 303  "nbformat": 4,
 304  "nbformat_minor": 2
 305 }