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(state S) bool, next func(state S, nextStates map[S]int), ...) int
- func Abs[T constraints.Signed | constraints.Float](v T) T
- 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 Clamp[T constraints.Ordered](val, min, max T) T
- func Color(c uint8) string
- 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 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 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 BFSOptions
- type BitReader
- type 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) RotateCW() ByteGrid
- func (b ByteGrid) Rows() int
- func (b ByteGrid) SetRect(r0, c0, r1, c1 int, ch byte)
- 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(state S) bool, next func(state S, nextStates map[S]int), estimate func(state 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 nextStates map with all states reachable in a single step from 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 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 *BFSOptions[S]) ( steps map[S]int, from map[S]S)
BFS performs a breadth-first search to discover paths to states reachable from initial. If opts is non-nil, it is used to configure the search. 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 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 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 a "-" command-line flag was provided, data is read from 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 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 BFSOptions ¶
type BFSOptions[S comparable] struct { // AllDests contains states that must all be reached before exiting. AllDests []S // AnyDests contains states of which just one must be reached before exiting. AnyDests map[S]struct{} // MaxSteps contains the maximum number of steps before exiting. // NoSteps must not be true. MaxSteps int // NoSteps indicates that steps don't need to be tracked. // The returned steps map will be nil. NoSteps bool // NoFrom indicates that preceding states don't need to be tracked. // The next function must terminate paths itself. // The returned from map will be nil. NoFrom bool }
BFSOptions specifies optional configuration for BFS.
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 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 NewByteGrid ¶
NewByteGrid returns a 2-dimensional array of ch with r rows and c columns.
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.
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.
Source Files