--- /dev/null
+{
+ "cells": [
+ {
+ "cell_type": "code",
+ "execution_count": 1,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "{-# LANGUAGE NegativeLiterals #-}\n",
+ "{-# LANGUAGE FlexibleContexts #-}"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 2,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "import qualified Data.Vector as V\n",
+ "import Data.Vector ((//), (!))\n",
+ "import Data.List (unfoldr)\n",
+ "import qualified Data.Map.Strict as M"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 3,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "type Memory = V.Vector Int\n",
+ "type Redist = (Int, Int, Memory)\n",
+ "type History = M.Map Memory Int"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 4,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[0,2,7,0]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "vec0 = V.fromList [0, 2, 7, 0]\n",
+ "vec0"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 5,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "redistStart :: Memory -> Redist\n",
+ "redistStart vec0 = (current, toDistribute, startVec)\n",
+ " where origin = V.maxIndex vec0\n",
+ " toDistribute = vec0!origin\n",
+ " current = (origin + 1) `mod` (length vec0)\n",
+ " startVec = vec0 // [(origin, 0)]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 6,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "(3,7,[0,2,0,0])"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "redistStart $ V.fromList [0, 2, 7, 0]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 7,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "redistR :: Redist -> Memory\n",
+ "redistR (_, 0, vec) = vec\n",
+ "redistR (i, n, vec) = redistR (i', n', vec')\n",
+ " where n' = n - 1\n",
+ " i' = (i + 1) `mod` (length vec)\n",
+ " vec' = vec // [(i, vec!i + 1)]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 8,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "redist = redistR . redistStart"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 9,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[2,4,1,2]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "redist $ V.fromList [0, 2, 7, 0]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 10,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[3,1,2,3]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "redist $ redist $ V.fromList [0, 2, 7, 0]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 11,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "redistSeq = unfoldr redistU\n",
+ " where redistU vec = Just (redist vec, redist vec)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 12,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[(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])]"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "take 8 $ zip [0..] $ redistSeq $ V.fromList [0, 2, 7, 0]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 13,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "findRepeat :: History -> [(Int, Memory)] -> Int\n",
+ "findRepeat h ((n, x) : nxs) = if x `M.member` h \n",
+ " then n + 1\n",
+ " else findRepeat (M.insert x n h) nxs\n",
+ " where n0 = (M.!) h x"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 26,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "findRepeatB :: History -> [(Int, Memory)] -> Int\n",
+ "findRepeatB h ((n, x) : nxs) = if x `M.member` h \n",
+ " then n - n0\n",
+ " else findRepeatB (M.insert x n h) nxs\n",
+ " where n0 = (M.!) h x"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 27,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "5"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "findRepeat M.empty $ zip [0..] $ redistSeq $ V.fromList [0, 2, 7, 0]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 28,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "part1 :: [Int] -> Int\n",
+ "-- part1 memlist = findRepeat M.empty $ zip [0..] $ redistSeq $ V.fromList memlist\n",
+ "part1 = (findRepeat M.empty) . (zip [0..]) . redistSeq . V.fromList"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 29,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "part2 :: [Int] -> Int\n",
+ "-- part1 memlist = findRepeat M.empty $ zip [0..] $ redistSeq $ V.fromList memlist\n",
+ "part2 = (findRepeatB M.empty) . (zip [0..]) . redistSeq . V.fromList"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 30,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "main :: IO ()\n",
+ "main = do \n",
+ " text <- readFile \"../../data/advent06.txt\"\n",
+ "-- text0 <- readFile \"../../data/advent06.txt\"\n",
+ "-- let text = \"0 2 7 0\"\n",
+ " let memory = map read $ words text\n",
+ " print $ part1 memory\n",
+ " print $ part2 memory"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 31,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "7864\n",
+ "1695"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "main"
+ ]
+ },
+ {
+ "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
+}
projects / advent-of-code-17.git / blobdiff