util

package
v0.0.0-...-be83087 Latest Latest
Warning

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

 Go to latest Published: Jan 2, 2024 License: Apache-2.0 Imports: 15 Imported by: 0

Documentation

Overview

Package util contains shared functions for several AoC days.

Index

Constants

This section is empty.

Variables

View Source 
var (
	// MinP is the P with the most negative coordinates possible.
	MinP = P{math.MinInt, math.MinInt}
	// MaxP is the P with the most positive coordinates possible.
	MaxP = P{math.MaxInt, math.MaxInt}
)

Functions

func CheckPrefix 

func CheckPrefix(s, prefix string) (tail string, ok bool)

CheckPrefix tests if a string contains a prefix, and if so, removes it. If the string does not contain the prefix, it's returned unmodified. The `ok` result is true if the prefix was found.

func Chunks 

func Chunks(s string) (chunks []string)

Chunks splits the input string as if by the ScanChunks function.

func Diag 

func Diag(a ...interface{})

Diag prints its arguments to the diagnostic output stream.

func Diagf 

func Diagf(format string, a ...interface{})

Diagf formats data to the diagnostic output stream.

func Diagln 

func Diagln(a ...interface{})

Diagln prints its arguments, followed by a newline, to the diagnostic output stream.

func DistC 

func DistC(a, b P) int

DistC returns the Chebyshev (chessboard, 8-neighbor) distance between two points.

func DistM 

func DistM(a, b P) int

DistM returns the Manhattan (taxicab, 4-neighbor) distance between two points.

func Ints 

func Ints(s string) (ints []int)

Ints returns the list of all contiguous sequences of decimal digits parsed as integers, as defined by the ScanInts split function.

func IsDiag 

func IsDiag() bool

IsDiag tests if verbose output has been requested.

func Lines 

func Lines(s string) (lines []string)

Lines splits the input string by newlines as if by bufio.ScanLines. In other words, it will not return an empty string even if the input has a trailing newline.

func NextInt 

func NextInt(s string) (n int, ok bool, tail string)

NextInt parses the leading decimal digits of s as a (nonnegative) decimal number, and returns both the parsed number and the remainder of the input. If there are no decimal digits, `ok` will be false.

func NextWord 

func NextWord(s string) (word, tail string)

NextWord returns the prefix of s up to the first space character, if any. If there is no space, the entire string is returned. The second return value gives the remainder of the input string.

func QuickSelect 

func QuickSelect(input []int, k int) int

QuickSelect returns the k'th smallest element of the input array.

func ReadChunks 

func ReadChunks(path string) (chunks []string, err error)

ReadChunks returns the contents of a text file as a slice of strings representing all paragraphs, as defined by text separated by a blank line (two consecutive newlines).

func ReadInts 

func ReadInts(path string) ([]int, error)

ReadInts parses a text file containing integers separated by any non-digits (see ScanInts).

func ReadLines 

func ReadLines(path string) ([]string, error)

ReadLines returns the contents of a text file as a slice of strings representing the lines. The newline separators are not kept. The last line need not have a newline character at the end.

func ReadRegexp 

func ReadRegexp(path, pattern string) ([][]string, error)

ReadRegexp parses a text file using a regular expression; see ScanAllRegexp for details.

func ScanAll 

func ScanAll(r io.Reader, split bufio.SplitFunc) (tokens []string, err error)

ScanAll runs a scanner on a reader with the given split function, and returns all tokens.

func ScanAllInts 

func ScanAllInts(r io.Reader) (ints []int, err error)

ScanAllInts extracts all decimal integers from the reader.

func ScanAllRegexp 

func ScanAllRegexp(r io.Reader, pattern string) ([][]string, error)

ScanAllRegexp parses a reader's contents using a regular expression. The return value is a list of lists, containing each line's submatches. Note that unlike the usual convention, the match of the entire regular expression is not included.

func ScanChunks 

func ScanChunks(data []byte, atEOF bool) (advance int, token []byte, err error)

ScanChunks implements a bufio.SplitFunc for scanning paragraphs delimited by a blank line (i.e., two consecutive '\n' bytes).

func ScanInts 

func ScanInts(data []byte, atEOF bool) (advance int, token []byte, err error)

ScanInts implements a bufio.SplitFunc for scanning decimal integers separated by any non-digits. An optional - can also be included as the first character of the token. "123-456" will be split to the two tokens "123", "-456".

func Sort3 

func Sort3(x, y, z int) (a, b, c int)

Sort3 returns the given three integers sorted by value (smallest first).

func SortBy 

func SortBy[S ~[]I, F ~func(I) O, I any, O cmp.Ordered](x S, f F)

SortBy is like slices.SortFunc except applies an accessor function to the objects. Comparing is then done using the natural ordering of the results.

func Words 

func Words(s string) (words []string)

Words returns the list of all nonempty contiguous sequences of non-whitespace characters in the input string. In other words, this is the list of tokens defined by the standard bufio.ScanWords function.

Types

type Bitmap2D 

type Bitmap2D struct {
	// contains filtered or unexported fields
}

func (*Bitmap2D) Clear 

func (bmp *Bitmap2D) Clear(x, y int)

func (*Bitmap2D) Count 

func (bmp *Bitmap2D) Count() (sum int)

func (*Bitmap2D) Get 

func (bmp *Bitmap2D) Get(x, y int) bool

func (*Bitmap2D) GetClear 

func (bmp *Bitmap2D) GetClear(x, y int) (old bool)

func (*Bitmap2D) GetR 

func (bmp *Bitmap2D) GetR(x0, y0, x1, y1 int) (result uint64)

func (*Bitmap2D) GetSet 

func (bmp *Bitmap2D) GetSet(x, y int) (old bool)

func (*Bitmap2D) Set 

func (bmp *Bitmap2D) Set(x, y int)

type BucketQ 

type BucketQ[T any] struct {
	// contains filtered or unexported fields
}

BucketQ is a priority queue using the "bucket queue" data structure.

func NewBucketQ 

func NewBucketQ[T any](span int) *BucketQ[T]

NewBucketQ makes a new queue with the given maximum span, which must be a power of 2. The distance between the lowest and highest priority item in the queue must not exceed the span.

func (*BucketQ[T]) Len 

func (q *BucketQ[T]) Len() int

Len returns the number of elements currently in the queue.

func (*BucketQ[T]) Pop 

func (q *BucketQ[T]) Pop() (prio int, item T)

Pop removes the lowest priority item currently in the queue.

func (*BucketQ[T]) Push 

func (q *BucketQ[T]) Push(prio int, item T)

Push adds an item to the queue with the given priority.

type FixedBitmap1D 

type FixedBitmap1D []uint64

func MakeFixedBitmap1D 

func MakeFixedBitmap1D(size int) FixedBitmap1D

func (FixedBitmap1D) Clear 

func (bmp FixedBitmap1D) Clear()

func (FixedBitmap1D) Get 

func (bmp FixedBitmap1D) Get(i int) bool

func (FixedBitmap1D) Set 

func (bmp FixedBitmap1D) Set(i int)

func (FixedBitmap1D) Unset 

func (bmp FixedBitmap1D) Unset(i int)

type FixedBitmap2D 

type FixedBitmap2D [][]uint64

func MakeFixedBitmap2D 

func MakeFixedBitmap2D(w, h int) FixedBitmap2D

func (FixedBitmap2D) Clear 

func (bmp FixedBitmap2D) Clear(x, y int)

func (FixedBitmap2D) Clone 

func (bmp FixedBitmap2D) Clone() (clone FixedBitmap2D)

func (FixedBitmap2D) Get 

func (bmp FixedBitmap2D) Get(x, y int) bool

func (FixedBitmap2D) GetN 

func (bmp FixedBitmap2D) GetN(x, y, n int) uint64

func (FixedBitmap2D) RotateL 

func (bmp FixedBitmap2D) RotateL(w int)

func (FixedBitmap2D) RotateR 

func (bmp FixedBitmap2D) RotateR(w int)

func (FixedBitmap2D) Set 

func (bmp FixedBitmap2D) Set(x, y int)

func (FixedBitmap2D) Size 

func (bmp FixedBitmap2D) Size() (w, h int)

type FixedLevel 

type FixedLevel struct {
	// W and H are the level size.
	W, H int
	// Data is a row-major representation of the level data in a W*H length array.
	Data []byte
}

FixedLevel is a restricted subset of Level, with less overhead for some operations.

Limitations:

  • The bounding box of the level has a predefined size based on the initial contents.
  • The northwest corner is fixed at (0, 0).

func EmptyFixedLevel 

func EmptyFixedLevel(w, h int, empty byte) *FixedLevel

EmptyFixedLevel returns an empty fixed level filled with the given byte.

func ParseFixedLevel 

func ParseFixedLevel(allData []byte) *FixedLevel

ParseFixedLevel converts the input to a level structure. All lines are expected to be equally long.

func (*FixedLevel) At 

func (l *FixedLevel) At(x, y int) byte

At returns the value at the given coordinates.

func (*FixedLevel) AtP 

func (l *FixedLevel) AtP(p P) byte

AtP returns At(p.X, p.Y).

func (*FixedLevel) Find 

func (l *FixedLevel) Find(key byte) (x, y int, found bool)

Find locates the coordinates of a byte, which must be unique on the level.

func (*FixedLevel) InBounds 

func (l *FixedLevel) InBounds(x, y int) bool

InBounds returns true if the given coordinates are within the area of the level.

func (*FixedLevel) Row 

func (l *FixedLevel) Row(y int) []byte

Row returns the contents of an entire single row of the level.

func (*FixedLevel) Set 

func (l *FixedLevel) Set(x, y int, b byte)

Set assigns a new value at the given coordinates.

func (*FixedLevel) Write 

func (l *FixedLevel) Write(w io.Writer)

Write outputs the contents of the level to the given writer.

type LabelMap 

type LabelMap map[string]int

LabelMap is a mapping from string labels to integer indices, with automatic allocation.

func (LabelMap) Get 

func (m LabelMap) Get(label string) int

Retrieves the corresponding index for a label, or allocates the next free one if it is new.

func (LabelMap) Slice 

func (m LabelMap) Slice() []string

Returns all the labels as a slice in the integer index order.

type Level 

type Level struct {
	// contains filtered or unexported fields
}

A Level models a two-dimensional map of ASCII character cells, similar to a roguelike level. The origin of the coordinate system is the top-left cell; X grows right, Y grows down.

func EmptyLevel 

func EmptyLevel(min, max P, empty byte) *Level

EmptyLevel returns a level filled with empty space matching the provided symbol. The given bounds determine the densely allocated space and the initial bounds of the level.

func ParseLevel 

func ParseLevel(data []byte, empty byte) *Level

ParseLevel parses a byte array into a level. See ReadLevel.

func ParseLevelAt 

func ParseLevelAt(data []byte, empty byte, min P) *Level

ParseLevelAt parses a byte array into a level using a specified offset.

func ParseLevelString 

func ParseLevelString(data string, empty byte) *Level

ParseLevelString parses a string into a level. See ReadLevel.

func ParseLevelStringAt 

func ParseLevelStringAt(data string, empty byte, min P) *Level

ParseLevelStringAt parses a string into a level using a specified offset.

func ReadLevel 

func ReadLevel(path string, empty byte) (*Level, error)

ReadLevel reads the contents of a text file into a level. Character cells outside the contents of the file are considered to be the specified empty byte.

func SparseLevel 

func SparseLevel(origin P, empty byte) *Level

SparseLevel returns a level with no densely allocated space at all. The level bounds are set to contain only the origin point.

func (*Level) At 

func (l *Level) At(x, y int) byte

At returns the byte at the given coordinates.

func (*Level) Bounds 

func (l *Level) Bounds() (min, max P)

Bounds returns the top-left and bottom-right corners of the level's bounding box. See InBounds for the definition.

func (*Level) Copy 

func (l *Level) Copy() *Level

Copy returns a deep copy of a level.

func (*Level) CoreAt 

func (l *Level) CoreAt(x, y int) byte

CoreAt returns the byte at the given coordinates, which must be within the densely stored region (see CoreBounds).

func (*Level) CoreBounds 

func (l *Level) CoreBounds() (min, max P)

CoreBounds returns the top-left and bottom-right corners of the core (densely stored) area.

func (*Level) CoreSet 

func (l *Level) CoreSet(x, y int, b byte)

CoreSet sets the byte at the given coordinates, which must be within the densely stored region (see CoreBounds).

func (*Level) Find 

func (l *Level) Find(key byte) (x, y int, found bool)

Find locates the coordinates of a byte, which must be unique on the level.

func (*Level) InBounds 

func (l *Level) InBounds(x, y int) bool

InBounds returns true if the given coordinates are within the bounding box of the level. The bounds will grow to accommodate new non-empty characters, but will never shrink even if those characters are later overwritten to be empty.

func (*Level) Lines 

func (l *Level) Lines(min, max P) []string

Lines returns the contents of a part of the level as a list of strings.

func (*Level) Range 

func (l *Level) Range(cb func(x, y int, b byte))

Range calls the callback function for all non-empty cells in the level.

func (*Level) Row 

func (l *Level) Row(x1, x2, y int) []byte

Row returns a []byte with the contents of a single contiguous row from the level. If this is within the core area, the returned slice will share storage with the level.

func (*Level) Set 

func (l *Level) Set(x, y int, b byte)

Set sets the byte at the given coordinates.

func (*Level) Size 

func (l *Level) Size() (w, h int)

Size returns the width and height of the bounding box of the level (see InBounds).

func (*Level) Write 

func (l *Level) Write(w io.Writer) error

Write prints out the bytes in-bounds area of the level.

func (*Level) WriteRect 

func (l *Level) WriteRect(w io.Writer, min, max P) error

WriteRect prints out the specified rectangle of the level.

type P 

type P struct {
	X, Y int
}

P represents a two-dimensional integer-valued coordinate.

func Bounds 

func Bounds(points []P) (min, max P)

Bounds returns the bounding box of a list of points.

func ParseP 

func ParseP(s string) (P, error)

ParseP parses a string in the "X,Y" format as a P.

func (P) Add 

func (p P) Add(q P) P

Add returns the point with coordinates corresponding to the sum of the receiver and the other point.

func (P) AddXY 

func (p P) AddXY(x, y int) P

AddXY returns Add(P{x, y}).

func (P) GoString 

func (p P) GoString() string

GoString formats the point in the style of a Go structure.

func (P) Neigh 

func (p P) Neigh() [4]P

Neigh returns a point's von Neumann neighbourhood (the 4 orthogonally adjacent elements).

The directions will be returned in this order: north, south, west, east.

func (P) Neigh8 

func (p P) Neigh8() [8]P

Neigh8 returns a point's Moore neighbourhood (the 8 orthogonally or diagonally adjacent elements).

func (P) Scale 

func (p P) Scale(n int) P

Scale returns the point multiplied by a scalar. Useful for points representing vectors.

func (P) String 

func (p P) String() string

String formats the point in the most common (X,Y) style.

type Queue 

type Queue[T any] struct {
	// contains filtered or unexported fields
}

Queue is a simple array-backed ring buffer implementation of an unbounded queue.

Using it in place of a simple slice might help avoid some copying, at least in a scenario where the "active" size stays roughly the same but a lot of elements go through the queue.

func MakeQueue 

func MakeQueue[T any](size int) Queue[T]

MakeQueue makes a new, empty queue of the given initial size, which must be a power of 2.

func QueueOf 

func QueueOf[T any](size int, init ...T) Queue[T]

QueueOf returns a new queue of the given size initialized with the specified contents.

func (Queue[T]) Cap 

func (q Queue[T]) Cap() int

Cap returns the physical size of the queue's backing array.

func (*Queue[T]) Clear 

func (q *Queue[T]) Clear()

Clear makes the queue empty but without releasing any storage associated with it.

func (Queue[T]) Empty 

func (q Queue[T]) Empty() bool

Empty returns true if the queue has no items.

func (Queue[T]) Index 

func (q Queue[T]) Index(i int) T

Index returns the i'th item in the queue. The head of the queue (least recently pushed item) is at index 0.

func (Queue[T]) Len 

func (q Queue[T]) Len() int

Len returns the number of items currently in the queue.

func (*Queue[T]) Pop 

func (q *Queue[T]) Pop() T

Pop removes (and returns) the first (least recently added) item in the queue. The queue must not be empty.

func (*Queue[T]) Push 

func (q *Queue[T]) Push(t T)

Push adds an item at the end of the queue.

func (*Queue[T]) Slice 

func (q *Queue[T]) Slice(low, high int) []T

Slice returns a segment of the contents of the queue as a slice. The semantics of the parameters are the same as the `s[low:high]` expression on a slice. If possible, the returned slice will share backing array with the queue. However, if the selected region wraps around, a copy will be made.

func (Queue[T]) String 

func (q Queue[T]) String() string

String formats the queue contents as a string, mostly for debugging purposes.

type Splitter 

type Splitter string

Splitter is a convenience type for iterating over the results of splitting a string without allocating a slice.

func (Splitter) Count 

func (s Splitter) Count(delim string) int

Count returns how many parts there would be in the string if it were to be split with a delimiter.

func (Splitter) Empty 

func (s Splitter) Empty() bool

Empty returns true if the current state of the splitter is the empty string (no components remain).

func (*Splitter) Next 

func (s *Splitter) Next(delim string) string

Next returns the part of the string leading up to the delimiter (if found), and also updates the splitter to retain the trailing part. If there is no delimiter, the entire contents are returned and the splitter becomes empty.

Source Files

View all Source files

Directories

Path Synopsis
Package fn contains the sort of non-Go-like, occasionally higher-order, utility functions you might find in a functional language.
 Package fn contains the sort of non-Go-like, occasionally higher-order, utility functions you might find in a functional language.
Package graph contains utilities for (sparse|dense) (un|)directed (un|)weighted graphs.
 Package graph contains utilities for (sparse|dense) (un|)directed (un|)weighted graphs.
Package ix contains small integer arithmetic functions in the style of the standard `math` package.
 Package ix contains small integer arithmetic functions in the style of the standard `math` package.

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.