Aoc 2021 Day 22

day22.go

package day22

import (
	"bufio"
	"fmt"
	"io"
	"sort"
)

type instr struct {
	v       byte
	x, y, z [2]int
}

func parse(r io.Reader) ([]instr, error) {
	var in []instr
	s := bufio.NewScanner(r)
	for s.Scan() {
		var vs string
		var i instr
		_, err := fmt.Sscanf(s.Text(), "%s x=%d..%d,y=%d..%d,z=%d..%d", &vs, &i.x[0], &i.x[1], &i.y[0], &i.y[1], &i.z[0], &i.z[1])
		if err != nil {
			return in, err
		}
		// ranges in the input are inclusive, make the right end exclusive
		i.x[1]++
		i.y[1]++
		i.z[1]++
		switch vs {
		case "on":
			i.v = 1
		case "off":
			i.v = 0
		default:
			return in, fmt.Errorf("parse error")
		}
		in = append(in, i)
	}
	return in, s.Err()
}

func unique(s []int) []int {
	sort.Ints(s)
	j := 1
	for i := 1; i < len(s); i++ {
		if s[i] == s[i-1] {
			continue
		}
		s[j] = s[i]
		j++
	}
	return s[:j]
}

func solve(in []instr) (uint64, uint64) {
	x := append(make([]int, 0, 2*len(in)+2), -50, 51)
	y := append(make([]int, 0, 2*len(in)+2), -50, 51)
	z := append(make([]int, 0, 2*len(in)+2), -50, 51)
	for _, i := range in {
		x = append(x, i.x[0], i.x[1])
		y = append(y, i.y[0], i.y[1])
		z = append(z, i.z[0], i.z[1])
	}
	x = unique(x)
	y = unique(y)
	z = unique(z)

	buf := make([]byte, len(x)*len(y)*len(z))

	for _, i := range in {
		zi0 := sort.SearchInts(z, i.z[0])
		zi1 := sort.SearchInts(z, i.z[1])
		yi0 := sort.SearchInts(y, i.y[0])
		yi1 := sort.SearchInts(y, i.y[1])
		xi0 := sort.SearchInts(x, i.x[0])
		xi1 := sort.SearchInts(x, i.x[1])
		for zi := zi0; zi < zi1; zi++ {
			off := zi * len(x) * len(y)
			for yi := yi0; yi < yi1; yi++ {
				off := yi*len(x) + off
				for xi := xi0; xi < xi1; xi++ {
					buf[off+xi] = i.v
				}
			}
		}
	}

	var s1, s2 uint64
	for zi := 0; zi < len(z)-1; zi++ {
		off := zi * len(x) * len(y)
		init := z[zi] >= -50 && z[zi] <= 50
		cubes := uint64(z[zi+1] - z[zi])
		for yi := 0; yi < len(y)-1; yi++ {
			off := yi*len(x) + off
			init := init && y[yi] >= -50 && y[yi] <= 50
			cubes := cubes * uint64(y[yi+1]-y[yi])
			for xi := 0; xi < len(x)-1; xi++ {
				if buf[off+xi] == 0 {
					continue
				}
				init := init && x[xi] >= -50 && x[xi] <= 50
				cubes := cubes * uint64(x[xi+1]-x[xi])
				s2 += cubes
				if init {
					s1 += cubes
				}
			}
		}
	}

	return s1, s2
}