From b59695dbe975d1883d1e8a26203c8ba43c94e931 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Wed, 6 Dec 2017 22:14:25 +0000 Subject: [PATCH] Day 6 --- advent-of-code.cabal | 9 ++ data/advent06.txt | 1 + src/advent06/advent06.hs | 56 +++++++ src/advent06/advent06.ipynb | 305 ++++++++++++++++++++++++++++++++++++ 4 files changed, 371 insertions(+) create mode 100644 data/advent06.txt create mode 100644 src/advent06/advent06.hs create mode 100644 src/advent06/advent06.ipynb diff --git a/advent-of-code.cabal b/advent-of-code.cabal index 6808b0c..341fc23 100644 --- a/advent-of-code.cabal +++ b/advent-of-code.cabal @@ -61,3 +61,12 @@ executable advent05 build-depends: base >= 4.7 && < 5 , containers , mtl + +executable advent06 + hs-source-dirs: src/advent06 + main-is: advent06.hs + default-language: Haskell2010 + build-depends: base >= 4.7 && < 5 + , containers + , vector + diff --git a/data/advent06.txt b/data/advent06.txt new file mode 100644 index 0000000..ec2afd2 --- /dev/null +++ b/data/advent06.txt @@ -0,0 +1 @@ +0 5 10 0 11 14 13 4 11 8 8 7 1 4 12 11 \ No newline at end of file diff --git a/src/advent06/advent06.hs b/src/advent06/advent06.hs new file mode 100644 index 0000000..34c4840 --- /dev/null +++ b/src/advent06/advent06.hs @@ -0,0 +1,56 @@ +import qualified Data.Vector as V +import Data.Vector ((//), (!)) +import Data.List (unfoldr) +import qualified Data.Map.Strict as M + +type Memory = V.Vector Int +type Redist = (Int, Int, Memory) +type History = M.Map Memory Int + +main :: IO () +main = do + text <- readFile "data/advent06.txt" + let memory = map read $ words text + print $ part1 memory + print $ part2 memory + +part1 :: [Int] -> Int +part1 = (findRepeat M.empty) . (zip [0..]) . redistSeq . V.fromList + +part2 :: [Int] -> Int +part2 = (findRepeatB M.empty) . (zip [0..]) . redistSeq . V.fromList + +findRepeat :: History -> [(Int, Memory)] -> Int +findRepeat h ((n, x) : nxs) = if x `M.member` h + then n + 1 + else findRepeat (M.insert x n h) nxs + +findRepeatB :: History -> [(Int, Memory)] -> Int +findRepeatB h ((n, x) : nxs) = if x `M.member` h + then n - n0 + else findRepeatB (M.insert x n h) nxs + where n0 = (M.!) h x + + +redistSeq :: Memory -> [Memory] +redistSeq = unfoldr redistU + where redistU vec = Just (redist vec, redist vec) + +redist :: Memory -> Memory +redist = redistR . redistStart + + + +redistStart :: Memory -> Redist +redistStart vec0 = (current, toDistribute, startVec) + where origin = V.maxIndex vec0 + toDistribute = vec0!origin + current = (origin + 1) `mod` (length vec0) + startVec = vec0 // [(origin, 0)] + +redistR :: Redist -> Memory +redistR (_, 0, vec) = vec +redistR (i, n, vec) = redistR (i', n', vec') + where n' = n - 1 + i' = (i + 1) `mod` (length vec) + vec' = vec // [(i, vec!i + 1)] \ No newline at end of file diff --git a/src/advent06/advent06.ipynb b/src/advent06/advent06.ipynb new file mode 100644 index 0000000..5896273 --- /dev/null +++ b/src/advent06/advent06.ipynb @@ -0,0 +1,305 @@ +{ + "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 +} -- 2.34.1