From 56a472b8d4126a5f146a655662d867d5c32a783a Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Mon, 4 Dec 2017 09:47:25 +0000 Subject: [PATCH] Day 3 --- src/advent03/advent03.hs | 79 ++ src/advent03/advent03.ipynb | 1509 +++++++++++++++++++++++++++++++++++ 2 files changed, 1588 insertions(+) create mode 100644 src/advent03/advent03.hs create mode 100644 src/advent03/advent03.ipynb diff --git a/src/advent03/advent03.hs b/src/advent03/advent03.hs new file mode 100644 index 0000000..e7348e4 --- /dev/null +++ b/src/advent03/advent03.hs @@ -0,0 +1,79 @@ +import Data.List (tails) +import qualified Data.HashMap.Strict as M +import Data.HashMap.Strict ((!)) +import Control.Monad.State.Lazy + +type Location = (Int, Int) +type Memory = M.HashMap Location Int + +target :: Int +target = 347991 + +main :: IO () +main = do + print $ part1 + print $ part2 + + +diagonal :: Int -> [Int] +diagonal n = scanl (+) 1 $ scanl (+) n $ repeat 8 +dr = diagonal 8 +ul = diagonal 4 +ur = diagonal 2 +dl = diagonal 6 + + +interleave :: [[a]] -> [a] +interleave ([]:_) = [] +interleave xss = map head xss ++ interleave (map tail xss) + + +countedDiags = interleave [(zip [0..] ur), (zip [0..] ul), (zip [0..] dl), (zip [0..] dr)] + +part1 = let corners = head $ dropWhile ((< target) . snd . head . tail) $ tails countedDiags + (pcd, pcv) = head corners + (ncd, ncv) = head $ tail corners + result = if pcd == ncd + then if (target - pcv + 2) < ncv - target + then pcd * 2 - (target - pcv) + else ncd * 2 - (ncv - target) + else if (target - pcv + 1) < ncv - target + then pcd * 2 - (target - pcv) + 2 + else ncd * 2 - (ncv - target) + in result + + +part2 = (!) memoryValues $ head $ dropWhile (\l -> memoryValues!l <= target) locations + where memoryValues = execState (updateMemory (take 100 $ drop 1 locations)) emptyMemory + +up (a, b) = (a, b + 1) +down (a, b) = (a, b - 1) +left (a, b) = (a - 1, b) +right (a, b) = (a + 1, b) +directions = [right, up, left, down] + +locations = scanl (\c f -> f c) (0,0) $ concat $ zipWith replicate steps (cycle directions) + where + steps = concat $ zipWith (\a b -> [a,b]) [1..] [1..] + +adjacentMap (r, c) = M.filterWithKey adjacent + where adjacent k _ = abs (fst k - r) <= 1 && abs (snd k - c) <= 1 + +adjacentMapSum here = M.foldr (+) 0 . adjacentMap here + + +emptyMemory = M.singleton (0, 0) 1 + +updateMemoryOnce :: Location -> State Memory Int +updateMemoryOnce here = + do m0 <- get + let total = adjacentMapSum here m0 + put (M.insert here total m0) + return total + +updateMemory :: [Location] -> State Memory Int +updateMemory [] = do return 0 +updateMemory (l:ls) = + do updateMemoryOnce l + updateMemory ls + diff --git a/src/advent03/advent03.ipynb b/src/advent03/advent03.ipynb new file mode 100644 index 0000000..f06014d --- /dev/null +++ b/src/advent03/advent03.ipynb @@ -0,0 +1,1509 @@ +{ + "cells": [ + { + "cell_type": "code", + "execution_count": 1, + "metadata": {}, + "outputs": [], + "source": [ + "{-# LANGUAGE FlexibleContexts #-}\n", + "{-# LANGUAGE MultiWayIf #-}" + ] + }, + { + "cell_type": "code", + "execution_count": 2, + "metadata": {}, + "outputs": [], + "source": [ + "import Data.List (tails)\n", + "import qualified Data.HashMap.Strict as M\n", + "import Data.HashMap.Strict ((!))\n", + "import Control.Monad.State.Lazy" + ] + }, + { + "cell_type": "code", + "execution_count": 3, + "metadata": {}, + "outputs": [], + "source": [ + "offsets2 = repeat 8" + ] + }, + { + "cell_type": "code", + "execution_count": 4, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[8,8,8]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "take 3 offsets2" + ] + }, + { + "cell_type": "code", + "execution_count": 5, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[8,16,24]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "take 3 $ scanl (+) 8 offsets2" + ] + }, + { + "cell_type": "code", + "execution_count": 6, + "metadata": {}, + "outputs": [], + "source": [ + "diagonal n = scanl (+) 1 $ scanl (+) n $ repeat 8" + ] + }, + { + "cell_type": "code", + "execution_count": 7, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[1,9,25,49,81]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "dr = diagonal 8\n", + "take 5 dr" + ] + }, + { + "cell_type": "code", + "execution_count": 8, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[1,5,17,37,65]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "ul = diagonal 4\n", + "take 5 ul" + ] + }, + { + "cell_type": "code", + "execution_count": 9, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[1,3,13,31,57]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "ur = diagonal 2\n", + "take 5 ur" + ] + }, + { + "cell_type": "code", + "execution_count": 10, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[1,7,21,43,73]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "dl = diagonal 6\n", + "take 5 dl" + ] + }, + { + "cell_type": "code", + "execution_count": 11, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "73" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "dl!!4" + ] + }, + { + "cell_type": "code", + "execution_count": 12, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "(4,73)" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "head $ dropWhile ((< 70) . snd) $ zip [0..] dl" + ] + }, + { + "cell_type": "code", + "execution_count": 13, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "(4,81)" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "head $ dropWhile ((< 70) . snd) $ zip [0..] dr" + ] + }, + { + "cell_type": "code", + "execution_count": 14, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[0,1,2]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "take 3 [0..]" + ] + }, + { + "cell_type": "code", + "execution_count": 15, + "metadata": {}, + "outputs": [], + "source": [ + "interleave4 (p:ps) (q:qs) (r:rs) (s:ss) = p:q:r:s:interleave4 ps qs rs ss" + ] + }, + { + "cell_type": "code", + "execution_count": 16, + "metadata": {}, + "outputs": [], + "source": [ + "interleave ([]:_) = []\n", + "interleave xss = map head xss ++ interleave (map tail xss)" + ] + }, + { + "cell_type": "code", + "execution_count": 17, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[(0,1),(1,3),(1,5),(1,7),(1,9),(2,13),(2,17),(2,21),(2,25),(3,31),(3,37),(3,43),(3,49),(4,57),(4,65),(4,73),(4,81),(5,91),(5,101),(5,111)]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "take 20 $ drop 3 $ interleave4 (zip [0..] ur) (zip [0..] ul) (zip [0..] dl) (zip [0..] dr)" + ] + }, + { + "cell_type": "code", + "execution_count": 18, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[1,1,1,1]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "map head [ur, ul, dl, dr]" + ] + }, + { + "cell_type": "code", + "execution_count": 19, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[[3,13],[5,17],[7,21],[9,25]]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "map (take 2 . tail) [ur, ul, dl, dr]" + ] + }, + { + "cell_type": "code", + "execution_count": 20, + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "
Redundant bracket
Found:
(map head [ur, ul, dl, dr]) : [[10, 11, 12, 13, 14, 15, 16, 17]]
Why Not:
map head [ur, ul, dl, dr] : [[10, 11, 12, 13, 14, 15, 16, 17]]
" + ], + "text/plain": [ + "Line 1: Redundant bracket\n", + "Found:\n", + "(map head [ur, ul, dl, dr]) : [[10, 11, 12, 13, 14, 15, 16, 17]]\n", + "Why not:\n", + "map head [ur, ul, dl, dr] : [[10, 11, 12, 13, 14, 15, 16, 17]]" + ] + }, + "metadata": {}, + "output_type": "display_data" + }, + { + "data": { + "text/plain": [ + "[1,1,1,1,10,11,12,13,14,15,16,17]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "concat $ (map head [ur, ul, dl, dr]) : [[10, 11, 12, 13, 14, 15, 16, 17]]" + ] + }, + { + "cell_type": "code", + "execution_count": 21, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[0,10,20,30,1,11,21,31,2,12,22,32]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "interleave [[0,1,2], [10,11,12], [20, 21, 22], [30, 31, 32]]" + ] + }, + { + "cell_type": "code", + "execution_count": 22, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[1,1,1,1,3,5,7,9,13,17,21,25,31,37,43,49,57,65,73,81]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "take 20 $ interleave [ur, ul, dl, dr]" + ] + }, + { + "cell_type": "code", + "execution_count": 23, + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "
Redundant bracket
Found:
[(zip [0 ..] ur), (zip [0 ..] ul), (zip [0 ..] dl),\n", + " (zip [0 ..] dr)]
Why Not:
[zip [0 ..] ur, (zip [0 ..] ul), (zip [0 ..] dl), (zip [0 ..] dr)]
Redundant bracket
Found:
[(zip [0 ..] ur), (zip [0 ..] ul), (zip [0 ..] dl),\n", + " (zip [0 ..] dr)]
Why Not:
[(zip [0 ..] ur), zip [0 ..] ul, (zip [0 ..] dl), (zip [0 ..] dr)]
Redundant bracket
Found:
[(zip [0 ..] ur), (zip [0 ..] ul), (zip [0 ..] dl),\n", + " (zip [0 ..] dr)]
Why Not:
[(zip [0 ..] ur), (zip [0 ..] ul), zip [0 ..] dl, (zip [0 ..] dr)]
Redundant bracket
Found:
[(zip [0 ..] ur), (zip [0 ..] ul), (zip [0 ..] dl),\n", + " (zip [0 ..] dr)]
Why Not:
[(zip [0 ..] ur), (zip [0 ..] ul), (zip [0 ..] dl), zip [0 ..] dr]
" + ], + "text/plain": [ + "Line 1: Redundant bracket\n", + "Found:\n", + "[(zip [0 ..] ur), (zip [0 ..] ul), (zip [0 ..] dl),\n", + " (zip [0 ..] dr)]\n", + "Why not:\n", + "[zip [0 ..] ur, (zip [0 ..] ul), (zip [0 ..] dl), (zip [0 ..] dr)]Line 1: Redundant bracket\n", + "Found:\n", + "[(zip [0 ..] ur), (zip [0 ..] ul), (zip [0 ..] dl),\n", + " (zip [0 ..] dr)]\n", + "Why not:\n", + "[(zip [0 ..] ur), zip [0 ..] ul, (zip [0 ..] dl), (zip [0 ..] dr)]Line 1: Redundant bracket\n", + "Found:\n", + "[(zip [0 ..] ur), (zip [0 ..] ul), (zip [0 ..] dl),\n", + " (zip [0 ..] dr)]\n", + "Why not:\n", + "[(zip [0 ..] ur), (zip [0 ..] ul), zip [0 ..] dl, (zip [0 ..] dr)]Line 1: Redundant bracket\n", + "Found:\n", + "[(zip [0 ..] ur), (zip [0 ..] ul), (zip [0 ..] dl),\n", + " (zip [0 ..] dr)]\n", + "Why not:\n", + "[(zip [0 ..] ur), (zip [0 ..] ul), (zip [0 ..] dl), zip [0 ..] dr]" + ] + }, + "metadata": {}, + "output_type": "display_data" + }, + { + "data": { + "text/plain": [ + "[(0,1),(1,3),(1,5),(1,7),(1,9),(2,13),(2,17),(2,21),(2,25),(3,31),(3,37),(3,43),(3,49),(4,57),(4,65),(4,73),(4,81),(5,91),(5,101),(5,111)]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "take 20 $ drop 3 $ interleave [(zip [0..] ur), (zip [0..] ul), (zip [0..] dl), (zip [0..] dr)]" + ] + }, + { + "cell_type": "code", + "execution_count": 24, + "metadata": {}, + "outputs": [], + "source": [ + "target = 30" + ] + }, + { + "cell_type": "code", + "execution_count": 25, + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "
Redundant bracket
Found:
[(zip [0 ..] ur), (zip [0 ..] ul), (zip [0 ..] dl),\n", + " (zip [0 ..] dr)]
Why Not:
[zip [0 ..] ur, (zip [0 ..] ul), (zip [0 ..] dl), (zip [0 ..] dr)]
Redundant bracket
Found:
[(zip [0 ..] ur), (zip [0 ..] ul), (zip [0 ..] dl),\n", + " (zip [0 ..] dr)]
Why Not:
[(zip [0 ..] ur), zip [0 ..] ul, (zip [0 ..] dl), (zip [0 ..] dr)]
Redundant bracket
Found:
[(zip [0 ..] ur), (zip [0 ..] ul), (zip [0 ..] dl),\n", + " (zip [0 ..] dr)]
Why Not:
[(zip [0 ..] ur), (zip [0 ..] ul), zip [0 ..] dl, (zip [0 ..] dr)]
Redundant bracket
Found:
[(zip [0 ..] ur), (zip [0 ..] ul), (zip [0 ..] dl),\n", + " (zip [0 ..] dr)]
Why Not:
[(zip [0 ..] ur), (zip [0 ..] ul), (zip [0 ..] dl), zip [0 ..] dr]
" + ], + "text/plain": [ + "Line 1: Redundant bracket\n", + "Found:\n", + "[(zip [0 ..] ur), (zip [0 ..] ul), (zip [0 ..] dl),\n", + " (zip [0 ..] dr)]\n", + "Why not:\n", + "[zip [0 ..] ur, (zip [0 ..] ul), (zip [0 ..] dl), (zip [0 ..] dr)]Line 1: Redundant bracket\n", + "Found:\n", + "[(zip [0 ..] ur), (zip [0 ..] ul), (zip [0 ..] dl),\n", + " (zip [0 ..] dr)]\n", + "Why not:\n", + "[(zip [0 ..] ur), zip [0 ..] ul, (zip [0 ..] dl), (zip [0 ..] dr)]Line 1: Redundant bracket\n", + "Found:\n", + "[(zip [0 ..] ur), (zip [0 ..] ul), (zip [0 ..] dl),\n", + " (zip [0 ..] dr)]\n", + "Why not:\n", + "[(zip [0 ..] ur), (zip [0 ..] ul), zip [0 ..] dl, (zip [0 ..] dr)]Line 1: Redundant bracket\n", + "Found:\n", + "[(zip [0 ..] ur), (zip [0 ..] ul), (zip [0 ..] dl),\n", + " (zip [0 ..] dr)]\n", + "Why not:\n", + "[(zip [0 ..] ur), (zip [0 ..] ul), (zip [0 ..] dl), zip [0 ..] dr]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "countedDiags = interleave [(zip [0..] ur), (zip [0..] ul), (zip [0..] dl), (zip [0..] dr)]" + ] + }, + { + "cell_type": "code", + "execution_count": 26, + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "
Use guards
Found:
result\n", + " = if pcd == ncd then\n", + " if (target - pcv + 2) < ncv - target then pcd * 2 - (target - pcv)\n", + " else ncd * 2 - (ncv - target)\n", + " else\n", + " if (target - pcv + 1) < ncv - target then\n", + " pcd * 2 - (target - pcv) + 2 else ncd * 2 - (ncv - target)
Why Not:
result\n", + " | pcd == ncd =\n", + " if (target - pcv + 2) < ncv - target then pcd * 2 - (target - pcv)\n", + " else ncd * 2 - (ncv - target)\n", + " | (target - pcv + 1) < ncv - target = pcd * 2 - (target - pcv) + 2\n", + " | otherwise = ncd * 2 - (ncv - target)
Redundant bracket
Found:
(result, pcd, ncd, (target - pcv + 2), ncv - target)
Why Not:
(result, pcd, ncd, target - pcv + 2, ncv - target)
" + ], + "text/plain": [ + "Line 4: Use guards\n", + "Found:\n", + "result\n", + " = if pcd == ncd then\n", + " if (target - pcv + 2) < ncv - target then pcd * 2 - (target - pcv)\n", + " else ncd * 2 - (ncv - target)\n", + " else\n", + " if (target - pcv + 1) < ncv - target then\n", + " pcd * 2 - (target - pcv) + 2 else ncd * 2 - (ncv - target)\n", + "Why not:\n", + "result\n", + " | pcd == ncd =\n", + " if (target - pcv + 2) < ncv - target then pcd * 2 - (target - pcv)\n", + " else ncd * 2 - (ncv - target)\n", + " | (target - pcv + 1) < ncv - target = pcd * 2 - (target - pcv) + 2\n", + " | otherwise = ncd * 2 - (ncv - target)Line 12: Redundant bracket\n", + "Found:\n", + "(result, pcd, ncd, (target - pcv + 2), ncv - target)\n", + "Why not:\n", + "(result, pcd, ncd, target - pcv + 2, ncv - target)" + ] + }, + "metadata": {}, + "output_type": "display_data" + }, + { + "data": { + "text/plain": [ + "(7,4,4,3,7)" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "target = 58\n", + "let corners = head $ dropWhile ((< target) . snd . head . tail) $ tails countedDiags\n", + " (pcd, pcv) = head corners\n", + " (ncd, ncv) = head $ tail corners\n", + " result = if pcd == ncd \n", + " then if (target - pcv + 2) < ncv - target\n", + " then pcd * 2 - (target - pcv)\n", + " else ncd * 2 - (ncv - target)\n", + " else if (target - pcv + 1) < ncv - target\n", + " then pcd * 2 - (target - pcv) + 2\n", + " else ncd * 2 - (ncv - target)\n", + " \n", + " in (result, pcd, ncd, (target - pcv + 2), ncv - target)" + ] + }, + { + "cell_type": "code", + "execution_count": 27, + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "
Use guards
Found:
result\n", + " = if pcd == ncd then\n", + " if (target - pcv + 2) < ncv - target then pcd * 2 - (target - pcv)\n", + " else ncd * 2 - (ncv - target)\n", + " else\n", + " if (target - pcv + 1) < ncv - target then\n", + " pcd * 2 - (target - pcv) + 2 else ncd * 2 - (ncv - target)
Why Not:
result\n", + " | pcd == ncd =\n", + " if (target - pcv + 2) < ncv - target then pcd * 2 - (target - pcv)\n", + " else ncd * 2 - (ncv - target)\n", + " | (target - pcv + 1) < ncv - target = pcd * 2 - (target - pcv) + 2\n", + " | otherwise = ncd * 2 - (ncv - target)
" + ], + "text/plain": [ + "Line 4: Use guards\n", + "Found:\n", + "result\n", + " = if pcd == ncd then\n", + " if (target - pcv + 2) < ncv - target then pcd * 2 - (target - pcv)\n", + " else ncd * 2 - (ncv - target)\n", + " else\n", + " if (target - pcv + 1) < ncv - target then\n", + " pcd * 2 - (target - pcv) + 2 else ncd * 2 - (ncv - target)\n", + "Why not:\n", + "result\n", + " | pcd == ncd =\n", + " if (target - pcv + 2) < ncv - target then pcd * 2 - (target - pcv)\n", + " else ncd * 2 - (ncv - target)\n", + " | (target - pcv + 1) < ncv - target = pcd * 2 - (target - pcv) + 2\n", + " | otherwise = ncd * 2 - (ncv - target)" + ] + }, + "metadata": {}, + "output_type": "display_data" + }, + { + "data": { + "text/plain": [ + "480" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "target = 347991\n", + "let corners = head $ dropWhile ((< target) . snd . head . tail) $ tails countedDiags\n", + " (pcd, pcv) = head corners\n", + " (ncd, ncv) = head $ tail corners\n", + " result = if pcd == ncd \n", + " then if (target - pcv + 2) < ncv - target\n", + " then pcd * 2 - (target - pcv)\n", + " else ncd * 2 - (ncv - target)\n", + " else if (target - pcv + 1) < ncv - target\n", + " then pcd * 2 - (target - pcv) + 2\n", + " else ncd * 2 - (ncv - target)\n", + " \n", + " in result" + ] + }, + { + "cell_type": "code", + "execution_count": 28, + "metadata": {}, + "outputs": [], + "source": [ + "plainDiags = map snd countedDiags" + ] + }, + { + "cell_type": "code", + "execution_count": 29, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[1,3,5,7,9,13,17,21,25,31,37,43,49,57,65,73,81,91,101,111]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "take 20 $ drop 3 plainDiags" + ] + }, + { + "cell_type": "code", + "execution_count": 30, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "steps = concat $ zipWith (\\a b -> [a,b]) [1..] [1..]\n", + "take 20 steps" + ] + }, + { + "cell_type": "code", + "execution_count": 31, + "metadata": {}, + "outputs": [], + "source": [ + "up (a, b) = (a, b + 1)\n", + "down (a, b) = (a, b - 1)\n", + "left (a, b) = (a - 1, b)\n", + "right (a, b) = (a + 1, b)\n", + "directions = [right, up, left, down]" + ] + }, + { + "cell_type": "code", + "execution_count": 32, + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<interactive>:1:1: error:
• No instance for (Show ((t10, t0) -> (t10, t0))) arising from a use of ‘print’
(maybe you haven't applied a function to enough arguments?)
• In a stmt of an interactive GHCi command: print it" + ], + "text/plain": [ + ":1:1: error:\n", + " • No instance for (Show ((t10, t0) -> (t10, t0))) arising from a use of ‘print’\n", + " (maybe you haven't applied a function to enough arguments?)\n", + " • In a stmt of an interactive GHCi command: print it" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "take 20 $ concat $ zipWith replicate steps (cycle directions)" + ] + }, + { + "cell_type": "code", + "execution_count": 33, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "take 20 steps" + ] + }, + { + "cell_type": "code", + "execution_count": 34, + "metadata": {}, + "outputs": [], + "source": [ + "locations = scanl (\\c f -> f c) (0,0) $ concat $ zipWith replicate steps (cycle directions)\n", + " where\n", + " steps = concat $ zipWith (\\a b -> [a,b]) [1..] [1..]" + ] + }, + { + "cell_type": "code", + "execution_count": 35, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[(0,0),(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1),(2,-1),(2,0),(2,1),(2,2),(1,2),(0,2),(-1,2),(-2,2),(-2,1),(-2,0),(-2,-1)]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "take 20 locations" + ] + }, + { + "cell_type": "code", + "execution_count": 36, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "fromList [((0,0),1)]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "M.singleton (0, 0) 1" + ] + }, + { + "cell_type": "code", + "execution_count": 37, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "fromList [((0,0),1),((0,1),4),((1,1),2),((1,0),1),((-1,1),5),((-1,0),10)]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "m0 = M.fromList [((0,0), 1),((1,0), 1), ((1,1), 2), ((0,1), 4), ((-1,1), 5), ((-1,0), 10)]\n", + "m0" + ] + }, + { + "cell_type": "code", + "execution_count": 38, + "metadata": {}, + "outputs": [], + "source": [ + "adjacentMap (r, c) = M.filterWithKey adjacent \n", + " where adjacent k _ = abs (fst k - r) <= 1 && abs (snd k - c) <= 1" + ] + }, + { + "cell_type": "code", + "execution_count": 39, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "fromList [((0,0),1),((0,1),4),((-1,1),5),((-1,0),10)]" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "adjacentMap (-1, 1) m0" + ] + }, + { + "cell_type": "code", + "execution_count": 40, + "metadata": {}, + "outputs": [], + "source": [ + "adjacentMapSum here = M.foldr (+) 0 . adjacentMap here" + ] + }, + { + "cell_type": "code", + "execution_count": 41, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "20" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "adjacentMapSum (-1, 1) m0" + ] + }, + { + "cell_type": "code", + "execution_count": 42, + "metadata": {}, + "outputs": [], + "source": [ + "type Location = (Int, Int)\n", + "type Memory = M.HashMap Location Int" + ] + }, + { + "cell_type": "code", + "execution_count": 43, + "metadata": {}, + "outputs": [], + "source": [ + "emptyMemory = M.singleton (0, 0) 1 " + ] + }, + { + "cell_type": "code", + "execution_count": 44, + "metadata": {}, + "outputs": [], + "source": [ + "updateMemoryOnce :: Location -> State Memory Int\n", + "updateMemoryOnce here = \n", + " do m0 <- get\n", + " let total = adjacentMapSum here m0\n", + " put (M.insert here total m0)\n", + " return total" + ] + }, + { + "cell_type": "code", + "execution_count": 45, + "metadata": {}, + "outputs": [], + "source": [ + "updateMemory :: [Location] -> State Memory Int\n", + "updateMemory [] = do return 0\n", + "updateMemory (l:ls) = \n", + " do updateMemoryOnce l\n", + " updateMemory ls" + ] + }, + { + "cell_type": "code", + "execution_count": 46, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "(0,fromList [((0,0),1),((5,-1),6573553),((1,3),5336),((-1,-3),37402),((-4,4),369601),((4,-4),2909666),((0,1),4),((5,-2),6262851),((1,2),122),((-1,-4),2292124),((4,-3),48065),((-4,5),24242690),((0,2),133),((2,4),279138),((5,-3),6013560),((-3,5),23510079),((1,1),2),((-1,-1),11),((4,-2),98098),((0,3),5733),((2,5),18565223),((5,-4),2957731),((-3,4),363010),((1,0),1),((-1,-2),747),((4,-1),103128),((0,4),312453),((2,2),59),((-2,-2),362),((-5,5),24612291),((-3,3),6591),((3,-3),47108),((-4,0),875851),((0,5),20390510),((-2,-1),351),((2,3),5022),((-3,2),13486),((3,-4),2814493),((-4,1),830037),((2,0),54),((-2,-4),2179400),((3,-1),1968),((-3,1),14267),((1,5),19452043),((-4,2),787032),((2,1),57),((-2,-3),35487),((3,-2),957),((-3,0),15252),((1,4),295229),((-4,3),752688),((4,4),130654),((-4,-4),1026827),((-1,5),21383723),((3,1),2275),((-3,-1),16295),((-2,2),147),((2,-2),931),((-4,-3),1009457),((4,5),17048404),((-1,4),330785),((3,0),2105),((-3,-2),17008),((2,-1),26),((-2,3),6444),((-4,-2),975079),((3,3),2450),((-3,-3),17370),((5,5),8391037),((-2,0),330),((2,-4),2674100),((-4,-1),924406),((3,2),2391),((-3,-4),2089141),((5,4),8260383),((-2,1),304),((2,-3),45220),((4,0),109476),((-1,1),5),((1,-1),25),((3,5),17724526),((5,3),8001525),((0,-4),2411813),((4,1),116247),((-1,0),10),((1,-2),880),((3,4),266330),((5,2),7619304),((0,-3),39835),((4,2),123363),((-1,3),6155),((1,-3),42452),((5,1),7251490),((-2,4),349975),((0,-2),806),((4,3),128204),((-1,2),142),((1,-4),2539320),((5,0),6902404),((-2,5),22427493),((0,-1),23)])" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "runState (updateMemory (take 100 $ drop 1 locations)) emptyMemory" + ] + }, + { + "cell_type": "code", + "execution_count": 51, + "metadata": {}, + "outputs": [], + "source": [ + "memoryValues = execState (updateMemory (take 100 $ drop 1 locations)) emptyMemory" + ] + }, + { + "cell_type": "code", + "execution_count": 48, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "347991" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "target" + ] + }, + { + "cell_type": "code", + "execution_count": 52, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "(-2,4)" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "head $ dropWhile (\\l -> memoryValues!l <= target) locations" + ] + }, + { + "cell_type": "code", + "execution_count": 53, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "349975" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "(!) memoryValues $ head $ dropWhile (\\l -> memoryValues!l <= target) locations" + ] + }, + { + "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