Documentation ¶
Overview ¶
Package lib contains a random assortment of code useful for solving Advent of Code challenges.
Index ¶
- Constants
- Variables
- func AStar[S comparable](initial []S, done func(S) bool, next func(S, map[S]int), estimate func(S) int) int
- func Abs[T constraints.Signed | constraints.Float](v T) T
- func AddEdge[S comparable](edges map[S]map[S]struct{}, a, b S)
- func AddEdges[S comparable](edges map[S]map[S]struct{}, a, b S)
- func AddSet[K comparable](m map[K]struct{}, keys ...K) map[K]struct{}
- func Assert(v bool)
- func AssertEq(a, b any)
- func AssertGreater[T constraints.Ordered](a, b T)
- func AssertGreaterEq[T constraints.Ordered](a, b T)
- func AssertInRange[T constraints.Ordered](v, min, max T)
- func AssertLess[T constraints.Ordered](a, b T)
- func AssertLessEq[T constraints.Ordered](a, b T)
- func AssertNil(v any)
- func Assertf(v bool, s string, args ...any)
- func AtLeast[T constraints.Ordered](n T, vals ...T) int
- func BFS[S comparable](initial []S, next func(state S, nextStates map[S]struct{}), ...) (steps map[S]int, from map[S]S)
- func BronKerbosch[S comparable](edges map[S]map[S]struct{}, opts ...BronKerboschOption) map[S]struct{}
- func Clamp[T constraints.Ordered](val, min, max T) T
- func Color(c uint8) string
- func Dijkstra[S comparable](initial []S, next func(S, map[S]int), opts ...DijkstraOption) (costs map[S]int, prevs map[S][]S)
- func DijkstraPaths[S comparable](start, end S, prevs map[S][]S) [][]S
- func Extract(s, re string, dsts ...interface{}) int
- func ExtractBits(v uint64, high, low int) uint64
- func ExtractDigits(s string) []int
- func ExtractInt(s string) int
- func ExtractInt64s(s string) []int64
- func ExtractInts(s string) []int
- func ExtractMaybe(s, re string, dsts ...interface{}) (int, bool)
- func ExtractUints(s string) []int
- func FindCombos[T constraints.Integer](items []T, initial uint64, target T) []uint64
- func GCD[T constraints.Integer](a, b T) T
- func HasBit(field uint64, i int) bool
- func Hi(b byte) byte
- func HiIsLo(b byte) bool
- func If[T any](cond bool, a, b T) T
- func Input(date string) string
- func InputInt64s(date string) []int64
- func InputInts(date string) []int
- func InputLines(date string) []string
- func InputLinesBytes(date string, valid ...byte) [][]byte
- func InputParagraphs(date string) [][]string
- func Intersect[K comparable, V any](a, b map[K]V) map[K]V
- func InvertMap[K, V comparable](m map[K]V) map[V]K
- func Join[T any](vals []T, sep string) string
- func LCM[T constraints.Integer](vals ...T) T
- func Lo(b byte) byte
- func MapHasKey[K comparable, V any](m map[K]V, k K) bool
- func MapHasValue[K, V comparable](m map[K]V, want V) bool
- func MapKeys[K comparable, V any](m map[K]V) []K
- func MapKeysWithVal[K, V comparable](m map[K]V, want V) []K
- func MapSomeKey[K comparable, V any](m map[K]V) K
- func MapVals[K comparable, V any](m map[K]V) []V
- func Max[T constraints.Ordered](vals ...T) T
- func Min[T constraints.Ordered](vals ...T) T
- func Mod[T constraints.Integer](n, m T) T
- func Move[T any](v []T, s1, s2, d int)
- func NewByteLines(s string, valid ...byte) [][]byte
- func OCR(b [][]byte, blank byte) string
- func PackInt[T constraints.Integer](packed uint64, val T, size, offset int) uint64
- func PackInts[T constraints.Integer](vals ...T) uint64
- func Panicf(s string, args ...any)
- func Perms[T any](s []T, ch chan []T)
- func Pow[T constraints.Integer](x T, n int) T
- func Product[T constraints.Integer | constraints.Float](vals ...T) T
- func Reverse[T any](s []T)
- func ReverseBytes(b []byte) []byte
- func Rotate(first, middle, last int, swap func(i, j int))
- func RotateBy(n, amt int, swap func(i, j int))
- func RotateSlice[T any](s []T, amt int)
- func Set[K comparable, V any](m map[K]V) map[K]struct{}
- func SetAscInt[T constraints.Integer](s []T, start T)
- func SetBit(field uint64, i int, v bool) uint64
- func SliceIndexesWithVal[T comparable](s []T, want T) []int
- func SortJoin[T constraints.Ordered](vals []T, sep string) string
- func Subgraphs[S comparable](edges map[S]map[S]struct{}) [][]S
- func Sum[T constraints.Integer | constraints.Float](vals ...T) T
- func Tokenize(s string, tokens ...interface{}) []string
- func TryExtract(s, re string, dsts ...interface{}) bool
- func Union[K comparable, V any](a, b map[K]V) map[K]V
- func UnpackInt[T constraints.Integer](packed uint64, size, offset int) T
- func UnpackInt2(p uint64) (a, b int)
- func UnpackIntSigned[T constraints.Signed](packed uint64, size, offset int) T
- func UnpackIntSigned2(p uint64) (a, b int)
- func UnpackInts[T constraints.Integer](packed uint64, n int) []T
- type BFSOption
- type BitReader
- type BronKerboschOption
- type ByteGrid
- func InputByteGrid(date string, valid ...byte) ByteGrid
- func InputByteGrids(date string, valid ...byte) []ByteGrid
- func NewByteGrid(r, c int, ch byte) ByteGrid
- func NewByteGridLines(lines []string, valid ...byte) ByteGrid
- func NewByteGridRow(r []byte) ByteGrid
- func NewByteGridString(s string, valid ...byte) ByteGrid
- func (b ByteGrid) Cols() int
- func (b ByteGrid) Copy() ByteGrid
- func (b ByteGrid) CopyRect(r0, c0, r1, c1 int) ByteGrid
- func (b ByteGrid) Count(chars ...byte) int
- func (b ByteGrid) CountRect(r0, c0, r1, c1 int, chars ...byte) int
- func (b ByteGrid) Dump() string
- func (b ByteGrid) Find(ch byte) (r, c int)
- func (b ByteGrid) FlipHoriz() ByteGrid
- func (b ByteGrid) FlipVert() ByteGrid
- func (b ByteGrid) Get(r, c int, def byte) byte
- func (b ByteGrid) InBounds(r, c int) bool
- func (b ByteGrid) Iter(f func(r, c int))
- func (b ByteGrid) IterLine(r0, c0, r1, c1 int, f func(r, c int))
- func (b ByteGrid) IterRect(r0, c0, r1, c1 int, f func(r, c int))
- func (b ByteGrid) MaxCol() int
- func (b ByteGrid) MaxRow() int
- func (b ByteGrid) MustFind(ch byte) (r, c int)
- func (b ByteGrid) RotateCW() ByteGrid
- func (b ByteGrid) Rows() int
- func (b ByteGrid) SetRect(r0, c0, r1, c1 int, ch byte)
- type DijkstraConfig
- type DijkstraOption
- type Dir
- type Heap
- type HeapFunc
- type Instr
- type Intcode
Constants ¶
const ( // ClearScreen clears the screen. ClearScreen = "\033[2J" // MoveHome moves the cursor to the top-left corner of the screen. // Writing to stdout will overwrite the existing contents of the screen. MoveHome = "\033[H" )
Variables ¶
Dirs lists all directions.
Functions ¶
func AStar ¶
func AStar[S comparable]( initial []S, done func(S) bool, next func(S, map[S]int), estimate func(S) int) int
AStar uses the A* algorithm to find the minimum cost from the initial state(s) to a state for which the done function returns true.
The next function should fill the passed map with all states reachable in a single step from the passed state along with the corresponding additional cost.
The estimate function should return a lower bound on the remaining cost to go from state to a target state (i.e. one for which done will return true).
See https://www.redblobgames.com/pathfinding/a-star/introduction.html.
func Abs ¶
func Abs[T constraints.Signed | constraints.Float](v T) T
Abs returns the absolute value of v.
func AddEdge ¶
func AddEdge[S comparable](edges map[S]map[S]struct{}, a, b S)
AddEdge adds an edge from a to b.
func AddEdges ¶
func AddEdges[S comparable](edges map[S]map[S]struct{}, a, b S)
AddEdges adds edges from a to b and from b to a.
func AddSet ¶
func AddSet[K comparable](m map[K]struct{}, keys ...K) map[K]struct{}
AddSet adds keys to the supplied (possibly-nil) map to struct{}. The set is returned (and should be used thereafter).
func AssertGreater ¶
func AssertGreater[T constraints.Ordered](a, b T)
AssertGreater panics if a <= b.
func AssertGreaterEq ¶
func AssertGreaterEq[T constraints.Ordered](a, b T)
AssertGreaterEq panics if a < b.
func AssertInRange ¶
func AssertInRange[T constraints.Ordered](v, min, max T)
AssertInRange panics if v is not between min and max (inclusive).
func AtLeast ¶
func AtLeast[T constraints.Ordered](n T, vals ...T) int
AtLeast returns the number of values greater than or equal to n.
func BFS ¶
func BFS[S comparable]( initial []S, next func(state S, nextStates map[S]struct{}), opts ...BFSOption[S], ) (steps map[S]int, from map[S]S)
BFS performs a breadth-first search to discover paths to states reachable from initial. The returned steps map contains the minimum number of steps to each state. The returned from map contains the state (value) preceding each destination state (key). Initial states are also included in from and list themselves as preceding states.
func BronKerbosch ¶
func BronKerbosch[S comparable](edges map[S]map[S]struct{}, opts ...BronKerboschOption) map[S]struct{}
BronKerbosch finds the maximal clique (that is, subgraph such that each pair of nodes is connected) in an undirected graph: https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm
func Clamp ¶
func Clamp[T constraints.Ordered](val, min, max T) T
Clamp clamps val within [min, max].
func Color ¶
Color returns the ANSI escape sequence for setting the foreground color to c. See https://stackoverflow.com/a/33206814 for available colors.
func Dijkstra ¶
func Dijkstra[S comparable]( initial []S, next func(S, map[S]int), opts ...DijkstraOption, ) (costs map[S]int, prevs map[S][]S)
Dijkstra uses Dijkstra's algorithm to find the minimum costs from one or more initial states to all reachable states. It also returns all minimum-cost paths.
The next function should fill the passed map with all states reachable in a single step from the passed state along with the corresponding additional cost.
The returned maps contain the minimum cost of reaching each state and the state(s) (values) directly preceding each state (key).
func DijkstraPaths ¶
func DijkstraPaths[S comparable](start, end S, prevs map[S][]S) [][]S
DijkstraPaths reconstructs min-cost paths from start to end given a prevs map returned by an earlier call to Dijkstra. start must be one of the starting states passed to Dijkstra. The returned paths will begin with the state after start (i.e. start is not included) and terminate with end (i.e. end is included).
func Extract ¶
Extract is a convenience wrapper around ExtractMaybe that panics if re doesn't match s.
func ExtractBits ¶
ExtractBits zeros all bits in v except the ones between indexes high and low (inclusive) and right-shifts the resulting value by low.
In other words:
val: abcdefgh pos: 76543210
If high is 7 and low is 0, returns abcdefgh. If high is 5 and low is 1, returns 000cdefg. If high is 3 and low is 3, returns 0000000e.
func ExtractDigits ¶
ExtractDigits extracts individual digits from s and returns them as ints.
func ExtractInt64s ¶
ExtractInt64s extracts all integers from s as 64-bit ints. Non-digits (besides '-') are ignored.
func ExtractInts ¶
ExtractInts extracts all integers from s. Non-digits (besides '-') are ignored.
func ExtractMaybe ¶
ExtractMaybe executes regular expression re on s and assigns groups to dsts. It returns the total match length and a bool indicating whether re matched s.
func ExtractUints ¶
ExtractUints extracts all zero or positive integers from s as ints. Non-digits (including '-') are ignored.
func FindCombos ¶
func FindCombos[T constraints.Integer](items []T, initial uint64, target T) []uint64
FindCombos returns all combinations of the supplied items that sum exactly to target. initial is a bitfield specifying available items, e.g. if 0x1 is set then items[0] can be used. Pass 1<<len(items)-1 to use all items.
func GCD ¶
func GCD[T constraints.Integer](a, b T) T
GCD returns the greatest common denominator of a and b using the Euclidean algorithm. See https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm.
func Input ¶
Input returns input for the specified date, e.g. "2020/13" (leading zero optional). Input is downloaded and cached. If path or "-" positional arg was passed, data is read from there (or stdin) instead.
func InputInt64s ¶
InputInt64s extracts 64-bit integers from the day's input. See ExtractInt64s.
func InputLines ¶
InputLines returns newline-separated lines of input for the specified day.
func InputLinesBytes ¶
InputLinesBytes returns newline-separated lines of input for the specified day. If valid is non-empty, panics if any unlisted bytes are encountered.
func InputParagraphs ¶
InputParagraphs returns the day's input split into paragraphs on multiple newlines. Each paragraph is split further into individual lines.
func Intersect ¶
func Intersect[K comparable, V any](a, b map[K]V) map[K]V
Intersect returns a new map with the intersection of keys from a and b. Values from a will be used.
func InvertMap ¶
func InvertMap[K, V comparable](m map[K]V) map[V]K
InvertMap returns a new map in which m's values map to its keys.
func LCM ¶
func LCM[T constraints.Integer](vals ...T) T
LCM reaturns the least common multiple of the supplied integers.
func MapHasKey ¶
func MapHasKey[K comparable, V any](m map[K]V, k K) bool
MapHasKey returns true if map m contains key k.
func MapHasValue ¶
func MapHasValue[K, V comparable](m map[K]V, want V) bool
MapHasValue returns true if map m contains the specified value.
func MapKeys ¶
func MapKeys[K comparable, V any](m map[K]V) []K
MapKeys returns keys from the provided map in an arbitrary order.
func MapKeysWithVal ¶
func MapKeysWithVal[K, V comparable](m map[K]V, want V) []K
MapKeysWithVal returns keys from the provided map that have want as their value.
func MapSomeKey ¶
func MapSomeKey[K comparable, V any](m map[K]V) K
MapSomeKey returns an arbitrary key from the supplied map.
func MapVals ¶
func MapVals[K comparable, V any](m map[K]V) []V
MapVals returns values from the provided map in an arbitrary order.
func Max ¶
func Max[T constraints.Ordered](vals ...T) T
Max returns the maximum of the supplied values.
func Min ¶
func Min[T constraints.Ordered](vals ...T) T
Min returns the minimum of the supplied values.
func Mod ¶
func Mod[T constraints.Integer](n, m T) T
Mod computes n % m but does what I actually want with negative n values.
func Move ¶
Move moves the elements in slice v's half-open range [s1,s2) to be at index d. Other elements are preserved and shifted as needed.
func NewByteLines ¶
NewByteLines returns newline-separated lines from s. Blank lines are skipped. If valid is non-empty, panics if any unlisted bytes are encountered.
func OCR ¶
OCR does a terrible job of trying to recognize glyphs in b. Glyphs must be in a single row with one or more blank columns between them.
func PackInt ¶
func PackInt[T constraints.Integer](packed uint64, val T, size, offset int) uint64
PackInt sets a size-bit region at the supplied offset (from the LSB) in packed to val.
func PackInts ¶
func PackInts[T constraints.Integer](vals ...T) uint64
PackInts packs vals into a uint64, dividing the total bits evenly across the values. Values must fit within the supplied bits. Use UnpackIntSigned to unpack signed ints.
func Perms ¶
func Perms[T any](s []T, ch chan []T)
Perms sends all permutations of the supplied slice to ch and closes it. This is the non-recursive version of https://en.wikipedia.org/wiki/Heap%27s_algorithm. s is modified in-place.
func Product ¶
func Product[T constraints.Integer | constraints.Float](vals ...T) T
Product returns the product of the supplied values.
func Reverse ¶
func Reverse[T any](s []T)
Reverse reverses the order of the elements in the supplied slice.
func ReverseBytes ¶
ReverseBytes reverses b in-place. A pointer to b is also returned.
func Rotate ¶
Rotate rotates the elements in [first,last) such that middle becomes the new first element. This comes from http://www.cplusplus.com/reference/algorithm/rotate/ .
func RotateSlice ¶
RotateSlice is a wrapper around RotateBy that operates on a slice.
func Set ¶
func Set[K comparable, V any](m map[K]V) map[K]struct{}
Set returns a map-to-empty-struct containing keys from m, a map.
func SetAscInt ¶
func SetAscInt[T constraints.Integer](s []T, start T)
SetAscInt initializes slice s to ascending signed integer values.
func SliceIndexesWithVal ¶
func SliceIndexesWithVal[T comparable](s []T, want T) []int
SliceIndexesWithVal returns indexes into s of elements equal to want.
func SortJoin ¶
func SortJoin[T constraints.Ordered](vals []T, sep string) string
SortJoin sorts vals (without modifying the passed-in slice), stringifies vals using fmt.Sprint, and joins them using sep.
func Subgraphs ¶
func Subgraphs[S comparable](edges map[S]map[S]struct{}) [][]S
Subgraphs returns all subgraphs from edges, the edges of an undirected graph.
func Sum ¶
func Sum[T constraints.Integer | constraints.Float](vals ...T) T
Sum returns the sum of the supplied values.
func Tokenize ¶
Tokenize splits s into tokens from the supplied args (either string or *regexp.Regexp). Whitespace is ignored. Regexps should be '^'-prefixed for better performance.
func TryExtract ¶
TryExtract is a convenience wrapper around ExtractMaybe that omits the number of matched characters. It's useful for case conditions in switch statements.
func Union ¶
func Union[K comparable, V any](a, b map[K]V) map[K]V
Union returns a new map with the union of keys from a and b. If a key is present in both maps, the value from a will be used.
func UnpackInt ¶
func UnpackInt[T constraints.Integer](packed uint64, size, offset int) T
UnpackInt unpacks and returns an unsigned value of size bits at the supplied offset (from the LSB) from packed.
func UnpackInt2 ¶
UnpackInt2 is a convenience function that unpacks two 32-bit values from p.
func UnpackIntSigned ¶
func UnpackIntSigned[T constraints.Signed](packed uint64, size, offset int) T
UnpackIntSigned is like UnpackInt but with support for negative numbers.
func UnpackIntSigned2 ¶
UnpackIntSigned2 is like UnpackInt2 but for signed ints.
func UnpackInts ¶
func UnpackInts[T constraints.Integer](packed uint64, n int) []T
UnpackInts unpacks n unsigned values previously packed using PackInts.
Types ¶
type BFSOption ¶
type BFSOption[S comparable] func(cfg *bfsConfig[S])
BFSOption can be passed to the BFS function to configure its behavior.
func BFSAllDests ¶
func BFSAllDests[S comparable](dests []S) BFSOption[S]
BFSAllDests specifies states that must all be reached before exiting.
func BFSAnyDests ¶
func BFSAnyDests[S comparable](dests map[S]struct{}) BFSOption[S]
BFSAnyDests specifies states of which just one must be reached before exiting.
func BFSMaxSteps ¶
func BFSMaxSteps[S comparable](steps int) BFSOption[S]
BFSMaxSteps specifies the maximum number of steps before exiting. BFSNoSteps must not also be passed.
func BFSNoFrom ¶
func BFSNoFrom[S comparable]() BFSOption[S]
BFSNoFrom indicates that preceding states don't need to be tracked. The next function must terminate paths itself. The returned from map will be nil.
func BFSNoSteps ¶
func BFSNoSteps[S comparable]() BFSOption[S]
BFSNoSteps indicates that steps don't need to be tracked. The returned steps map will be nil.
type BitReader ¶
type BitReader struct {
// contains filtered or unexported fields
}
BitReader reads variable numbers of bits from a byte slice.
func NewBitReader ¶
NewBitReader returns a BitReader that reads bits from b starting at the specified bit offset (with 0 being the MSB of the first byte in the slice).
func (*BitReader) Offset ¶
Offset returns the current offset into the slice that was passed to NewBitReader.
type BronKerboschOption ¶
type BronKerboschOption func(*bronKerboschConfig)
BronKerboschOption can be passed to BronKerbosch to configure its behavior.
func BronKerboschMaxSize ¶
func BronKerboschMaxSize(v int) BronKerboschOption
BronKerboschMaxSize aborts the algorithm once a clique of the given size or larger has been found.
type ByteGrid ¶
type ByteGrid [][]byte
ByteGrid holds a two-dimensional grid of bytes.
func InputByteGrid ¶
InputByteGrid returns a ByteGrid holding the input for the specified day. If valid is non-empty, panics if any unlisted bytes are encountered.
func InputByteGrids ¶
InputByteGrids returns the day's input with each paragraph (per InputParagraphs) interpreted as a ByteGrid.
func NewByteGrid ¶
NewByteGrid returns a 2-dimensional array of ch with r rows and c columns.
func NewByteGridLines ¶
NewByteGridLines returns a ByteGrid consisting of the supplied lines.
func NewByteGridRow ¶
NewByteGrid creates a ByteGrid containing only the supplied row.
func NewByteGridString ¶
NewByteGridString splits s into rows per NewByteLines and returns a ByteGrid.
func (ByteGrid) CopyRect ¶
CopyRect returns a copy of the rectangle bounded by (r0, c0) and (r1, c1), inclusive.
func (ByteGrid) CountRect ¶
CountRect returns the number of occurrences of chars in the rectangle bounded by (r0, c0) and (r1, c1), inclusive. The supplied bounds are clamped.
func (ByteGrid) Find ¶
Find returns the coordinates of the first occurrence of ch. Positions are checked in ascending (row, column) order. (-1, -1) is returned if the character isn't found.
func (ByteGrid) Get ¶
Get returns the byte at (r, c). If the coordinates are outside b's bounds, def is returned instead.
func (ByteGrid) IterLine ¶
IterLine calls f for each coordinate in the line from (r0, c0) to (r1, c1). The supplied points may be outside of b's bounds, but f will only be called for in-bounds coordinates.
func (ByteGrid) IterRect ¶
IterRect calls f for each coordinate in the rectangle bounded by (r0, c0) and (r1, c1), inclusive. The supplied bounds are clamped and swapped if needed.
func (ByteGrid) MustFind ¶
MustFind is a convinence wrapper around Find that asserts that ch is found.
type DijkstraConfig ¶
type DijkstraConfig struct {
// contains filtered or unexported fields
}
type DijkstraOption ¶
type DijkstraOption func(cfg *DijkstraConfig)
DijkstraOption can be passed to the Dijkstra function to configure its behavior.
func DijkstraMaxCost ¶
func DijkstraMaxCost(cost int) DijkstraOption
DjistraMaxCost specifies the maximum path cost to explore.
type Dir ¶
type Dir int
Dir represents a cardinal direction.
type Heap ¶
type Heap[T any] struct { // contains filtered or unexported fields }
Heap implements a binary heap. See https://runestone.academy/runestone/books/published/pythonds/Trees/BinaryHeapImplementation.html. (I originally used the description from https://www.cs.princeton.edu/~wayne/cs423/lectures/heaps-4up.pdf but I ended up with buggy code; probably I messed up while writing it.)
type Instr ¶
type Instr struct { Op uint8 // contains filtered or unexported fields }
Instr represents a single instruction.
func NewInstr ¶
NewInstr parses an instruction from ln. rmin and rmax specify the start and end characters for registers. ops maps from opcode to a regular expression matching the operation, with 0, 1, or 2 subgroups used to extract arguments.
type Intcode ¶
type Intcode struct { Mem map[int64]int64 In, Out chan int64 InFunc func() int64 // used instead of In if non-nil OutFunc func(int64) // used instead of Out if non-nil // contains filtered or unexported fields }
Intcode runs Intcode instructions.
func NewIntcode ¶
NewIntcode returns a new Intcode VM with a copy of the supplied initial memory.
func (*Intcode) Halt ¶
func (vm *Intcode) Halt()
Halt makes the VM exit with success before running the next instruction.
func (*Intcode) Run ¶
Run synchronously runs the VM to completion. It returns true if hlt was executed and false if the VM crashed due to an invalid opcode or bad memory access.