2021-advent-19.go

package main

import (
	"fmt"
	"io/ioutil"
	"log"
	"math"
	"strconv"
	"strings"
)

func permutations(data []int) [][]int {
	if len(data) == 0 {
		return nil
	}
	perms := make([][]int, 1)
	perms[0] = []int{data[0]}
	for _, nextElement := range data[1:] {
		allOnLevel := make([][]int, 0)
		for _, permutation := range perms {
			singlePermExp := make([][]int, 0)
			for inserPos := 0; inserPos < len(permutation)+1; inserPos++ {
				nxtPerm := make([]int, len(permutation)+1)
				nxtPerm[inserPos] = nextElement
				copy(nxtPerm[0:inserPos], permutation[0:inserPos])
				copy(nxtPerm[inserPos+1:], permutation[inserPos:])
				singlePermExp = append(singlePermExp, nxtPerm)
			}
			allOnLevel = append(allOnLevel, singlePermExp...)
		}
		perms = allOnLevel
	}
	return perms
}

type Rotation struct {
	d    []int
	sign []int
}

func NewRotationa(x, y, z, sx, sy, sz int) Rotation {
	return Rotation{
		d:    []int{x, y, z},
		sign: []int{sx, sy, sz},
	}
}

func AllRotations() []Rotation {
	allTranslations := permutations([]int{0, 1, 2})
	rot := make([]Rotation, 0)

	signs := [][]int{
		{-1, -1, -1},
		{1, -1, -1},
		{1, 1, -1},
		{1, 1, 1},
		{-1, 1, 1},
		{-1, -1, 1},
		{-1, 1, -1},
		{1, -1, 1},
	}

	for _, v := range allTranslations {
		for _, s := range signs {
			rot = append(rot, NewRotationa(v[0], v[1], v[2], s[0], s[1], s[2]))
		}
	}
	return rot
}

type Coord []int
type CoordStruct struct {
	x, y, z int
}

func NewCoord(x, y, z int) Coord {
	return Coord([]int{x, y, z})
}

func (c Coord) ToStruct() CoordStruct {
	return CoordStruct{c[0], c[1], c[2]}
}

func (c Coord) Equals(oc Coord) bool {
	return c[0] == oc[0] && c[1] == oc[1] && c[2] == oc[2]
}

func (c Coord) Add(oc Coord) Coord {
	return Coord([]int{c[0] + oc[0], c[1] + oc[1], c[2] + oc[2]})
}

func (c Coord) Sub(oc Coord) Coord {
	return Coord([]int{c[0] - oc[0], c[1] - oc[1], c[2] - oc[2]})
}

func (c Coord) Rotate(r Rotation) Coord {
	c1 := NewCoord(0, 0, 0)
	c1[r.d[0]] = c[0] * r.sign[0]
	c1[r.d[1]] = c[1] * r.sign[1]
	c1[r.d[2]] = c[2] * r.sign[2]
	return c1
}

func Contains(beacons []Coord, c Coord) bool {
	for _, c2 := range beacons {
		if c.Equals(c2) {
			return true
		}
	}
	return false
}

type Scanner struct {
	beacons []Coord
}

func readInput(input string) []Scanner {
	bytes, err := ioutil.ReadFile(input)
	if err != nil {
		log.Fatal(err)
	}
	unsfeAtoi := func(s string) int {
		r, _ := strconv.Atoi(s)
		return r
	}
	scanners := make([]Scanner, 0)
	for _, scannerData := range strings.Split(string(bytes), "\n\n") {
		lines := strings.Split(scannerData, "\n")
		scanner := Scanner{}
		// scanner.id = unsfeAtoi(strings.Split(lines[0], " ")[2])
		for _, coordStr := range lines[1:] {
			if len(coordStr) == 0 {
				continue
			}
			c := strings.Split(coordStr, ",")
			scanner.beacons = append(scanner.beacons, Coord{unsfeAtoi(c[0]), unsfeAtoi(c[1]), unsfeAtoi(c[2])})
		}
		scanners = append(scanners, scanner)
	}
	return scanners
}

const SCANNER_STEP = 12

func task(input string) {
	Scanners := readInput(input)
	NumberOfScanners := len(Scanners)
	Locations := make([]Coord, NumberOfScanners)
	Locations[0] = Coord{0, 0, 0}
	Rotations := make([]Rotation, NumberOfScanners)
	Rotations[0] = NewRotationa(0, 1, 2, 1, 1, 1)

	// Compare everything with everything
	// sc1 location is "known"
	// In first iteration scanner 0 is at 0,0,0, has all magnetic "normal"
	// and is source of truth
	for {
		for sc1 := 0; sc1 < NumberOfScanners; sc1++ {
			//It is unknonw yet
			if Locations[sc1] == nil {
				continue
			}

			//build points in global "space"
			knowInGlobalSpace := make([]Coord, 0)
			for _, b := range Scanners[sc1].beacons {
				el := Locations[sc1].Add(b.Rotate(Rotations[sc1]))
				knowInGlobalSpace = append(knowInGlobalSpace, el)
			}

			for sc2 := 0; sc2 < NumberOfScanners; sc2++ {
				if sc1 == sc2 || Locations[sc2] != nil {
					continue
				}
				// fmt.Printf("Trying scanners %d with %d\n", sc1, sc2)
				// Need to try in all orientations
				for _, potentialRotationt := range AllRotations() {
					//transform them
					unknownInGlobalSpace := make([]Coord, 0)
					for _, p2 := range Scanners[sc2].beacons {
						el := p2.Rotate(potentialRotationt)
						unknownInGlobalSpace = append(unknownInGlobalSpace, el)
					}

					// Try to find coverage between scanners
					for i := 0; i < len(knowInGlobalSpace); i++ {
						for j := 0; j < len(unknownInGlobalSpace); j++ {
							// fmt.Printf("Beacon %d to beacon %d\n", i, j)
							// If those two maps, this vector needs to be attached to other
							shift := knowInGlobalSpace[i].Sub(unknownInGlobalSpace[j])
							matchesCounter := 0
							for k := 0; k < len(unknownInGlobalSpace); k++ {
								pt := unknownInGlobalSpace[k].Add(shift)
								if Contains(knowInGlobalSpace, pt) {
									matchesCounter += 1
									if matchesCounter >= SCANNER_STEP {
										break
									}
								}
							}
							if matchesCounter >= SCANNER_STEP {
								Locations[sc2] = shift
								Rotations[sc2] = potentialRotationt
								break
							}
						}
					}
				}
			}
		}
		all_nonNil := true
		for _, c := range Locations {
			if c == nil {
				all_nonNil = false
				break
			}
		}
		if all_nonNil {
			break
		}
	}

	//count beacons
	allBeacons := make(map[CoordStruct]bool)
	for i, scanner := range Scanners {
		for _, coord := range scanner.beacons {
			k := Locations[i].Add(coord.Rotate(Rotations[i])).ToStruct()
			allBeacons[k] = true
		}
	}

	beaconCounter := 0
	for range allBeacons {
		beaconCounter += 1
	}
	fmt.Printf("Day19 task1 %s: %v\n", input, beaconCounter)

	maxDis := -1
	for sc1 := range Locations {
		for sc2 := range Locations {
			coord := Locations[sc1].Sub(Locations[sc2]).ToStruct()
			newDis := math.Abs(float64(coord.x)) + math.Abs(float64(coord.y)) + math.Abs(float64(coord.z))
			if newDis > float64(maxDis) {
				maxDis = int(newDis)
			}
		}
	}
	fmt.Printf("Day19 task2 %s: %v\n", input, maxDis)

}

func main() {
	task("example.txt")
	task("input.txt")
}