| Copyright | (c) M1n3c4rt 2025 |
|---|---|
| License | BSD-3-Clause |
| Maintainer | vedicbits@gmail.com |
| Stability | stable |
| Safe Haskell | Safe-Inferred |
| Language | Haskell2010 |
Utility.AOC
Description
Synopsis
- shortestDistance :: (Foldable t, Hashable n, Ord a, Num a) => HashMap n (t (n, a)) -> n -> n -> Maybe a
- shortestPaths :: (Foldable t, Hashable n, Ord a, Num a) => HashMap n (t (n, a)) -> n -> n -> (Maybe a, [[n]])
- shortestDistanceOnMagma :: (Foldable t, Hashable n, Ord a, Num a) => [HashMap n (t (n, a))] -> n -> n -> Maybe a
- shortestPathsOnMagma :: (Foldable t, Hashable n, Ord a, Num a) => [HashMap n (t (n, a))] -> n -> n -> (Maybe a, [[n]])
- neighbours4 :: (Num a, Num b) => (a, b) -> [(a, b)]
- neighbours8 :: (Enum a, Enum b, Eq a, Eq b, Num a, Num b) => (a, b) -> [(a, b)]
- neighbours6 :: (Num a, Num b, Num c) => (a, b, c) -> [(a, b, c)]
- 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)]
- taxicab2 :: Num a => (a, a) -> (a, a) -> a
- taxicab3 :: Num a => (a, a, a) -> (a, a, a) -> a
- enumerate :: (Num y, Num x, Enum y, Enum x) => String -> [(x, y, Char)]
- enumerateRead :: (Read c, Num y, Num x, Enum y, Enum x) => String -> [(x, y, c)]
- enumerateHM :: (Num x, Num y, Enum x, Enum y, Hashable x, Hashable y) => String -> HashMap (x, y) Char
- enumerateReadHM :: (Num x, Num y, Enum x, Enum y, Hashable x, Hashable y, Read c) => String -> HashMap (x, y) c
- enumerateFilter :: (Num y, Num x, Enum y, Enum x) => (Char -> Bool) -> String -> [(x, y)]
- enumerateFilterSet :: (Ord x, Ord y, Num y, Num x, Enum y, Enum x) => (Char -> Bool) -> String -> Set (x, y)
- floodFill :: Ord a => (a -> [a]) -> Set a -> Set a -> Set a
- floodFillWith :: Ord a => (a -> a -> Bool) -> (a -> [a]) -> Set a -> Set a
- choose :: (Num n, Eq n) => n -> [a] -> [[a]]
- permute :: (Num n, Eq n) => n -> [a] -> [[a]]
- extrapolate :: (Integral b, Ord a) => b -> [a] -> a
- range :: (Ord a, Enum a) => a -> a -> [a]
- rangeIntersect :: Ord b => (b, b) -> (b, b) -> Maybe (b, b)
- binToDec :: Num a => [Bool] -> a
Pathfinding algorithms
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.
Arguments
| :: (Foldable t, Hashable n, Ord a, Num a) | |
| => HashMap n (t (n, a)) | Graph |
| -> n | Start node |
| -> n | End node |
| -> Maybe a |
Returns the shortest distance between two nodes in a graph.
Arguments
| :: (Foldable t, Hashable n, Ord a, Num a) | |
| => HashMap n (t (n, a)) | Graph |
| -> n | Start node |
| -> n | End node |
| -> (Maybe a, [[n]]) |
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.
shortestDistanceOnMagma Source #
Arguments
| :: (Foldable t, Hashable n, Ord a, Num a) | |
| => [HashMap n (t (n, a))] | Graphs |
| -> n | Start node |
| -> n | End node |
| -> Maybe a |
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.
Arguments
| :: (Foldable t, Hashable n, Ord a, Num a) | |
| => [HashMap n (t (n, a))] | Graphs |
| -> n | Start node |
| -> n | End node |
| -> (Maybe a, [[n]]) |
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.
Neighbour functions
neighbours4 :: (Num a, Num b) => (a, b) -> [(a, b)] Source #
Returns the 4 points orthogonally adjacent to the given point.
neighbours8 :: (Enum a, Enum b, Eq a, Eq b, Num a, Num b) => (a, b) -> [(a, b)] Source #
Returns the 8 points orthogonally or diagonally adjacent to the given point.
neighbours6 :: (Num a, Num b, Num c) => (a, b, c) -> [(a, b, c)] Source #
Returns the 6 points orthogonally 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)] Source #
Returns the 26 points orthogonally or diagonally adjacent to the given point in 3D space.
Taxicab (Manhattan) distance
taxicab2 :: Num a => (a, a) -> (a, a) -> a Source #
Returns the Taxicab/Manhattan distance between two points in 2D space.
taxicab3 :: Num a => (a, a, a) -> (a, a, a) -> a Source #
Returns the Taxicab/Manhattan distance between two points in 3D space.
Grid enumeration
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).
enumerate :: (Num y, Num x, Enum y, Enum x) => String -> [(x, y, Char)] Source #
Converts a grid to a list of triples (x,y,c) representing xy coordinates and the character at that location.
enumerateRead :: (Read c, Num y, Num x, Enum y, Enum x) => String -> [(x, y, c)] Source #
Enumerates a grid along with reading the characters (usually as integers).
enumerateHM :: (Num x, Num y, Enum x, Enum y, Hashable x, Hashable y) => String -> HashMap (x, y) Char Source #
Enumerates a grid and stores it in a HashMap where points are mapped to the character at that location.
enumerateReadHM :: (Num x, Num y, Enum x, Enum y, Hashable x, Hashable y, Read c) => String -> HashMap (x, y) c Source #
Enumerates a grid and stores it in a HashMap along with reading the characters (usually as integers).
enumerateFilter :: (Num y, Num x, Enum y, Enum x) => (Char -> Bool) -> String -> [(x, y)] Source #
Returns a list 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 -> Set (x, y) Source #
Returns a set of points on a grid for which a certain condition is met.
Flood fill
Arguments
| :: Ord a | |
| => (a -> [a]) | Neighbour function |
| -> Set a | Initial set of points |
| -> Set a | Set of points to avoid |
| -> Set a |
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.
Arguments
| :: Ord a | |
| => (a -> a -> Bool) | Condition |
| -> (a -> [a]) | Neighbour function |
| -> Set a | Initial set of points |
| -> Set a |
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.
List selection
choose :: (Num n, Eq n) => n -> [a] -> [[a]] Source #
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 nCl.
permute :: (Num n, Eq n) => n -> [a] -> [[a]] Source #
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 nPl.
Extrapolation
extrapolate :: (Integral b, Ord a) => b -> [a] -> a Source #
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.
Miscellaneous
range :: (Ord a, Enum a) => a -> a -> [a] Source #
Generates a range with [x..y], but reverses the list instead of returning an empty range if x > y.
rangeIntersect :: Ord b => (b, b) -> (b, b) -> Maybe (b, b) Source #
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.