lib

package
v0.0.0-...-b60e3a7 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Apr 15, 2023 License: BSD-3-Clause Imports: 16 Imported by: 0

Documentation

Overview

Package lib contains a random assortment of code useful for solving Advent of Code challenges.

Index

Constants

View Source 
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"
)
View Source 
const (
	Up Dir = iota
	Left
	Down
	Right

	// Alternate names.
	North = Up
	West  = Left
	South = Down
	East  = Right
)

Variables

This section is empty.

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 Assert 

func Assert(v bool)

Assert panics if v is false.

func AssertEq 

func AssertEq(a, b any)

AssertEq panics if a doesn't equal b.

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 AssertLess 

func AssertLess[T constraints.Ordered](a, b T)

AssertLess panics if a >= b.

func AssertLessEq 

func AssertLessEq[T constraints.Ordered](a, b T)

AssertLessEq panics if a > b.

func AssertNil 

func AssertNil(v any)

AssertNil panics if v is non-nil.

func Assertf 

func Assertf(v bool, s string, args ...any)

Assertf panics if v is false.

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 

func Color(c uint8) string

Color returns the ANSI escape sequence for setting the foreground color to c. See https://stackoverflow.com/a/33206814 for available colors.

func Extract 

func Extract(s, re string, dsts ...interface{}) int

Extract is a convenience wrapper around ExtractMaybe that panics if re doesn't match s.

func ExtractBits 

func ExtractBits(v uint64, high, low int) uint64

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 

func ExtractDigits(s string) []int

ExtractDigits extracts individual digits from s and returns them as ints.

func ExtractInt 

func ExtractInt(s string) int

ExtractInt extracts a single integer from s.

func ExtractInt64s 

func ExtractInt64s(s string) []int64

ExtractInt64s extracts all integers from s as 64-bit ints. Non-digits (besides '-') are ignored.

func ExtractInts 

func ExtractInts(s string) []int

ExtractInts extracts all integers from s. Non-digits (besides '-') are ignored.

func ExtractMaybe 

func ExtractMaybe(s, re string, dsts ...interface{}) (int, bool)

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 

func ExtractUints(s string) []int

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 HasBit 

func HasBit(field uint64, i int) bool

HasBit returns true if the i-th bit in field is set.

func Hi 

func Hi(b byte) byte

Hi returns the top 4 bits of b.

func HiIsLo 

func HiIsLo(b byte) bool

HiIsLo returns true if Hi(b) equals Lo(b).

func If 

func If[T any](cond bool, a, b T) T

If returns a if cond is true and b otherwise. It does not short-circuit.

func Input 

func Input(date string) string

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 

func InputInt64s(date string) []int64

InputInt64s extracts 64-bit integers from the day's input. See ExtractInt64s.

func InputInts 

func InputInts(date string) []int

InputInts extracts integers from the day's input. See ExtractInts.

func InputLines 

func InputLines(date string) []string

InputLines returns newline-separated lines of input for the specified day.

func InputLinesBytes 

func InputLinesBytes(date string, valid ...byte) [][]byte

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 

func InputParagraphs(date string) [][]string

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 Lo 

func Lo(b byte) byte

Hi returns the bottom 4 bits of b.

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 Move 

func Move[T any](v []T, s1, s2, d int)

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 

func NewByteLines(s string, valid ...byte) [][]byte

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 

func OCR(b [][]byte, blank byte) string

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 Panicf 

func Panicf(s string, args ...any)

Panicf panics with the supplied message.

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 Pow 

func Pow[T constraints.Integer](x T, n int) T

Pow returns x to the power of n.

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 

func ReverseBytes(b []byte) []byte

ReverseBytes reverses b in-place. A pointer to b is also returned.

func Rotate 

func Rotate(first, middle, last int, swap func(i, j int))

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 RotateBy 

func RotateBy(n, amt int, swap func(i, j int))

RotateBy is a wrapper around Rotate that rotates n elements right by amt.

func RotateSlice 

func RotateSlice[T any](s []T, amt int)

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 SetBit 

func SetBit(field uint64, i int, v bool) uint64

SetBit sets the i-th bit in field to v and returns the field.

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 

func Tokenize(s string, tokens ...interface{}) []string

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 

func TryExtract(s, re string, dsts ...interface{}) bool

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 

func UnpackInt2(p uint64) (a, b int)

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 

func UnpackIntSigned2(p uint64) (a, b int)

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 

func NewBitReader(b []byte, off int) *BitReader

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 

func (br *BitReader) Offset() int

Offset returns the current offset into the slice that was passed to NewBitReader.

func (*BitReader) Read 

func (br *BitReader) Read(nbits int) uint64

Read reads and returns the specified number of bits, advancing the current offset.

func (*BitReader) ReadInt 

func (br *BitReader) ReadInt(nbits int) int

ReadInt is a convenience method that calls Read and casts the returned value to an int.

type ByteGrid 

type ByteGrid [][]byte

ByteGrid holds a two-dimensional grid of bytes.

func InputByteGrid 

func InputByteGrid(date string, valid ...byte) ByteGrid

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 

func NewByteGrid(r, c int, ch byte) ByteGrid

NewByteGrid returns a 2-dimensional array of ch with r rows and c columns.

func NewByteGridRow 

func NewByteGridRow(r []byte) ByteGrid

NewByteGrid creates a ByteGrid containing only the supplied row.

func NewByteGridString 

func NewByteGridString(s string, valid ...byte) ByteGrid

NewByteGridString splits s into rows per NewByteLines and returns a ByteGrid.

func (ByteGrid) Cols 

func (b ByteGrid) Cols() int

func (ByteGrid) Copy 

func (b ByteGrid) Copy() ByteGrid

Copy returns a deep copy of b.

func (ByteGrid) CopyRect 

func (b ByteGrid) CopyRect(r0, c0, r1, c1 int) ByteGrid

CopyRect returns a copy of the rectangle bounded by (r0, c0) and (r1, c1), inclusive.

func (ByteGrid) Count 

func (b ByteGrid) Count(chars ...byte) int

Count returns the number of occurrences of chars in b.

func (ByteGrid) CountRect 

func (b ByteGrid) CountRect(r0, c0, r1, c1 int, chars ...byte) int

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) Dump 

func (b ByteGrid) Dump() string

Dump returns b as a newline-separated string.

func (ByteGrid) Find 

func (b ByteGrid) Find(ch byte) (r, c int)

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) FlipHoriz 

func (b ByteGrid) FlipHoriz() ByteGrid

FlipHoriz returns a copy of b reflected across the Y axis.

func (ByteGrid) FlipVert 

func (b ByteGrid) FlipVert() ByteGrid

FlipVert returns a copy of b reflected across the X axis.

func (ByteGrid) Get 

func (b ByteGrid) Get(r, c int, def byte) byte

Get returns the byte at (r, c). If the coordinates are outside b's bounds, def is returned instead.

func (ByteGrid) InBounds 

func (b ByteGrid) InBounds(r, c int) bool

func (ByteGrid) Iter 

func (b ByteGrid) Iter(f func(r, c int))

Iter calls f for each coordinate in b.

func (ByteGrid) IterLine 

func (b ByteGrid) IterLine(r0, c0, r1, c1 int, f func(r, c int))

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 

func (b ByteGrid) IterRect(r0, c0, r1, c1 int, f func(r, c int))

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) MaxCol 

func (b ByteGrid) MaxCol() int

func (ByteGrid) MaxRow 

func (b ByteGrid) MaxRow() int

func (ByteGrid) RotateCW 

func (b ByteGrid) RotateCW() ByteGrid

RotateCW returns a copy of b rotated 90 degrees clockwise.

func (ByteGrid) Rows 

func (b ByteGrid) Rows() int

func (ByteGrid) SetRect 

func (b ByteGrid) SetRect(r0, c0, r1, c1 int, ch byte)

SetRect sets the rectangle bounded by (r0, c0) and (r1, c1), inclusive, to ch.

type Dir 

type Dir int

Dir represents a cardinal direction.

func (Dir) DC 

func (d Dir) DC() int

DC returns the change in column after a single step.

func (Dir) DR 

func (d Dir) DR() int

DR returns the change in row after a single step.

func (Dir) Left 

func (d Dir) Left() Dir

Left returns the resulting direction after turning to the left.

func (Dir) Reverse 

func (d Dir) Reverse() Dir

Reverse returns the resulting direction after turning 180 degrees.

func (Dir) Right 

func (d Dir) Right() Dir

Right returns the resulting direction after turning to the right.

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.)

func NewHeap 

func NewHeap[T any](before HeapFunc[T]) *Heap[T]

func (*Heap[T]) Insert 

func (h *Heap[T]) Insert(x T)

func (*Heap[T]) Len 

func (h *Heap[T]) Len() int

func (*Heap[T]) Pop 

func (h *Heap[T]) Pop() T

type HeapFunc 

type HeapFunc[T any] func(a, b T) bool

HeapFunc returns true if a is ordered before b.

type Instr 

type Instr struct {
	Op uint8
	// contains filtered or unexported fields
}

Instr represents a single instruction.

func NewInstr 

func NewInstr(ln string, rmin, rmax byte, ops map[uint8]string) Instr

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.

func (*Instr) Ptr 

func (in *Instr) Ptr(i int, regs []int64) *int64

Ptr returns a pointer to in's i-th argument, which must be a register.

func (*Instr) Val 

func (in *Instr) Val(i int, regs []int64) int64

Val returns the value of in's i-th argument.

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 

func NewIntcode(init []int64) *Intcode

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 

func (vm *Intcode) Run() (halted bool)

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.

func (*Intcode) Start 

func (vm *Intcode) Start()

Start starts the VM in a goroutine. Wait can be used to wait for the VM to halt.

func (*Intcode) Wait 

func (vm *Intcode) Wait() bool

Wait waits for the previously-started VM to halt. Its return value is the same as that of Run.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.