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.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL