From 5fca4f5eb64fc9c568346ef657e2daba9039b208 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Mon, 7 Dec 2020 17:06:35 +0000 Subject: [PATCH] Initial setup --- .gitignore | 46 +++++++ README.md | 105 ++++++++++++++ Setup.hs | 2 + advent-of-code-20.sublime-project | 8 ++ advent01/package.yaml | 58 ++++++++ advent01/src/advent01.hs | 152 +++++++++++++++++++++ modest.css | 219 ++++++++++++++++++++++++++++++ src/Main.hs | 5 + stack.yaml | 67 +++++++++ 9 files changed, 662 insertions(+) create mode 100644 .gitignore create mode 100644 README.md create mode 100644 Setup.hs create mode 100644 advent-of-code-20.sublime-project create mode 100644 advent01/package.yaml create mode 100644 advent01/src/advent01.hs create mode 100644 modest.css create mode 100644 src/Main.hs create mode 100644 stack.yaml diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..071d799 --- /dev/null +++ b/.gitignore @@ -0,0 +1,46 @@ +# Extensionless files +* +!/**/ +!*.* + +# Haskell bits +dist +dist-* +cabal-dev +*.o +*.hi +*.chi +*.chs.h +*.dyn_o +*.dyn_hi +.hpc +.hsenv +.cabal-sandbox/ +cabal.sandbox.config +*.prof +*.aux +*.hp +*.eventlog +.stack-work/ +cabal.project.local +stack.yaml.lock +.HTF/ + +# Haskell Stack cabal files: they're automatically generated. +*.cabal + +# IPython / IHaskell notebook checkpoints +.ipynb* + +# Sublime text +*.sublime-workspace + +# Logs +*.log + +# Profile exports +*.ps + +# KDE +.directory + diff --git a/README.md b/README.md new file mode 100644 index 0000000..1c6a5d4 --- /dev/null +++ b/README.md @@ -0,0 +1,105 @@ +--- +title: "Advent of Code 2019" +output: html_document +css: modest.css +--- +Code to solve the [Advent of Code](http://adventofcode.com/2019/) puzzles. This year, I'm using the puzzles to develop my skills in [Haskell](https://wiki.haskell.org/Haskell). I'm writing up a [commentary on these puzzles and my solutions](https://work.njae.me.uk/tag/advent-of-code/) on my blog. + +[Learn you a Haskell](http://learnyouahaskell.com/chapters), [Introduction to Haskell 98](https://www.haskell.org/tutorial/index.html), and [Hackage](https://hackage.haskell.org/) are good resources. + +The [Stack documentation](https://docs.haskellstack.org/en/stable/README/) and [How I Start: Haskell](http://howistart.org/posts/haskell/1/) are good sources of using the tools. + +# Toolchain + +I'm using the basic Haskell Platform installation, together with `stack` to manage the packages and dependencies (install with +``` +$ sudo aptitude install haskell-platform haskell-stack +``` +), then updgrade with +``` + stack upgrade --binary-only +``` +as the version in the Ubuntu repos is too old to work with current Haskell Stack package sets. + +## Creating the repository and project +Create the repository as normal: create the project in Gitolite, clone it, and insert the `.gitignore` and `README.md` files. + +There's one package per day, with the code for each package in sub-directories of the root directory. + +Create the basic `stack` project. This will create a new directory. Note that this new directory name can't have a hyphen-delimited word that's just digits, so the project will have to be `advent-of-code` + +``` +stack new advent-of-code --bare simple +``` + +Modify the `stack.yaml` file as needed, such as adding the `ghc-options` stanza. + +## Creating subsequent days + +Each day lives in a separate directory, with its own `package.yaml` file and code in the `src` directory. (I based this configuration from [mstksg's setup](https://github.com/mstksg/advent-of-code-2018).) + +Compile with +``` +stack build +``` +or +``` +stack build advent01 +``` + +Run with +``` +stack exec advent01 +``` + +If you want to pass in additional RTS parameters, do it like this: +``` +stack exec -- advent01 +RTS -K0 -RTS +``` + +Run interactively with +``` +stack ghci advent01 +``` +or +``` +stack ghci advent01:exe:advent01 +``` +if the first form is ambiguous. + +To profile, use +``` +stack build --executable-profiling --library-profiling --ghc-options="-fprof-auto -rtsopts" advent01 +``` +then run with +``` +stack exec --profile -- advent01 +RTS -p -hy +``` +Generate the profile graph with +``` +stack exec hp2ps advent01.hp +``` + +# Packages + +Stack is using the [14.16-lts resolver](https://www.stackage.org/lts-14.16) for packages, so make sure you read the [correct documentation for the packages included in it](https://www.stackage.org/lts-14.16/docs). + +When you use a new package, use + +``` +stack solver +``` +to see how the `stack.yaml` file needs to change, and +``` +stack solver --update-yaml +``` +to implement the changes. + +# Readme + +Build this readme file wth +``` +pandoc -s README.md > README.html +``` + +(Using the [Modest style](https://github.com/markdowncss/modest).) diff --git a/Setup.hs b/Setup.hs new file mode 100644 index 0000000..9a994af --- /dev/null +++ b/Setup.hs @@ -0,0 +1,2 @@ +import Distribution.Simple +main = defaultMain diff --git a/advent-of-code-20.sublime-project b/advent-of-code-20.sublime-project new file mode 100644 index 0000000..24db303 --- /dev/null +++ b/advent-of-code-20.sublime-project @@ -0,0 +1,8 @@ +{ + "folders": + [ + { + "path": "." + } + ] +} diff --git a/advent01/package.yaml b/advent01/package.yaml new file mode 100644 index 0000000..d681f43 --- /dev/null +++ b/advent01/package.yaml @@ -0,0 +1,58 @@ +# This YAML file describes your package. Stack will automatically generate a +# Cabal file when you run `stack build`. See the hpack website for help with +# this file: . + +name: advent201 +synopsis: Advent of Code +version: '0.0.1' + +default-extensions: +- AllowAmbiguousTypes +- ApplicativeDo +- BangPatterns +- BlockArguments +- DataKinds +- DeriveFoldable +- DeriveFunctor +- DeriveGeneric +- DeriveTraversable +- EmptyCase +- FlexibleContexts +- FlexibleInstances +- FunctionalDependencies +- GADTs +- GeneralizedNewtypeDeriving +- ImplicitParams +- KindSignatures +- LambdaCase +- MonadComprehensions +- MonoLocalBinds +- MultiParamTypeClasses +- MultiWayIf +- NamedFieldPuns +- NegativeLiterals +- NumDecimals +# - OverloadedLists +- OverloadedStrings +- PartialTypeSignatures +- PatternGuards +- PatternSynonyms +- PolyKinds +- RankNTypes +- RecordWildCards +- ScopedTypeVariables +- TemplateHaskell +- TransformListComp +- TupleSections +- TypeApplications +- TypeFamilies +- TypeInType +- TypeOperators +- ViewPatterns + +executables: + advent01: + main: advent01.hs + source-dirs: src + dependencies: + - base >= 2 && < 6 diff --git a/advent01/src/advent01.hs b/advent01/src/advent01.hs new file mode 100644 index 0000000..34cf113 --- /dev/null +++ b/advent01/src/advent01.hs @@ -0,0 +1,152 @@ +-- import Debug.Trace + + +import Data.Finite (Finite, modulo, getFinite) +import GHC.TypeNats (KnownNat) + + +-- import Data.Functor.Compose (Compose(..)) +-- import Data.Matrix (Matrix, matrix, safeGet, (!), prettyMatrix, mapPos, fromList, toList) +import qualified Data.Matrix as X +import Data.Bool (bool) +import Data.Distributive (Distributive(..)) +import Data.Functor.Rep (Representable(..), distributeRep) +import Data.Functor.Identity (Identity(..)) +import Control.Comonad.Representable.Store (Store(..), StoreT(..), store, experiment, runStore) +import Control.Comonad (Comonad(..)) + +import Data.Maybe +import Data.List +import qualified Data.Set as S +import qualified Data.Map as M + +import Control.Concurrent (threadDelay) +import Control.Monad (forM_) + + +instance Ord Grid where + m1 `compare` m2 = (X.toList m1) `compare` (X.toList m2) + + +type Coord = (Int, Int) +type Grid = X.Matrix Bool +type StoredGrid = Store X.Matrix Bool +type Rule = StoredGrid -> Bool + +type GridCache = S.Set Grid + +-- mGet :: Coord -> Matrix a -> a +-- mGet (r, c) mtx = fromMaybe False $ safeGet r c mtx +-- mGet rc mtx = mtx ! rc + + +validCoord :: Coord -> Bool +validCoord (r, c) = r >= 1 && r <= gridSize && c >= 1 && c <= gridSize + + +instance Distributive X.Matrix where + distribute = distributeRep + +instance Representable X.Matrix where + type Rep X.Matrix = Coord + index m c = (X.!) m c -- mGet c m + tabulate = X.matrix gridSize gridSize + +gridSize :: Int +gridSize = 5 + + +neighbourCoords :: [Coord] +-- neighbourCoords = [(x, y) | x <- [-1, 0, 1], y <- [-1, 0, 1], (x, y) /= (0, 0)] +neighbourCoords = [(-1, 0), (1, 0), (0, -1), (0, 1)] + +addCoords :: Coord -> Coord -> Coord +addCoords (x, y) (x', y') = (x + x', y + y') + +basicRule :: Rule +basicRule g = (alive && numNeighboursAlive == 1) || ((not alive) && (numNeighboursAlive == 1 || numNeighboursAlive == 2)) + where + alive = extract g + neighbours = experiment ((filter validCoord) . (at neighbourCoords)) g + numNeighboursAlive = length (filter id neighbours) + +step :: Rule -> StoredGrid -> StoredGrid +step = extend + +render :: StoredGrid -> String +-- render (StoreT (Identity g) _) = foldMap ((++ "\n") . foldMap (bool "." "#")) g +render grid = X.prettyMatrix $ X.mapPos (\_ c -> bool "." "#" c) g + where g = unGrid grid + + +mkGrid :: [Coord] -> StoredGrid +mkGrid xs = store (`elem` xs) (1, 1) + +unGrid :: StoredGrid -> Grid +-- unGrid (StoreT (Identity g) _) = g +unGrid grid = X.fromList gridSize gridSize gridList + where (sgf, _sgl) = runStore grid + gridList = [sgf (r, c) | r <- [1..gridSize], c <- [1..gridSize]] + + +at :: [Coord] -> Coord -> [Coord] +coords `at` origin = map (addCoords origin) coords + +-- glider, blinker, beacon :: [Coord] +-- glider = [(1, 0), (2, 1), (0, 2), (1, 2), (2, 2)] +-- blinker = [(0, 0), (1, 0), (2, 0)] +-- beacon = [(0, 0), (1, 0), (0, 1), (3, 2), (2, 3), (3, 3)] + + +tickTime :: Int +tickTime = 200000 + +start :: IO StoredGrid +start = do coords <- readGrid + return $ mkGrid coords + -- glider `at` (1, 1) + -- ++ beacon `at` (15, 5) + +main :: IO () +main = + do sG <- start + print $ part1 sG + -- let grids = map unGrid $ iterate (step basicRule) sG + -- forM_ (take 5 $ iterate (step basicRule) sG) $ \grid -> do + -- -- putStr "\ESC[2J" -- Clear terminal screen + -- putStrLn (render grid) + -- -- threadDelay tickTime + + +readGrid = + do gs <- readFile "data/advent24.txt" + let grid = lines gs + let isBug r c = (grid!!r)!!c == '#' + let ng = gridSize - 1 + return [(r + 1, c + 1) | r <- [0..ng], c <- [0..ng], isBug r c] + + +-- part1 :: Grid -> [Grid] +part1 :: StoredGrid -> Integer +-- part1 startingGrid = map fst $ takeWhile (uncurry . S.notMember) (zip grids gridCache) +-- part1 startingGrid = map fst $ takeWhile (\(g, c) -> S.notMember g c) (zip grids gridCache) +-- part1 startingGrid = fst $ head $ dropWhile (\(g, c) -> S.notMember g c) (zip grids gridCache) +part1 startingGrid = bioDiversity firstRepeat + where + -- grids = map unGrid $ iterate (step basicRule) startingGrid + -- gridCache = scanl' (flip . S.insert) S.empty grids + grids = fGrids startingGrid + gridCache = fGridCache grids + firstRepeat = fst $ head $ dropWhile (uncurry S.notMember) (zip grids gridCache) + +fGrids :: StoredGrid -> [Grid] +fGrids stG = map unGrid $ iterate (step basicRule) stG + +fGridCache :: [Grid] -> [S.Set Grid] +fGridCache gs = scanl' (flip S.insert) S.empty gs +-- fGridCache gs = scanl' (\s g -> S.insert g s) S.empty gs + + +bioDiversity :: Grid -> Integer +bioDiversity g = sum $ map snd $ filter (id . fst) $ zip bugs $ iterate ( * 2) 1 + where bugs = X.toList g diff --git a/modest.css b/modest.css new file mode 100644 index 0000000..947a9ea --- /dev/null +++ b/modest.css @@ -0,0 +1,219 @@ +@media print { + *, + *:before, + *:after { + background: transparent !important; + color: #000 !important; + box-shadow: none !important; + text-shadow: none !important; + } + + a, + a:visited { + text-decoration: underline; + } + + a[href]:after { + content: " (" attr(href) ")"; + } + + abbr[title]:after { + content: " (" attr(title) ")"; + } + + a[href^="#"]:after, + a[href^="javascript:"]:after { + content: ""; + } + + pre, + blockquote { + border: 1px solid #999; + page-break-inside: avoid; + } + + thead { + display: table-header-group; + } + + tr, + img { + page-break-inside: avoid; + } + + img { + max-width: 100% !important; + } + + p, + h2, + h3 { + orphans: 3; + widows: 3; + } + + h2, + h3 { + page-break-after: avoid; + } +} + +pre, +code { + font-family: Menlo, Monaco, "Courier New", monospace; +} + +pre { + padding: .5rem; + line-height: 1.25; + overflow-x: scroll; +} + +a, +a:visited { + color: #3498db; +} + +a:hover, +a:focus, +a:active { + color: #2980b9; +} + +.modest-no-decoration { + text-decoration: none; +} + +html { + font-size: 12px; +} + +@media screen and (min-width: 32rem) and (max-width: 48rem) { + html { + font-size: 15px; + } +} + +@media screen and (min-width: 48rem) { + html { + font-size: 16px; + } +} + +body { + line-height: 1.85; +} + +p, +.modest-p { + font-size: 1rem; + margin-bottom: 1.3rem; +} + +h1, +.modest-h1, +h2, +.modest-h2, +h3, +.modest-h3, +h4, +.modest-h4 { + margin: 1.414rem 0 .5rem; + font-weight: inherit; + line-height: 1.42; +} + +h1, +.modest-h1 { + margin-top: 0; + font-size: 3.998rem; +} + +h2, +.modest-h2 { + font-size: 2.827rem; +} + +h3, +.modest-h3 { + font-size: 1.999rem; +} + +h4, +.modest-h4 { + font-size: 1.414rem; +} + +h5, +.modest-h5 { + font-size: 1.121rem; +} + +h6, +.modest-h6 { + font-size: .88rem; +} + +small, +.modest-small { + font-size: .707em; +} + +/* https://github.com/mrmrs/fluidity */ + +img, +canvas, +iframe, +video, +svg, +select, +textarea { + max-width: 100%; +} + +@import url(http://fonts.googleapis.com/css?family=Open+Sans+Condensed:300,300italic,700); + +@import url(http://fonts.googleapis.com/css?family=Arimo:700,700italic); + +html { + font-size: 18px; + max-width: 100%; +} + +body { + color: #444; + font-family: 'Open Sans Condensed', sans-serif; + font-weight: 300; + margin: 0 auto; + max-width: 48rem; + line-height: 1.45; + padding: .25rem; +} + +h1, +h2, +h3, +h4, +h5, +h6 { + font-family: Arimo, Helvetica, sans-serif; +} + +h1, +h2, +h3 { + border-bottom: 2px solid #fafafa; + margin-bottom: 1.15rem; + padding-bottom: .5rem; + text-align: center; +} + +blockquote { + border-left: 8px solid #fafafa; + padding: 1rem; +} + +pre, +code { + background-color: #fafafa; +} \ No newline at end of file diff --git a/src/Main.hs b/src/Main.hs new file mode 100644 index 0000000..9cd992d --- /dev/null +++ b/src/Main.hs @@ -0,0 +1,5 @@ +module Main where + +main :: IO () +main = do + putStrLn "hello world" diff --git a/stack.yaml b/stack.yaml new file mode 100644 index 0000000..4a79eef --- /dev/null +++ b/stack.yaml @@ -0,0 +1,67 @@ +# This file was automatically generated by 'stack init' +# +# Some commonly used options have been documented as comments in this file. +# For advanced use and comprehensive documentation of the format, please see: +# https://docs.haskellstack.org/en/stable/yaml_configuration/ + +# Resolver to choose a 'specific' stackage snapshot or a compiler version. +# A snapshot resolver dictates the compiler version and the set of packages +# to be used for project dependencies. For example: +# +# resolver: lts-3.5 +# resolver: nightly-2015-09-21 +# resolver: ghc-7.10.2 +# +# The location of a snapshot can be provided as a file or url. Stack assumes +# a snapshot provided as a file might change, whereas a url resource does not. +# +# resolver: ./custom-snapshot.yaml +# resolver: https://example.com/snapshots/2018-01-01.yaml +resolver: + url: https://raw.githubusercontent.com/commercialhaskell/stackage-snapshots/master/lts/16/25.yaml + +# User packages to be built. +# Various formats can be used as shown in the example below. +# +# packages: +# - some-directory +# - https://example.com/foo/bar/baz-0.0.2.tar.gz +# subdirs: +# - auto-update +# - wai +packages: +- . +# Dependency packages to be pulled from upstream that are not in the resolver. +# These entries can reference officially published versions as well as +# forks / in-progress versions pinned to a git hash. For example: +# +# extra-deps: +# - acme-missiles-0.3 +# - git: https://github.com/commercialhaskell/stack.git +# commit: e7b331f14bcffb8367cd58fbfc8b40ec7642100a +# +# extra-deps: [] + +# Override default flag values for local packages and extra-deps +# flags: {} + +# Extra package databases containing global packages +# extra-package-dbs: [] + +# Control whether we use the GHC we find on the path +# system-ghc: true +# +# Require a specific version of stack, using version ranges +# require-stack-version: -any # Default +# require-stack-version: ">=2.5" +# +# Override the architecture used by stack, especially useful on Windows +# arch: i386 +# arch: x86_64 +# +# Extra directories used by stack for building +# extra-include-dirs: [/path/to/dir] +# extra-lib-dirs: [/path/to/dir] +# +# Allow a newer minor version of GHC than the snapshot specifies +# compiler-check: newer-minor -- 2.34.1