aoc (empty) → 0.1.0.0

raw patch · 4 files changed

+356/−0 lines, 4 filesdep +basedep +containersdep +hashable

Dependencies added: base, containers, hashable, heap, unordered-containers

Files

• CHANGELOG.md +5/−0
• LICENSE +29/−0
• aoc.cabal +77/−0
• src/Utility/AOC.hs +245/−0

@@ -0,0 +1,5 @@+# Revision history for aoc
+
+## 0.1.0.0 -- YYYY-mm-dd
+
+* First version. Released on an unsuspecting world.

@@ -0,0 +1,29 @@+Copyright (c) 2025, M1n3c4rt
+
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright
+      notice, this list of conditions and the following disclaimer.
+
+    * Redistributions in binary form must reproduce the above
+      copyright notice, this list of conditions and the following
+      disclaimer in the documentation and/or other materials provided
+      with the distribution.
+
+    * Neither the name of the copyright holder nor the names of its
+      contributors may be used to endorse or promote products derived
+      from this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

@@ -0,0 +1,77 @@+cabal-version:      3.0
+-- The cabal-version field refers to the version of the .cabal specification,
+-- and can be different from the cabal-install (the tool) version and the
+-- Cabal (the library) version you are using. As such, the Cabal (the library)
+-- version used must be equal or greater than the version stated in this field.
+-- Starting from the specification version 2.2, the cabal-version field must be
+-- the first thing in the cabal file.
+
+-- Initial package description 'aoc' generated by
+-- 'cabal init'. For further documentation, see:
+--   http://haskell.org/cabal/users-guide/
+--
+-- The name of the package.
+name:               aoc
+
+-- The package version.
+-- See the Haskell package versioning policy (PVP) for standards
+-- guiding when and how versions should be incremented.
+-- https://pvp.haskell.org
+-- PVP summary:     +-+------- breaking API changes
+--                  | | +----- non-breaking API additions
+--                  | | | +--- code changes with no API change
+version:            0.1.0.0
+
+-- A short (one-line) description of the package.
+synopsis:           Utility functions commonly used while solving Advent of Code puzzles
+
+-- A longer description of the package.
+description:        A collection of miscellaneous utility functions, including but not limited to pathfinding, grid enumeration, coordinate/range operations and extrapolation functions.
+
+-- The license under which the package is released.
+license:            BSD-3-Clause
+
+-- The file containing the license text.
+license-file:       LICENSE
+
+-- The package author(s).
+author:             M1n3c4rt
+
+-- An email address to which users can send suggestions, bug reports, and patches.
+maintainer:         vedicbits@gmail.com
+
+-- A copyright notice.
+-- copyright:
+category:           Utility
+build-type:         Simple
+
+-- Extra doc files to be distributed with the package, such as a CHANGELOG or a README.
+extra-doc-files:    CHANGELOG.md
+
+-- Extra source files to be distributed with the package, such as examples, or a tutorial module.
+-- extra-source-files:
+
+common warnings
+    ghc-options: -Wall
+
+library
+    -- Import common warning flags.
+    import:           warnings
+
+    -- Modules exported by the library.
+    exposed-modules:  Utility.AOC
+
+    -- Modules included in this library but not exported.
+    -- other-modules:
+
+    -- LANGUAGE extensions used by modules in this package.
+    -- other-extensions:
+
+    -- Other library packages from which modules are imported.
+    build-depends: base ^>=4.17.2.1, heap >= 1.0.4 && < 1.1, unordered-containers >= 0.2.20 && < 0.3, containers >= 0.6.7 && <= 0.7, hashable >= 1.4.7 && < 1.5
+
+    -- Directories containing source files.
+    hs-source-dirs:   src
+
+    -- Base language which the package is written in.
+    default-language: Haskell2010

@@ -0,0 +1,245 @@+{-|
+Module      : AOC
+Description : Utility functions commonly used while solving Advent of Code puzzles
+Copyright   : (c) M1n3c4rt, 2025
+License     : BSD-3-Clause
+Maintainer  : vedicbits@gmail.com
+Stability   : stable
+-}
+
+{-# LANGUAGE FlexibleContexts #-}
+{-# LANGUAGE TupleSections #-}
+{-# OPTIONS_GHC -Wno-incomplete-patterns #-}
+{-# OPTIONS_GHC -Wno-incomplete-uni-patterns #-}
+{-# OPTIONS_GHC -Wno-type-defaults #-}
+
+module Utility.AOC (
+    -- * Pathfinding algorithms
+    -- $cat1
+    shortestDistance,
+    shortestPaths,
+    shortestDistanceOnMagma,
+    shortestPathsOnMagma,
+    -- * Neighbour functions
+    neighbours4,
+    neighbours8,
+    neighbours6,
+    neighbours26,
+    -- * Taxicab (Manhattan) distance
+    taxicab2,
+    taxicab3,
+    -- * Grid enumeration
+    -- $cat2
+    enumerate,
+    enumerateRead,
+    enumerateHM,
+    enumerateReadHM,
+    enumerateFilter,
+    enumerateFilterSet,
+    -- * Flood fill
+    floodFill,
+    floodFillWith,
+    -- * List selection
+    choose,
+    permute,
+    -- * Extrapolation
+    extrapolate,
+    -- * Miscellaneous
+    range,
+    rangeIntersect,
+    binToDec
+) where
+
+import qualified Data.HashMap.Strict as HM
+import Data.Hashable (Hashable)
+import qualified Data.Set as S
+import qualified Data.Heap as H
+import Data.List (permutations, genericIndex)
+
+createMinPrioHeap :: Ord a1 => (a1,a) -> H.MinPrioHeap a1 a
+createMinPrioHeap = H.singleton
+
+-- $cat1
+-- All of the following functions return distances as a @Maybe Int@, where @Nothing@ is returned if no path is found.
+-- The graph is a @HashMap@ mapping each node to a sequence of (neighbour, edge weight) pairs.
+
+-- | Returns the shortest distance between two nodes in a graph.
+shortestDistance :: (Foldable t, Hashable n, Ord a, Num a)
+    => HM.HashMap n (t (n, a)) -- ^ Graph
+    -> n -- ^ Start node
+    -> n -- ^ End node
+    -> Maybe a
+shortestDistance graph = shortestDistanceOnMagma (repeat graph)
+
+-- | Returns the shortest distance between two nodes in a graph and a list of all possible paths from the ending node to the starting node.
+-- The starting node is not included in each path.
+shortestPaths :: (Foldable t, Hashable n, Ord a, Num a)
+    => HM.HashMap n (t (n, a)) -- ^ Graph
+    -> n -- ^ Start node
+    -> n -- ^ End node
+    -> (Maybe a, [[n]])
+shortestPaths graph = shortestPathsOnMagma (repeat graph)
+
+-- | Returns the shortest distance between two nodes in a list of graphs where the neighbours of a node in any given graph all lie in the succeeding graph. The ending node must be present in each graph.
+-- This precondition is not checked.
+shortestDistanceOnMagma :: (Foldable t, Hashable n, Ord a, Num a)
+    => [HM.HashMap n (t (n, a))] -- ^ Graphs
+    -> n -- ^ Start node
+    -> n -- ^ End node
+    -> Maybe a
+shortestDistanceOnMagma graphs start end = fst $ shortestPathsOnMagma graphs start end
+
+-- | Returns the shortest distance between two nodes in a list of graphs and a list of all possible paths from the ending node to the starting node. The ending node must be present in each graph.
+-- This precondition is not checked.
+-- The starting node is not included in each path.
+shortestPathsOnMagma :: (Foldable t, Hashable n, Ord a, Num a)
+    => [HM.HashMap n (t (n, a))] -- ^ Graphs
+    -> n -- ^ Start node
+    -> n -- ^ End node
+    -> (Maybe a, [[n]])
+shortestPathsOnMagma graphs start end =
+    let initQueue = createMinPrioHeap (0,start)
+        initPaths = HM.singleton start (0,[[]])
+        helper (paths,queue) = case H.view queue of
+            Nothing -> (paths,queue)
+            Just ((_,n),ns) ->
+                let Just (currentDistance,currentPaths) = HM.lookup n paths
+                    Just neighbours = HM.lookup n (graphs !! length (head currentPaths))
+                    updateNeighbour (n',d') (p',q') = case HM.lookup n' p' of
+                        Nothing -> (HM.insert n' (currentDistance+d',map (n':) currentPaths) p', H.insert (currentDistance+d',n') q')
+                        Just (d'',ps'') ->
+                            if d'' < currentDistance+d' then
+                                (p',q')
+                            else if d'' > currentDistance+d' then
+                                (HM.insert n' (currentDistance+d',map (n':) currentPaths) p', H.insert (currentDistance+d',n') q')
+                            else
+                                (HM.insert n' (currentDistance+d',ps'' ++ map (n':) currentPaths) p', q')
+                in helper $ foldr updateNeighbour (paths,ns) neighbours
+
+    in case HM.lookup end $ fst (helper (initPaths,initQueue)) of
+        Nothing -> (Nothing, [])
+        Just (d,ps) -> (Just d, ps)
+
+-- | Returns the 4 points orthogonally adjacent to the given point.
+neighbours4 :: (Num a, Num b) => (a, b) -> [(a, b)]
+neighbours4 (x,y) = [(x+1,y),(x,y+1),(x-1,y),(x,y-1)]
+
+-- | Returns the 8 points orthogonally or diagonally adjacent to the given point.
+neighbours8 :: (Enum a, Enum b, Eq a, Eq b, Num a, Num b) => (a, b) -> [(a, b)]
+neighbours8 (x,y) = [(x+p,y+q) | p <- [-1..1], q <- [-1..1], p /= 0 || q /= 0]
+
+-- | Returns the 6 points orthogonally adjacent to the given point in 3D space.
+neighbours6 :: (Num a, Num b, Num c) => (a, b, c) -> [(a, b, c)]
+neighbours6 (x,y,z) = [(x+1,y,z),(x,y+1,z),(x,y,z+1),(x-1,y,z),(x,y-1,z),(x,y,z-1)]
+
+-- | Returns the 26 points orthogonally or diagonally adjacent to the given point in 3D space.
+neighbours26 :: (Enum a, Enum b, Enum c, Eq a, Eq b, Eq c, Num a, Num b, Num c) => (a, b, c) -> [(a, b, c)]
+neighbours26 (x,y,z) = [(x+p,y+q,z+r) | p <- [-1..1], q <- [-1..1], r <- [-1..1], p /= 0 || q /= 0 || r /= 0]
+
+-- | Returns the Taxicab/Manhattan distance between two points in 2D space.
+taxicab2 :: Num a => (a, a) -> (a, a) -> a
+taxicab2 (a,b) (c,d) = abs (a-c) + abs (b-d)
+
+-- | Returns the Taxicab/Manhattan distance between two points in 3D space.
+taxicab3 :: Num a => (a, a, a) -> (a, a, a) -> a
+taxicab3 (a,b,c) (d,e,f) = abs (a-d) + abs (b-e) + abs (c-f)
+
+enumerateBase :: (Num y, Num x, Enum y, Enum x) => String -> [((x, y), Char)]
+enumerateBase s =
+    let ss = lines s
+        ys = zipWith (\n l -> map (n,) l) [0..] ss
+        xs = map (zipWith (\x (y,c) -> ((x,y),c)) [0..]) ys
+    in concat xs
+
+-- $cat2
+-- The following functions operate on a grid of characters as a string with a newline after each row (as seen in several Advent of Code puzzle inputs).
+
+-- | Converts a grid to a list of triples @(x,y,c)@ representing xy coordinates and the character at that location.
+enumerate :: (Num y, Num x, Enum y, Enum x) => String -> [(x, y, Char)]
+enumerate = map (\((x,y),c) -> (x,y,c)) . enumerateBase
+
+-- | Enumerates a grid along with reading the characters (usually as integers).
+enumerateRead :: (Read c, Num y, Num x, Enum y, Enum x) => String -> [(x, y, c)]
+enumerateRead = map (\((x,y),c) -> (x,y,read [c])) . enumerateBase
+
+-- | Enumerates a grid and stores it in a @HashMap@ where points are mapped to the character at that location.
+enumerateHM :: (Num x, Num y, Enum x, Enum y, Hashable x, Hashable y) => String -> HM.HashMap (x, y) Char
+enumerateHM = HM.fromList . enumerateBase
+
+-- | Enumerates a grid and stores it in a @HashMap@ along with reading the characters (usually as integers).
+enumerateReadHM :: (Num x, Num y, Enum x, Enum y, Hashable x, Hashable y, Read c) => String -> HM.HashMap (x, y) c
+enumerateReadHM = HM.fromList . map (\((x,y),c) -> ((x,y),read [c])) . enumerateBase
+
+-- | Returns a list of points on a grid for which a certain condition is met.
+enumerateFilter :: (Num y, Num x, Enum y, Enum x) => (Char -> Bool) -> String -> [(x, y)]
+enumerateFilter f = map fst . filter (f . snd) . enumerateBase
+
+-- | Returns a set of points on a grid for which a certain condition is met.
+enumerateFilterSet :: (Ord x, Ord y, Num y, Num x, Enum y, Enum x) => (Char -> Bool) -> String -> S.Set (x, y)
+enumerateFilterSet f = S.fromList . enumerateFilter f
+
+floodFill' :: Ord a => (a -> [a]) -> S.Set a -> S.Set a -> S.Set a -> S.Set a
+floodFill' neighbours finished frontier blocks
+    | S.null frontier = finished
+    | otherwise = floodFill' neighbours (S.union frontier finished) newfrontier blocks
+    where
+        newfrontier = S.filter (\n -> n `S.notMember` finished || n `S.notMember` frontier || n `S.notMember` blocks) $ S.unions $ S.map (S.fromList . neighbours) frontier
+
+floodFillWith' :: Ord a => (a -> a -> Bool) -> (a -> [a]) -> S.Set a -> S.Set a -> S.Set a
+floodFillWith' cond neighbours finished frontier
+    | S.null frontier = finished
+    | otherwise = floodFillWith' cond neighbours (S.union frontier finished) newfrontier
+    where
+        newfrontier = S.filter (\n -> n `S.notMember` finished || n `S.notMember` frontier) $ S.unions $ S.map (S.fromList . (\c -> filter (cond c) $ neighbours c)) frontier
+
+-- | Applies a flood fill algorithm given a function to generate a point's neighbours, a starting set of points, and a set of points to avoid. Returns a set of all points covered.
+floodFill :: Ord a
+    => (a -> [a]) -- ^ Neighbour function
+    -> S.Set a -- ^ Initial set of points
+    -> S.Set a -- ^ Set of points to avoid
+    -> S.Set a
+floodFill neighbours = floodFill' neighbours S.empty
+
+-- | Applies a flood fill algorithm given a function to generate a point's neighbours, a condition that filters out points generated by said function, and a starting set of points. Returns a set of all points covered.
+-- The condition is of the form @a -> a -> Bool@, which returns @True@ if the second point is a valid neighbour of the first point and @False@ otherwise.
+floodFillWith :: Ord a
+    => (a -> a -> Bool) -- ^ Condition
+    -> (a -> [a]) -- ^ Neighbour function
+    -> S.Set a -- ^ Initial set of points
+    -> S.Set a
+floodFillWith cond neighbours = floodFillWith' cond neighbours S.empty
+
+-- | Generates a list of all possible lists of length n by taking elements from the provided list of length l.
+-- Relative order is maintained, and the length of the returned list is \(_{n}C_{l}\).
+choose :: (Num n, Eq n) => n -> [a] -> [[a]]
+choose n (x:xs) = map (x:) (choose (n-1) xs) ++ choose n xs
+choose 0 _ = [[]]
+choose _ [] = []
+
+-- | Generates a list of all possible lists of length n by taking elements from the provided list of length l.
+-- The length of the returned list is \(_{n}P_{l}\).
+permute :: (Num n, Eq n) => n -> [a] -> [[a]]
+permute n = concatMap permutations . choose n
+
+-- | Gets the nth element of an infinite list, assuming that each element in the list can be generated using the previous element, for example, a list generated with @iterate@.
+extrapolate :: (Integral b, Ord a) => b -> [a] -> a
+extrapolate n ls = let (o,p) = helper 0 S.empty ls in ls `genericIndex` (((n-o) `mod` p) + o)
+    where
+        helper k finished (l:ls')
+            | S.null matches = helper (k+1) (S.insert (k,l) finished) ls'
+            | otherwise = let o = fst $ S.elemAt 0 matches in (o,k-o)
+            where matches = S.filter ((==l) . snd) finished
+
+-- | Generates a range with @[x..y]@, but reverses the list instead of returning an empty range if x > y.
+range :: (Ord a, Enum a) => a -> a -> [a]
+range x y = if y < x then [x,pred x..y] else [x..y]
+
+-- | Takes (a,b) and (c,d) as arguments and returns the intersection of the ranges [a..b] and [c..d] as another pair if it is not empty.
+rangeIntersect :: Ord b => (b, b) -> (b, b) -> Maybe (b, b)
+rangeIntersect (a,b) (c,d)
+    | b < c || a > d = Nothing
+    | otherwise = Just (max a c, min b d)
+
+-- | Converts a list of booleans (parsed as a binary number) to an integer.
+binToDec :: Num a => [Bool] -> a
+binToDec = sum . zipWith (*) (map (2^) [0..]) . map (fromIntegral . fromEnum) . reverse