Skip to content

Instantly share code, notes, and snippets.

@k0001

k0001/Aoc1.hs

Last active December 8, 2019 14:51
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save k0001/c121f90a9faa6f1afad8cb50ad9e1e89 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save k0001/c121f90a9faa6f1afad8cb50ad9e1e89 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. k0001 revised this gist Dec 3, 2019. 1 changed file with 0 additions and 81 deletions.
    81 changes: 0 additions & 81 deletions Aoc2_1.hs
    View file
    Original file line number Diff line number Diff line change
    @@ -1,81 +0,0 @@
    -- This enables the `\case` syntax, which is not standard Haskell.
    {-# LANGUAGE LambdaCase #-}

    -- | Solution for https://adventofcode.com/2019/day/2
    module Aoc2_1 where

    -- We like Natural numbers. Kind of.
    import Numeric.Natural

    -- We redefine `drop` below, so we hide its original implementation
    import Prelude hiding (drop)

    ------------------------------

    -- Wherever there is meaning, there is a type.

    -- | Instruction Pointer
    data IP = IP Natural

    -- | A Program
    data Intcode = Intcode [Natural]
    deriving (Show)

    ------------------------------

    -- This is the solution to the problem.

    -- | Run an program starting at the given position.
    run :: Intcode -> IP -> Maybe Intcode
    run (Intcode xs) (IP pos) = case drop pos xs of
    (99 : _) -> Just (Intcode xs)
    (1 : a : b : c : _) ->
    get a xs >>= \a' ->
    get b xs >>= \b' ->
    set c (a' + b') xs >>= \xs' ->
    run (Intcode xs') (IP (pos + 4))
    (2 : a : b : c : _) ->
    get a xs >>= \a' ->
    get b xs >>= \b' ->
    set c (a' * b') xs >>= \xs' ->
    run (Intcode xs') (IP (pos + 4))
    _ -> Nothing

    --------------------------------

    -- Miscelaneous functions for modifying lists.
    -- These are rather slow because lists are not the optimal
    -- data structure for this problem.
    -- But we are learning, so who cares.

    -- | `get n xs` returns the element in `xs` at position `n`.
    -- Returns `Nothing` if `n` is out of bounds.
    get :: Natural -> [a] -> Maybe a
    get _ [] = Nothing
    get 0 (a : _) = Just a
    get n (_ : rest) = get (n - 1) rest

    -- | `set n x xs` sets the element at position `n` in `xs` to `x`.
    -- Returns `Nothing` if `n` is out of bounds.
    set :: Natural -> a -> [a] -> Maybe [a]
    set _ _ [] = Nothing
    set 0 a (_ : rest) = Just (a : rest)
    set n a (b : rest) = fmap (b :) (set (n - 1) a rest)

    -- | `drop n xs` drops the first `n` elements of `xs`,
    -- or maybe less if the list is shorter than `n`.
    drop :: Natural -> [a] -> [a]
    drop 0 xs = xs
    drop n (_ : xs) = drop (n - 1) xs

    ------------------------------

    -- | This is the input I was given.
    input :: Intcode
    input = Intcode [1, {- 0 -} 12, {- 0 -} 2, 3, 1, 1, 2, 3, 1, 3, 4, 3, 1, 5, 0, 3, 2, 1, 6, 19, 1, 5, 19, 23, 1, 23, 6, 27, 1, 5, 27, 31, 1, 31, 6, 35, 1, 9, 35, 39, 2, 10, 39, 43, 1, 43, 6, 47, 2, 6, 47, 51, 1, 5, 51, 55, 1, 55, 13, 59, 1, 59, 10, 63, 2, 10, 63, 67, 1, 9, 67, 71, 2, 6, 71, 75, 1, 5, 75, 79, 2, 79, 13, 83, 1, 83, 5, 87, 1, 87, 9, 91, 1, 5, 91, 95, 1, 5, 95, 99, 1, 99, 13, 103, 1, 10, 103, 107, 1, 107, 9, 111, 1, 6, 111, 115, 2, 115, 13, 119, 1, 10, 119, 123, 2, 123, 6, 127, 1, 5, 127, 131, 1, 5, 131, 135, 1, 135, 6, 139, 2, 139, 10, 143, 2, 143, 9, 147, 1, 147, 6, 151, 1, 151, 13, 155, 2, 155, 9, 159, 1, 6, 159, 163, 1, 5, 163, 167, 1, 5, 167, 171, 1, 10, 171, 175, 1, 13, 175, 179, 1, 179, 2, 183, 1, 9, 183, 0, 99, 2, 14, 0, 0]

    -- | This is my answer, which as long as the given `input` was well-formed, should be `Just`.
    answer :: Maybe Natural
    answer = run input (IP 0) >>= \case
    Intcode (n : _) -> Just n
    Intcode _ -> Nothing
  2. k0001 revised this gist Dec 3, 2019. 1 changed file with 60 additions and 20 deletions.
    80 changes: 60 additions & 20 deletions Aoc2_1.hs
    View file
    Original file line number Diff line number Diff line change
    @@ -1,41 +1,81 @@
    -- This enables the `\case` syntax, which is not standard Haskell.
    {-# LANGUAGE LambdaCase #-}

    -- | Solution for https://adventofcode.com/2019/day/2
    module Aoc2_1 where

    -- NB! We use Int everywhere to keep this example short, but one shouldn't do that.
    -- We like Natural numbers. Kind of.
    import Numeric.Natural

    -- We redefine `drop` below, so we hide its original implementation
    import Prelude hiding (drop)

    ------------------------------

    -- Wherever there is meaning, there is a type.

    -- | Instruction Pointer
    newtype IP = IP Int
    data IP = IP Natural

    -- | A Program
    newtype Intcode = Intcode [Int]
    data Intcode = Intcode [Natural]
    deriving (Show)

    -- | Run an Intcode program starting at the given instruction position.
    run :: IP -> Intcode -> Maybe Intcode
    run (IP pos) (Intcode xs) = case drop pos xs of
    ------------------------------

    -- This is the solution to the problem.

    -- | Run an program starting at the given position.
    run :: Intcode -> IP -> Maybe Intcode
    run (Intcode xs) (IP pos) = case drop pos xs of
    (99 : _) -> Just (Intcode xs)
    (1 : a : b : c : _) -> do
    a' <- get a xs
    b' <- get b xs
    xs' <- set c (a' + b') xs
    run (IP (pos + 4)) (Intcode xs')
    (2 : a : b : c : _) -> do
    a' <- get a xs
    b' <- get b xs
    xs' <- set c (a' * b') xs
    run (IP (pos + 4)) (Intcode xs')
    (1 : a : b : c : _) ->
    get a xs >>= \a' ->
    get b xs >>= \b' ->
    set c (a' + b') xs >>= \xs' ->
    run (Intcode xs') (IP (pos + 4))
    (2 : a : b : c : _) ->
    get a xs >>= \a' ->
    get b xs >>= \b' ->
    set c (a' * b') xs >>= \xs' ->
    run (Intcode xs') (IP (pos + 4))
    _ -> Nothing

    -- | Super slow list lookup by index. Nobody cares.
    get :: Int -> [a] -> Maybe a
    --------------------------------

    -- Miscelaneous functions for modifying lists.
    -- These are rather slow because lists are not the optimal
    -- data structure for this problem.
    -- But we are learning, so who cares.

    -- | `get n xs` returns the element in `xs` at position `n`.
    -- Returns `Nothing` if `n` is out of bounds.
    get :: Natural -> [a] -> Maybe a
    get _ [] = Nothing
    get 0 (a : _) = Just a
    get n (_ : rest) = get (n - 1) rest

    -- | Super slow list insert at index. Nobody cares.
    set :: Int -> a -> [a] -> Maybe [a]
    -- | `set n x xs` sets the element at position `n` in `xs` to `x`.
    -- Returns `Nothing` if `n` is out of bounds.
    set :: Natural -> a -> [a] -> Maybe [a]
    set _ _ [] = Nothing
    set 0 a (_ : rest) = Just (a : rest)
    set n a (b : rest) = fmap (b :) (set (n - 1) a rest)

    -- | `drop n xs` drops the first `n` elements of `xs`,
    -- or maybe less if the list is shorter than `n`.
    drop :: Natural -> [a] -> [a]
    drop 0 xs = xs
    drop n (_ : xs) = drop (n - 1) xs

    ------------------------------

    -- | This is the input I was given.
    input :: Intcode
    input = Intcode [1, {- 0 -} 12, {- 0 -} 2, 3, 1, 1, 2, 3, 1, 3, 4, 3, 1, 5, 0, 3, 2, 1, 6, 19, 1, 5, 19, 23, 1, 23, 6, 27, 1, 5, 27, 31, 1, 31, 6, 35, 1, 9, 35, 39, 2, 10, 39, 43, 1, 43, 6, 47, 2, 6, 47, 51, 1, 5, 51, 55, 1, 55, 13, 59, 1, 59, 10, 63, 2, 10, 63, 67, 1, 9, 67, 71, 2, 6, 71, 75, 1, 5, 75, 79, 2, 79, 13, 83, 1, 83, 5, 87, 1, 87, 9, 91, 1, 5, 91, 95, 1, 5, 95, 99, 1, 99, 13, 103, 1, 10, 103, 107, 1, 107, 9, 111, 1, 6, 111, 115, 2, 115, 13, 119, 1, 10, 119, 123, 2, 123, 6, 127, 1, 5, 127, 131, 1, 5, 131, 135, 1, 135, 6, 139, 2, 139, 10, 143, 2, 143, 9, 147, 1, 147, 6, 151, 1, 151, 13, 155, 2, 155, 9, 159, 1, 6, 159, 163, 1, 5, 163, 167, 1, 5, 167, 171, 1, 10, 171, 175, 1, 13, 175, 179, 1, 179, 2, 183, 1, 9, 183, 0, 99, 2, 14, 0, 0]

    -- | This is my answer, which as long as the given `input` was well-formed, should be `Just`.
    answer :: Maybe Natural
    answer = run input (IP 0) >>= \case
    Intcode (n : _) -> Just n
    Intcode _ -> Nothing
  3. k0001 revised this gist Dec 3, 2019. 1 changed file with 41 additions and 0 deletions.
    41 changes: 41 additions & 0 deletions Aoc2_1.hs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,41 @@
    module Aoc2_1 where

    -- NB! We use Int everywhere to keep this example short, but one shouldn't do that.

    -- | Instruction Pointer
    newtype IP = IP Int

    -- | A Program
    newtype Intcode = Intcode [Int]
    deriving (Show)

    -- | Run an Intcode program starting at the given instruction position.
    run :: IP -> Intcode -> Maybe Intcode
    run (IP pos) (Intcode xs) = case drop pos xs of
    (99 : _) -> Just (Intcode xs)
    (1 : a : b : c : _) -> do
    a' <- get a xs
    b' <- get b xs
    xs' <- set c (a' + b') xs
    run (IP (pos + 4)) (Intcode xs')
    (2 : a : b : c : _) -> do
    a' <- get a xs
    b' <- get b xs
    xs' <- set c (a' * b') xs
    run (IP (pos + 4)) (Intcode xs')
    _ -> Nothing

    -- | Super slow list lookup by index. Nobody cares.
    get :: Int -> [a] -> Maybe a
    get _ [] = Nothing
    get 0 (a : _) = Just a
    get n (_ : rest) = get (n - 1) rest

    -- | Super slow list insert at index. Nobody cares.
    set :: Int -> a -> [a] -> Maybe [a]
    set _ _ [] = Nothing
    set 0 a (_ : rest) = Just (a : rest)
    set n a (b : rest) = fmap (b :) (set (n - 1) a rest)

    input :: Intcode
    input = Intcode [1, {- 0 -} 12, {- 0 -} 2, 3, 1, 1, 2, 3, 1, 3, 4, 3, 1, 5, 0, 3, 2, 1, 6, 19, 1, 5, 19, 23, 1, 23, 6, 27, 1, 5, 27, 31, 1, 31, 6, 35, 1, 9, 35, 39, 2, 10, 39, 43, 1, 43, 6, 47, 2, 6, 47, 51, 1, 5, 51, 55, 1, 55, 13, 59, 1, 59, 10, 63, 2, 10, 63, 67, 1, 9, 67, 71, 2, 6, 71, 75, 1, 5, 75, 79, 2, 79, 13, 83, 1, 83, 5, 87, 1, 87, 9, 91, 1, 5, 91, 95, 1, 5, 95, 99, 1, 99, 13, 103, 1, 10, 103, 107, 1, 107, 9, 111, 1, 6, 111, 115, 2, 115, 13, 119, 1, 10, 119, 123, 2, 123, 6, 127, 1, 5, 127, 131, 1, 5, 131, 135, 1, 135, 6, 139, 2, 139, 10, 143, 2, 143, 9, 147, 1, 147, 6, 151, 1, 151, 13, 155, 2, 155, 9, 159, 1, 6, 159, 163, 1, 5, 163, 167, 1, 5, 167, 171, 1, 10, 171, 175, 1, 13, 175, 179, 1, 179, 2, 183, 1, 9, 183, 0, 99, 2, 14, 0, 0]
  4. k0001 created this gist Dec 2, 2019.
    143 changes: 143 additions & 0 deletions Aoc1.hs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,143 @@
    {-# LANGUAGE DerivingStrategies #-}
    {-# LANGUAGE DerivingVia #-}
    {-# LANGUAGE GeneralizedNewtypeDeriving #-}

    module Aoc1 where

    import Data.Foldable
    import Data.Monoid (Sum(..))
    import Data.Ratio

    ---- Excercise 1

    newtype Mass = Mass Integer
    deriving stock (Eq, Ord, Show)
    deriving Semigroup via (Sum Integer)
    deriving Monoid via (Sum Integer)

    newtype Fuel = Fuel Mass
    deriving stock (Eq, Ord, Show)
    deriving newtype Semigroup
    deriving newtype Monoid

    massCost :: Mass -> Fuel
    massCost (Mass i) = Fuel (Mass (floor (i % 3) - 2))

    -- 3471229
    answer1 :: Fuel
    answer1 = foldl' mappend mempty (fmap massCost input)

    ---- Exercise 2

    fuelCost :: Fuel -> Fuel
    fuelCost (Fuel m0) =
    case massCost m0 of
    f1 | f1 > mempty -> mappend f1 (fuelCost f1)
    | otherwise -> mempty

    -- 5203967
    answer2 :: Fuel
    answer2 = foldl' mappend mempty (fmap (fuelCost . Fuel) input)

    input :: [Mass]
    input = fmap Mass
    [129192,
    58561,
    57267,
    95382,
    84995,
    127372,
    93598,
    97264,
    138550,
    79327,
    135661,
    139468,
    108860,
    149642,
    72123,
    128333,
    69002,
    98450,
    86267,
    70171,
    101333,
    79822,
    142539,
    142743,
    51371,
    111381,
    62073,
    72210,
    125168,
    135952,
    131060,
    121842,
    88234,
    146774,
    136571,
    126719,
    50644,
    75696,
    51195,
    77171,
    118052,
    83691,
    133779,
    149814,
    64847,
    110697,
    92695,
    59453,
    139517,
    129487,
    79271,
    97896,
    146987,
    149822,
    71866,
    90797,
    104732,
    54997,
    50139,
    134115,
    133017,
    144979,
    89428,
    124750,
    91833,
    57252,
    67195,
    121624,
    102706,
    138245,
    127700,
    124098,
    110382,
    121557,
    103613,
    133576,
    122801,
    112306,
    120203,
    134696,
    76129,
    84576,
    80854,
    147237,
    71025,
    127513,
    143631,
    125090,
    115698,
    57979,
    84880,
    120177,
    147389,
    88380,
    114688,
    56355,
    126265,
    58220,
    63523,
    130179]