func main() {
	windowSize := defaultWindowSize
	if windowFromEnv, err := strconv.Atoi(os.Getenv(windowEnvVarName)); err == nil {
		log.Printf("Using window size %d from env var %s.", windowFromEnv, windowEnvVarName)
		windowSize = windowFromEnv
	}
	depths, err := ReadLinesAsInts()
	if err != nil {
		log.Fatalf("cannot read depth values from stdin due to %v", err.Error())
	}
	if len(depths) < windowSize {
		log.Fatalf("cannot process fewer numbers than %d but got %d", windowSize, len(depths))
	}
	depthsWithoutNoise := SlidingWindow(depths, windowSize, Sum)
	increments := CountIncrements(depthsWithoutNoise)
	fmt.Printf("Counted %d increments.\n", increments)
}

// Sum computes the sum of all values in an int slice. This is a possible reduction function for
// SlidingWindow.
func Sum(vals []int) int {
	result := 0
	for _, val := range vals {
		result += val
	}
	return result
}

// SlidingWindow converts an int slice into one that results from applying a reduction function to
// each sliding window of size `size`.
func SlidingWindow(sli []int, size int, reductionFn func([]int) int) []int {
	result := make([]int, 0, len(sli)-size+1)
	for startIdx := range sli[:len(sli)-size+1] {
		window := sli[startIdx : startIdx+size]
		windowSum := reductionFn(window)
		result = append(result, windowSum)
	}
	return result
}

// CountIncrements counts how often an int in an int slice is larger than its predecessor.
func CountIncrements(sli []int) int {
	var increments int
	if len(sli) == 0 {
		return 0
	}
	last := sli[0]
	for _, val := range sli[1:] {
		if val > last {
			increments++
		}
		last = val
	}
	return increments
}

func main() {
	movements, err := ReadLinesAsStates()
	if err != nil {
		log.Fatalf("cannot read movement values from stdin due to %v", err.Error())
	}
	pos := State{Disp: 0, Depth: 0, Aim: 0}
	for _, mov := range movements {
		pos = pos.Displace(mov)
	}
	fmt.Printf("Area under total movement is %d\n", pos.Area())
}

// TokensInInstruction specifies how many token are needed to describe one movement.
const TokensInInstruction = 2

// StateFromString converts an instructions string to a movement.
func StateFromString(str string) (State, error) {
	splitStr := strings.Fields(str)
	if len(splitStr) != TokensInInstruction {
		return State{}, fmt.Errorf("wrong number %d of tokens in '%s'", len(splitStr), str)
	}
	unit, ok := Units[splitStr[0]]
	if !ok {
		return State{}, fmt.Errorf("cannot understand %s as unit vector name", splitStr[0])
	}
	repeats, err := strconv.Atoi(splitStr[1])
	if err != nil {
		return State{}, fmt.Errorf("cannot convert repeats in %s to int: %s", str, err.Error())
	}
	return unit.Mul(repeats), nil
}

// This file contains vector manipulation routines. All of the methods here always return a new
// vector, they never modify the original.

// DepthT describes the depth. To avoid intermingling depth and displacement, they are separate
// types.
type DepthT int

// DispT describes the depth. To avoid intermingling depth and displacement, they are separate
// types.
type DispT int

// AimT describes the aim.
type AimT int

// State describes the subs overall state, i.e. position and aim. It has depth, displacement, and
// aim.
type State struct {
	Depth DepthT
	Disp  DispT
	Aim   AimT
}

// Units contains unit vectors and name assignments.
var Units = map[string]State{
	"up": State{
		Depth: 0,
		Disp:  0,
		Aim:   -1,
	},
	"down": State{
		Depth: 0,
		Disp:  0,
		Aim:   +1,
	},
	"forward": State{
		// The depth change implicitly depends on the current aim.
		Depth: +1,
		Disp:  +1,
		Aim:   0,
	},
}

// Displace Displaces one vector by the distance specified by another. This takes the current aim
// into account. The new aim does not influence the depth change.
func (s State) Displace(delta State) State {
	result := State{
		Depth: s.Depth + delta.Depth*DepthT(s.Aim),
		Disp:  s.Disp + delta.Disp,
		Aim:   s.Aim + delta.Aim,
	}
	return result
}

// Mul multiplies each component of a vector with a number.
func (s State) Mul(factor int) State {
	result := State{
		Depth: DepthT(factor) * s.Depth,
		Disp:  DispT(factor) * s.Disp,
		Aim:   AimT(factor) * s.Aim,
	}
	return result
}

// Inv inverts a vector.
func (s State) Inv() State {
	return s.Mul(-1)
}

// Sub subtracts a vector's data from another one's.
func (s State) Sub(delta State) State {
	return s.Displace(delta.Inv())
}

// Area returns the area spanned by a vector. The aim does not matter for this compuation.
func (s State) Area() int {
	return int(s.Depth) * int(s.Disp)
}

const (
	base = 2
)

func filterForGenerator(sli []string, set CountingSet) []bool {
	filter := set.MostCommon("1")
	return FilterBy(sli, filter)
}

func filterForScrubber(sli []string, set CountingSet) []bool {
	filter := set.LeastCommon("0")
	return FilterBy(sli, filter)
}

// This function fatals if an error is detected.
func mustConvertBinarySliceToInt(sli []string) int {
	str := strings.Join(sli, "")
	return mustConvertBinaryToInt(str)
}

// This function fatals if an error is detected.
func mustConvertBinaryToInt(str string) int {
	val, err := strconv.ParseInt(str, base, 0)
	if err != nil {
		log.Fatal(err.Error())
	}
	return int(val)
}

//nolint: funlen
func main() {
	// Read input.
	binaryNumsAsStrings, err := ReadLines()
	if err != nil {
		log.Fatalf("cannot read binary numbers from stdin due to %v", err.Error())
	}
	if len(binaryNumsAsStrings) == 0 {
		log.Fatal("no input provided")
	}
	counts, err := CountTokens(binaryNumsAsStrings)
	if err != nil {
		log.Fatal(err.Error())
	}

	// First part.
	epsilonSli := make([]string, 0, len(counts))
	gammaSli := make([]string, 0, len(counts))
	// Map the least common and most common operators to the obtained counting sets.
	for _, sli := range counts {
		// Epsilon
		newEpsilonDigit := sli.LeastCommon("0")
		epsilonSli = append(epsilonSli, newEpsilonDigit)
		// Gamma
		newGammaDigit := sli.MostCommon("1")
		gammaSli = append(gammaSli, newGammaDigit)
	}
	epsilon := mustConvertBinarySliceToInt(epsilonSli)
	gamma := mustConvertBinarySliceToInt(gammaSli)
	fmt.Printf("Counts are %v\n", counts)
	fmt.Printf("Gamma is %v and %d\n", gammaSli, gamma)
	fmt.Printf("Epsilon is %v and %d\n", epsilonSli, epsilon)
	fmt.Printf("Product of both numbers is %d\n", epsilon*gamma)

	// Second part. Here comes the fun.
	generatorRatingStr, err := FilterCounts(binaryNumsAsStrings, filterForGenerator)
	if err != nil {
		log.Fatal(err.Error())
	}
	scrubberRatingStr, err := FilterCounts(binaryNumsAsStrings, filterForScrubber)
	if err != nil {
		log.Fatal(err.Error())
	}
	generatorRating := mustConvertBinaryToInt(generatorRatingStr)
	scrubberRating := mustConvertBinaryToInt(scrubberRatingStr)
	fmt.Printf("Generator rating is %d\n", generatorRating)
	fmt.Printf("Scrubber rating is %d\n", scrubberRating)
	fmt.Printf("Product of both ratings is %d\n", generatorRating*scrubberRating)
}

// CountTokens counts the tokens at each position of each string and returns one CountingSet per
// position. All strings must be of equal length.
func CountTokens(input []string) ([]CountingSet, error) {
	if len(input) == 0 {
		return []CountingSet{}, fmt.Errorf("empty string slice obtained")
	}
	length := len(input[0])
	for idx, str := range input {
		if len(str) != length {
			err := fmt.Errorf("string '%s' of unexpected length at index %d, expected %d got %d",
				str, idx+1, length, len(str),
			)
			return []CountingSet{}, err
		}
	}
	result := make([]CountingSet, length)
	for idx := range result {
		result[idx] = make(CountingSet)
	}
	for _, str := range input {
		for idx, char := range str {
			err := result[idx].Add(string(char))
			if err != nil {
				return []CountingSet{}, err
			}
		}
	}
	return result, nil
}

// Function sliceByIndex returns a slice of length-one strings that have been taken from the given
// index of each slice. An error is returned if a string in the slice is too short. This would be
// very easy in, say, NumPy, but it requires iteration in plain Go.
func sliceByIndex(sli []string, idx int) ([]string, error) {
	reqLength := idx + 1
	result := make([]string, 0, len(sli))
	for _, str := range sli {
		if len(str) < reqLength {
			err := fmt.Errorf(
				"entry '%s' too short, need at least %d but got %d",
				str, reqLength, len(str),
			)
			return []string{}, err
		}
		result = append(result, string(str[idx]))
	}
	return result, nil
}

// FilterFunc is a type needed to filter counts out. Based on values in a counting set, it
// determines which entries of a string slice to keep. For each value to keep, the resulting boolean
// array contains true, false otherwise.
type FilterFunc = func([]string, CountingSet) []bool

// FilterBy contains true in the resulting boolean array for every entry in sli that is equal to
// filter.
func FilterBy(sli []string, filter string) []bool {
	// The initial value of a boolean array is all false. Thus, only set those to true we wish to
	// keep.
	result := make([]bool, len(sli))
	for idx, val := range sli {
		if val == filter {
			result[idx] = true
		}
	}
	return result
}

// FilterCounts filters out inputs that are assigned true by filterFunc until exactly one remains.
// If none remains at the end, an error is returned.
func FilterCounts(inputs []string, filterFunc FilterFunc) (string, error) {
	allGoneErr := fmt.Errorf("everything was filtered out")
	copied := make([]string, len(inputs))
	_ = copy(copied, inputs)
	for idx := 0; len(copied) > 1; idx++ {
		counts, err := CountTokens(copied)
		if err != nil {
			return "", err
		}
		if len(counts) < idx+1 {
			return "", allGoneErr
		}
		sliced, err := sliceByIndex(copied, idx)
		if err != nil {
			return "", err
		}
		filtered := filterFunc(sliced, counts[idx])
		newCopy := make([]string, 0, len(filtered))
		for idx, include := range filtered {
			if include {
				newCopy = append(newCopy, copied[idx])
			}
		}
		copied = newCopy
	}
	if len(copied) == 0 {
		return "", allGoneErr
	}
	return copied[0], nil
}

// CountingSet is a set that also knows how often each element has been added. It does support
// non-empty strings only.
type CountingSet map[string]int

// Add adds an entry to the set. The empty string is not supported!
func (c *CountingSet) Add(entry string) error {
	if len(entry) == 0 {
		return fmt.Errorf("empty string not supported in counting set")
	}
	// We don't have to handle non-existing values here since Go returns the zero value (0 for
	// integers) for such entries.
	(*c)[entry] = (*c)[entry] + 1
	return nil
}

// Count determines how often an entry has been added to the set.
func (c *CountingSet) Count(entry string) int {
	return (*c)[entry]
}

// RemoveAll removes all counts for a specific key.
func (c *CountingSet) RemoveAll(entry string) {
	delete(*c, entry)
}

// MostCommon determines the most common entry in the set. If the set is empty, this returns the
// empty string! A non-empty tie breaker will be returned in case there are multiple most common
// entries. If the tie breaker is empty but there are duplicates, an empty string will be returned.
func (c *CountingSet) MostCommon(tieBreaker string) string {
	return c.filter(
		tieBreaker,
		func(i1, i2 int) bool {
			return i1 > i2
		},
	)
}

// LeastCommon determines the least common entry in the set. If the set is empty, this returns the
// empty string! A non-empty tie breaker will be returned in case there are multiple least common
// entries. If the tie breaker is empty but there are duplicates, an empty string will be returned.
func (c *CountingSet) LeastCommon(tieBreaker string) string {
	return c.filter(
		tieBreaker,
		func(i1, i2 int) bool {
			return i1 < i2
		},
	)
}

type comparisonFunc = func(int, int) bool

func (c *CountingSet) filter(tieBreaker string, cmpFn comparisonFunc) string {
	var result string
	var resultCount int
	foundOne := false
	for entry, count := range *c {
		if !foundOne || cmpFn(count, resultCount) {
			foundOne = true
			result = entry
			resultCount = count
		}
	}
	// Check whether there are any duplicate findings and handle appropriately.
	for entry, count := range *c {
		if count == resultCount && entry != result {
			return tieBreaker
		}
	}
	return result
}

func findFirstWinner(picks []int, boards []Board) (Board, error) {
	for _, pick := range picks {
		for boardIdx := range boards {
			board := &boards[boardIdx]
			if board.Mark(pick) && board.Score() >= 0 {
				return *board, nil
			}
		}
	}
	return Board{}, fmt.Errorf("no winner found")
}

//nolint: funlen
func main() {
	// -1 means no score assigned yet.
	firstWinningScore, lastWinningScore := -1, -1
	// Read input.
	picks, boards, err := ReadLinesAsPicksOrBoards()
	if err != nil {
		log.Fatalf("cannot read in: %s", err.Error())
	}
	// Both parts.
	for len(boards) > 0 {
		winner, err := findFirstWinner(picks, boards)
		if err != nil {
			if len(boards) > 0 {
				log.Fatal(err.Error())
			} else {
				fmt.Println("All done")
				return
			}
		}
		score := winner.Score()
		if firstWinningScore < 0 {
			firstWinningScore = score
		} else {
			lastWinningScore = score
		}
		fmt.Printf("Next winner follows, winning score is %d\n", score)
		fmt.Println(winner.Pretty())
		// Remove all winners, find next winner, and repeat.
		newBoards := make([]Board, 0, len(boards))
		for _, board := range boards {
			if board.Score() < 0 {
				newBoards = append(newBoards, board)
			}
		}
		boards = newBoards
	}
	fmt.Printf(
		"All done, first (last) winning score is %d (%d).\n",
		firstWinningScore, lastWinningScore,
	)
}

func strSliceToIntSlice(sli []string) ([]int, error) {
	// I wish Go had a map function...
	result := make([]int, 0, len(sli))
	for _, val := range sli {
		conv, err := strconv.Atoi(val)
		if err != nil {
			return []int{}, err
		}
		result = append(result, conv)
	}
	return result, nil
}

const pickSep = ","

// ReadLinesAsPicksOrBoards reads all lines from stdin as picks or boards.
func ReadLinesAsPicksOrBoards() ([]int, []Board, error) {
	var picks []int
	var boards []Board
	var board Board
	for {
		line, err := readLine()
		if err == io.EOF {
			// Success case, no more input to read.
			return picks, boards, nil
		}
		if err != nil {
			return []int{}, []Board{}, err
		}
		line = strings.TrimSpace(line)
		if strings.Contains(line, pickSep) {
			// This is a line with picks.
			fields := strings.Split(line, pickSep)
			newPicks, err := strSliceToIntSlice(fields)
			if err != nil {
				return []int{}, []Board{}, err
			}
			picks = append(picks, newPicks...)
		} else {
			// This is a line with boards.
			row, err := strSliceToIntSlice(strings.Fields(line))
			if err != nil {
				return []int{}, []Board{}, err
			}
			err = board.AddRow(row)
			if err != nil {
				return []int{}, []Board{}, err
			}
		}
		if board.IsComplete() {
			boards = append(boards, board)
			board = Board{}
		}
	}
}

// Code in this file likely performs quite a few unnecessary copy operations on data. Performance
// doesn't matter much here, though.

// Field is a field of a bingo board.
type Field struct {
	val    int
	marked bool
}

// Board is a bingo board.
type Board struct {
	fields [][]Field
	last   int
}

// Convert an int slice into a field slice, initialising all fields as unmarked.
func fieldsFromInts(ints []int) []Field {
	fields := make([]Field, 0, len(ints))
	for _, val := range ints {
		newField := Field{
			val:    val,
			marked: false,
		}
		fields = append(fields, newField)
	}
	return fields
}

// Determine whether a set of fields is a winning set, i.e. whether all fields in the set (actually
// a slice) are marked.
func winningSet(fields []Field) bool {
	for _, f := range fields {
		if !f.marked {
			return false
		}
	}
	return true
}

// IsComplete determines whether a board has as many rows as cols. Such a board is complete since
// bingo boards are square.
func (b Board) IsComplete() bool {
	if len(b.fields) == 0 {
		return false
	}
	// A square board is considered complete.
	return len(b.fields) == len(b.fields[0])
}

// AddRow adds a row to a board.
func (b *Board) AddRow(input []int) error {
	if len(input) == 0 {
		// Ignore empty lines as a convenience feature.
		return nil
	}
	if len(b.fields) > 0 && len(input) != len(b.fields[0]) {
		return fmt.Errorf("cannot process row of length %d, require %d", len(input), len(b.fields))
	}
	fields := fieldsFromInts(input)
	b.fields = append(b.fields, fields)
	return nil
}

// Row gets the row with the specified index. If the index is out of range, an empty slice is
// returned.
func (b Board) Row(idx int) []Field {
	if idx < 0 || idx+1 > len(b.fields) {
		return []Field{}
	}
	// This is easy.
	result := make([]Field, len(b.fields))
	_ = copy(result, b.fields[idx])
	return result
}

// Col gets the column with the specified index. If the index is out of range, an empty slice is
// returned.
func (b Board) Col(idx int) []Field {
	if idx < 0 || idx+1 > len(b.fields) {
		return []Field{}
	}
	// This is less easy.
	result := make([]Field, 0, len(b.fields))
	for _, row := range b.fields {
		result = append(result, row[idx])
	}
	return result
}

// Mark marks a number and returns whether the board had the number. All occurrences are marked.
func (b *Board) Mark(num int) bool {
	found := false
	for rowIdx := range b.fields {
		for fieldIdx := range b.fields {
			field := &b.fields[rowIdx][fieldIdx]
			if field.val == num {
				field.marked = true
				found = true
			}
		}
	}
	if found {
		b.last = num
	}
	return found
}

// Sum sums up all numbers. The value of `marked` determines whether marked or unmarked unes are
// summed up.
func (b Board) Sum(marked bool) int {
	sum := 0
	for _, row := range b.fields {
		for _, field := range row {
			if field.marked == marked {
				sum += field.val
			}
		}
	}
	return sum
}

// Score determines whether this is a winning board by returning the score. A non-winning board has
// -1 score. That way, we can distinguish winning with a zero from non-winning boards.
func (b Board) Score() int {
	for idx := 0; idx < len(b.fields); idx++ {
		if winningSet(b.Row(idx)) || winningSet(b.Col(idx)) {
			score := b.last * b.Sum(false)
			return score
		}
	}
	return -1
}

// Pretty makes a pretty string representation for this board. A marked field is followed by the
// letter "X". An unmarked field is represented by its number alone followed by a space.
func (b Board) Pretty() string {
	// Hard-code formatting helper strings.
	pre := "> "
	post := " <"
	sep := " | "
	marker := "X"
	clear := " "
	formatter := "%-4s"
	// Actually build the representation.
	result := ""
	for _, row := range b.fields {
		result += pre
		for colIdx, field := range row {
			fieldRep := fmt.Sprintf("%d", field.val)
			if field.marked {
				fieldRep += marker
			} else {
				fieldRep += clear
			}
			fieldRep = fmt.Sprintf(formatter, fieldRep)
			if colIdx > 0 {
				result += sep
			}
			result += fieldRep
		}
		result += post + "\n"
	}
	return result
}

const (
	dangerThreshold = 2
)

func filterDanger(num int) bool {
	return num >= dangerThreshold
}

//nolint: funlen
func main() {
	grid := make(Grid)
	lines, err := ReadLinesAsLines()
	if err != nil {
		log.Fatal(err.Error())
	}
	for _, line := range lines {
		points, err := line.Points()
		if err != nil {
			log.Fatal(err.Error())
		}
		for _, point := range points {
			grid.Mark(point)
		}
	}
	danger := grid.FilterCounts(filterDanger)
	fmt.Printf("There are %d dangerous spots.\n", len(danger))
}

// ReadLinesAsLines reads all lines from stdin as Line structs.
func ReadLinesAsLines() ([]Line, error) {
	var result []Line
	for {
		line, err := readLine()
		if err == io.EOF {
			// Success case, no more input to read.
			return result, nil
		}
		if err != nil {
			return []Line{}, err
		}
		line = strings.TrimSpace(line)
		parsed, err := LineFromStr(line)
		if err != nil {
			return []Line{}, err
		}
		result = append(result, parsed)
	}
}

// Vec is a 2D vector. Most of it has been taken from a previous solution.
type Vec struct {
	x, y int
}

// VecFromStr converts a sring into a vector.
func VecFromStr(str string) (Vec, error) {
	fields := trimStrings(strings.Split(str, vecSep))
	if len(fields) != tokensPerPoint {
		return Vec{}, fmt.Errorf("cannot parse %v as vector, wrong number of fields", str)
	}
	ints, err := strSliceToIntSlice(fields)
	if err != nil {
		return Vec{}, fmt.Errorf("cannot parse %s as vector, %s", str, err.Error())
	}
	result := Vec{
		x: ints[0],
		y: ints[1],
	}
	return result, nil
}

// Add adds one vector to another one.
func (v Vec) Add(delta Vec) Vec {
	result := Vec{
		x: v.x + delta.x,
		y: v.y + delta.y,
	}
	return result
}

// Mul multiplies each component of a vector with a number.
func (v Vec) Mul(factor int) Vec {
	result := Vec{
		x: v.x * factor,
		y: v.y * factor,
	}
	return result
}

// Inv inverts a vector.
func (v Vec) Inv() Vec {
	return v.Mul(-1)
}

// Sub subtracts a vector'v data from another one'v.
func (v Vec) Sub(delta Vec) Vec {
	return v.Add(delta.Inv())
}

func abs(num int) int {
	if num < 0 {
		return -num
	}
	return num
}

func max(i1, i2 int) int {
	if i1 > i2 {
		return i1
	}
	return i2
}

// Normalize returns a unit vector with the same direction as the original vector. For now, this
// does not support diagonals.
func (v Vec) Normalize() (Vec, error) {
	if partSelect == "1" {
		if v.x != 0 && v.y != 0 {
			return Vec{}, fmt.Errorf("cannot normalize %v", v)
		}
	} else {
		// Default to part 2.
		if v.x != 0 && v.y != 0 && abs(v.x) != abs(v.y) {
			return Vec{}, fmt.Errorf("cannot normalize %v", v)
		}
	}
	length := max(abs(v.x), abs(v.y))
	norm := Vec{
		x: v.x / length,
		y: v.y / length,
	}
	return norm, nil
}

// Line is a line in 2D with a start and an end.
type Line struct {
	start, end Vec
}

// LineFromStr converts a sring into a line.
func LineFromStr(str string) (Line, error) {
	fields := trimStrings(strings.Split(str, lineSep))
	if len(fields) != tokensPerLine {
		return Line{}, fmt.Errorf("cannot parse %v as line, wrong number of fields", str)
	}
	start, err := VecFromStr(fields[0])
	if err != nil {
		return Line{}, fmt.Errorf("cannot parse %v as line, %v", str, err.Error())
	}
	end, err := VecFromStr(fields[1])
	if err != nil {
		return Line{}, fmt.Errorf("cannot parse %v as line, %v", str, err.Error())
	}
	result := Line{
		start: start,
		end:   end,
	}
	return result, nil
}

// Points determines all points on this line.
func (l Line) Points() ([]Vec, error) {
	result := []Vec{}
	direction, err := l.end.Sub(l.start).Normalize()
	if err != nil {
		// We ignore lines whose direction we cannot determine.
		return []Vec{}, nil
	}
	pos := l.start
	for pos != l.end {
		result = append(result, pos)
		pos = pos.Add(direction)
	}
	result = append(result, pos)
	return result, nil
}

// Grid is a lazily evaluated grid that supports marking points on it. Most of it has been taken
// from a previous solution.
type Grid map[Vec]int

// Mark marks a point on the grid once.
func (g *Grid) Mark(entry Vec) {
	// We don't have to handle non-existing values here since Go returns the zero value (0 for
	// integers) for such entries.
	(*g)[entry] = (*g)[entry] + 1
}

// Count determines how often a point has been marked.
func (g *Grid) Count(entry Vec) int {
	return (*g)[entry]
}

// RemoveAll removes all markings for a specific point.
func (g *Grid) RemoveAll(entry Vec) {
	delete(*g, entry)
}

// FilterFn is a type that can be used for FilterCounts to filter counts that fulfil a predicate.
type FilterFn = func(int) bool

// FilterCounts allow to filter points based counts using a FilterFn.
func (g *Grid) FilterCounts(filterFn FilterFn) []Vec {
	result := []Vec{}
	for point, count := range *g {
		if filterFn(count) {
			result = append(result, point)
		}
	}
	return result
}

const (
	initialDaysToBreed = 9
	daysToBreed        = 7
)

var (
	partChoice = os.Getenv("PART")
)

//nolint: funlen
func main() {
	var days int
	if partChoice == "1" {
		days = 80
	} else {
		days = 256
	}
	sets, err := ReadLinesAsSets()
	if err != nil {
		log.Fatal(err.Error())
	}
	if len(sets) != 1 {
		log.Fatal("exactly 1 population supported")
	}
	population, err := NewPopulation(daysToBreed, initialDaysToBreed)
	if err != nil {
		log.Fatal(err.Error())
	}
	population.PopulateFromSet(sets[0])
	population.Age(days)
	fmt.Printf("There are %d fish after %d days.\n", population.Size(), days)
}

// ReadLinesAsSets reads all lines from stdin as counting sets.
func ReadLinesAsSets() ([]CountingSet, error) {
	var result []CountingSet
	for {
		line, err := readLine()
		if err == io.EOF {
			// Success case, no more input to read.
			return result, nil
		}
		if err != nil {
			return []CountingSet{}, err
		}
		fields := trimStrings(strings.Split(line, setSep))
		set := CountingSet{}
		for _, field := range fields {
			err := set.Add(field)
			if err != nil {
				return []CountingSet{}, err
			}
		}
		result = append(result, set)
	}
}

// Population tracks the time left until breeding of life forms and counts how many there are per
// such time.
type Population struct {
	pop            []int
	adultDuration  int
	infantDuration int
}

// NewPopulation initialises a new population with times for adults and infants until they breed.
func NewPopulation(adultDuration, infantDuration int) (Population, error) {
	if adultDuration > infantDuration {
		return Population{}, fmt.Errorf("infants must breed slower than adults")
	}
	return Population{
		pop:            make([]int, infantDuration),
		adultDuration:  adultDuration,
		infantDuration: infantDuration,
	}, nil
}

// PopulateFromSet populates a population from a counting set. This ignores entries in the set
// larger than the maximum supported time to breed.
func (p *Population) PopulateFromSet(set CountingSet) {
	for idx := 0; idx < p.infantDuration; idx++ {
		p.pop[idx] = set.Count(fmt.Sprint(idx))
	}
}

// Age ages a population by the given number of days, breeding appropriately.
func (p *Population) Age(days int) {
	for dayCount := 0; dayCount < days; dayCount++ {
		// This new population is auto-initialised with all zeroes.
		newPop := make([]int, len(p.pop))
		// Handle all non-special cases. Simply decrease time to breed by one.
		for breedTime := 0; breedTime < p.infantDuration-1; breedTime++ {
			newPop[breedTime] = p.pop[breedTime+1]
		}
		// Handle special case of those ready to breed.
		newPop[p.infantDuration-1] += p.pop[0]
		newPop[p.adultDuration-1] += p.pop[0]
		// Overwrite the data about the current population.
		_ = copy(p.pop, newPop)
	}
}

// Size determines the total size of the population.
func (p Population) Size() int {
	sum := 0
	for _, val := range p.pop {
		sum += val
	}
	return sum
}

// This file contains the exact same counting set as used for day 3.

// CountingSet is a set that also knows how often each element has been added. It does support
// non-empty strings only.
type CountingSet map[string]int

// Add adds an entry to the set. The empty string is not supported!
func (c *CountingSet) Add(entry string) error {
	if len(entry) == 0 {
		return fmt.Errorf("empty string not supported in counting set")
	}
	// We don't have to handle non-existing values here since Go returns the zero value (0 for
	// integers) for such entries.
	(*c)[entry] = (*c)[entry] + 1
	return nil
}

// Count determines how often an entry has been added to the set.
func (c *CountingSet) Count(entry string) int {
	return (*c)[entry]
}

// RemoveAll removes all counts for a specific key.
func (c *CountingSet) RemoveAll(entry string) {
	delete(*c, entry)
}

// MostCommon determines the most common entry in the set. If the set is empty, this returns the
// empty string! A non-empty tie breaker will be returned in case there are multiple most common
// entries. If the tie breaker is empty but there are duplicates, an empty string will be returned.
func (c *CountingSet) MostCommon(tieBreaker string) string {
	return c.filter(
		tieBreaker,
		func(i1, i2 int) bool {
			return i1 > i2
		},
	)
}

// LeastCommon determines the least common entry in the set. If the set is empty, this returns the
// empty string! A non-empty tie breaker will be returned in case there are multiple least common
// entries. If the tie breaker is empty but there are duplicates, an empty string will be returned.
func (c *CountingSet) LeastCommon(tieBreaker string) string {
	return c.filter(
		tieBreaker,
		func(i1, i2 int) bool {
			return i1 < i2
		},
	)
}

type comparisonFunc = func(int, int) bool

func (c *CountingSet) filter(tieBreaker string, cmpFn comparisonFunc) string {
	var result string
	var resultCount int
	foundOne := false
	for entry, count := range *c {
		if !foundOne || cmpFn(count, resultCount) {
			foundOne = true
			result = entry
			resultCount = count
		}
	}
	// Check whether there are any duplicate findings and handle appropriately.
	for entry, count := range *c {
		if count == resultCount && entry != result {
			return tieBreaker
		}
	}
	return result
}

// For each entry in the set, compute the cost based on some cost function. The target will be every
// possible number between the smallest and largest entry in the set. Multiples of set entries are
// accounted for. The lowest cost and associated target are returned.
func overallCost(set CountingSet, costFn func(int, int) int) (int, int) {
	bestCost := 0
	bestPos := 0
	found := false
	for checkPos := set.Min(); checkPos <= set.Max(); checkPos++ {
		checkCost := 0
		for _, startPos := range set.Keys() {
			additionalCost := costFn(startPos, checkPos) * set.Count(startPos)
			checkCost += additionalCost
		}
		if !found || checkCost < bestCost {
			bestPos = checkPos
			bestCost = checkCost
			found = true
		}
	}
	return bestCost, bestPos
}

//nolint: funlen
func main() {
	sets, err := ReadLinesAsSets()
	if err != nil {
		log.Fatal(err.Error())
	}
	if len(sets) != 1 {
		log.Fatal("exactly 1 input set supported")
	}
	set := sets[0]
	// Part 1.
	fuelConsumptionFnPart1 := func(start, end int) int {
		return abs(start - end)
	}
	bestCost, bestPos := overallCost(set, fuelConsumptionFnPart1)
	fmt.Printf("Best position is %d with cost %d\n", bestPos, bestCost)
	// Part 2. Same code, different cost formula.
	fuelConsumptionFnPart2 := func(start, end int) int {
		diff := abs(start - end)
		// This is the sum of the first diff natural numbers. This also nicely works for diff==0.
		return (diff * (diff + 1)) / 2 //nolint: gomnd
	}
	bestCost, bestPos = overallCost(set, fuelConsumptionFnPart2)
	fmt.Printf("Best position is %d with cost %d\n", bestPos, bestCost)
}

// ReadLinesAsSets reads all lines from stdin as counting sets.
func ReadLinesAsSets() ([]CountingSet, error) {
	var result []CountingSet
	for {
		line, err := readLine()
		if err == io.EOF {
			// Success case, no more input to read.
			return result, nil
		}
		if err != nil {
			return []CountingSet{}, err
		}
		fields := trimStrings(strings.Split(line, setSep))
		set := CountingSet{}
		for _, field := range fields {
			err := set.Add(field)
			if err != nil {
				return []CountingSet{}, err
			}
		}
		result = append(result, set)
	}
}

// This file contains the counting set as used for day 3 but with ints instead of strings and with
// some unneeded functionality removed.

// CountingSet is a set that also knows how often each element has been added. It does support
// non-empty strings only.
type CountingSet map[int]int

// Add adds an entry to the set.
func (c *CountingSet) Add(entry string) error {
	conv, err := strconv.Atoi(entry)
	if err != nil {
		return err
	}
	// We don't have to handle non-existing values here since Go returns the zero value (0 for
	// integers) for such entries.
	(*c)[conv] = (*c)[conv] + 1
	return nil
}

// Min returns the smallest key.
func (c *CountingSet) Min() int {
	var result int
	found := false
	for key := range *c {
		if !found || key < result {
			result = key
			found = true
		}
	}
	return result
}

// Max returns the largest key.
func (c *CountingSet) Max() int {
	var result int
	found := false
	for key := range *c {
		if !found || key > result {
			result = key
			found = true
		}
	}
	return result
}

// Keys returns all keys of the set.
func (c *CountingSet) Keys() []int {
	result := make([]int, 0, len(*c))
	for key := range *c {
		result = append(result, key)
	}
	return result
}

// Count determines how often an entry has been added to the set.
func (c *CountingSet) Count(entry int) int {
	return (*c)[entry]
}

// RemoveAll removes all counts for a specific key.
func (c *CountingSet) RemoveAll(entry int) {
	delete(*c, entry)
}

// Pow computes an integer power of an integer base.
func Pow(base, exponent int) int {
	result := 1
	for exp := 0; exp < exponent; exp++ {
		result *= base
	}
	return result
}

// ReadLinesAsInputsAndOutputs reads all lines from stdin, splitting tokens, and determining how
// many outputs there are. If not all lines have the same number of outputs, an error is returned.
func ReadLinesAsInputsAndOutputs() ([][]string, int, error) {
	var result [][]string
	var numOutputs int
	for {
		line, err := readLine()
		if err == io.EOF {
			// Success case, no more input to read.
			return result, numOutputs, nil
		}
		if err != nil {
			return [][]string{}, 0, err
		}
		line = strings.TrimSpace(line)
		separated := trimStrings(strings.Split(line, inputOutputSep))
		if len(separated) != expectedSplits+1 {
			err := fmt.Errorf("cannot split into inputs and outputs")
			return [][]string{}, 0, err
		}
		if len(result) == 0 {
			numOutputs = len(strings.Fields(separated[1]))
		} else if len(strings.Fields(separated[1])) != numOutputs {
			err := fmt.Errorf("unexpected number of outputs in %s, wanted %d", line, numOutputs)
			return [][]string{}, 0, err
		}
		localResult := []string{}
		localResult = append(localResult, strings.Fields(separated[0])...)
		localResult = append(localResult, strings.Fields(separated[1])...)
		result = append(result, localResult)
	}
}

// AllPermutations returns all possible permutations of a string via a channel. It uses Heap's
// algorithm. See https://en.wikipedia.org/wiki/Heap%27s_algorithm for details.
func AllPermutations(str string) <-chan string {
	channel := make(chan string)

	sli := strings.Split(str, "")

	var generate func([]string, int)
	generate = func(sli []string, permLen int) {
		if permLen == 1 {
			// This is a solution, emit it.
			emittedStr := strings.Join(sli, "")
			channel <- emittedStr
		} else {
			for idx := 0; idx < permLen; idx++ {
				generate(sli, permLen-1)
				if permLen%2 == 1 {
					sli[idx], sli[permLen-1] = sli[permLen-1], sli[idx]
				} else {
					sli[0], sli[permLen-1] = sli[permLen-1], sli[0]
				}
			}
		}
		// This is the outer-most call to generate. Make sure to close the channel in the end.
		if permLen == len(sli) {
			close(channel)
		}
	}
	go generate(sli, len(sli))

	return channel
}

// SortString sorts a string character-wise. This is particularly useful to determine whether two
// strings contain the same characters.
func SortString(str string) string {
	split := strings.Split(str, "")
	sort.Strings(split)
	combined := strings.Join(split, "")
	return combined
}

const (
	noMoreBasinHeight = 9
	numLargestBasins  = 3
)

//nolint: funlen
func main() {
	grid, err := ReadLinesAsGrid()
	if err != nil {
		log.Fatal(err.Error())
	}
	minima := []Vec{}
	risk := 0
	for point := range grid.Points() {
		if grid.IsLocalMin(point) {
			risk += 1 + grid.Count(point)
			minima = append(minima, point)
		}
	}
	// minima = []Vec{Vec{x: 0, y: 1}}
	fmt.Printf("There is %d risk.\n", risk)
	sizes := []int{}
	for _, min := range minima {
		basin, err := grid.Basin(min, noMoreBasinHeight-1)
		if err != nil {
			log.Fatal(err.Error())
		}
		sizes = append(sizes, len(basin))
	}
	// Multiply the sizes of the three largest basins.
	sort.Ints(sizes)
	sizeMult := 1
	for _, size := range sizes[len(sizes)-numLargestBasins:] {
		sizeMult *= size
	}
	fmt.Printf("Multiplied basin size is %d.\n", sizeMult)
}

// ReadLinesAsGrid reads all lines from stdin as a grid. That is, each point on the grid has a
// height and a location.
func ReadLinesAsGrid() (Grid, error) {
	lineIdx := 0
	result := make(Grid)
	for {
		line, err := readLine()
		if err == io.EOF {
			// Success case, no more input to read.
			return result, nil
		}
		if err != nil {
			return Grid{}, err
		}
		line = strings.TrimSpace(line)
		ints, err := strSliceToIntSlice(strings.Split(line, ""))
		if err != nil {
			return Grid{}, err
		}
		for rowIdx, val := range ints {
			// This is lazy but I wanted to re-use old code.
			point, err := VecFromStr(fmt.Sprintf("%d%s%d", lineIdx, vecSep, rowIdx))
			if err != nil {
				return Grid{}, err
			}
			err = result.Mark(point, val)
			if err != nil {
				return Grid{}, err
			}
		}
		if err != nil {
			return Grid{}, err
		}
		lineIdx++
	}
}

// Vec is a 2D vector. Most of it has been taken from a previous solution.
type Vec struct {
	x, y int
}

var (
	unitX     = Vec{x: 1}
	unitY     = Vec{y: 1}
	unitDisps = []Vec{unitX, unitY, unitX.Inv(), unitY.Inv()}
)

// VecFromStr converts a sring into a vector.
func VecFromStr(str string) (Vec, error) {
	fields := trimStrings(strings.Split(str, vecSep))
	if len(fields) != tokensPerPoint {
		return Vec{}, fmt.Errorf("cannot parse %v as vector, wrong number of fields", str)
	}
	ints, err := strSliceToIntSlice(fields)
	if err != nil {
		return Vec{}, fmt.Errorf("cannot parse %s as vector, %s", str, err.Error())
	}
	result := Vec{
		x: ints[0],
		y: ints[1],
	}
	return result, nil
}

// Add adds one vector to another one.
func (v Vec) Add(delta Vec) Vec {
	result := Vec{
		x: v.x + delta.x,
		y: v.y + delta.y,
	}
	return result
}

// Mul multiplies each component of a vector with a number.
func (v Vec) Mul(factor int) Vec {
	result := Vec{
		x: v.x * factor,
		y: v.y * factor,
	}
	return result
}

// Inv inverts a vector.
func (v Vec) Inv() Vec {
	return v.Mul(-1)
}

// Sub subtracts a vector'v data from another one'v.
func (v Vec) Sub(delta Vec) Vec {
	return v.Add(delta.Inv())
}

// Grid is a lazily evaluated grid that supports marking points on it. Most of it has been taken
// from a previous solution.
type Grid map[Vec]int

// Mark marks a point on the grid n times. Don't accept numbers <0.
func (g *Grid) Mark(entry Vec, n int) error {
	if n < 0 {
		return fmt.Errorf("can only mark non-negative times")
	}
	// We don't have to handle non-existing values here since Go returns the zero value (0 for
	// integers) for such entries.
	(*g)[entry] = (*g)[entry] + n
	return nil
}

// Count determines how often a point has been marked.
func (g *Grid) Count(entry Vec) int {
	return (*g)[entry]
}

// Has determines whether a point is on the grid.
func (g *Grid) Has(entry Vec) bool {
	_, ok := (*g)[entry]
	return ok
}

// RemoveAll removes all markings for a specific point.
func (g *Grid) RemoveAll(entry Vec) {
	delete(*g, entry)
}

// IsLocalMin determines whether a point is a local minimum.
func (g *Grid) IsLocalMin(entry Vec) bool {
	for neigh := range pointEnv(entry) {
		if !g.Has(neigh) {
			continue
		}
		if g.Count(entry) >= g.Count(neigh) {
			return false
		}
	}
	return true
}

// Points returns an iterator over all points on the grid.
func (g *Grid) Points() <-chan Vec {
	channel := make(chan Vec)
	go func() {
		for point := range *g {
			channel <- point
		}
		close(channel)
	}()
	return channel
}

// Check whether a slice has a specific entry.
func sliceHasEntry(sli []Vec, entry Vec) bool {
	for _, val := range sli {
		if entry == val {
			return true
		}
	}
	return false
}

// Obtain an iterator over a point's environment.
func pointEnv(point Vec) <-chan Vec {
	channel := make(chan Vec)
	go func() {
		for _, disp := range unitDisps {
			displaced := point.Add(disp)
			channel <- displaced
		}
		close(channel)
	}()
	return channel
}

// Basin returns a "grid" that contains the basin associated with the given entry. The value of max
// will be the maximum value permitted for a point in a basin.
func (g *Grid) Basin(entry Vec, max int) (Grid, error) {
	if !g.IsLocalMin(entry) {
		err := fmt.Errorf("can only start basin generation from local minimum")
		return Grid{}, err
	}
	result := Grid{}
	for checkEnv := []Vec{entry}; len(checkEnv) != 0; {
		newEnv := []Vec{}
		// Add each entry of checkEnv to the basin if it is lower than or equal to all of its
		// surrounding points that are not yet in the basin.
		for _, checkVec := range checkEnv {
			keepThis := true
			for displaced := range pointEnv(checkVec) {
				// Non-existent points count as ultra-high walls.
				if !g.Has(displaced) {
					continue
				}
				// If the to-be-checked point itself does not exist, it cannot be added. Neither can
				// it be added if it is too large.
				if !g.Has(checkVec) || g.Count(checkVec) > max {
					keepThis = false
				}
				// We use > here since we assume lava can also flow horizontally instead of just
				// downward all the time.
				if !result.Has(displaced) && g.Count(checkVec) > g.Count(displaced) {
					keepThis = false
				}
			}
			if keepThis && !result.Has(checkVec) {
				err := result.Mark(checkVec, g.Count(checkVec))
				if err != nil {
					return Grid{}, err
				}
				// Add a point's entire surrounding to be checked for the same basin next time.
				for displaced := range pointEnv(checkVec) {
					if !sliceHasEntry(newEnv, displaced) {
						newEnv = append(newEnv, displaced)
					}
				}
			}
		}
		checkEnv = newEnv
	}
	return result, nil
}

var openerCloser = map[string]string{
	"(": ")",
	"[": "]",
	"{": "}",
	"<": ">",
}

//nolint:gomnd
var delimScorePart1 = map[string]int{
	")": 3,
	"]": 57,
	"}": 1197,
	">": 25137,
}

//nolint:gomnd
const (
	multScorePart2 = 5
)

//nolint:gomnd
var delimScorePart2 = map[string]int{
	")": 1,
	"]": 2,
	"}": 3,
	">": 4,
}

// Check the syntax. Return whether the syntax was OK, the sequence of expected closing delimiters,
// and the first offending character.
func checkSyntax(line string) (bool, Stack, string) {
	stack := Stack{}
	for _, char := range strings.Split(line, "") {
		if closer, isOpener := openerCloser[char]; isOpener {
			// We found a new opener. Add the corresponding closer to the stack.
			stack.Push(closer)
		} else {
			// We did not find an opener. Check whether the closer we found is the expected one.
			expectedCloser, ok := stack.Pop()
			if !ok {
				// The stack was empty. An empty offender means the line had more closing delimiters
				// than opening ones.
				return false, stack, ""
			}
			if expectedCloser != char {
				// We did not find the closer we expected. The current char is the offender.
				return false, stack, char
			}
		}
	}
	return true, stack, ""
}

//nolint: funlen
func main() {
	lines, err := ReadLines()
	if err != nil {
		log.Fatal(err.Error())
	}
	remainingLines := []string{}
	// Part 1.
	scorePart1 := 0
	for _, line := range lines {
		ok, _, offender := checkSyntax(line)
		// The second condition means we currently only check corrupted lines but not such ones that
		// are incomplete.
		if !ok && offender != "" {
			newScore, found := delimScorePart1[offender]
			if !found {
				log.Fatalf("cannot find score for offender %s", offender)
			}
			scorePart1 += newScore
		} else {
			// Keep all lines that are not corrupted.
			remainingLines = append(remainingLines, line)
		}
	}
	fmt.Printf("Score is %d points.\n", scorePart1)
	// Part 1.
	scoresPart2 := []int{}
	for _, line := range remainingLines {
		lineScore := 0
		ok, remainder, _ := checkSyntax(line)
		if !ok {
			// We wanted to filter out all corrupted lines already. Thus, finding one here is a bug.
			log.Fatalf("found corrupted line '%s' but we have filtered them all", line)
		}
		// Iterate over all the remaining characters.
		for char, nonEmpty := remainder.Pop(); nonEmpty; char, nonEmpty = remainder.Pop() {
			lineScore *= multScorePart2
			newScore, found := delimScorePart2[char]
			if !found {
				log.Fatalf("cannot find score for character %s", char)
			}
			lineScore += newScore
		}
		scoresPart2 = append(scoresPart2, lineScore)
	}
	// Pick the middle one.
	sort.Ints(scoresPart2)
	if len(scoresPart2)%2 != 1 {
		log.Fatal("we were promised an odd number of scores but found an even one")
	}
	// Integer division FTW.
	scorePart2 := scoresPart2[len(scoresPart2)/2]
	fmt.Printf("Score is %d points.\n", scorePart2)
}

// Stack is a FIFO.
type Stack []string

// Push puts a value on the stack.
func (s *Stack) Push(val string) {
	*s = append(*s, val)
}

// Pop removes the topmost value and returns it. Also returns whether the stack was non-empty.
func (s *Stack) Pop() (string, bool) {
	if len(*s) == 0 {
		return "", false
	}
	val := (*s)[len(*s)-1]
	*s = (*s)[0 : len(*s)-1 : len(*s)-1]
	return val, true
}

const (
	flashThreshold   = 9
	generationsPart1 = 100
	// We set a max number of generations to prevent an endless loop.
	maxGenerationsPart2 = 1000
)

// SolutionOutput is the output of `solve`'s channel.
type SolutionOutput struct {
	value int
	err   error
}

func solve(grid Grid, threshold int) <-chan SolutionOutput {
	channel := make(chan SolutionOutput)

	go func() {
		for {
			flashesThisGen := 0
			if err := grid.MarkAll(1); err != nil {
				channel <- SolutionOutput{0, err}
				close(channel)
				return
			}
			addUsBack := []Vec{}
			for o := grid.FilterThreshold(threshold); len(o) > 0; o = grid.FilterThreshold(threshold) {
				// If we found any that will flash, handle them.
				// First, count their flashes.
				flashesThisGen += len(o)
				// Then, remove them from the grid. They cannot flash again this time. But remember to
				// add them back later.
				for _, p := range o {
					grid.RemoveAll(p)
					addUsBack = append(addUsBack, p)
				}
				// Then, their flashes will increase the energy levels of their environment. Propagate
				// that. Only points that are still on the grid will have their energy levels changed.
				for _, p := range o {
					if err := grid.MarkExistingEnv(1, p, pointEnv); err != nil {
						channel <- SolutionOutput{0, err}
						close(channel)
						return
					}
				}
				// Rinse repeat until no more points exceed the threshold.
			}
			// Add those points back that were removed. Their initial energy level will be zero.
			for _, addBack := range addUsBack {
				if err := grid.Mark(addBack, 0); err != nil {
					channel <- SolutionOutput{0, err}
					close(channel)
					return
				}
			}
			channel <- SolutionOutput{flashesThisGen, nil}
		}
	}()

	return channel
}

//nolint: funlen
func main() {
	grid, err := ReadLinesAsGrid()
	if err != nil {
		log.Fatal(err.Error())
	}
	numOctopodes := len(grid)
	flashes := 0
	solutionGenerator := solve(grid, flashThreshold)
	for gen := 1; gen <= generationsPart1; gen++ {
		sol := <-solutionGenerator
		if err := sol.err; err != nil {
			log.Fatal(err.Error())
		}
		flashes += sol.value
	}
	fmt.Printf("The octopodes flashed %d times in %d generations.\n", flashes, generationsPart1)
	for gen := generationsPart1; gen <= maxGenerationsPart2; gen++ {
		sol := <-solutionGenerator
		if err := sol.err; err != nil {
			log.Fatal(err.Error())
		}
		if sol.value == numOctopodes {
			fmt.Printf(
				"The octopodes all flashed together the 1st time the %d'th generation.\n", gen,
			)
			return
		}
	}
	log.Fatal("the octopodes never flashed all together")
}

// ReadLinesAsGrid reads all lines from stdin as a grid. That is, each point on the grid has a
// value and a location.
func ReadLinesAsGrid() (Grid, error) {
	lineIdx := 0
	result := make(Grid)
	for {
		line, err := readLine()
		if err == io.EOF {
			// Success case, no more input to read.
			return result, nil
		}
		if err != nil {
			return Grid{}, err
		}
		line = strings.TrimSpace(line)
		ints, err := strSliceToIntSlice(strings.Split(line, ""))
		if err != nil {
			return Grid{}, err
		}
		for rowIdx, val := range ints {
			// This is lazy but I wanted to re-use old code.
			point, err := VecFromStr(fmt.Sprintf("%d%s%d", lineIdx, vecSep, rowIdx))
			if err != nil {
				return Grid{}, err
			}
			err = result.Mark(point, val)
			if err != nil {
				return Grid{}, err
			}
		}
		if err != nil {
			return Grid{}, err
		}
		lineIdx++
	}
}

// Vec is a 2D vector. Most of it has been taken from a previous solution.
type Vec struct {
	x, y int
}

var (
	unitX         = Vec{x: 1}
	unitY         = Vec{y: 1}
	pointEnvDisps = []Vec{
		// x==1
		unitX.Add(unitY),
		unitX,
		unitX.Sub(unitY),
		// x==0
		unitY,
		unitY.Inv(),
		// x==-1
		unitX.Inv().Add(unitY),
		unitX.Inv(),
		unitX.Inv().Sub(unitY),
	}
)

// Obtain an iterator over a point's environment.
func pointEnv(point Vec) <-chan Vec {
	channel := make(chan Vec)
	go func() {
		for _, disp := range pointEnvDisps {
			displaced := point.Add(disp)
			channel <- displaced
		}
		close(channel)
	}()
	return channel
}

// VecFromStr converts a sring into a vector.
func VecFromStr(str string) (Vec, error) {
	fields := trimStrings(strings.Split(str, vecSep))
	if len(fields) != tokensPerPoint {
		return Vec{}, fmt.Errorf("cannot parse %v as vector, wrong number of fields", str)
	}
	ints, err := strSliceToIntSlice(fields)
	if err != nil {
		return Vec{}, fmt.Errorf("cannot parse %s as vector, %s", str, err.Error())
	}
	result := Vec{
		x: ints[0],
		y: ints[1],
	}
	return result, nil
}

// Add adds one vector to another one.
func (v Vec) Add(delta Vec) Vec {
	result := Vec{
		x: v.x + delta.x,
		y: v.y + delta.y,
	}
	return result
}

// Mul multiplies each component of a vector with a number.
func (v Vec) Mul(factor int) Vec {
	result := Vec{
		x: v.x * factor,
		y: v.y * factor,
	}
	return result
}

// Inv inverts a vector.
func (v Vec) Inv() Vec {
	return v.Mul(-1)
}

// Sub subtracts a vector'v data from another one'v.
func (v Vec) Sub(delta Vec) Vec {
	return v.Add(delta.Inv())
}

// Grid is a lazily evaluated grid that supports marking points on it. Most of it has been taken
// from a previous solution.
type Grid map[Vec]int

// Mark marks a point on the grid n times. Don't accept numbers <0.
func (g *Grid) Mark(entry Vec, n int) error {
	if n < 0 {
		return fmt.Errorf("can only mark non-negative times")
	}
	// We don't have to handle non-existing values here since Go returns the zero value (0 for
	// integers) for such entries.
	(*g)[entry] = (*g)[entry] + n
	return nil
}

// Count determines how often a point has been marked.
func (g *Grid) Count(entry Vec) int {
	return (*g)[entry]
}

// Has determines whether a point is on the grid.
func (g *Grid) Has(entry Vec) bool {
	_, ok := (*g)[entry]
	return ok
}

// RemoveAll removes all markings for a specific point.
func (g *Grid) RemoveAll(entry Vec) {
	delete(*g, entry)
}

// FilterThreshold returns all points whose value exceeds a threshold.
func (g *Grid) FilterThreshold(threshold int) []Vec {
	result := []Vec{}
	for point := range g.Points() {
		if g.Count(point) > threshold {
			result = append(result, point)
		}
	}
	return result
}

// MarkAll maks all points in the grid with the same value.
func (g *Grid) MarkAll(val int) error {
	for p := range g.Points() {
		if err := g.Mark(p, val); err != nil {
			return err
		}
	}
	return nil
}

// EnvFn is a function type used to determine a point's environment.
type EnvFn = func(point Vec) <-chan Vec

// MarkExistingEnv marks all points by the specified value in the environment of a given point. The
// environment is defined by envFn. Only points that actually exist will be marked.
func (g *Grid) MarkExistingEnv(val int, point Vec, envFn EnvFn) error {
	for neigh := range envFn(point) {
		if !g.Has(neigh) {
			continue
		}
		if err := g.Mark(neigh, val); err != nil {
			return err
		}
	}
	return nil
}

// Points returns an iterator over all points on the grid.
func (g *Grid) Points() <-chan Vec {
	channel := make(chan Vec)
	go func() {
		for point := range *g {
			channel <- point
		}
		close(channel)
	}()
	return channel
}

const (
	startNode = "start"
	endNode   = "end"
)

// func printStack(stack *Stack) {
// 	for _, node := range *stack {
// 		nodeStr := nodeToStr(node.Node)
// 		fmt.Printf("%s -> %d\n", nodeStr, *node.ConnectionCount)
// 	}
// }

func atOrOverLimit(node *Node, curr int) bool {
	if node.Limit == 0 {
		// This is a node we may visit any number of times.
		return false
	}
	return curr >= node.Limit
}

// A validityFn checks whether the currently-attempted solution is stil a valid one.
type validityFn = func(*CountingSet) bool

//nolint:funlen
func findConnections(nodes []*Node, start, end string, checkFn validityFn) (<-chan []*Node, error) {
	channel := make(chan []*Node)
	startNode := FindNode(nodes, startNode)
	endNode := FindNode(nodes, endNode)
	if startNode == nil || endNode == nil {
		close(channel)
		return channel, fmt.Errorf("start or end not defined")
	}
	stack := Stack{}
	stack.Push(startNode, 0)
	set := CountingSet{}
	_ = set.Add(startNode)

	go func() {
		for {
			topNode := stack.Peek().Node
			progress := stack.Peek().ConnectionCount

			if !checkFn(&set) {
				// This is no longer a valid solution. Don't continue to explore solutions based on
				// it. Make sure to skip it by setting the progress counter to its maximum.
				*progress = len(topNode.Connections)
			}

			if *progress < len(topNode.Connections) {
				// We have not yet tried out all connections. Try out the next one.
				// Get the next in line and check if we have not yet exceeded its visitation limit.
				var nextTop *Node
				for idx, checkNext := range topNode.Connections[*progress:] {
					if !atOrOverLimit(checkNext, set.Count(checkNext)) {
						*progress += idx
						nextTop = checkNext
						break
					}
				}
				if nextTop == nil {
					// We've not found any available connections. Thus, trigger the removal of the
					// topmost node and continue with the one beneath it. This is done by stating
					// that we've tried out all possible connections from this one.
					*progress = len(topNode.Connections)
				}
				if nextTop == endNode {
					// We have found a connection! Yeah! Emit it.
					stack.Push(nextTop, 0)
					channel <- stack.ToList()
					// fmt.Println("EMIT")
					_, _ = stack.Pop()
					// Make sure we don't check this connection again.
					*progress++
					// Make sure we never traverse the end node.
					continue
				}
				if nextTop != nil {
					// We know the next top node. Add it.
					stack.Push(nextTop, 0)
					_ = set.Add(nextTop)
				}
			}
			if *progress >= len(topNode.Connections) {
				// We have exceeded what we can achieve with this topmost node. Remove the top-most
				// one and continue from the one underneath.
				oldTop, nonEmpty := stack.Pop()
				set.Remove(oldTop.Node)
				if nonEmpty {
					// If the stack is not empty, make sure we check the next connection for the new
					// top node.
					// fmt.Println("Removing", nodeToStr(oldTop.Node))
					// If we ever remove the start node, we have reached the end.
					if oldTop.Node == startNode {
						close(channel)
						return
					}
					newTop := stack.Peek()
					*newTop.ConnectionCount++
				}
			}
		}
	}()

	return channel, nil
}

// Filter for part 1. Only count connections that don't visit any small cave more than once.
func filterPart1(set *CountingSet) bool {
	threshold := 1
	filterFn := func(node *Node, curr int) bool {
		if strings.ToUpper(node.ID) == node.ID {
			// This is a node we may visit any number of times. Thus, don't filter it out.
			return false
		}
		return curr > threshold
	}
	// If we didn't filter out anything, that means the input describes a connection that does not
	// visit any small cave more than once.
	return set.FilterCount(filterFn) == 0
}

// Filter for part 2. Only count connections that don't visit more than one small cave more than
// once.
func filterPart2(set *CountingSet) bool {
	threshold := 1
	filterFn := func(node *Node, curr int) bool {
		if strings.ToUpper(node.ID) == node.ID {
			// This is a node we may visit any number of times. Thus, don't filter it out.
			return false
		}
		return curr > threshold
	}
	// If we didn't filter out more than one entry, that means the input describes a connection that
	// does not visit more than one small cave more than twice.
	return set.FilterCount(filterFn) <= 1
}

func setFromList(nodes []*Node) (CountingSet, error) {
	set := CountingSet{}
	for _, node := range nodes {
		if err := set.Add(node); err != nil {
			return CountingSet{}, err
		}
	}
	return set, nil
}

//nolint: funlen
func main() {
	nodes, err := ReadLinesAsNodes()
	if err != nil {
		log.Fatal(err.Error())
	}
	fmt.Printf("Nodes: %s\n", NodesToStr(nodes))
	iterator, err := findConnections(nodes, startNode, endNode, filterPart2)
	if err != nil {
		log.Fatal(err)
	}
	pathCountPart1 := 0
	pathCountPart2 := 0
	for con := range iterator {
		set, err := setFromList(con)
		if err != nil {
			log.Fatal("internal error while filtering")
		}
		if filterPart1(&set) {
			pathCountPart1++
		}
		// We have already filtered for part 2's validity function.
		pathCountPart2++
	}
	fmt.Printf("there are %d paths for part 1\n", pathCountPart1)
	fmt.Printf("there are %d paths for part 2\n", pathCountPart2)
}

// FindNode finds a node based on its ID in a list of them.
func FindNode(nodes []*Node, id string) *Node {
	for _, checkNode := range nodes {
		if checkNode.ID == id {
			return checkNode
		}
	}
	return nil
}

// ReadLinesAsNodes reads all lines from stdin as nodes. Note that each line refers to more than one
// node.
func ReadLinesAsNodes() ([]*Node, error) {
	var result []*Node
	for {
		line, err := readLine()
		if err == io.EOF {
			// Success case, no more input to read.
			return result, nil
		}
		if err != nil {
			return []*Node{}, err
		}
		fields := trimStrings(strings.Split(line, connectionSep))
		// Try to find an existing node of the names. If none is found, create one.
		for _, field := range fields {
			if node := FindNode(result, field); node == nil {
				// No node found, add a new one.
				// A limit of zero means no limit in visiting.
				limit := 0
				if strings.ToLower(field) == field {
					// Lower case node name, we cannot visit it more than once.
					// But for part 2, we may visit at most one small cave twice. Thus, we consider
					// small caves as though they can be visited twice and filter out later.
					limit = 2
				}
				// The start and end nodes must never be visited more than once.
				if field == "start" || field == "end" {
					limit = 1
				}
				newNode := &Node{
					ID:          field,
					Limit:       limit,
					Connections: []*Node{},
				}
				result = append(result, newNode)
			}
		}
		// For each node in this line, add links to all other nodes mentioned in it. Note that
		// FindNode will not be able to return nil here as we already added all nodes mentioned in
		// this line.
		for _, startField := range fields {
			startNode := FindNode(result, startField)
			for _, endField := range fields {
				if endField == startField {
					continue
				}
				endNode := FindNode(result, endField)
				// Luckily, AddConnection will not do anything if the node is already known.
				startNode.AddConnection(endNode)
				endNode.AddConnection(startNode)
			}
		}
	}
}

// CountingSet is a set that also knows how often each element has been added. It does support
// non-empty strings only.
type CountingSet map[*Node]int

// Add adds an entry to the set. The empty *Node is not supported!
func (c *CountingSet) Add(entry *Node) error {
	if entry == nil {
		return fmt.Errorf("empty *Node not supported in counting set")
	}
	// We don't have to handle non-existing values here since Go returns the zero value (0 for
	// integers) for such entries.
	(*c)[entry] = (*c)[entry] + 1
	return nil
}

// Count determines how often an entry has been added to the set.
func (c *CountingSet) Count(entry *Node) int {
	return (*c)[entry]
}

// Remove removes one count for a specific key.
func (c *CountingSet) Remove(entry *Node) {
	if (*c)[entry] == 0 || (*c)[entry] == 1 {
		// Trying to remove an entry we don't have or one that has just one count left results in
		// that entry no longer being present.
		c.RemoveAll(entry)
		return
	}
	(*c)[entry] = (*c)[entry] - 1
}

// RemoveAll removes all counts for a specific key.
func (c *CountingSet) RemoveAll(entry *Node) {
	delete(*c, entry)
}

// FilterFn is a function that can be used to filter entries.
type FilterFn = func(*Node, int) bool

// Filter filters ebtries based on a predicate. That predicate, a FilterFn, gets the entry checked
// and its count in the data set.
func (c *CountingSet) Filter(predicate FilterFn) []*Node {
	result := []*Node{}
	for entry, count := range *c {
		if predicate(entry, count) {
			result = append(result, entry)
		}
	}
	return result
}

// FilterCount counts how many points would be filtered out by a FilterFn.
func (c *CountingSet) FilterCount(predicate FilterFn) int {
	result := 0
	for entry, count := range *c {
		if predicate(entry, count) {
			result++
		}
	}
	return result
}

// StackedNode tracks nodes on the stack as well as how many of its connections have not yet been
// visited.
type StackedNode struct {
	Node            *Node
	ConnectionCount *int
}

// Stack is a FIFO.
type Stack []StackedNode

// Push puts a value on the stack.
func (s *Stack) Push(node *Node, connectionCount int) {
	stackedNode := StackedNode{
		Node:            node,
		ConnectionCount: &connectionCount,
	}
	*s = append(*s, stackedNode)
}

// Pop removes the topmost value and returns it. Also returns whether the stack was non-empty.
func (s *Stack) Pop() (*StackedNode, bool) {
	if len(*s) == 0 {
		return &StackedNode{}, false
	}
	val := &(*s)[len(*s)-1]
	*s = (*s)[0 : len(*s)-1 : len(*s)-1]
	return val, true
}

// Peek returns the top-most entry.
func (s *Stack) Peek() *StackedNode {
	if len(*s) == 0 {
		return &StackedNode{}
	}
	return &(*s)[len(*s)-1]
}

// ToList gets the nodes stacked in the stack in the order they were stacked in (FIFO).
func (s *Stack) ToList() []*Node {
	result := []*Node{}
	for _, stackedNode := range *s {
		result = append(result, stackedNode.Node)
	}
	return result
}

// Node is a node in a tree.
type Node struct {
	ID          string
	Limit       int
	Connections []*Node
}

// AddConnection adds a connection to a node, but only if that connection does not yet exist. If it
// does, nothing is done.
func (n *Node) AddConnection(connection *Node) {
	for _, con := range n.Connections {
		if con == connection {
			return
		}
	}
	n.Connections = append(n.Connections, connection)
}

// NodeToStr provides a string representation for a node.
func NodeToStr(node *Node) string {
	connectionIDs := []string{}
	for _, con := range node.Connections {
		connectionIDs = append(connectionIDs, con.ID)
	}
	connections := strings.Join(connectionIDs, ",")
	str := fmt.Sprintf("{N: %s, L: %d, C: %s}", node.ID, node.Limit, connections)
	return str
}

// NodesToStr provides a string representation for multiple nodes.
func NodesToStr(nodes []*Node) string {
	str := ""
	for _, node := range nodes {
		str += NodeToStr(node) + "\n"
	}
	return str
}

func foldPoint(point Vec, ins Instruction) Vec {
	// Assume the point is unaffected.
	newPoint := point
	if ins.Dir == "x" && point.x > ins.Val {
		// Affected by fold.
		newPoint = Vec{
			x: ins.Val - (point.x - ins.Val),
			y: point.y,
		}
	} else if ins.Dir == "y" && point.y > ins.Val {
		// Affected by fold.
		newPoint = Vec{
			x: point.x,
			y: ins.Val - (point.y - ins.Val),
		}
	} else if !strings.Contains("xy", ins.Dir) {
		// Cannot reach here, so fatalling is OK if we do.
		log.Fatal("internal error while folding")
	}
	return newPoint
}

func fold(grid Grid, ins Instruction) (Grid, error) {
	result := Grid{}
	if !strings.Contains("xy", ins.Dir) {
		return Grid{}, fmt.Errorf("internal error")
	}
	// Check that no point is on the fold line.
	for p := range grid.Points() {
		if (ins.Dir == "x" && p.x == ins.Val) || (ins.Dir == "y" && p.y == ins.Val) {
			return Grid{}, fmt.Errorf("point on fold line")
		}
	}
	// Fold the points.
	for p := range grid.Points() {
		newPoint := foldPoint(p, ins)
		err := result.Mark(newPoint, 1)
		if err != nil {
			return Grid{}, err
		}
	}
	return result, nil
}

//nolint: funlen
func main() {
	prettyPrint := os.Getenv(prettyPrintEnvVar) == "1"
	grid, ins, err := ReadLinesAsGridAndInstructions()
	if err != nil {
		log.Fatal(err.Error())
	}
	if prettyPrint {
		fmt.Println(grid.Pretty(1))
	}
	for _, instruct := range ins {
		folded, err := fold(grid, instruct)
		if err != nil {
			log.Fatal(err.Error())
		}
		fmt.Printf("There are %d marked points.\n", len(folded))
		if prettyPrint {
			fmt.Println(folded.Pretty(1))
		}
		// err = folded.ReduceMarked(1)
		// if err != nil {
		// 	log.Fatal(err.Error())
		// }
		grid = folded
	}
	fmt.Println()
	// We need this in the end even though generating it might take long.
	fmt.Println(grid.Pretty(1)) //nolint:gomnd
}

const (
	defaultGridVal    = 1
	instructionSep    = "fold along "
	instructionFields = 2
	lineSep           = "="
)

// Instruction describes a folding instruction.
type Instruction struct {
	Val int
	Dir string
}

func instructionFromString(str string) (Instruction, error) {
	fields := strings.Split(str, lineSep)
	if len(fields) != instructionFields {
		return Instruction{}, fmt.Errorf("cannot convert %s to instruction, fields", str)
	}
	var result Instruction
	val, err := strconv.Atoi(fields[1])
	if err != nil {
		return Instruction{}, err
	}
	result = Instruction{
		Val: val,
		Dir: fields[0],
	}
	if !strings.Contains("xy", fields[0]) {
		return Instruction{}, fmt.Errorf("cannot convert %s to instruction, coord", str)
	}
	return result, nil
}

// ReadLinesAsGridAndInstructions reads all lines from stdin as a grid and instructions.
func ReadLinesAsGridAndInstructions() (Grid, []Instruction, error) {
	result := make(Grid)
	instructions := []Instruction{}
	for {
		line, err := readLine()
		if err == io.EOF {
			// Success case, no more input to read.
			return result, instructions, nil
		}
		if err != nil {
			return Grid{}, []Instruction{}, err
		}
		line = strings.TrimSpace(line)
		if len(line) == 0 {
			// Ignore empty lines.
			continue
		}
		//nolint:nestif
		if strings.Contains(line, instructionSep) {
			// Line with instruction.
			fields := strings.Split(line, instructionSep)
			if len(fields) != instructionFields {
				err := fmt.Errorf("cannot extract instruction from %s", line)
				return Grid{}, []Instruction{}, err
			}
			ins, err := instructionFromString(fields[1])
			if err != nil {
				return Grid{}, []Instruction{}, err
			}
			instructions = append(instructions, ins)
		} else {
			// Line with grid point.
			vec, err := VecFromStr(line)
			if err != nil {
				return Grid{}, []Instruction{}, err
			}
			err = result.Mark(vec, defaultGridVal)
			if err != nil {
				return Grid{}, []Instruction{}, err
			}
		}
	}
}

// Vec is a 2D vector. Most of it has been taken from a previous solution.
type Vec struct {
	x, y int
}

// VecFromStr converts a sring into a vector.
func VecFromStr(str string) (Vec, error) {
	fields := trimStrings(strings.Split(str, vecSep))
	if len(fields) != tokensPerPoint {
		return Vec{}, fmt.Errorf("cannot parse %v as vector, wrong number of fields", str)
	}
	ints, err := strSliceToIntSlice(fields)
	if err != nil {
		return Vec{}, fmt.Errorf("cannot parse %s as vector, %s", str, err.Error())
	}
	result := Vec{
		x: ints[0],
		y: ints[1],
	}
	return result, nil
}

// Add adds one vector to another one.
func (v Vec) Add(delta Vec) Vec {
	result := Vec{
		x: v.x + delta.x,
		y: v.y + delta.y,
	}
	return result
}

// Mul multiplies each component of a vector with a number.
func (v Vec) Mul(factor int) Vec {
	result := Vec{
		x: v.x * factor,
		y: v.y * factor,
	}
	return result
}

// Inv inverts a vector.
func (v Vec) Inv() Vec {
	return v.Mul(-1)
}

// Sub subtracts a vector'v data from another one'v.
func (v Vec) Sub(delta Vec) Vec {
	return v.Add(delta.Inv())
}

// Grid is a lazily evaluated grid that supports marking points on it. Most of it has been taken
// from a previous solution.
type Grid map[Vec]int

// Mark marks a point on the grid n times. Don't accept numbers <0.
func (g *Grid) Mark(entry Vec, n int) error {
	if n < 0 {
		return fmt.Errorf("can only mark non-negative times")
	}
	// We don't have to handle non-existing values here since Go returns the zero value (0 for
	// integers) for such entries.
	(*g)[entry] = (*g)[entry] + n
	return nil
}

// Count determines how often a point has been marked.
func (g *Grid) Count(entry Vec) int {
	return (*g)[entry]
}

// Has determines whether a point is on the grid.
func (g *Grid) Has(entry Vec) bool {
	_, ok := (*g)[entry]
	return ok
}

// RemoveAll removes all markings for a specific point.
func (g *Grid) RemoveAll(entry Vec) {
	delete(*g, entry)
}

// Points returns an iterator over all points on the grid.
func (g *Grid) Points() <-chan Vec {
	channel := make(chan Vec)
	go func() {
		for point := range *g {
			channel <- point
		}
		close(channel)
	}()
	return channel
}

// ReduceMarked sets the marking value of all points that are marked to the given value.
func (g *Grid) ReduceMarked(val int) error {
	if val < 0 {
		return fmt.Errorf("can only mark non-negative times")
	}
	for p := range g.Points() {
		(*g)[p] = val
	}
	return nil
}

func (g *Grid) topLeft() (int, int) {
	foundX, foundY := false, false
	minX, minY := 0, 0
	for p := range g.Points() {
		if !foundX || p.x < minX {
			minX = p.x
			foundX = true
		}
		if !foundY || p.y < minY {
			minY = p.y
			foundY = true
		}
	}
	return minX, minY
}

func (g *Grid) bottomRight() (int, int) {
	foundX, foundY := false, false
	maxX, maxY := 0, 0
	for p := range g.Points() {
		if !foundX || p.x > maxX {
			maxX = p.x
			foundX = true
		}
		if !foundY || p.y > maxY {
			maxY = p.y
			foundY = true
		}
	}
	return maxX, maxY
}

// Pretty creates a pretty string representation of this grid.
func (g *Grid) Pretty(digits int) string {
	result := ""
	empty := " "
	maxVal := 10
	for count := 1; count < digits; count++ {
		empty += " "
		maxVal *= 10
	}
	formatStr := fmt.Sprintf("%%-%dd", digits)
	minX, minY := g.topLeft()
	maxX, maxY := g.bottomRight()
	for y := minY; y <= maxY; y++ {
		for x := minX; x <= maxX; x++ {
			val := g.Count(Vec{x: x, y: y})
			if val > 0 {
				result += fmt.Sprintf(formatStr, val)
				if val >= maxVal {
					// Return the string up to the offending point so that the caller sees what the
					// offending number was. This is a hack at best but good enough for me right
					// now.
					return result + "\nINCOMPLETE"
				}
			} else {
				result += empty
			}
		}
		result += "\n"
	}
	return result
}

const (
	// We make the buffer large to achieve some degree of parallelism with goroutines.
	buffer      = 100000
	roundsPart1 = 10
	roundsPart2 = 40
)

func makeMap(replacements []Replacement) map[Match]rune {
	result := map[Match]rune{}
	for _, rep := range replacements {
		result[rep.Match] = rep.Insert
	}
	return result
}

func replace(input <-chan rune, output chan<- rune, replacements map[Match]rune, idx int) {
	myReps := map[Match]rune{}
	// Copy the map so that each goroutine has its own.
	for key, val := range replacements {
		myReps[key] = val
	}
	lastRune := <-input
	for char := range input {
		output <- lastRune
		if match, ok := myReps[Match{Left: lastRune, Right: char}]; ok {
			output <- match
		}
		lastRune = char
	}
	output <- lastRune
	close(output)
	fmt.Printf("Closing stage %d.\n", idx)
}

func feed(input string, channel chan<- rune) {
	for _, char := range input {
		channel <- char
	}
	close(channel)
	fmt.Println("Closing feeder.")
}

func count(input <-chan rune) map[rune]int {
	result := map[rune]int{}
	for char := range input {
		result[char]++
	}
	return result
}

func max(input map[rune]int) int {
	found := false
	var max int
	for _, val := range input {
		if !found || val > max {
			found = true
			max = val
		}
	}
	return max
}

func min(input map[rune]int) int {
	found := false
	var min int
	for _, val := range input {
		if !found || val < min {
			found = true
			min = val
		}
	}
	return min
}

// Run the polymerization riddle for a given number of rounds. Note how we never construct the full
// string in memory.
func runRounds(input string, reps map[Match]rune, rounds int) map[rune]int {
	// Construct pipeline.
	inChannel := make(chan rune, buffer)
	var outChannel chan rune
	// Run pipeline.
	go feed(input, inChannel)
	for roundIdx := 0; roundIdx < rounds; roundIdx++ {
		outChannel = make(chan rune, buffer)
		go replace(inChannel, outChannel, reps, roundIdx)
		inChannel = outChannel
	}
	counts := count(outChannel)
	return counts
}

// Split a string into pairs of characters. Each pair knows whether it's in the middle or at an
// edge. If it's at an edge, it also knows which one.
func stringToMatches(str string) []Match {
	result := []Match{}
	if len(str) == 0 {
		// This is an error case that will never happen. Thus, don't catch it.
		return []Match{}
	}
	split := strings.Split(str, "")
	lastChar := rune(split[0][0])
	for idx, c := range split[1:] {
		char := rune(c[0])
		var leftEdge, rightEdge bool
		if idx == 0 {
			leftEdge = true
		}
		if idx == len(split)-2 {
			rightEdge = true
		}
		match := Match{Left: lastChar, Right: char, LeftEdge: leftEdge, RightEdge: rightEdge}
		lastChar = char
		result = append(result, match)
	}
	return result
}

// Perform one pair split according to the rules. That is, a pair is converted into two pairs by
// inserting a letter in between. This also takes care of propagating the information of which
// matches are at the edges.
func translateMatch(match Match, reps *map[Match]rune) []Match {
	// make sure to strip away the edge information. Otherwise, matches at the edges will never be
	// found.
	matchWithoutEdge := Match{Right: match.Right, Left: match.Left}
	if insert, foundMatch := (*reps)[matchWithoutEdge]; foundMatch {
		leftMatch := Match{
			Left:      match.Left,
			Right:     insert,
			LeftEdge:  match.LeftEdge,
			RightEdge: false,
		}
		rightMatch := Match{
			Left:      insert,
			Right:     match.Right,
			LeftEdge:  false,
			RightEdge: match.RightEdge,
		}
		return []Match{leftMatch, rightMatch}
	}
	// No match found, return the original one.
	return []Match{match}
}

// Run the polymerization riddle for a given number of rounds, but do it differently. This approach
// does not scale exponentially with the number of rounds.
func runRoundsDifferently(input string, reps map[Match]rune, rounds int) map[rune]int {
	matches := stringToMatches(input)
	// We treat all identical matches the same way.
	matchCounts := map[Match]int{}
	for _, match := range matches {
		matchCounts[match]++
	}
	// Run!
	for round := 0; round < rounds; round++ {
		newMatchCounts := map[Match]int{}
		for match, count := range matchCounts {
			newMatches := translateMatch(match, &reps)
			for _, newM := range newMatches {
				newMatchCounts[newM] += count
			}
		}
		matchCounts = newMatchCounts
	}
	foundLeftEdge := false
	foundRightEdge := false
	// Count characters! Each char is in two pairs apart from the ones at the edges.
	result := map[rune]int{}
	// First, count all characters in all pairs. This will be twice the number we want.
	for match, count := range matchCounts {
		// Count each character in a pair for each pair that has it.
		result[match.Right] += count
		result[match.Left] += count
		// Handle edge cases (pun very much intended).
		if (match.LeftEdge || match.RightEdge) && count != 1 {
			// Error case, should never happen, so fatalling is OK if it does.
			log.Fatal("more than one character at the left edge")
		}
		// Also add one for each character at an edge. This makes sure we also counted them twice.
		if match.LeftEdge {
			if foundLeftEdge {
				log.Fatal("there can only be one left edge")
			}
			result[match.Left]++
		}
		if match.RightEdge {
			if foundRightEdge {
				log.Fatal("there can only be one right edge")
			}
			result[match.Right]++
		}
	}
	// Then, divide all counts by two.
	for char, count := range result {
		if count%2 != 0 {
			// Error case, should never happen, so fatalling is OK if it does.
			log.Fatalf("cannot divide odd number %d by 2 for %c", count, char)
		}
		result[char] /= 2
	}
	return result
}

//nolint: funlen
func main() {
	input, replacements, err := ReadLinesAsReplacementsOrInput()
	if err != nil {
		log.Fatal(err.Error())
	}
	reps := makeMap(replacements)
	counts := runRounds(input, reps, roundsPart1)
	fmt.Printf(
		"Part 1: max: %d, min: %d, diff: %d\n",
		max(counts), min(counts), max(counts)-min(counts),
	)
	// Part 2 cannot be solved this way, it just takes too long. Thus, solve it differently.
	counts = runRoundsDifferently(input, reps, roundsPart1)
	fmt.Printf(
		"Part 1 differently: max: %d, min: %d, diff: %d\n",
		max(counts), min(counts), max(counts)-min(counts),
	)
	counts = runRoundsDifferently(input, reps, roundsPart2)
	fmt.Printf(
		"Part 2 differently: max: %d, min: %d, diff: %d\n",
		max(counts), min(counts), max(counts)-min(counts),
	)
}

// ReadLinesAsReplacementsOrInput reads all lines from stdin as replacement instructions or input.
func ReadLinesAsReplacementsOrInput() (string, []Replacement, error) {
	var result []Replacement
	var input string
	for {
		line, err := readLine()
		if err == io.EOF {
			// Success case, no more input to read.
			return input, result, nil
		}
		if err != nil {
			return "", []Replacement{}, err
		}
		line = strings.TrimSpace(line)
		if len(line) == 0 {
			// Skip empty lines.
			continue
		}
		if strings.Contains(line, repSep) {
			// A line with a replacement.
			parsed, err := RepFromString(line)
			if err != nil {
				return "", []Replacement{}, err
			}
			result = append(result, parsed)
		} else {
			// A line with the input string.
			if len(input) != 0 {
				err := fmt.Errorf("already processed input")
				return "", []Replacement{}, err
			}
			input = line
		}
	}
}

// Match described one match of two characters.
type Match struct {
	Left      rune
	Right     rune
	LeftEdge  bool
	RightEdge bool
}

func b2s(b bool) rune {
	if b {
		return '1'
	}
	return '0'
}

// ToString provides a nice string representation for a match.
func (m Match) ToString() string {
	return fmt.Sprintf(
		"{%c%c [%c|%c]}",
		m.Left, m.Right, b2s(m.LeftEdge), b2s(m.RightEdge),
	)
}

// Replacement describes one replacement instruction by insertion.
type Replacement struct {
	Match  Match
	Insert rune
}

// RepFromString converts a sring into a replacement instruction.
func RepFromString(str string) (Replacement, error) {
	fields := trimStrings(strings.Split(str, repSep))
	if len(fields) != tokensPerRep {
		err := fmt.Errorf("cannot parse %v as rep, wrong number of fields", str)
		return Replacement{}, err
	}
	if len(fields[0]) != tokensPerRep {
		err := fmt.Errorf("cannot parse %v as rep, wrong number of characters", str)
		return Replacement{}, err
	}
	if len(fields[1]) != 1 {
		err := fmt.Errorf("cannot parse %v as rep, wrong number of insertions", str)
		return Replacement{}, err
	}
	match := Match{
		Left:  rune(fields[0][0]),
		Right: rune(fields[0][1]),
	}
	rep := Replacement{
		Match:  match,
		Insert: rune(fields[1][0]),
	}
	return rep, nil
}

const (
	numNeigh = 4
	replicas = 5
)

func gridToNodes(grid Grid) (map[*astar.Node]struct{}, *astar.Node, *astar.Node, error) {
	result := map[*astar.Node]struct{}{}
	var start, end *astar.Node
	// Remember which node belonged to which location.
	convertedNodes := map[Vec]*astar.Node{}

	// Our grid is not guaranteed to be square. Thus, we extract the expected positions this way and
	// error out if we cannot find them later on.
	startX, startY := grid.TopLeft()
	endX, endY := grid.BottomRight()
	startVec := Vec{startX, startY}
	endVec := Vec{endX, endY}

	// Process the nodes themselves.
	for vec, cost := range grid {
		if _, ok := convertedNodes[vec]; ok {
			err := fmt.Errorf("node already present")
			return result, start, end, err
		}

		node, err := astar.NewNode(fmt.Sprint(vec), cost, numNeigh, vec)
		if err != nil {
			return result, start, end, err
		}

		convertedNodes[vec] = node
		result[node] = struct{}{}

		if vec == startVec {
			start = node
		}
		if vec == endVec {
			end = node
		}
	}
	if start == nil || end == nil {
		err := fmt.Errorf("cannot find start or end node in grid")
		return result, start, end, err
	}
	// Add pairwise connections. This might take a while.
	for vec := range grid {
		node, ok := convertedNodes[vec]
		if !ok {
			err := fmt.Errorf("node not found")
			return result, start, end, err
		}
		for neigh := range pointEnv(vec) {
			if !grid.Has(neigh) {
				continue // Ignore nodes outside the grid.
			}
			neighNode, ok := convertedNodes[neigh]
			if !ok {
				err := fmt.Errorf("node not found")
				return result, start, end, err
			}
			// If a connection already exists, this is a no-op.
			node.AddConnection(neighNode)
			neighNode.AddConnection(node)
		}
	}
	return result, start, end, nil
}

//nolint: funlen
func main() {
	grid, err := ReadLinesAsGrid()
	if err != nil {
		log.Fatal(err.Error())
	}
	// Part 1.
	nodes, startNode, endNode, err := gridToNodes(grid)
	if err != nil {
		log.Fatal(err.Error())
	}

	fastAlgorithm(nodes, startNode, endNode)

	startX, startY := grid.TopLeft()
	endX, endY := grid.BottomRight()

	// Part 2.
	// Replicate grid. Then, run the fast algorithm
	largeGrid := Grid{}
	for p := range grid {
		for xRep := 0; xRep < replicas; xRep++ {
			for yRep := 0; yRep < replicas; yRep++ {
				newPoint := Vec{
					x: p.x + xRep*(endX-startX+1),
					y: p.y + yRep*(endY-startY+1),
				}
				newMarking := (grid.Count(p)-1+xRep+yRep)%9 + 1 //nolint:gomnd
				if largeGrid.Has(newPoint) {
					// Sanity check, we should never add a node twice.
					log.Fatal("node already there")
				}
				_ = largeGrid.Mark(newPoint, newMarking)
			}
		}
	}

	nodes, startNode, endNode, err = gridToNodes(largeGrid)
	if err != nil {
		log.Fatal(err.Error())
	}

	fastAlgorithm(nodes, startNode, endNode)
}

// ReadLinesAsGrid reads all lines from stdin as a grid. That is, each point on the grid has a
// value and a location.
func ReadLinesAsGrid() (Grid, error) {
	lineIdx := 0
	result := make(Grid)
	for {
		line, err := readLine()
		if err == io.EOF {
			// Success case, no more input to read.
			return result, nil
		}
		if err != nil {
			return Grid{}, err
		}
		line = strings.TrimSpace(line)
		ints, err := strSliceToIntSlice(strings.Split(line, ""))
		if err != nil {
			return Grid{}, err
		}
		for rowIdx, val := range ints {
			// This is lazy but I wanted to re-use old code.
			point, err := VecFromStr(fmt.Sprintf("%d%s%d", lineIdx, vecSep, rowIdx))
			if err != nil {
				return Grid{}, err
			}
			err = result.Mark(point, val)
			if err != nil {
				return Grid{}, err
			}
		}
		if err != nil {
			return Grid{}, err
		}
		lineIdx++
	}
}

// Vec is a 2D vector. Most of it has been taken from a previous solution.
type Vec struct {
	x, y int
}

var (
	unitX         = Vec{x: 1}
	unitY         = Vec{y: 1}
	pointEnvDisps = []Vec{
		unitX,
		unitY,
		unitY.Inv(),
		unitX.Inv(),
	}
)

// Obtain an iterator over a point's environment.
func pointEnv(point Vec) <-chan Vec {
	channel := make(chan Vec)
	go func() {
		for _, disp := range pointEnvDisps {
			displaced := point.Add(disp)
			channel <- displaced
		}
		close(channel)
	}()
	return channel
}

// VecFromStr converts a sring into a vector.
func VecFromStr(str string) (Vec, error) {
	fields := trimStrings(strings.Split(str, vecSep))
	if len(fields) != tokensPerPoint {
		return Vec{}, fmt.Errorf("cannot parse %v as vector, wrong number of fields", str)
	}
	ints, err := strSliceToIntSlice(fields)
	if err != nil {
		return Vec{}, fmt.Errorf("cannot parse %s as vector, %s", str, err.Error())
	}
	result := Vec{
		x: ints[0],
		y: ints[1],
	}
	return result, nil
}

// Add adds one vector to another one.
func (v Vec) Add(delta Vec) Vec {
	result := Vec{
		x: v.x + delta.x,
		y: v.y + delta.y,
	}
	return result
}

// Mul multiplies each component of a vector with a number.
func (v Vec) Mul(factor int) Vec {
	result := Vec{
		x: v.x * factor,
		y: v.y * factor,
	}
	return result
}

// Inv inverts a vector.
func (v Vec) Inv() Vec {
	return v.Mul(-1)
}

// Sub subtracts a vector'v data from another one'v.
func (v Vec) Sub(delta Vec) Vec {
	return v.Add(delta.Inv())
}

// Grid is a lazily evaluated grid that supports marking points on it. Most of it has been taken
// from a previous solution.
type Grid map[Vec]int

// Mark marks a point on the grid n times. Don't accept numbers <0.
func (g *Grid) Mark(entry Vec, n int) error {
	if n < 0 {
		return fmt.Errorf("can only mark non-negative times")
	}
	// We don't have to handle non-existing values here since Go returns the zero value (0 for
	// integers) for such entries.
	(*g)[entry] = (*g)[entry] + n
	return nil
}

// Count determines how often a point has been marked.
func (g *Grid) Count(entry Vec) int {
	return (*g)[entry]
}

// Has determines whether a point is on the grid.
func (g *Grid) Has(entry Vec) bool {
	_, ok := (*g)[entry]
	return ok
}

// RemoveAll removes all markings for a specific point.
func (g *Grid) RemoveAll(entry Vec) {
	delete(*g, entry)
}

// FilterThreshold returns all points whose value exceeds a threshold.
func (g *Grid) FilterThreshold(threshold int) []Vec {
	result := []Vec{}
	for point := range g.Points() {
		if g.Count(point) > threshold {
			result = append(result, point)
		}
	}
	return result
}

// MarkAll maks all points in the grid with the same value.
func (g *Grid) MarkAll(val int) error {
	for p := range g.Points() {
		if err := g.Mark(p, val); err != nil {
			return err
		}
	}
	return nil
}

// EnvFn is a function type used to determine a point's environment.
type EnvFn = func(point Vec) <-chan Vec

// MarkExistingEnv marks all points by the specified value in the environment of a given point. The
// environment is defined by envFn. Only points that actually exist will be marked.
func (g *Grid) MarkExistingEnv(val int, point Vec, envFn EnvFn) error {
	for neigh := range envFn(point) {
		if !g.Has(neigh) {
			continue
		}
		if err := g.Mark(neigh, val); err != nil {
			return err
		}
	}
	return nil
}

// Points returns an iterator over all points on the grid.
func (g *Grid) Points() <-chan Vec {
	channel := make(chan Vec)
	go func() {
		for point := range *g {
			channel <- point
		}
		close(channel)
	}()
	return channel
}

// TopLeft returns the coordinates of the top left node.
func (g *Grid) TopLeft() (int, int) {
	foundX, foundY := false, false
	minX, minY := 0, 0
	for p := range g.Points() {
		if !foundX || p.x < minX {
			minX = p.x
			foundX = true
		}
		if !foundY || p.y < minY {
			minY = p.y
			foundY = true
		}
	}
	return minX, minY
}

// BottomRight returns the coordinates of the bottom right node.
func (g *Grid) BottomRight() (int, int) {
	foundX, foundY := false, false
	maxX, maxY := 0, 0
	for p := range g.Points() {
		if !foundX || p.x > maxX {
			maxX = p.x
			foundX = true
		}
		if !foundY || p.y > maxY {
			maxY = p.y
			foundY = true
		}
	}
	return maxX, maxY
}

// Pretty creates a pretty string representation of this grid.
func (g *Grid) Pretty(digits int) string {
	result := ""
	empty := " "
	maxVal := 10
	for count := 1; count < digits; count++ {
		empty += " "
		maxVal *= 10
	}
	formatStr := fmt.Sprintf("%%-%dd", digits)
	minX, minY := g.TopLeft()
	maxX, maxY := g.BottomRight()
	for x := minX; x <= maxX; x++ {
		for y := minY; y <= maxY; y++ {
			val := g.Count(Vec{x: x, y: y})
			if val > 0 {
				result += fmt.Sprintf(formatStr, val)
				if val >= maxVal {
					// Return the string up to the offending point so that the caller sees what the
					// offending number was. This is a hack at best but good enough for me right
					// now.
					return result + "\nINCOMPLETE"
				}
			} else {
				result += empty
			}
		}
		result += "\n"
	}
	return result
}

// This is an implementation using an A* algorithm implemented by me.

import (
	"fmt"
	"log"

	"github.com/razziel89/astar"
)

func fastAlgorithm(nodes map[*astar.Node]struct{}, start, end *astar.Node) {
	// Build heuristic that measures distance to end node.
	heuristic := astar.ConstantHeuristic{}
	// Extract payload. We know that these are the coordinates.
	endVec := end.Payload.(Vec)
	for node := range nodes {
		vec := node.Payload.(Vec)
		// The estimate assumes a cost of 1 for the most direct connection.
		estimate := (vec.x - endVec.x) + (vec.y - endVec.y)
		err := heuristic.AddNode(node, estimate)
		if err != nil {
			log.Fatal(err.Error())
		}
	}
	// Plot path.
	path, err := astar.FindPath(nodes, start, end, heuristic.Heuristic(0))
	if err != nil {
		log.Fatal(err.Error())
	}
	// Compute cost.
	cost := 0
	for _, node := range path[1:] {
		fmt.Println(node.ToString())
		cost += node.Cost
	}
	fmt.Println("Cost is", cost)
}

//nolint: funlen
func main() {
	lines, err := ReadLinesAsLines()
	if err != nil {
		log.Fatal(err.Error())
	}
	if len(lines) != 1 {
		log.Fatal("wrong number of lines")
	}

	parsed, err := Parse(lines[0])
	if err != nil {
		log.Fatal(err.Error())
	}

	// Declare here to allow recursion.
	var addVersionsUp func([]Package) int

	addVersionsUp = func(packages []Package) int {
		result := 0
		for _, pkg := range packages {
			result += pkg.Version()
			result += addVersionsUp(pkg.SubPackages())
		}
		return result
	}

	totalVersion := addVersionsUp(parsed)

	fmt.Println("Sum of all version numbers is", totalVersion)

	if len(parsed) != 1 {
		log.Fatal("we were promised exactly one package")
	}
	fmt.Println("Value of outermost package is", parsed[0].Value())
}

// ReadLinesAsLines reads in some lines.
func ReadLinesAsLines() ([]string, error) {
	result := []string{}
	for {
		line, err := readLine()
		if err == io.EOF {
			// Success case, no more input to read.
			return result, nil
		}
		if err != nil {
			return []string{}, err
		}
		line = strings.TrimSpace(line)
		result = append(result, line)
	}
}

import (
	"fmt"
	"log"
	"strconv"
	"strings"
)

const (
	hexBase    = 16
	binarybase = 2
	padding    = 4
)

func hexToBinary(char rune) ([]bool, error) {
	num, err := strconv.ParseInt(string(char), hexBase, 0)
	if err != nil {
		return []bool{}, err
	}
	// This is being lazy, but it's fast enough here.
	binaryString := strconv.FormatInt(num, binarybase)
	for len(binaryString) < padding {
		binaryString = "0" + binaryString
	}
	result := make([]bool, 0, len(binaryString))
	for _, char := range binaryString {
		result = append(result, char == '1')
	}
	return result, nil
}

// BitStream provides a stream of bits based on hex code. I am using boolean values here to
// represent bits.
type BitStream struct {
	bin  []bool
	pad  int
	read int
}

// Next provides the next num bits.
func (s *BitStream) Next(num int) []bool {
	if s.read+num > len(s.bin) {
		log.Fatalf("trying to read too much, remaining %s, reading %d", s.ToString(true), num)
	}
	if num <= 0 {
		return []bool{}
	}
	result := s.bin[s.read : s.read+num : s.read+num]
	s.read += num
	s.pad = (s.pad + num) % padding
	return result
}

// Done determines whether any characters are left. If only zeroes are left, we also exit.
func (s *BitStream) Done() bool {
	if s.read >= len(s.bin) {
		return true
	}
	for _, bit := range s.bin[s.read:] {
		if bit {
			return false
		}
	}
	return true
}

// Pad reads up to the next multiple of `padding` since one hexadecimal digit is four binary digits.
func (s *BitStream) Pad() {
	if s.pad > 0 {
		_ = s.Next(padding - s.pad)
	}
}

// AddHex adds a hex string.
func (s *BitStream) AddHex(hex string) error {
	if len(s.bin) == 0 {
		s.bin = make([]bool, 0, len(hex))
	} else {
		newBin := make([]bool, 0, len(s.bin)+len(hex))
		_ = copy(newBin, s.bin)
		s.bin = newBin
	}
	hex = strings.ToUpper(hex)
	for _, char := range hex {
		binarySequence, err := hexToBinary(char)
		if err != nil {
			return fmt.Errorf("error in hex to binary conversion: %s", err.Error())
		}
		s.bin = append(s.bin, binarySequence...)
	}
	return nil
}

// ToString converts to a binary string. Specify whether you want truncated (true) or full (false)
func (s *BitStream) ToString(truncated bool) string {
	result := ""
	start := 0
	if truncated {
		start = s.read
	}
	for _, val := range s.bin[start:] {
		if val {
			result += "1"
		} else {
			result += "0"
		}
	}
	fmtStr := fmt.Sprintf("%%%ds", len(s.bin))
	return fmt.Sprintf(fmtStr, result)
}

// LimitedStream creates a limited bit stream based on the next limit bits of this one. This makes
// it easy to read operators in the "limited number of bits" mode. Any zeroes at the end are then
// part of the limited stream and the original one doesn't have to care.
func (s *BitStream) LimitedStream(limit int) BitStream {
	stream := BitStream{
		bin:  s.Next(limit),
		pad:  0,
		read: 0,
	}
	return stream
}

// BitsToInt converts a stream of bits into an integer.
func BitsToInt(bits []bool) int {
	result := 0
	for _, bit := range bits {
		result *= 2
		if bit {
			result++
		}
	}
	return result
}

// Parse parses a string into packages and sub-packages.
func Parse(input string) ([]Package, error) {
	result := []Package{}

	stream := BitStream{}
	if err := stream.AddHex(input); err != nil {
		return []Package{}, err
	}

	for !stream.Done() {
		pkg := FromBitStream(&stream)
		result = append(result, pkg)
		stream.Pad()
	}

	return result, nil
}

const (
	// Numerical values, there are a lot of them this time.
	totalLengthModeBits      = 15
	totalNumPackagesModeBits = 11
)

// Operator is an actual implementation of the package interface, operator value.
type Operator struct {
	version     int
	typeInfo    int
	subPackages []Package
}

// Version provides the version number.
func (p *Operator) Version() int {
	return p.version
}

// Type provides the type information.
func (p *Operator) Type() int {
	return p.typeInfo
}

// SubPackages provides a list of sub-packages.
func (p *Operator) SubPackages() []Package {
	return p.subPackages
}

// Value determines the value of this package.
//nolint:funlen
func (p *Operator) Value() int {
	//nolint:gomnd
	switch p.Type() {
	case 0:
		// Packets with type ID 0 are sum packets - their value is the sum of the values of their
		// sub-packets. If they only have a single sub-packet, their value is the value of the
		// sub-packet.
		result := 0
		for _, pkg := range p.SubPackages() {
			result += pkg.Value()
		}
		return result
	case 1:
		// Packets with type ID 1 are product packets - their value is the result of multiplying
		// together the values of their sub-packets. If they only have a single sub-packet, their
		// value is the value of the sub-packet.
		//
		// Treat packages without sub-packages as having no value. This should not happen for prduct
		// packages.
		if len(p.subPackages) == 0 {
			return 0
		}
		result := 1
		for _, pkg := range p.subPackages {
			result *= pkg.Value()
		}
		return result
	case 2:
		// Packets with type ID 2 are minimum packets - their value is the minimum of the values of
		// their sub-packets.
		result := 0
		found := false
		for _, pkg := range p.subPackages {
			val := pkg.Value()
			if !found || val < result {
				result = val
				found = true
			}
		}
		return result
	case 3:
		// Packets with type ID 3 are maximum packets - their value is the maximum of the values of
		// their sub-packets.
		result := 0
		found := false
		for _, pkg := range p.subPackages {
			val := pkg.Value()
			if !found || val > result {
				result = val
				found = true
			}
		}
		return result
	case 5:
		// Packets with type ID 5 are greater than packets - their value is 1 if the value of the
		// first sub-packet is greater than the value of the second sub-packet; otherwise, their
		// value is 0.  These packets always have exactly two sub-packets.
		result := 0
		if len(p.subPackages) == 2 && p.subPackages[0].Value() > p.subPackages[1].Value() {
			result = 1
		}
		return result
	case 6:
		// Packets with type ID 6 are less than packets - their value is 1 if the value of the first
		// sub-packet is less than the value of the second sub-packet; otherwise, their value is 0.
		// These packets always have exactly two sub-packets.
		result := 0
		if len(p.subPackages) == 2 && p.subPackages[0].Value() < p.subPackages[1].Value() {
			result = 1
		}
		return result
	case 7:
		// Packets with type ID 7 are equal to packets - their value is 1 if the value of the first
		// sub-packet is equal to the value of the second sub-packet; otherwise, their value is 0.
		// These packets always have exactly two sub-packets.
		result := 0
		if len(p.subPackages) == 2 && p.subPackages[0].Value() == p.subPackages[1].Value() {
			result = 1
		}
		return result
	default:
		// Should never happen.
		return 0
	}
}

// NewOperator creates a new literal package. Version and type information have to be provided.
func NewOperator(version, typeInfo int, stream *BitStream) Operator {
	subPackages := []Package{}
	modeBit := stream.Next(1)
	if !modeBit[0] {
		// Total length mode.
		totalLength := BitsToInt(stream.Next(totalLengthModeBits))
		shortStream := stream.LimitedStream(totalLength)
		for !shortStream.Done() {
			// No padding in between according to the task.
			pkg := FromBitStream(&shortStream)
			subPackages = append(subPackages, pkg)
		}
	} else {
		// Number of packages mode.
		numPkgs := BitsToInt(stream.Next(totalNumPackagesModeBits))
		for count := 0; count < numPkgs; count++ {
			// No padding in between according to the task.
			pkg := FromBitStream(stream)
			subPackages = append(subPackages, pkg)
		}
	}
	return Operator{
		version:     version,
		typeInfo:    typeInfo,
		subPackages: subPackages,
	}
}

const (
	bitsPerLiteralSet = 4
)

// Literal is an actual implementation of the package interface, literal value.
type Literal struct {
	version  int
	typeInfo int
	value    int
}

// Version provides the version number.
func (p *Literal) Version() int {
	return p.version
}

// Type provides the type information.
func (p *Literal) Type() int {
	return p.typeInfo
}

// Value provides the value information.
func (p *Literal) Value() int {
	return p.value
}

// SubPackages provides a list of sub-packages.
func (p *Literal) SubPackages() []Package {
	// Literal packages have no sub-packages. To implement the interface, we return an empty slice
	// here.
	return []Package{}
}

// NewLiteral creates a new literal package. Version and type information have to be provided.
func NewLiteral(version, typeInfo int, stream *BitStream) Literal {
	bits := []bool{}
	for notLastGroup := stream.Next(1); notLastGroup[0]; notLastGroup = stream.Next(1) {
		bits = append(bits, stream.Next(bitsPerLiteralSet)...)
	}
	bits = append(bits, stream.Next(bitsPerLiteralSet)...)
	num := BitsToInt(bits)
	return Literal{
		version:  version,
		typeInfo: typeInfo,
		value:    num,
	}
}

const (
	// Numerical values, there are a lot of them this time.
	versionBits  = 3
	typeInfoBits = 3
	// Type information.
	literalType = 4
)

// Package describes a package.
type Package interface {
	Version() int
	Type() int
	SubPackages() []Package
	Value() int
}

// FromBitStream obtains a package from a bit stream. No padding on the stream is done. Will create
// operators or literals as mandated by the type information.
func FromBitStream(stream *BitStream) Package {
	version := BitsToInt(stream.Next(versionBits))
	typeInfo := BitsToInt(stream.Next(typeInfoBits))
	var pkg Package
	if typeInfo == literalType {
		lit := NewLiteral(version, typeInfo, stream)
		pkg = &lit
	} else {
		op := NewOperator(version, typeInfo, stream)
		pkg = &op
	}
	return pkg
}

const (
	// Our algorithm does not end by itself since we can never really be sure that we have found the
	// highest y-velocity that will still result in a hit. Thus, we end after this many velocities
	// at most. Empirically, this has been proven to be enough.
	maxNumVelocities = 1000000
	buffer           = 100
	drag             = -1
	gravity          = -1
)

// Generate valid velocity vectors up to a maximum x value and a minimum y value.
func generateVelocities(xMax, yMin int) <-chan Vec {
	channel := make(chan Vec, buffer)

	go func() {
		numVelocities := 0
		// Start with a Manhattan distance of 1 and successively create all values in the allowed
		// range.
		distance := 1
		for {
			// For all smaller x, explore only y==+distance and y==-distance.
			for x := 0; x < distance; x++ {
				channel <- Vec{x, distance}
				numVelocities++
				if -distance >= yMin {
					channel <- Vec{x, -distance}
					numVelocities++
				}
			}
			if distance <= xMax {
				// For x==distance, explore all y in [-distance, +distance].
				for y := -distance; y <= distance; y++ {
					channel <- Vec{distance, y}
					numVelocities++
				}
			}
			distance++
			// It is not guaranteed that we have found the solution, but we did ^^. So this hack is
			// fine to make the algorithm end by itself.
			if numVelocities > maxNumVelocities {
				break
			}
		}
		close(channel)
	}()

	return channel
}

func generateTrajectory(input <-chan Vec, drag, gravity int, area Area) <-chan int {
	channel := make(chan int, buffer)

	go func() {
		// Obtain one velocity vector and follow its trajectory.
		for vel := range input {
			if vel.x < 0 {
				log.Fatal("negative x velocity detected")
			}
			pos := Vec{0, 0}
			trackedHeight := pos.y
			inside := area.Inside(pos)
			invalid := area.Invalid(pos)
			for !inside && !invalid {
				// Explore the trajectory based on an initial velocity.
				// We explore as long as our x position is not higher than the max and our y
				// position is not lower than the min.

				// Generate the next step in the trajectory.
				pos = pos.Add(vel)
				// Update the velocity. We will never have negative x velocities.
				if vel.x > 0 {
					vel.x += drag
				}
				vel.y += gravity

				if pos.y > trackedHeight {
					trackedHeight = pos.y
				}

				// Check whether we are still on track to possibly hit the area.
				inside = area.Inside(pos)
				invalid = area.Invalid(pos)
			}
			// Don't return invalid data.
			if inside && !invalid {
				channel <- trackedHeight
			}
		}
		close(channel)
	}()

	return channel
}

func main() {
	areas, err := ReadLinesAsAreas()
	if err != nil {
		log.Fatal(err.Error())
	}
	if len(areas) != 1 {
		log.Fatal("only one area expected")
	}
	area := areas[0]
	if err := area.IsValid(); err != nil {
		log.Fatal(err.Error())
	}
	velocities := generateVelocities(area.xMax, area.yMin)
	trajectories := generateTrajectory(velocities, drag, gravity, area)

	count := 1
	maxHeight := <-trajectories
	for height := range trajectories {
		count++
		if height > maxHeight {
			maxHeight = height
		}
		fmt.Println("Max valid height is", maxHeight, "and valid trajectories found are", count)
	}
}

// ReadLinesAsAreas reads all lines from stdin as areas.
func ReadLinesAsAreas() ([]Area, error) {
	var result []Area
	for {
		line, err := readLine()
		if err == io.EOF {
			// Success case, no more input to read.
			return result, nil
		}
		if err != nil {
			return []Area{}, err
		}
		fields := trimStrings(strings.Fields(line))
		if len(fields) == 0 {
			// Skip empty lines.
			continue
		}
		if len(fields) != numExpectedFields {
			return []Area{}, fmt.Errorf("unexpected number of fields")
		}
		if fields[0] != areaStart[0] || fields[1] != areaStart[1] {
			return []Area{}, fmt.Errorf("unexpected start of line")
		}
		area, err := AreaFromString(strings.Join(fields[2:], " "))
		if err != nil {
			return []Area{}, err
		}
		result = append(result, area)
	}
}

//nolint: funlen
func main() {
	numbers, err := ReadLinesAsNumbers()
	if err != nil {
		log.Fatal(err.Error())
	}
	if len(numbers) < 2 { //nolint:gomnd
		log.Fatal("we were promised some numbers")
	}
	fmt.Println("Part 1")
	sum := numbers[0].Copy()
	sum = Reduce(sum)
	for _, addMe := range numbers[1:] {
		sum = Add(sum, addMe)
		sum = Reduce(sum)
	}
	fmt.Println(sum)
	fmt.Println(sum.Magnitude())

	fmt.Println("Part 2")
	maxMagnitude := 0
	for leftIdx, left := range numbers {
		for rightIdx, right := range numbers {
			if leftIdx == rightIdx {
				// We cannot add a number to itself here.
				continue
			}
			sum := Add(left, right)
			sum = Reduce(sum)
			magnitude := sum.Magnitude()
			if magnitude > maxMagnitude {
				maxMagnitude = magnitude
			}
			sum = Add(right, left)
			sum = Reduce(sum)
			magnitude = sum.Magnitude()
			if magnitude > maxMagnitude {
				maxMagnitude = magnitude
			}
		}
	}
	fmt.Println(maxMagnitude)
}

// ReadLinesAsNumbers reads all lines from stdin as replacement instructions or input.
func ReadLinesAsNumbers() ([]Number, error) {
	var result []Number
	for {
		line, err := readLine()
		if err == io.EOF {
			// Success case, no more input to read.
			return result, nil
		}
		if err != nil {
			return []Number{}, err
		}
		line = strings.TrimSpace(line)
		if len(line) == 0 {
			// Skip empty lines.
			continue
		}
		parsed, err := NumberFromString(line)
		if err != nil {
			return []Number{}, err
		}
		result = append(result, parsed)
	}
}

const (
	explodeLevel   = 4
	splitThreshold = 10
)

// Reduce reduces a snailfish number.
//nolint:funlen
func Reduce(num Number) Number {
	result := num.Copy()
	for reduced := true; reduced; {
		// Assume no reduction happened.
		reduced = false

		// Determine whether the number needs an explosion or a split.

		// Explosion-related.
		// Also remember pointers to the raw digits to be able to easily change the values later.
		rawDigits := []*int{}
		explodeIdx := -1
		var explodeMyChild Number
		var explodeLeftChild bool
		// Split-related.
		var splitMyChild Number
		var splitLeftChild bool
		splitIdx := -1

		// Declare to use in recursion.
		var changeCheck func(Number, Number, int, bool)
		// Close over the above variables so that we can remember which numbers to change for splits
		// or explosions.
		// This function actually determines a lot. It checks whether an explosion or a split is
		// needed.
		changeCheck = func(n Number, parent Number, level int, left bool) {
			//nolint:nestif
			if n.IsPair() {
				// A pair can only explode if it consists of actual numbers and nothing else.
				if !n.Left().IsPair() && !n.Right().IsPair() {
					// Only explode if we are very far nested in and if no previous pair needs to
					// explode.
					if level >= explodeLevel && explodeMyChild == nil {
						explodeMyChild = parent
						explodeLeftChild = left
						// Even though a number with this index hasn't been added yet, we
						// already know it.
						explodeIdx = len(rawDigits)
					}
				}
				changeCheck(n.Left(), n, level+1, true)
				changeCheck(n.Right(), n, level+1, false)
			} else {
				// Only split if we exceed the threshold and if no previous number needs splitting.
				if *n.Val() >= splitThreshold && splitMyChild == nil {
					splitMyChild = parent
					splitLeftChild = left
					// Even though a number with this index hasn't been added yet, we already know
					// it.
					splitIdx = len(rawDigits)
				}
				// Remember a pointer to our actual value. That way, explosions can easily be
				// handled.
				rawDigits = append(rawDigits, n.Val())
			}
		}

		changeCheck(result, nil, 0, true)

		// Process explision and splits. Explosions take precedence.

		if explodeIdx >= 0 {
			reduced = true
			// Explode!
			// Add numbers to neighbours. We remembered pointers to all actual numbers, so this is
			// easy.
			if explodeIdx > 0 {
				// Add the left digit if the pair to its left neighbour, in whichever pair it is.
				// Don't do that if there is no such neighbour.
				*rawDigits[explodeIdx-1] += *rawDigits[explodeIdx]
			}
			if explodeIdx+1 < len(rawDigits)-1 {
				// Add the right digit if the pair to its right neighbour, in whichever pair it is.
				// Don't do that if there is no such neighbour.
				*rawDigits[explodeIdx+2] += *rawDigits[explodeIdx+1]
			}
			// Replace pair by a literal zero. This is where I struggled with pointer receivers in
			// Go. But this works nicely since Go has a garbage collector. Otherwise, manually
			// free'ing memory would be a nightmare with this hacked implementation.
			if explodeLeftChild {
				explodeMyChild.SetLeft(&Digit{0})
			} else {
				explodeMyChild.SetRight(&Digit{0})
			}
			// Start back at the beginning.
			continue
		}

		if splitIdx >= 0 {
			reduced = true
			// Split!
			// Determine the values on the left and the right.
			largeVal := *rawDigits[splitIdx]
			// This is integer division, which is equivalent to rounding down.
			left := largeVal / 2 //nolint:gomnd
			// Take care of "rounding up". This way, we don't have to use floats to round up.
			right := left + largeVal%2 //nolint:gomnd

			newPair := Pair{left: &Digit{left}, right: &Digit{right}}
			// Replace number by a new pair.
			if splitLeftChild {
				splitMyChild.SetLeft(&newPair)
			} else {
				splitMyChild.SetRight(&newPair)
			}
			// Start back at the beginning.
			continue
		}
	}
	return result
}

const (
	numReqMatches = 12
	maxDist       = 1000.
	// tol           = 1e-7
)

func rotate(rot *mat.Dense, vecs []mat.Vector) []mat.Vector {
	result := make([]mat.Vector, 0, len(vecs))
	for _, vec := range vecs {
		resultVec := mat.NewVecDense(dims, nil)
		resultVec.MulVec(rot, vec)
		result = append(result, resultVec)
	}
	return result
}

func translate(trans mat.Vector, vecs []mat.Vector) []mat.Vector {
	result := make([]mat.Vector, 0, len(vecs))
	for _, vec := range vecs {
		resultVec := mat.NewVecDense(dims, nil)
		resultVec.AddVec(trans, vec)
		result = append(result, resultVec)
	}
	return result
}

func findMatchIndices(posRef, posCheck []mat.Vector) map[int]struct{} {
	matches := make(map[int]struct{}, len(posCheck))
	for _, ref := range posRef {
		for checkIdx, check := range posCheck {
			// Try actual equality first, we might need to switch to EqualApprox, which is something
			// like an all-close.
			if mat.Equal(ref, check) {
				matches[checkIdx] = struct{}{}
				break
			}
		}
	}
	return matches
}

func countMatches(posRef, posCheck, refSens, checkSens []mat.Vector) int {
	matches := 0
	for _, ref := range posRef {
		matched := false
		for _, check := range posCheck {
			// Try actual equality first, we might need to switch to EqualApprox, which is something
			// like an all-close.
			if mat.Equal(ref, check) {
				matched = true
				matches++
				break
			}
		}
		// // Following is a sanity check that is supposed to ensure that no point that is not
		// // matched is within 1000 of another sensor. Switching it on causes there to be no
		// // matches. The implementation is likely incorrect.
		// if !matched {
		// 	for _, sens := range refSens {
		// 		for _, check := range posCheck {
		// 			// Check whether any check pos is closer to any of the ref sensors than maxDist.
		// 			// If so, this cannot be a match.
		// 			dist := mat.NewVecDense(dims, nil)
		// 			dist.SubVec(check, sens)
		// 			//nolint:gomnd
		// 			if math.Abs(dist.AtVec(0)) <= maxDist && math.Abs(dist.AtVec(1)) <= maxDist &&
		// 				math.Abs(dist.AtVec(2)) <= maxDist {
		// 				// log.Println("excluded due to cube check")
		// 				return 0
		// 			}
		// 		}
		// 	}
		// 	for _, sens := range checkSens {
		// 		for _, ref := range posRef {
		// 			// Check whether any check pos is closer to any of the ref sensors than maxDist.
		// 			// If so, this cannot be a match.
		// 			dist := mat.NewVecDense(dims, nil)
		// 			dist.SubVec(ref, sens)
		// 			//nolint:gomnd
		// 			if math.Abs(dist.AtVec(0)) <= maxDist && math.Abs(dist.AtVec(1)) <= maxDist &&
		// 				math.Abs(dist.AtVec(2)) <= maxDist {
		// 				// log.Println("excluded due to cube check")
		// 				return 0
		// 			}
		// 		}
		// 	}
		// }
		_ = matched
		_ = maxDist
	}
	return matches
}

// Returns true if a match is found. Also returns the translation vector needed to translate
// one set of co-ordinates to the other to match.
func assessMatch(
	rot *mat.Dense, refPositions, checkPositions, refSens, checkSens []mat.Vector,
) (mat.Vector, bool) {
	rotated := rotate(rot, checkPositions)
	rotatedSens := rotate(rot, checkSens)
	for _, refPosRef := range refPositions {
		diff := mat.NewVecDense(dims, nil)

		for _, refPosCheck := range rotated {
			diff.SubVec(refPosRef, refPosCheck)

			checkPosTranslated := translate(diff, rotated)
			checkSensTranslated := translate(diff, rotatedSens)

			matches := countMatches(refPositions, checkPosTranslated, refSens, checkSensTranslated)
			if matches >= numReqMatches {
				return diff, true
			}
		}
	}
	return nil, false
}

func printMat(matrix *mat.Dense) {
	for row := 0; row < dims; row++ {
		fmt.Println(matrix.RowView(row))
	}
	fmt.Println()

}

func printVec(vec mat.Vector) {
	fmt.Println(vec)
	fmt.Println()

}

func printVecs(vecs []mat.Vector) {
	for _, vec := range vecs {
		fmt.Println(vec)
	}
	fmt.Println()

}

func mergeOneMatch(data, sensorPositions map[int][]mat.Vector, rots []*mat.Dense) bool {
	for refIdx, ref := range data {
		for checkIdx, check := range data {
			if checkIdx == refIdx {
				// Don't merge a sensor's data with its own data.
				continue
			}
			log.Printf("assessing %d and %d", refIdx, checkIdx)
			for _, rot := range rots {
				refSens := sensorPositions[refIdx]
				checkSens := sensorPositions[checkIdx]

				if diff, matching := assessMatch(rot, ref, check, refSens, checkSens); matching {
					// Merge start.
					log.Println("merging", checkIdx, "into", refIdx)

					adjusted := translate(diff, rotate(rot, check))
					adjSens := translate(diff, rotate(rot, checkSens))

					// Determine matching sensor data.
					matchingIdx := findMatchIndices(ref, adjusted)
					if len(matchingIdx) < numReqMatches {
						log.Fatalf("found only %d matches", len(matchingIdx))
					}

					// Keep all the data from the base list.
					// Only add those not yet present from the merge list.
					for mergeIdx, merge := range adjusted {
						if _, exists := matchingIdx[mergeIdx]; !exists {
							ref = append(ref, merge)
						}
					}

					// Remember the updated base data and remove the data that has been merged in.
					data[refIdx] = ref
					delete(data, checkIdx)

					// Remember the translated sensor positions merged in for cube sanity checks.
					refSens = append(refSens, adjSens...)

					// Remember the updated base sensor and remove the sensor data of the merge.
					sensorPositions[refIdx] = refSens
					delete(sensorPositions, checkIdx)

					return true
					// Merge end.
				}
			}
		}
	}
	return false
}

func maxSensorDist(sensorData map[int][]mat.Vector) float64 {
	result := 0.
	for _, sensors := range sensorData {
		if len(sensors) <= 1 {
			// Don't process sensor data sets that don't yet have enough data.
			continue
		}
		for _, sens := range sensors {
			for _, otherSens := range sensors {
				diff := mat.NewVecDense(dims, nil)
				diff.SubVec(sens, otherSens)
				norm := mat.Norm(diff, 1)
				if norm > result {
					result = norm
				}
			}
		}
	}
	return result
}

func main() {
	// Create all valid rotation matrices.
	rots := allRots()
	for _, rot := range rots {
		printMat(rot)
	}

	// Read data.
	sensorData, err := ReadLinesAsSensorData()
	if err != nil {
		log.Fatal(err.Error())
	}
	for _, data := range sensorData {
		printVecs(data)
	}
	sensorPositions := map[int][]mat.Vector{}
	for idx := range sensorData {
		sensorPositions[idx] = []mat.Vector{mat.NewVecDense(dims, []float64{0., 0., 0.})}
	}

	// Continuously merge sensor data until only one remains.
	for len(sensorData) != 1 {
		merged := mergeOneMatch(sensorData, sensorPositions, rots)
		if !merged {
			log.Fatal("did not find any match")
		}
		log.Printf("%d remaining", len(sensorData))
		log.Println("max sensor dist is", maxSensorDist(sensorPositions))
	}

	for _, dat := range sensorData {
		fmt.Println("There are", len(dat), "beacons in total.")
	}

	// This line stops Go complaining that this helper function was unused.
	_ = printVec
}

// ReadLinesAsSensorData reads line in as sensor data.
func ReadLinesAsSensorData() (map[int][]mat.Vector, error) {
	result := map[int][]mat.Vector{}
	var data []mat.Vector
	for {
		line, err := readLine()
		if err == io.EOF {
			// Success case, no more input to read.
			return result, nil
		}
		if err != nil {
			return map[int][]mat.Vector{}, err
		}
		line = strings.TrimSpace(line)
		//nolint:nestif
		if len(line) == 0 {
			result[len(result)] = data
		} else if line[0] == scannerStart && line[1] == scannerStart && line[2] == scannerStart {
			var scannerIdx int
			count, err := fmt.Sscanf(line, scannerFormat, &scannerIdx)
			if err != nil {
				return map[int][]mat.Vector{}, err
			}
			if scannerIdx != len(result) || count != 1 {
				err := fmt.Errorf("error parsing line %s", line)
				return map[int][]mat.Vector{}, err
			}
			data = []mat.Vector{}
		} else {
			var vecData [vectorDims]float64
			count, err := fmt.Sscanf(line, vectorFormat, &vecData[0], &vecData[1], &vecData[2])
			if err != nil {
				return map[int][]mat.Vector{}, err
			}
			if count != vectorDims {
				err := fmt.Errorf("error parsing line %s", line)
				return map[int][]mat.Vector{}, err
			}
			data = append(data, mat.NewVecDense(vectorDims, vecData[:]))
		}
	}
}

const (
	dims = 3
)

// Determine all possible rotation matrices. This means swap all axes and flip app axes.
// Filter out co-ordinate systems that we don't support.
func allRots() []*mat.Dense {
	result := []*mat.Dense{}

	indices := []mat.Vector{
		mat.NewVecDense(dims, []float64{0., 1., 2.}),
		mat.NewVecDense(dims, []float64{0., 2., 1.}),
		mat.NewVecDense(dims, []float64{1., 0., 2.}),
		mat.NewVecDense(dims, []float64{1., 2., 0.}),
		mat.NewVecDense(dims, []float64{2., 0., 1.}),
		mat.NewVecDense(dims, []float64{2., 1., 0.}),
	}

	signs := []mat.Vector{
		mat.NewVecDense(dims, []float64{1., 1., 1.}),
		mat.NewVecDense(dims, []float64{1., 1., -1.}),
		mat.NewVecDense(dims, []float64{1., -1., 1.}),
		mat.NewVecDense(dims, []float64{1., -1., -1.}),
		mat.NewVecDense(dims, []float64{-1., 1., 1.}),
		mat.NewVecDense(dims, []float64{-1., 1., -1.}),
		mat.NewVecDense(dims, []float64{-1., -1., 1.}),
		mat.NewVecDense(dims, []float64{-1., -1., -1.}),
	}

	for _, targetIdx := range indices {
		for _, sign := range signs {
			rotMatIdx := mat.VecDenseCopyOf(targetIdx)
			rotMatIdx.MulElemVec(rotMatIdx, sign)

			rotMat := mat.NewDense(dims, dims, []float64{0., 0., 0., 0., 0., 0., 0., 0., 0.})

			for orgDim := 0; orgDim < dims; orgDim++ {
				targetDim := targetIdx.AtVec(orgDim)
				sig := sign.AtVec(orgDim)
				rotMat.Set(int(orgDim), int(targetDim), sig)
			}
			// Ignore left-handed coordinate systems.
			if mat.Det(rotMat) > 0 {
				result = append(result, rotMat)
			}
		}
	}

	return result
}

const (
	numConvPart1     = 2
	numConvPart2     = 50
	startBorderPart1 = 4
	startBorderPart2 = 52
)

func main() {
	algo, grid, err := ReadLinesAsPixelGrid()
	if err != nil {
		log.Fatal(err.Error())
	}

	gridP1 := grid
	gridP2 := grid

	// Convert image twice for part 1. Take care of the background!
	for count := 0; count < numConvPart1; count++ {
		gridP1 = gridP1.Convert(algo)
	}

	// Convert image 50 times for part 2. Take care of the background!
	for count := 0; count < numConvPart2; count++ {
		gridP2 = gridP2.Convert(algo)
	}

	fmt.Println("Part 2, final image follows")
	fmt.Println(gridP2.Pretty(startBorderPart2 - numConvPart2))
	fmt.Println("Part 1, final image follows")
	fmt.Println(gridP1.Pretty(startBorderPart1 - numConvPart1))

	fmt.Println("Part 2, solution follows")
	fmt.Println(len(gridP2.data))
	fmt.Println("Part 1, solution follows")
	fmt.Println(len(gridP1.data))
}

// ReadLinesAsPixelGrid reads lines in as a pixel grid.
func ReadLinesAsPixelGrid() ([]bool, Grid, error) {
	result := Grid{background: false, data: map[Vec]bool{}}
	var algo []bool
	rowIdx := 0
	for {
		line, err := readLine()
		if err == io.EOF {
			if len(algo) != enhancementLength {
				err := fmt.Errorf("enhancement algorithm not of correct length")
				return []bool{}, Grid{}, err
			}
			// Success case, no more input to read.
			return algo, result, nil
		}
		if err != nil {
			return []bool{}, Grid{}, err
		}
		line = strings.TrimSpace(line)
		//nolint:nestif
		if len(line) == enhancementLength {
			algo = make([]bool, 0, len(line))
			for _, char := range line {
				algo = append(algo, char == full)
				if char != full && char != empty {
					err := fmt.Errorf("unknown character %c", char)
					return []bool{}, Grid{}, err
				}
			}
		} else if len(line) == 0 {
			continue
		} else {
			for colIdx, char := range line {
				pos := Vec{x: colIdx, y: rowIdx}
				result.Mark(pos, char == full)
				if char != full && char != empty {
					err := fmt.Errorf("unknown character %c", char)
					return []bool{}, Grid{}, err
				}
			}
			rowIdx++
		}
	}
}

// Vec is a 2D vector. Most of it has been taken from a previous solution.
type Vec struct {
	x, y int
}

const (
	allZeroesAsDecimal = 0
	allOnesAsDecimal   = 511
	buffer             = 9
)

var (
	unitX = Vec{x: 1}
	unitY = Vec{y: 1}
	// The order of these relevant disps is important for binary to decimal conversion!
	relevantDisps = []Vec{
		// y==-1
		unitX.Inv().Sub(unitY),
		unitY.Inv(),
		unitX.Sub(unitY),
		// y==0
		unitX.Inv(),
		Vec{},
		unitX,
		// y==1
		unitX.Inv().Add(unitY),
		unitY,
		unitX.Add(unitY),
	}
)

// Obtain an iterator over all relevant points. That is, all neighbours and the point itself.
func relevantPoints(point Vec) <-chan Vec {
	channel := make(chan Vec, buffer)
	go func() {
		for _, disp := range relevantDisps {
			displaced := point.Add(disp)
			channel <- displaced
		}
		close(channel)
	}()
	return channel
}

// Add adds one vector to another one.
func (v Vec) Add(delta Vec) Vec {
	result := Vec{
		x: v.x + delta.x,
		y: v.y + delta.y,
	}
	return result
}

// Mul multiplies each component of a vector with a number.
func (v Vec) Mul(factor int) Vec {
	result := Vec{
		x: v.x * factor,
		y: v.y * factor,
	}
	return result
}

// Inv inverts a vector.
func (v Vec) Inv() Vec {
	return v.Mul(-1)
}

// Sub subtracts a vector'v data from another one'v.
func (v Vec) Sub(delta Vec) Vec {
	return v.Add(delta.Inv())
}

// Grid is a lazily evaluated grid that supports marking points on it. Most of it has been taken
// from a previous solution.
type Grid struct {
	data       map[Vec]bool
	background bool
}

// Mark marks a point on the grid as true or false. Any markings equal to the background are
// ignored.
func (g *Grid) Mark(entry Vec, val bool) {
	// We don't have to handle non-existing values here since Go returns the zero value (false for
	// boolean values) for such entries. Accepting any boolean value here allows us to ignore the
	// background setting and always call Mark the same way.
	if val != g.background {
		g.data[entry] = val
	}
}

// Marked determines whether a point has been marked.
func (g *Grid) Marked(entry Vec) bool {
	if val, found := g.data[entry]; found {
		return val
	}
	return g.background
}

// Has determines whether a point is on the grid.
func (g *Grid) Has(entry Vec) bool {
	_, ok := g.data[entry]
	return ok
}

// RemoveAll removes all markings for a specific point.
func (g *Grid) RemoveAll(entry Vec) {
	delete(g.data, entry)
}

// Points returns an iterator over all points on the grid that deviate from the background.
func (g *Grid) Points() <-chan Vec {
	channel := make(chan Vec, buffer)
	go func() {
		for point := range g.data {
			if g.Marked(point) != g.background {
				channel <- point
			}
		}
		close(channel)
	}()
	return channel
}

// TopLeft returns the coordinates of the top left node.
func (g *Grid) TopLeft() (int, int) {
	foundX, foundY := false, false
	minX, minY := 0, 0
	for p := range g.Points() {
		if !foundX || p.x < minX {
			minX = p.x
			foundX = true
		}
		if !foundY || p.y < minY {
			minY = p.y
			foundY = true
		}
	}
	return minX, minY
}

// BottomRight returns the coordinates of the bottom right node.
func (g *Grid) BottomRight() (int, int) {
	foundX, foundY := false, false
	maxX, maxY := 0, 0
	for p := range g.Points() {
		if !foundX || p.x > maxX {
			maxX = p.x
			foundX = true
		}
		if !foundY || p.y > maxY {
			maxY = p.y
			foundY = true
		}
	}
	return maxX, maxY
}

// Pretty creates a pretty string representation of this grid.
func (g *Grid) Pretty(border int) string {
	result := ""
	empty := "."
	filled := "#"
	minX, minY := g.TopLeft()
	maxX, maxY := g.BottomRight()
	for y := minY - border; y <= maxY+border; y++ {
		for x := minX - border; x <= maxX+border; x++ {
			if g.Marked(Vec{x: x, y: y}) {
				result += filled
			} else {
				result += empty
			}
		}
		result += "\n"
	}
	return result
}

func newPointVal(g *Grid, point *Vec, algo *[]bool) bool {
	// Convert binary to decimal.
	index := 0
	for p := range relevantPoints(*point) {
		index *= 2
		if g.Marked(p) {
			index++
		}
	}
	if index > len(*algo) {
		log.Fatalf("algorithm not long enough for %d", index)
	}
	// Extract new value.
	newVal := (*algo)[index]
	return newVal
}

// Convert converts a grid to another one according to the algorithm. It also takes care of
// converting the background as needed.
func (g *Grid) Convert(algo []bool) Grid {
	// Determine background of new grid.
	var newBackground bool
	if g.background {
		newBackground = algo[allOnesAsDecimal]
	} else {
		newBackground = algo[allZeroesAsDecimal]
	}
	grid := Grid{background: newBackground, data: make(map[Vec]bool)}

	// Fill all points. We need to check each neighbour of each point for whether it needs to be
	// marked.
	// This algorithm will mark some points multiple times. But that's OK, we'll just be wasting
	// time but not causing any errors that way.
	for p := range g.Points() {
		for markMe := range relevantPoints(p) {
			newVal := newPointVal(g, &markMe, &algo)
			grid.Mark(markMe, newVal)
		}
	}

	return grid
}

const (
	boardSize = 10
	dieSize   = 100
	numRolls  = 3
	winScore  = 1000
)

// Player is a player of the die game.
type Player struct {
	ID        int
	Pos       int
	Score     int
	BoardSize int
}

// Update updates a player with a roll.
func (p *Player) Update(roll int) {
	// Positions will be in [1,10]
	p.Pos = (p.Pos-1+roll)%p.BoardSize + 1
	p.Score += p.Pos
}

// String provides a string representation.
func (p *Player) String() string {
	return fmt.Sprintf("{id: %d, pos: %d, s: %d}", p.ID, p.Pos, p.Score)
}

// DetDie is a deterministic die.
type DetDie struct {
	LastRoll int
	DieSize  int
	NumRools int
}

// Roll rolls the dice the required number of times.
func (d *DetDie) Roll() int {
	result := 0
	for rollIdx := 0; rollIdx < d.NumRools; rollIdx++ {
		d.LastRoll++
		result += d.LastRoll
		d.LastRoll = d.LastRoll % d.DieSize
	}
	return result
}

func maxScore(players []Player) int {
	result := 0
	found := false
	for _, player := range players {
		if !found || player.Score > result {
			found = true
			result = player.Score
		}
	}
	return result
}

func main() {
	players, err := ReadLinesAsPlayers()
	if err != nil {
		log.Fatal(err.Error())
	}
	fmt.Println(players)

	pos1, pos2 := players[0].Pos, players[1].Pos

	die := DetDie{LastRoll: 0, DieSize: dieSize, NumRools: numRolls}

	rollCount := 0
	for playerIdx := 0; maxScore(players) < winScore; playerIdx = (playerIdx + 1) % len(players) {
		roll := die.Roll()
		rollCount += numRolls
		players[playerIdx].Update(roll)
	}

	fmt.Printf("We have a winner! Results after %d rolls are:\n", rollCount)
	for _, player := range players {
		fmt.Println(player.String(), "Relevant value is:", rollCount*player.Score)
	}

	buildMetaverse(pos1, pos2)
}

// ReadLinesAsPlayers reads lines in as players.
func ReadLinesAsPlayers() ([]Player, error) {
	result := []Player{}
	for {
		line, err := readLine()
		if err == io.EOF {
			// Success case, no more input to read.
			return result, nil
		}
		if err != nil {
			return []Player{}, err
		}
		line = strings.TrimSpace(line)
		//nolint:nestif
		var player Player
		count, err := fmt.Sscanf(line, inputFormat, &player.ID, &player.Pos)
		player.BoardSize = boardSize
		if err != nil {
			return []Player{}, err
		}
		if count != inputNums {
			return []Player{}, fmt.Errorf("cannot parse %s as player", line)
		}
		result = append(result, player)
	}
}

// Game describes the state of one two-player game.
type Game struct {
	Pos1, Pos2     int
	Score1, Score2 int
}

const (
	diracSize     = 3
	winScoreDirac = 21
)

// Metaverse tracks how many universes there are for each game state.
type Metaverse map[Game]int

// I'm too lazy to write out all possible rolls and counts when rolling a 3-sided die 3 times in a
// row. Hence, I compute that once.
func dieRolls(diracSize, numRolls int) map[int]int {
	state := map[int]int{1: 1, 2: 1, 3: 1}
	for rollIdx := 1; rollIdx < numRolls; rollIdx++ {
		newState := map[int]int{}
		for dieRoll := 1; dieRoll <= diracSize; dieRoll++ {
			for val, count := range state {
				newState[val+dieRoll] += count
			}
		}
		state = newState
	}
	return state
}

// We always assume it's player 1's turn. But we swap players so that each has their turn after the
// other.
func updateMetaverse(meta Metaverse, dieRolls map[int]int, boardSize int) Metaverse {
	newMeta := Metaverse{}
	for game, gameCount := range meta {
		// Deconstruct the game data.
		pos1 := game.Pos1
		pos2 := game.Pos2
		score1 := game.Score1
		score2 := game.Score2
		// Update the new metaverse for each possible outcome.
		for roll, rollCount := range dieRolls {
			newPos := (pos1+roll-1)%boardSize + 1
			newGame := Game{
				Pos1:   pos2,
				Pos2:   newPos,
				Score1: score2,
				Score2: score1 + newPos,
			}
			newMeta[newGame] += gameCount * rollCount
		}
	}
	return newMeta
}

func countAndRemoveWins(meta *Metaverse) int {
	wins := 0
	for game, count := range *meta {
		// The score that has last been updated will always be score 2 due to the fact that we swap
		// players all the time.
		if game.Score2 >= winScoreDirac {
			wins += count
			// Deleting from a map while iterating over it is not a problem in Go.
			delete(*meta, game)
		}
	}
	return wins
}

func buildMetaverse(pos1, pos2 int) {
	rollUpdate := dieRolls(diracSize, numRolls)
	fmt.Println(rollUpdate)
	// Set up the starting metaverse. During each round, we will update the metaverse.
	meta := Metaverse{}
	startGame := Game{Pos1: pos1, Pos2: pos2, Score1: 0, Score2: 0}
	meta[startGame] = 1
	// Count how many victories there were for each player. Go's zero value for integers is zero, so
	// we don't need to initialise the map.
	numPlayers := 2
	wins := map[int]int{}
	// Update the metaverse.
	for playerIdx := 0; len(meta) > 0; playerIdx = (playerIdx + 1) % numPlayers {
		meta = updateMetaverse(meta, rollUpdate, boardSize)
		wins[playerIdx] += countAndRemoveWins(&meta)
	}
	fmt.Println("Wins player 1:", wins[0])
	fmt.Println("Wins player 2:", wins[1])
}

const (
	clampVal   = 50
	maxNumCubs = 26
)

func max(num1, num2 int) int {
	if num1 > num2 {
		return num1
	}
	return num2
}

func min(num1, num2 int) int {
	if num1 < num2 {
		return num1
	}
	return num2
}

// One cuboid eats a chunk out of another cuboid, splitting the first one into up to 26 new ones.
//nolint:funlen,gomnd,dupl
func eatChunk(onCub, offCub Cuboid) ([]Cuboid, bool) {
	result := make([]Cuboid, 0, maxNumCubs)
	// At first, determine a cuboid that is fully within both of the other cuboids.
	inside := Cuboid{
		start: Vec{
			x: max(onCub.start.x, offCub.start.x),
			y: max(onCub.start.y, offCub.start.y),
			z: max(onCub.start.z, offCub.start.z),
		},
		end: Vec{
			x: min(onCub.end.x, offCub.end.x),
			y: min(onCub.end.y, offCub.end.y),
			z: min(onCub.end.z, offCub.end.z),
		},
	}
	if inside.Size() == 0 {
		// In this case, one cuboid is completely outside the other one.
		return []Cuboid{}, false
	}
	if inside == onCub {
		// In this case, one cuboid is completely outside the other one.
		return []Cuboid{}, true
	}
	for _, dim := range [3]int{0, 1, 2} {
		// Negative direction.
		{
			newCub := Cuboid{start: inside.start, end: inside.end}
			newCub.start.Set(dim, onCub.start.Get(dim))
			newCub.end.Set(dim, inside.start.Get(dim))
			if newCub.Size() > 0 {
				result = append(result, newCub)
			}
		}
		// Positive direction.
		{
			newCub := Cuboid{start: inside.start, end: inside.end}
			newCub.start.Set(dim, inside.end.Get(dim))
			newCub.end.Set(dim, onCub.end.Get(dim))
			if newCub.Size() > 0 {
				result = append(result, newCub)
			}
		}
	}
	// count == 6
	for _, dim := range [3]int{0, 1, 2} {
		nextDim := (dim + 1) % 3
		// Negative dim direction
		{
			// Negative nextDim direction
			{
				newCub := Cuboid{start: inside.start, end: inside.end}
				newCub.start.Set(dim, onCub.start.Get(dim))
				newCub.end.Set(dim, inside.start.Get(dim))
				newCub.start.Set(nextDim, onCub.start.Get(nextDim))
				newCub.end.Set(nextDim, inside.start.Get(nextDim))
				if newCub.Size() > 0 {
					result = append(result, newCub)
				}
			}
			// Positive nextDim direction
			{
				newCub := Cuboid{start: inside.start, end: inside.end}
				newCub.start.Set(dim, onCub.start.Get(dim))
				newCub.end.Set(dim, inside.start.Get(dim))
				newCub.start.Set(nextDim, inside.end.Get(nextDim))
				newCub.end.Set(nextDim, onCub.end.Get(nextDim))
				if newCub.Size() > 0 {
					result = append(result, newCub)
				}
			}
		}
		// Positive dim direction
		{
			// Negative nextDim direction
			{
				newCub := Cuboid{start: inside.start, end: inside.end}
				newCub.start.Set(dim, inside.end.Get(dim))
				newCub.end.Set(dim, onCub.end.Get(dim))
				newCub.start.Set(nextDim, onCub.start.Get(nextDim))
				newCub.end.Set(nextDim, inside.start.Get(nextDim))
				if newCub.Size() > 0 {
					result = append(result, newCub)
				}
			}
			// Positive nextDim direction
			{
				newCub := Cuboid{start: inside.start, end: inside.end}
				newCub.start.Set(dim, inside.end.Get(dim))
				newCub.end.Set(dim, onCub.end.Get(dim))
				newCub.start.Set(nextDim, inside.end.Get(nextDim))
				newCub.end.Set(nextDim, onCub.end.Get(nextDim))
				if newCub.Size() > 0 {
					result = append(result, newCub)
				}
			}
		}
	}
	// Eight corners.
	// x>0 y>0 z>0
	{
		newCub := Cuboid{start: inside.end, end: onCub.end}
		if newCub.Size() > 0 {
			result = append(result, newCub)
		}
	}
	// x>0 y>0 z<0
	{
		newCub := Cuboid{start: inside.end, end: onCub.end}
		newCub.start.z = onCub.start.z
		newCub.end.z = inside.start.z
		if newCub.Size() > 0 {
			result = append(result, newCub)
		}
	}
	// x>0 y<0 z>0
	{
		newCub := Cuboid{start: inside.end, end: onCub.end}
		newCub.start.y = onCub.start.y
		newCub.end.y = inside.start.y
		if newCub.Size() > 0 {
			result = append(result, newCub)
		}
	}
	// x>0 y<0 z<0
	{
		newCub := Cuboid{start: inside.end, end: onCub.end}
		newCub.start.y = onCub.start.y
		newCub.end.y = inside.start.y
		newCub.start.z = onCub.start.z
		newCub.end.z = inside.start.z
		if newCub.Size() > 0 {
			result = append(result, newCub)
		}
	}
	// x<0 y<0 z<0
	{
		newCub := Cuboid{start: onCub.start, end: inside.start}
		if newCub.Size() > 0 {
			result = append(result, newCub)
		}
	}
	// x<0 y<0 z>0
	{
		newCub := Cuboid{start: onCub.start, end: inside.start}
		newCub.start.z = inside.end.z
		newCub.end.z = onCub.end.z
		if newCub.Size() > 0 {
			result = append(result, newCub)
		}
	}
	// x<0 y>0 z<0
	{
		newCub := Cuboid{start: onCub.start, end: inside.start}
		newCub.start.y = inside.end.y
		newCub.end.y = onCub.end.y
		if newCub.Size() > 0 {
			result = append(result, newCub)
		}
	}
	// x<0 y>0 z>0
	{
		newCub := Cuboid{start: onCub.start, end: inside.start}
		newCub.start.y = inside.end.y
		newCub.end.y = onCub.end.y
		newCub.start.z = inside.end.z
		newCub.end.z = onCub.end.z
		if newCub.Size() > 0 {
			result = append(result, newCub)
		}
	}
	if len(result) == 0 && inside.Size() > 0 {
		log.Fatal("something went wrong")
	}
	return result, true
}

func totalSize(cubs []Cuboid) int {
	sum := 0
	for _, cub := range cubs {
		sum += cub.Size()
	}
	return sum
}

//nolint:funlen
func main() {
	cubs, switches, err := ReadLinesAsCuboids()
	if err != nil {
		log.Fatal(err.Error())
	}
	if len(cubs) != len(switches) {
		log.Fatal("need as many switches as cuboids")
	}

	fmt.Println("Part 1")

	grid := Grid{data: map[Vec]bool{}, clamp: clampVal, background: false}

	for idx, cub := range cubs {
		swit := switches[idx]
		grid.MarkCuboid(cub, swit)
	}
	fmt.Println("Number of cubes marked:", len(grid.data))

	fmt.Println()
	fmt.Println("Part 2")

	currentCubs := []Cuboid{cubs[0]}
	if !switches[0] {
		log.Fatal("expect first one to switch something on")
	}

	for idx, cub := range cubs[1:] {
		swit := switches[idx+1]
		// Switch something on: Let the new chunk eat something out of all existing chunks.
		// Then, add the new chunk whole.
		// Switch something off: Let the new chunk eat something out of all existing chunks.
		// Only add those reduces chunks but don't add the new chunk.
		newCubs := []Cuboid{}
		for _, currCub := range currentCubs {
			chunks, overlap := eatChunk(currCub, cub)
			if len(chunks) > 0 {
				// There was definitely some overlap.
				newCubs = append(newCubs, chunks...)
			} else if !overlap {
				// No overlap, keep the old cub.
				newCubs = append(newCubs, currCub)
			} /* else {
				// Otherwise, there was full overlap. Don't add anything back. The current cub will
				// be fully contained within the new cub. If this is not an addition but a removal,
				// then the odl cub will be removed entirely.
			}*/
		}
		if swit {
			newCubs = append(newCubs, cub)
		}
		currentCubs = newCubs
	}
	fmt.Println("Number of cubes marked:", totalSize(currentCubs))
}

// ReadLinesAsCuboids reads lines in as cuboids.
func ReadLinesAsCuboids() ([]Cuboid, []bool, error) {
	result := []Cuboid{}
	switches := []bool{}
	for {
		line, err := readLine()
		if err == io.EOF {
			// Success case, no more input to read.
			return result, switches, nil
		}
		if err != nil {
			return []Cuboid{}, []bool{}, err
		}
		line = strings.TrimSpace(line)
		//nolint:nestif
		var onOff string
		var x1, x2, y1, y2, z1, z2 int
		count, err := fmt.Sscanf(line, cuboidFormat, &onOff, &x1, &x2, &y1, &y2, &z1, &z2)
		if err != nil {
			return []Cuboid{}, []bool{}, err
		}
		if count != parsedVals {
			return []Cuboid{}, []bool{}, fmt.Errorf("parsed wrong number of values")
		}
		if onOff != onStr && onOff != offStr {
			return []Cuboid{}, []bool{}, fmt.Errorf("icorrect on-off string")
		}
		cub := NewCuboid(x1, x2+1, y1, y2+1, z1, z2+1)
		result = append(result, cub)
		switches = append(switches, onOff == onStr)
	}
}

const (
	buffer = 100
)

// Vec is a £D vector. Most of it has been taken from a previous solution.
type Vec struct {
	x, y, z int
}

// Add adds one vector to another one.
func (v Vec) Add(delta Vec) Vec {
	result := Vec{
		x: v.x + delta.x,
		y: v.y + delta.y,
		z: v.z + delta.z,
	}
	return result
}

// Get gets the co-ordinate based on the index.
func (v Vec) Get(idx int) int {
	if idx == 0 {
		return v.x
	}
	if idx == 1 {
		return v.y
	}
	if idx == 2 { //nolint:gomnd
		return v.z
	}
	panic("incorrect co-ordinate")
}

// Set sets the co-ordinate based on the index.
func (v *Vec) Set(idx, val int) {
	if idx == 0 {
		v.x = val
		return
	}
	if idx == 1 {
		v.y = val
		return
	}
	if idx == 2 { //nolint:gomnd
		v.z = val
		return
	}
	panic("incorrect co-ordinate")
}

// Mul multiplies each component of a vector with a number.
func (v Vec) Mul(factor int) Vec {
	result := Vec{
		x: v.x * factor,
		y: v.y * factor,
		z: v.z * factor,
	}
	return result
}

// Inv inverts a vector.
func (v Vec) Inv() Vec {
	return v.Mul(-1)
}

// Sub subtracts a vector'v data from another one'v.
func (v Vec) Sub(delta Vec) Vec {
	return v.Add(delta.Inv())
}

func abs(val int) int {
	if val < 0 {
		return -val
	}
	return val
}

// Size gives the size of space spanned by a vector.
func (v Vec) Size() int {
	return abs(v.x * v.y * v.z)
}

// Cuboid is a cubouid in space.
type Cuboid struct {
	start, end Vec
}

// Size gives the size of space spanned by a cuboid.
func (c Cuboid) Size() int {
	diff := c.end.Sub(c.start)
	if diff.x <= 0 || diff.y <= 0 || diff.z <= 0 {
		// In this case, this cuboid does not describe a valid one.
		return 0
	}
	return diff.Size()
}

// Overlaps determines whether two overlap.
func (c Cuboid) Overlaps(other Cuboid) bool {
	inside := Cuboid{
		start: Vec{
			x: max(c.start.x, other.start.x),
			y: max(c.start.y, other.start.y),
			z: max(c.start.z, other.start.z),
		},
		end: Vec{
			x: min(c.end.x, other.end.x),
			y: min(c.end.y, other.end.y),
			z: min(c.end.z, other.end.z),
		},
	}
	return inside.Size() != 0
}

// String provides a string rep.
func (c Cuboid) String() string {
	return fmt.Sprintf(
		"x=%d..%d,y=%d..%d,z=%d..%d",
		c.start.x, c.end.x, c.start.y, c.end.y, c.start.z, c.end.z,
	)
}

// NewCuboid gets a new cuboid, ensuring that the co-ordinates are ordered correctly.
func NewCuboid(x1, x2, y1, y2, z1, z2 int) Cuboid {
	if x2 < x1 {
		x1, x2 = x2, x1
	}
	if y2 < y1 {
		y1, y2 = y2, y1
	}
	if z2 < z1 {
		z1, z2 = z2, z1
	}
	cub := Cuboid{
		start: Vec{
			x: x1,
			y: y1,
			z: z1,
		},
		end: Vec{
			x: x2,
			y: y2,
			z: z2,
		},
	}
	return cub
}

// Contains determines whether a vector lies within a cuboid.
func (c *Cuboid) Contains(vec Vec) bool {
	return vec.x-c.start.x < c.end.x && vec.y-c.start.y < c.end.y && vec.z-c.start.z < c.end.z
}

// Grid is a lazily evaluated grid that supports marking points on it. Most of it has been taken
// from a previous solution.
type Grid struct {
	data       map[Vec]bool
	background bool
	clamp      int
}

// Mark marks a point on the grid as true or false. Any markings equal to the background are
// ignored.
func (g *Grid) Mark(entry Vec, val bool) {
	// We don't have to handle non-existing values here since Go returns the zero value (false for
	// boolean values) for such entries. Accepting any boolean value here allows us to ignore the
	// background setting and always call Mark the same way.
	if val != g.background {
		g.data[entry] = val
	} else {
		delete(g.data, entry)
	}
}

//nolint:funlen
func clamp(cub Cuboid, startVal, endVal int) (Cuboid, bool) {
	x1 := cub.start.x
	y1 := cub.start.y
	z1 := cub.start.z

	if x1 < startVal {
		x1 = startVal
	} else if x1 > endVal {
		// In this case, the entire cuboid is outside the area of validity.
		return Cuboid{}, false
	}

	if y1 < startVal {
		y1 = startVal
	} else if y1 > endVal {
		// In this case, the entire cuboid is outside the area of validity.
		return Cuboid{}, false
	}

	if z1 < startVal {
		z1 = startVal
	} else if z1 > endVal {
		// In this case, the entire cuboid is outside the area of validity.
		return Cuboid{}, false
	}

	x2 := cub.end.x - 1
	y2 := cub.end.y - 1
	z2 := cub.end.z - 1

	if x2 > endVal {
		x2 = endVal
	} else if x2 < startVal {
		// In this case, the entire cuboid is outside the area of validity.
		return Cuboid{}, false
	}

	if y2 > endVal {
		y2 = endVal
	} else if y2 < startVal {
		// In this case, the entire cuboid is outside the area of validity.
		return Cuboid{}, false
	}

	if z2 > endVal {
		z2 = endVal
	} else if z2 < startVal {
		// In this case, the entire cuboid is outside the area of validity.
		return Cuboid{}, false
	}

	result := Cuboid{
		start: Vec{
			x: x1,
			y: y1,
			z: z1,
		},
		end: Vec{
			x: x2 + 1,
			y: y2 + 1,
			z: z2 + 1,
		},
	}
	return result, true
}

// MarkCuboid marks a point on the grid as true or false within a cuboid.
func (g *Grid) MarkCuboid(area Cuboid, val bool) {
	// Permit disabling the clamping by providing a value <=0.
	if g.clamp > 0 {
		var valid bool
		area, valid = clamp(area, -g.clamp, g.clamp)
		if !valid {
			// The cuboid is completely outside the area of validity. Don't to anything.
			return
		}
	}
	// If the to-be-marked value is equal to the background, we can get away with not iterating over
	// the entirety of the cuboid. This is only then more efficient, if the cuboid contains more
	// points that the grid. Otherwise, we have to iterate over the entire cuboid, but clamped to
	// the supported area.
	if val == g.background && len(g.data) < area.Size() {
		for vec := range g.data {
			if area.Contains(vec) {
				g.RemoveAll(vec)
			}
		}
	} else {
		// Iterate over the entire cuboid and mark each point with the given value.
		for x := area.start.x; x < area.end.x; x++ {
			for y := area.start.y; y < area.end.y; y++ {
				for z := area.start.z; z < area.end.z; z++ {
					vec := Vec{x: x, y: y, z: z}
					g.Mark(vec, val)
				}
			}
		}
	}

}

// Marked determines whether a point has been marked.
func (g *Grid) Marked(entry Vec) bool {
	if val, found := g.data[entry]; found {
		return val
	}
	return g.background
}

// Has determines whether a point is on the grid.
func (g *Grid) Has(entry Vec) bool {
	_, ok := g.data[entry]
	return ok
}

// RemoveAll removes all markings for a specific point.
func (g *Grid) RemoveAll(entry Vec) {
	delete(g.data, entry)
}

// Points returns an iterator over all points on the grid that deviate from the background.
func (g *Grid) Points() <-chan Vec {
	channel := make(chan Vec, buffer)
	go func() {
		for point := range g.data {
			if g.Marked(point) != g.background {
				channel <- point
			}
		}
		close(channel)
	}()
	return channel
}

// String gives you a string.
func (g Grid) String() string {
	points := make([]Vec, 0, len(g.data))
	for p := range g.data {
		points = append(points, p)
	}

	lessFn := func(i, j int) bool {
		if points[i].x < points[j].x {
			return true
		}
		if points[i].y < points[j].y {
			return true
		}
		if points[i].z < points[j].z {
			return true
		}
		return false
	}

	sort.Slice(points, lessFn)
	str := ""
	for _, p := range points {
		str += fmt.Sprintf("%v\n", p)
	}
	return str
}

const (
	numGames = 1000000
)

// This solution really isn't that efficient, but it can find the solution for each example in under
// 10min and for each actual puzzle in way under an hour. That's fine by me.

//nolint:nestif,funlen
func main() {
	// Part 1 stuff has been augmented to fit into the part 2 board by adding pieces that will never
	// leave their rooms to the very bottom of their destination rooms.
	gameInput, err := ReadLinesAsGame()
	if err != nil {
		log.Fatal(err.Error())
	}
	g := newGame(gameInput)
	// Initialise. Allocate much since we don't know how deep we need to iterate. This uses about
	// 1.5GB of RAM.
	stack := make(Stack, 0, numGames)
	fmt.Println(g.pretty())

	cheapest := 0
	found := false
	popped := false

	var moves []move

	trackedCost := 0
	path := 0

	count := -1

	for done := false; !done; {
		count++

		if !popped {
			moves = g.moves()
		}
		// fmt.Println(moves)
		if path < len(moves) {
			// There are still moves available. Save the game state.
			move := moves[path]
			path++
			stack.Push(g, trackedCost, path, moves)
			path = 0
			trackedCost += move.cost
			g = g.update(move)
			popped = false
		} else {
			// There are no more moves available. Check whether this is final and pop the last
			// element and continue from there.
			if g.isFinal() {
				if !found || trackedCost < cheapest {
					found = true
					cheapest = trackedCost
					// Print out the entire solution.
					fmt.Println(cheapest, "==============================")
					for _, gam := range stack {
						fmt.Println(gam.game.pretty())
						fmt.Println(gam.cost)
						fmt.Println(gam.moves[gam.path-1])
					}
					fmt.Println(g.pretty())
					fmt.Println("New cheapest path shown above found, it has a cost of ", cheapest)
				}
			}
			if len(stack) == 0 {
				// We have reached the end. No more moves and the stack is empty.
				break
			}
			g, trackedCost, path, moves = stack.Pop()
			popped = true
		}
	}
	fmt.Println("Cehapest track is the last one shown with cost", cheapest)
}

// An example game looks like this:
// #############
// #...........#
// ###B#C#B#D###
//   #A#D#C#A#
//   #########

const (
	frontWallFormat = "#############"
	hallFormat      = "#...........#"
	entryFormat     = "###%c#%c#%c#%c###"
	roomFormat      = "#%c#%c#%c#%c#"
	backWallFormat  = "#########"
	numHalls        = 4
	numPods         = 4
	firstInputLine  = 2
)

var hallVals = [numHalls]rune{a, b, c, d}

// ReadLinesAsGame reads lines as a game for the amphipods.
//nolint:funlen
func ReadLinesAsGame() ([16]rune, error) {
	result := [16]rune{}
	// Initialise with the assumption all rooms are correctly filled.
	for hallIdx, hallVal := range hallVals {
		for podIdx := 0; podIdx < numPods; podIdx++ {
			result[hallIdx*numPods+podIdx] = hallVal
		}
	}
	for lineNr := 0; ; lineNr++ {
		line, err := readLine()
		if err == io.EOF {
			// Success case, no more input to read.
			return result, nil
		}
		if err != nil {
			return [16]rune{}, err
		}
		line = strings.TrimSpace(line)
		//nolint:gomnd
		switch lineNr {
		case 0:
			if line != frontWallFormat {
				err := fmt.Errorf("incorrect line %d", lineNr)
				return [16]rune{}, err
			}
		case 1:
			if line != hallFormat {
				err := fmt.Errorf("incorrect line %d", lineNr)
				return [16]rune{}, err
			}
		case firstInputLine:
			count, err := fmt.Sscanf(
				line, entryFormat,
				&result[0], &result[4], &result[8], &result[12],
			)
			if count != numHalls {
				err := fmt.Errorf("incorrect line %d", lineNr)
				return [16]rune{}, err
			}
			if err != nil {
				return [16]rune{}, err
			}
		}
		//nolint:gomnd
		if lineNr > firstInputLine && line != backWallFormat {
			// If we have reached the back wall, this is not a problem.
			memberIdx := lineNr - firstInputLine
			count, err := fmt.Sscanf(
				line, roomFormat,
				&result[memberIdx+0],
				&result[memberIdx+4],
				&result[memberIdx+8],
				&result[memberIdx+12],
			)
			if count != numHalls {
				err := fmt.Errorf("incorrect line %d", lineNr)
				return [16]rune{}, err
			}
			if err != nil {
				return [16]rune{}, err
			}
		}
	}
}

// Go doesn't have enums, sadly. Use constants with name prefixes instead.
const (
	a            = 'A'
	b            = 'B'
	c            = 'C'
	d            = 'D'
	costA        = 1
	costB        = 10
	costC        = 100
	costD        = 1000
	kindA        = 0
	kindB        = 1
	kindC        = 2
	kindD        = 3
	kindFree     = 4
	firstHallIdx = -1
	lastHallIdx  = 11
	firstRoomIdx = 11
	kindToRoom   = 4
	// Assume there are at least 16 possible moves per situation. This number influences performance
	// a bit.
	buffer = 16
)

// I'll try to keep this structure as copyable as possible. That way, I can simply put it on a stack
// to remember the old state, instead of reverting to an old state. Hence, I need to use
// fixed-length arrays here instead of variable-length slices.
type game struct {
	pods   [16]pod
	spaces [27]space
}

func getCharForPos(pods [16]pod, pos int) rune {
	for _, p := range pods {
		if p.pos == pos {
			switch p.cost {
			case costA:
				return a
			case costB:
				return b
			case costC:
				return c
			case costD:
				return d
			default:
				log.Fatalf("internal error, %v", p)
			}
		}
	}
	return '.'
}

func (g game) pretty() string {
	str := "#############\n"
	str += "#"
	for pos := 0; pos < 11; pos++ {
		str += string(getCharForPos(g.pods, pos))
	}
	str += "#\n"
	roomChars := [16]rune{}
	for pos := 11; pos < 27; pos++ {
		char := getCharForPos(g.pods, pos)
		roomChars[pos-firstRoomIdx] = char
	}
	str += fmt.Sprintf(
		"###%c#%c#%c#%c###\n",
		roomChars[0], roomChars[4], roomChars[8], roomChars[12],
	)
	str += fmt.Sprintf(
		"  #%c#%c#%c#%c#\n",
		roomChars[1], roomChars[5], roomChars[9], roomChars[13],
	)
	str += fmt.Sprintf(
		"  #%c#%c#%c#%c#\n",
		roomChars[2], roomChars[6], roomChars[10], roomChars[14],
	)
	str += fmt.Sprintf(
		"  #%c#%c#%c#%c#\n",
		roomChars[3], roomChars[7], roomChars[11], roomChars[15],
	)

	str += "  #########\n"
	return str
}

//nolint:funlen
func newGame(inPods [16]rune) game {

	// Build the game board first.

	// The game board consists of all rooms and the hall, 27 spaces in total.
	spaces := [27]space{}

	// These are the spaces we cannot move to in the hall, but they are still in the hall. We use
	// them to identify which positions are to the top left or right of a room.
	aboveSpaces := []int{2, 4, 6, 8}

	// Determine which spaces are rooms and which are the spaces directly above them. We use this
	// for easy distance computation later.
	for roomIdx, roomStart := range []int{11, 15, 19, 23} {
		aboveRoom := aboveSpaces[roomIdx]
		for _, count := range []int{0, 1, 2, 3} {
			spaceIdx := roomStart + count
			roomSpace := &spaces[spaceIdx]
			roomSpace.above = aboveRoom
			roomSpace.room = true
		}
	}

	// Build the pods based on user input.
	pods := [16]pod{}
	costs := map[rune]int{a: costA, b: costB, c: costC, d: costD}
	kinds := map[rune]int{a: kindA, b: kindB, c: kindC, d: kindD}
	podIdx := 0
	for _, roomStart := range []int{11, 15, 19, 23} {
		for _, count := range []int{0, 1, 2, 3} {
			spaceIdx := roomStart + count
			pods[podIdx].pos = spaceIdx
			pods[podIdx].cost = costs[inPods[podIdx]]
			pods[podIdx].kind = kinds[inPods[podIdx]]
			podIdx++
		}
	}

	return game{
		spaces: spaces,
		pods:   pods,
	}
}

type pod struct {
	pos  int
	cost int
	kind int
}

type space struct {
	above int
	room  bool
}

type move struct {
	start, end, cost int
}

func (m move) String() string {
	return fmt.Sprintf("[s: %d, e: %d, c: %d]", m.start, m.end, m.cost)
}

func abs(i int) int {
	if i < 0 {
		return -i
	}
	return i
}

// Determine possible moves. This is the crux of the entire thing.
//nolint:nestif,funlen
func (g game) moves() []move {
	moves := make([]move, 0, buffer)

	occupied := [27]int{}
	for idx := range occupied {
		occupied[idx] = kindFree
	}
	for _, p := range g.pods {
		occupied[p.pos] = p.kind
	}
PODLOOP:
	for _, p := range g.pods {
		mySpace := g.spaces[p.pos]
		if mySpace.room {
			// If we are in a room, we can only move to the hall, but not in some cases.
			diffToRoomStart := p.pos - firstRoomIdx
			//nolint:gomnd
			if diffToRoomStart/kindToRoom == p.kind {
				// If we already are in our room, we don't want to move anymore, but only if the
				// other ones in our room are also of our kind.
				// If we are at the bottom, we are good to go.
				if diffToRoomStart%4 == 3 {
					continue PODLOOP
				}
				// If we are somewhere at the top, we still have to move if the ones below us are of
				// a different kind. But if the ones below us is of the same kind, we don't want to
				// move anymore.
				if diffToRoomStart%4 == 2 {
					if occupied[p.pos+1] == p.kind {
						continue PODLOOP
					}
				}
				if diffToRoomStart%4 == 1 {
					if occupied[p.pos+1] == p.kind && occupied[p.pos+2] == p.kind {
						continue PODLOOP
					}
				}
				if diffToRoomStart%4 == 0 {
					if occupied[p.pos+1] == p.kind && occupied[p.pos+2] == p.kind && occupied[p.pos+3] == p.kind {
						continue PODLOOP
					}
				}
			}
			if diffToRoomStart%kindToRoom > 0 {
				// These are the bottom spaces of a room. If there is someone above us, we cannot
				// move.
				topSpace := kindToRoom * ((p.pos - firstRoomIdx) / kindToRoom)
				// Only check spaces above us.
				for checkSpace := firstRoomIdx + topSpace; checkSpace < p.pos; checkSpace++ {
					if occupied[checkSpace] != kindFree {
						// If any of the spaces above us are occupied, we don't have any moves.
						continue PODLOOP
					}
				}
			}
			// Find the largest occupied space in the hall smaller than our "above" space. We cannot
			// move past it. Do the same for the smallest one larger than our above space.
			// For now, assume the entire hall is free to the left.
			left := firstHallIdx
			for spaceIdx := firstHallIdx + 1; spaceIdx < mySpace.above; spaceIdx++ {
				// Find the largest occupied space to the left of our above space.
				if occupied[spaceIdx] != kindFree {
					left = spaceIdx
				}
			}
			// For now, assume the entire hall is free to the right.
			right := lastHallIdx
			for spaceIdx := lastHallIdx - 1; spaceIdx > mySpace.above; spaceIdx-- {
				// Find the smallest occupied space to the right of our above space.
				if occupied[spaceIdx] != kindFree {
					right = spaceIdx
				}
			}
			// Add all moves between left (exclusive) and right (exclusive) that are not also an
			// above space. That is, iterate over the hall and check whether we are at least left or
			// at most right.
			for _, pos := range []int{0, 1, 3, 5, 7, 9, 10} {
				if pos > left && pos < right {
					// The number of spaces moved is the distance between the target position and
					// the above space, plus distanceToAbove, which is hte distance to the space
					// directly above our room.
					distanceToAbove := diffToRoomStart%kindToRoom + 1
					spacesMoved := abs(pos-mySpace.above) + distanceToAbove
					m := move{
						start: p.pos,
						end:   pos,
						cost:  p.cost * spacesMoved,
					}
					// Anyone is allowed in the hall. Don't check if we are allowed.
					moves = append(moves, m)
				}
			}
		} else {
			// If we are in the hall, we can only move to a room. We can only move to our room,
			// though.
			ourRoom := firstRoomIdx + kindToRoom*p.kind
			aboveOurRoom := g.spaces[ourRoom].above
			// If a space on our side of the hall of the above space is occupied, we cannot move to
			// our room.
			if p.pos < aboveOurRoom {
				// We are to the left of the above position.
				for checkPos := p.pos + 1; checkPos < aboveOurRoom; checkPos++ {
					if occupied[checkPos] != kindFree {
						// There is a space occupied to our right, blocking our room. We cannot move
						// into our room.
						continue PODLOOP
					}
				}
			} else {
				// We cannot be in an above position. Hence, we are to the right of the above spot.
				for checkPos := p.pos - 1; checkPos > aboveOurRoom; checkPos-- {
					if occupied[checkPos] != kindFree {
						// There is a space occupied to our left, blocking our room. We cannot move
						// into our room.
						continue PODLOOP
					}
				}
			}
			// Check whether any space already in the room is occupied. We may only move to the
			// lowest unoccupied space. But only if there are only the same kind of pods there like
			// us.
			diffToTop := kindToRoom
			bottomSpace := ourRoom + kindToRoom - 1
			// This block uses the implicit knowledge that, if we find a free space, all spaces
			// above it must be free, too, since all rooms start out full. And we only ever want to
			// move to the lowest unoccupied space.
			for space := bottomSpace; space >= ourRoom; space-- {
				if occupied[space] == kindFree {
					spacesMoved := abs(p.pos-aboveOurRoom) + diffToTop //nolint:gomnd
					m := move{
						start: p.pos,
						end:   space,
						cost:  p.cost * spacesMoved,
					}
					moves = append(moves, m)
					continue PODLOOP
				}
				if occupied[space] != p.kind {
					// If we find anyone of a different kind here, we must not enter the room. Since
					// we've already taken care of the empty case, this one means we cannot move
					// into the room.
					continue PODLOOP
				}
				diffToTop--
			}
		}
	}

	return moves
}

func (g game) update(m move) game {
	mover := -1
	for moverIdx, p := range g.pods {
		if p.pos == m.start {
			mover = moverIdx
			break
		}
	}
	if mover < 0 {
		fmt.Println(g.pretty())
		fmt.Println(m)
		fmt.Println(g.pods)
		log.Fatal("invalid move, no mover")
	}
	// Sanity check, try to find something at the target position.
	for _, p := range g.pods {
		if p.pos == m.end {
			log.Fatal("invalid move, target occupied")
		}
	}
	g.pods[mover].pos = m.end
	return g
}

func (g *game) isFinal() bool {
	occupied := [27]int{}
	for idx := range occupied {
		occupied[idx] = kindFree
	}
	for _, p := range g.pods {
		occupied[p.pos] = p.kind
	}
	occ := occupied[11] == kindA &&
		occupied[12] == kindA &&
		occupied[13] == kindA &&
		occupied[14] == kindA &&
		occupied[15] == kindB &&
		occupied[16] == kindB &&
		occupied[17] == kindB &&
		occupied[18] == kindB &&
		occupied[19] == kindC &&
		occupied[20] == kindC &&
		occupied[21] == kindC &&
		occupied[22] == kindC &&
		occupied[23] == kindD &&
		occupied[24] == kindD &&
		occupied[25] == kindD &&
		occupied[26] == kindD
	return occ
}

func (p pod) String() string {
	var name rune
	switch p.kind {
	case kindA:
		name = a
	case kindB:
		name = b
	case kindC:
		name = c
	case kindD:
		name = d
	default:
		log.Fatalf("internal error, %v, %v, %v", p.cost, p.kind, p.pos)
	}
	return fmt.Sprintf("{k: %c, p: %d, c: %d}", name, p.pos, p.cost)
}

const (
	// Digits and levels for the brute-force search.
	smallestDigit = 1
	largestDigit  = 9
	firstLevel    = 0
	lastLevel     = 13
)

type acl struct {
	// w, x, y int
	z int
}

type fn = func(acl, int) acl

var funcs []fn

const ten = 10

func pow10(exp int) int {
	result := 1
	for count := 0; count < exp; count++ {
		result *= ten
	}
	return result
}

type cacheElem struct {
	state acl
	level int
}

var cache map[cacheElem]int

func findNum(inState acl, startDig, endDig, increment, level int) (int, bool) {
	cacheHit := cacheElem{
		state: inState,
		level: level,
	}
	if val, hit := cache[cacheHit]; hit {
		return val, val != 0
	}
	myFn := funcs[level]
	for dig := startDig; dig != endDig+increment; dig += increment {
		state := myFn(inState, dig)
		if level == lastLevel {
			if state.z == 0 {
				cache[cacheHit] = dig
				return dig, true
			}
		} else {
			num, valid := findNum(state, startDig, endDig, increment, level+1)
			if valid {
				cache[cacheHit] = dig
				return pow10(lastLevel-level)*dig + num, true
			}
		}
	}
	cache[cacheHit] = 0
	return 0, false
}

func main() {
	// Read ops in.
	ops, err := ReadLinesAsOps()
	if err != nil {
		log.Fatal(err.Error())
	}
	// Convert ops to functions we want to use.
	funcs, err = opsToFuncs(ops)
	if err != nil {
		log.Fatal(err.Error())
	}

	// Initialise the cache.
	cache = make(map[cacheElem]int)

	// Part 1, largest accepted model number.
	state := acl{} // Automatically zero-initialised.
	num, valid := findNum(state, largestDigit, smallestDigit, -1, firstLevel)
	if !valid {
		log.Fatal("no solution found")
	}
	fmt.Println("Largest model number is", num, "- cached", len(cache), "function calls")

	// Clear the cache in between.
	cache = make(map[cacheElem]int)

	// Part 2, smallest accepted model number.
	state = acl{}
	num, valid = findNum(state, smallestDigit, largestDigit, 1, firstLevel)
	if !valid {
		log.Fatal("no solution found")
	}
	fmt.Println("Smallest model number is", num, "- cached", len(cache), "function calls")
}

const (
	// Registers.
	allRegs = "wxyz"
)

var reader = bufio.NewReader(os.Stdin)

func readLine() (string, error) {
	return reader.ReadString('\n')
}

// ReadLinesAsOps reads lines as ops that are the input to the submarine's ACL.
//nolint:gomnd,funlen
func ReadLinesAsOps() ([]op, error) {
	result := []op{}
	for {
		line, err := readLine()
		if err == io.EOF {
			// Success case, no more input to read.
			return result, nil
		}
		if err != nil {
			return []op{}, err
		}
		line = strings.TrimSpace(line)
		fields := strings.Fields(line)
		if len(fields[1]) != 1 {
			err := fmt.Errorf("cannot extract register")
			return []op{}, err
		}
		if !strings.Contains(allRegs, fields[1]) {
			err := fmt.Errorf("unknown register")
			return []op{}, err
		}
		reg := rune(fields[1][0])
		var data interface{}
		if len(fields) == 3 {
			if strings.Contains(allRegs, fields[2]) {
				// Is a register.
				data = rune(fields[2][0])
			} else {
				// Is a number.
				num, err := strconv.Atoi(fields[2])
				if err != nil {
					return []op{}, err
				}
				data = num
			}
		}
		var o op
		opStr := fields[0]
		switch opStr {
		case "inp":
			if data != nil {
				err := fmt.Errorf("non-nil interface")
				return []op{}, err
			}
			o = op{act: opInp, reg: reg}
		case "add", "mul", "div", "mod", "eql":
			if data == nil {
				err := fmt.Errorf("nil interface")
				return []op{}, err
			}
			var opType rune
			switch opStr {
			case "add":
				opType = opAdd
			case "mul":
				opType = opMul
			case "div":
				opType = opDiv
			case "mod":
				opType = opMod
			case "eql":
				opType = opEql
			default:
				err := fmt.Errorf("internal error")
				return []op{}, err
			}
			o = op{act: opType, reg: reg, dat: data}
		default:
			err := fmt.Errorf("unknown op")
			return []op{}, err
		}
		result = append(result, o)
	}
}

const (
	// Ops.
	opInp = 'i'
	opAdd = 'a'
	opMul = 'm'
	opDiv = 'd'
	opMod = 'o'
	opEql = 'e'
	// Registers.
	inReg = 'w'
	regW  = 'w'
	regX  = 'x'
	regY  = 'y'
	regZ  = 'z'
)

type op struct {
	act rune
	reg rune
	dat interface{}
}

// String gets a string rep.
func (o op) String() string {
	str := fmt.Sprintf("%c -> %c", o.act, o.reg)
	switch t := o.dat.(type) {
	case int:
		str += fmt.Sprintf(" : %d", t)
	case rune:
		str += fmt.Sprintf(" : %c", t)
	}
	return str
}

// Compare two ops. If the data is nil, it is excluded from the comparison
func (o op) cmp(other op) bool {
	if o.act != other.act {
		return false
	}
	if o.reg != other.reg {
		return false
	}
	if o.dat != nil && o.dat != other.dat {
		return false
	}
	return true
}

// This is an example block of operations that shows the expected order of operations:
// mul x 0
// add x z
// mod x 26
// div z 26 => 26 is called "divVal" below, the value "nil" in the expected ops signifies this.
// add x -9 => -9 is called "addX" below, the value "nil" in the expected ops signifies this.
// eql x w
// eql x 0
// mul y 0
// add y 25
// mul y x
// add y 1
// mul z y
// mul y 0
// add y w
// add y 5 => 5 is called "addY" below, the value "nil" in the expected ops signifies this.
// mul y x
// add z y

// Convert a set of ops between input operations into a neat function.
//nolint:gomnd,funlen
func getFunc(ops []op) (fn, error) {
	var f fn
	vals := []int{}
	// Sanity check the expected order of operations. Also extract the values we need.
	expectedOps := []op{
		op{act: opMul, reg: regX, dat: 0},
		op{act: opAdd, reg: regX, dat: regZ},
		op{act: opMod, reg: regX, dat: 26},
		op{act: opDiv, reg: regZ, dat: nil},
		op{act: opAdd, reg: regX, dat: nil},
		op{act: opEql, reg: regX, dat: regW},
		op{act: opEql, reg: regX, dat: 0},
		op{act: opMul, reg: regY, dat: 0},
		op{act: opAdd, reg: regY, dat: 25},
		op{act: opMul, reg: regY, dat: regX},
		op{act: opAdd, reg: regY, dat: 1},
		op{act: opMul, reg: regZ, dat: regY},
		op{act: opMul, reg: regY, dat: 0},
		op{act: opAdd, reg: regY, dat: regW},
		op{act: opAdd, reg: regY, dat: nil},
		op{act: opMul, reg: regY, dat: regX},
		op{act: opAdd, reg: regZ, dat: regY},
	}
	if len(ops) != len(expectedOps) {
		return nil, fmt.Errorf("unqeual number of ops, cannot process")
	}
	for opIdx, inOp := range ops {
		expectedOp := expectedOps[opIdx]
		if !expectedOp.cmp(inOp) {
			return nil, fmt.Errorf(
				"unexpected op '%s' at line %d, wanted '%s'",
				inOp, opIdx+1, expectedOp,
			)
		}
		if expectedOp.dat == nil {
			converted, ok := inOp.dat.(int)
			if !ok {
				return nil, fmt.Errorf("failure in integer conversion")
			}
			vals = append(vals, converted)
		}
	}
	if len(vals) != 3 {
		return nil, fmt.Errorf("cannot extract enough variables from op input")
	}

	divVal := vals[0]
	addX := vals[1]
	addY := vals[2]

	// There are basically two different kinds of functions. Ones that divide z by 26 and ones that
	// divide z by 1 as per divVal. The first kind is a bit more complex and will involve comparing
	// the value of "z mod 26 + addX" with the input digit. The second type is a lot simpler. Using
	// some math, it can easily be deduced that those functions do not use the addX value at all.
	// The value will simply be consumed by the modulo or integer division operation, I can't recall
	// which one.
	if divVal == 1 {
		f = func(s acl, dig int) acl {
			// This function does not need the addX value.
			return acl{z: s.z*26 + dig + addY}
		}
	} else {
		f = func(s acl, dig int) acl {
			var val int
			if s.z%26+addX != dig {
				val = 1
			}
			return acl{z: s.z/26*(25*val+1) + (dig+addY)*val}
		}
	}
	return f, nil
}

//nolint:nestif
func opsToFuncs(ops []op) ([]fn, error) {
	funcs := []fn{}
	// Separate ops into partitions that start with an input operation. Furthermore, sanity check
	// whether all input happens to the w register.
	partition := []op{}
	for _, o := range ops {
		if o.act == opInp {
			if o.reg != inReg {
				return []fn{}, fmt.Errorf("input to a non-w register detected")
			}
			if len(partition) > 0 {
				f, err := getFunc(partition)
				if err != nil {
					return []fn{}, err
				}
				funcs = append(funcs, f)
				partition = []op{}
			}
		} else {
			partition = append(partition, o)
		}
	}
	f, err := getFunc(partition)
	if err != nil {
		return []fn{}, err
	}
	funcs = append(funcs, f)

	return funcs, nil
}

func pretty(image []rune, lineLen int) {
	var zeroVal rune
	for idx, char := range image {
		if char == zeroVal || char == kindEmpty {
			char = '.'
		}
		fmt.Printf("%c", char)
		if (idx+1)%lineLen == 0 {
			fmt.Println()
		}
	}
	fmt.Println()
}

func step(image []rune, lineLen int) ([]rune, bool) {
	var zeroVal rune
	length := len(image)
	next := make([]rune, len(image))
	moved := false
	// East first.
	for idx, char := range image {
		if char == kindEast {
			neigh := lineLen*(idx/lineLen) + (idx+1)%lineLen
			if image[neigh] == zeroVal {
				next[neigh] = char
				moved = true
			} else {
				next[idx] = char
			}
		}
	}
	// Then south.
	for idx, char := range image {
		if char == kindSouth {
			neigh := (idx + lineLen) % length
			if image[neigh] != kindSouth && next[neigh] != kindEast {
				next[neigh] = char
				moved = true
			} else {
				next[idx] = char
			}
		}
	}
	return next, moved
}

func main() {
	prettyPrint := os.Getenv("PRETTY_PRINT") == "1"

	image, lineLen, err := ReadLinesAsImage()
	if err != nil {
		log.Fatal(err.Error())
	}

	count := 0
	if prettyPrint {
		pretty(image, lineLen)
	}
	for moved := true; moved; {
		count++
		image, moved = step(image, lineLen)
		if prettyPrint {
			pretty(image, lineLen)
		}
	}
	fmt.Println("Cucumbers stop moving after", count, "steps.")
}

// ReadLinesAsImage reads input as an image of sea cucumbers.
func ReadLinesAsImage() ([]rune, int, error) {
	var zeroVal rune
	result := []rune{}
	lineLen := -1
	for rowIdx := 0; ; rowIdx++ {
		line, err := readLine()
		if err == io.EOF {
			// Success case, no more input to read.
			return result, lineLen, nil
		}
		if err != nil {
			return []rune{}, 0, err
		}
		line = strings.TrimSpace(line)
		if lineLen < 0 {
			lineLen = len(line)
		}
		if len(line) != lineLen {
			return []rune{}, 0, fmt.Errorf("line %s has incorrect length", line)
		}
		for _, char := range line {
			if char == emptyChar {
				char = zeroVal
			}
			result = append(result, char)
		}
	}
}