aoc-2021-22.go

package main

import (
	"fmt"
	"log"
	"sort"
)

func main() {
	test1 := []string{
		"on x=-20..26,y=-36..17,z=-47..7",
		"on x=-20..33,y=-21..23,z=-26..28",
		"on x=-22..28,y=-29..23,z=-38..16",
		"on x=-46..7,y=-6..46,z=-50..-1",
		"on x=-49..1,y=-3..46,z=-24..28",
		"on x=2..47,y=-22..22,z=-23..27",
		"on x=-27..23,y=-28..26,z=-21..29",
		"on x=-39..5,y=-6..47,z=-3..44",
		"on x=-30..21,y=-8..43,z=-13..34",
		"on x=-22..26,y=-27..20,z=-29..19",
		"off x=-48..-32,y=26..41,z=-47..-37",
		"on x=-12..35,y=6..50,z=-50..-2",
		"off x=-48..-32,y=-32..-16,z=-15..-5",
		"on x=-18..26,y=-33..15,z=-7..46",
		"off x=-40..-22,y=-38..-28,z=23..41",
		"on x=-16..35,y=-41..10,z=-47..6",
		"off x=-32..-23,y=11..30,z=-14..3",
		"on x=-49..-5,y=-3..45,z=-29..18",
		"off x=18..30,y=-20..-8,z=-3..13",
		"on x=-41..9,y=-7..43,z=-33..15",
	}
	_ = test1

	test2 := []string{
		"on x=-5..47,y=-31..22,z=-19..33",
		"on x=-44..5,y=-27..21,z=-14..35",
		"on x=-49..-1,y=-11..42,z=-10..38",
		"on x=-20..34,y=-40..6,z=-44..1",
		"off x=26..39,y=40..50,z=-2..11",
		"on x=-41..5,y=-41..6,z=-36..8",
		"off x=-43..-33,y=-45..-28,z=7..25",
		"on x=-33..15,y=-32..19,z=-34..11",
		"off x=35..47,y=-46..-34,z=-11..5",
		"on x=-14..36,y=-6..44,z=-16..29",
		"on x=-57795..-6158,y=29564..72030,z=20435..90618",
		"on x=36731..105352,y=-21140..28532,z=16094..90401",
		"on x=30999..107136,y=-53464..15513,z=8553..71215",
		"on x=13528..83982,y=-99403..-27377,z=-24141..23996",
		"on x=-72682..-12347,y=18159..111354,z=7391..80950",
		"on x=-1060..80757,y=-65301..-20884,z=-103788..-16709",
		"on x=-83015..-9461,y=-72160..-8347,z=-81239..-26856",
		"on x=-52752..22273,y=-49450..9096,z=54442..119054",
		"on x=-29982..40483,y=-108474..-28371,z=-24328..38471",
		"on x=-4958..62750,y=40422..118853,z=-7672..65583",
		"on x=55694..108686,y=-43367..46958,z=-26781..48729",
		"on x=-98497..-18186,y=-63569..3412,z=1232..88485",
		"on x=-726..56291,y=-62629..13224,z=18033..85226",
		"on x=-110886..-34664,y=-81338..-8658,z=8914..63723",
		"on x=-55829..24974,y=-16897..54165,z=-121762..-28058",
		"on x=-65152..-11147,y=22489..91432,z=-58782..1780",
		"on x=-120100..-32970,y=-46592..27473,z=-11695..61039",
		"on x=-18631..37533,y=-124565..-50804,z=-35667..28308",
		"on x=-57817..18248,y=49321..117703,z=5745..55881",
		"on x=14781..98692,y=-1341..70827,z=15753..70151",
		"on x=-34419..55919,y=-19626..40991,z=39015..114138",
		"on x=-60785..11593,y=-56135..2999,z=-95368..-26915",
		"on x=-32178..58085,y=17647..101866,z=-91405..-8878",
		"on x=-53655..12091,y=50097..105568,z=-75335..-4862",
		"on x=-111166..-40997,y=-71714..2688,z=5609..50954",
		"on x=-16602..70118,y=-98693..-44401,z=5197..76897",
		"on x=16383..101554,y=4615..83635,z=-44907..18747",
		"off x=-95822..-15171,y=-19987..48940,z=10804..104439",
		"on x=-89813..-14614,y=16069..88491,z=-3297..45228",
		"on x=41075..99376,y=-20427..49978,z=-52012..13762",
		"on x=-21330..50085,y=-17944..62733,z=-112280..-30197",
		"on x=-16478..35915,y=36008..118594,z=-7885..47086",
		"off x=-98156..-27851,y=-49952..43171,z=-99005..-8456",
		"off x=2032..69770,y=-71013..4824,z=7471..94418",
		"on x=43670..120875,y=-42068..12382,z=-24787..38892",
		"off x=37514..111226,y=-45862..25743,z=-16714..54663",
		"off x=25699..97951,y=-30668..59918,z=-15349..69697",
		"off x=-44271..17935,y=-9516..60759,z=49131..112598",
		"on x=-61695..-5813,y=40978..94975,z=8655..80240",
		"off x=-101086..-9439,y=-7088..67543,z=33935..83858",
		"off x=18020..114017,y=-48931..32606,z=21474..89843",
		"off x=-77139..10506,y=-89994..-18797,z=-80..59318",
		"off x=8476..79288,y=-75520..11602,z=-96624..-24783",
		"on x=-47488..-1262,y=24338..100707,z=16292..72967",
		"off x=-84341..13987,y=2429..92914,z=-90671..-1318",
		"off x=-37810..49457,y=-71013..-7894,z=-105357..-13188",
		"off x=-27365..46395,y=31009..98017,z=15428..76570",
		"off x=-70369..-16548,y=22648..78696,z=-1892..86821",
		"on x=-53470..21291,y=-120233..-33476,z=-44150..38147",
		"off x=-93533..-4276,y=-16170..68771,z=-104985..-24507",
	}
	_ = test2

	test := []string{
		"on x=4..6,y=0..2,z=0..0",
		"on x=0..2,y=1..3,z=0..0",
		"on x=1..4,y=2..4,z=0..0",
		//"on x=0..4,y=0..4,z=0..0",
		//"on x=3..6,y=3..6,z=0..0",
	}
	_ = test

	p := Space{}
	for i, inst := range test {
		fmt.Println("[", i+1, "/", len(test), "]", inst)
		p.exec(inst)
		p.compact()
	}

	var count int64
	for _, c := range p {
		count += c.Volume()
	}
	fmt.Println(count)
}

func (p *Plane) exec(inst string) {
	var flag string
	var x1, x2, y1, y2, z1, z2 int
	fmt.Sscanf(inst, "%s x=%d..%d,y=%d..%d,z=%d..%d",
		&flag, &x1, &x2, &y1, &y2, &z1, &z2)

	if x2 < x1 {
		x1, x2 = x2, x1
	}
	if y2 < y1 {
		y1, y2 = y2, y1
	}

	r := rect{x1, y1, x2 + 1, y2 + 1}

	// find all intersecting points
	xs := []int{r.x1, r.x2}
	ys := []int{r.y1, r.y2}

	intersects := make([]rect, 0, len(*p))
	for i := len(*p) - 1; i >= 0; i-- {
		s := (*p)[i]
		if r.Intersects(s) {
			xs = append(xs, s.x1, s.x2)
			ys = append(ys, s.y1, s.y2)
			*p = append((*p)[:i], (*p)[i+1:]...)
			intersects = append(intersects, s)
		}
	}

	if len(intersects) > 0 {
		xs = sortAndUniq(xs...)
		ys = sortAndUniq(ys...)
		for j := 0; j < len(ys)-1; j++ {
			for i := 0; i < len(xs)-1; i++ {
				t := rect{xs[i], ys[j], xs[i+1], ys[j+1]}

				_b := t.In(r)
				if !_b {
					for _, v := range intersects {
						if t.In(v) {
							_b = true
							break
						}
					}
				}
				if _b {
					*p = append(*p, t)
				}
			}
		}
	} else {
		*p = append(*p, r)
	}
}

func (p *Plane) compact() {
	orig := len(*p)

	sort.SliceStable(*p, func(i, j int) bool {
		if (*p)[i].y1 != (*p)[j].y1 {
			return (*p)[i].y1 < (*p)[j].y1
		}
		return (*p)[i].x1 < (*p)[j].x1
	})
	for i := len(*p) - 1; i >= 1; i-- {
		if (*p)[i].y1 == (*p)[i-1].y1 &&
			(*p)[i].y2 == (*p)[i-1].y2 &&
			(*p)[i].x1 == (*p)[i-1].x2 {
			(*p)[i-1].x2 = (*p)[i].x2
			(*p)[i-1].y2 = (*p)[i].y2
			*p = append((*p)[:i], (*p)[i+1:]...)
		}
	}

	sort.SliceStable(*p, func(i, j int) bool {
		if (*p)[i].x1 != (*p)[j].x1 {
			return (*p)[i].x1 < (*p)[j].x1
		}
		return (*p)[i].y1 < (*p)[j].y1
	})
	for i := len(*p) - 1; i >= 1; i-- {
		if (*p)[i].x1 == (*p)[i-1].x1 &&
			(*p)[i].x2 == (*p)[i-1].x2 &&
			(*p)[i].y1 == (*p)[i-1].y2 {
			(*p)[i-1].x2 = (*p)[i].x2
			(*p)[i-1].y2 = (*p)[i].y2
			*p = append((*p)[:i], (*p)[i+1:]...)
		}
	}

	fmt.Println("compact:", orig, "->", len(*p))
}

func (p *Space) compact() {
	orig := len(*p)

	sort.SliceStable(*p, func(i, j int) bool {
		if (*p)[i].y1 != (*p)[j].y1 {
			return (*p)[i].y1 < (*p)[j].y1
		}
		if (*p)[i].z1 != (*p)[j].z1 {
			return (*p)[i].z1 < (*p)[j].z1
		}
		return (*p)[i].x1 < (*p)[j].x1
	})
	for i := len(*p) - 1; i >= 1; i-- {
		if (*p)[i].y1 == (*p)[i-1].y1 &&
			(*p)[i].y2 == (*p)[i-1].y2 &&
			(*p)[i].z1 == (*p)[i-1].z1 &&
			(*p)[i].z2 == (*p)[i-1].z2 &&
			(*p)[i].x1 == (*p)[i-1].x2 {
			(*p)[i-1].x2 = (*p)[i].x2
			(*p)[i-1].y2 = (*p)[i].y2
			(*p)[i-1].z2 = (*p)[i].z2
			*p = append((*p)[:i], (*p)[i+1:]...)
		}
	}

	sort.SliceStable(*p, func(i, j int) bool {
		if (*p)[i].x1 != (*p)[j].x1 {
			return (*p)[i].x1 < (*p)[j].x1
		}
		if (*p)[i].z1 != (*p)[j].z1 {
			return (*p)[i].z1 < (*p)[j].z1
		}
		return (*p)[i].y1 < (*p)[j].y1
	})
	for i := len(*p) - 1; i >= 1; i-- {
		if (*p)[i].x1 == (*p)[i-1].x1 &&
			(*p)[i].x2 == (*p)[i-1].x2 &&
			(*p)[i].z1 == (*p)[i-1].z1 &&
			(*p)[i].z2 == (*p)[i-1].z2 &&
			(*p)[i].y1 == (*p)[i-1].y2 {
			(*p)[i-1].x2 = (*p)[i].x2
			(*p)[i-1].y2 = (*p)[i].y2
			(*p)[i-1].z2 = (*p)[i].z2
			*p = append((*p)[:i], (*p)[i+1:]...)
		}
	}

	sort.SliceStable(*p, func(i, j int) bool {
		if (*p)[i].x1 != (*p)[j].x1 {
			return (*p)[i].x1 < (*p)[j].x1
		}
		if (*p)[i].y1 != (*p)[j].y1 {
			return (*p)[i].y1 < (*p)[j].y1
		}
		return (*p)[i].z1 < (*p)[j].z1
	})
	for i := len(*p) - 1; i >= 1; i-- {
		if (*p)[i].x1 == (*p)[i-1].x1 &&
			(*p)[i].x2 == (*p)[i-1].x2 &&
			(*p)[i].y1 == (*p)[i-1].y1 &&
			(*p)[i].y2 == (*p)[i-1].y2 &&
			(*p)[i].z1 == (*p)[i-1].z2 {
			(*p)[i-1].x2 = (*p)[i].x2
			(*p)[i-1].y2 = (*p)[i].y2
			(*p)[i-1].z2 = (*p)[i].z2
			*p = append((*p)[:i], (*p)[i+1:]...)
		}
	}

	fmt.Println("compact:", orig, "->", len(*p))
}

func (p *Space) exec(inst string) {
	var flag string
	var x1, x2, y1, y2, z1, z2 int
	fmt.Sscanf(inst, "%s x=%d..%d,y=%d..%d,z=%d..%d",
		&flag, &x1, &x2, &y1, &y2, &z1, &z2)

	if x2 < x1 {
		x1, x2 = x2, x1
	}
	if y2 < y1 {
		y1, y2 = y2, y1
	}
	if z2 < z1 {
		z1, z2 = z2, z1
	}

	c := cube{x1, y1, z1, x2 + 1, y2 + 1, z2 + 1}

	// find all intersecting points
	xs := []int{c.x1, c.x2}
	ys := []int{c.y1, c.y2}
	zs := []int{c.z1, c.z2}

	intersects := make([]cube, 0, len(*p))
	for i := len(*p) - 1; i >= 0; i-- {
		d := (*p)[i]
		if c.Intersects(d) {
			xs = append(xs, d.x1, d.x2)
			ys = append(ys, d.y1, d.y2)
			zs = append(zs, d.z1, d.z2)
			*p = append((*p)[:i], (*p)[i+1:]...)
			intersects = append(intersects, d)
		}
	}

	if len(intersects) > 0 {
		xs = sortAndUniq(xs...)
		ys = sortAndUniq(ys...)
		zs = sortAndUniq(zs...)
		fmt.Println("xs", len(xs), "ys", len(ys), "zs", len(zs), len(xs)*len(ys)*len(zs))
		for k := 0; k < len(zs)-1; k++ {
			for j := 0; j < len(ys)-1; j++ {
				for i := 0; i < len(xs)-1; i++ {
					t := cube{xs[i], ys[j], zs[k], xs[i+1], ys[j+1], zs[k+1]}

					// if off and in new cube, skip
					if flag == "off" && t.In(c) {
						continue
					}

					// otherwise check if it's in an existing cube
					_b := t.In(c)
					if !_b {
						for _, v := range intersects {
							if t.In(v) {
								_b = true
								break
							}
						}
					}
					if _b {
						*p = append(*p, t)
					}
				}
			}
		}
	} else {
		*p = append(*p, c)
	}
}

func sortAndUniq(xs ...int) []int {
	sort.Ints(xs)
	for i := len(xs) - 1; i >= 1; i-- {
		if xs[i] == xs[i-1] {
			xs = append(xs[:i], xs[i+1:]...)
		}
	}
	return xs
}

type Plane []rect

type rect struct {
	x1, y1, x2, y2 int
}

type Space []cube

type cube struct {
	x1, y1, z1, x2, y2, z2 int
}

func (r *rect) Area() int64 {
	return int64(r.x2-r.x1) * int64(r.y2-r.y1)
}

func (c *cube) Volume() int64 {
	return int64(c.x2-c.x1) * int64(c.y2-c.y1) * int64(c.z2-c.z1)
}

func (r *rect) In(s rect) bool {
	return r.x1 >= s.x1 &&
		r.x2 <= s.x2 &&
		r.y1 >= s.y1 &&
		r.y2 <= s.y2
}

func (c *cube) In(d cube) bool {
	return c.x1 >= d.x1 &&
		c.x2 <= d.x2 &&
		c.y1 >= d.y1 &&
		c.y2 <= d.y2 &&
		c.z1 >= d.z1 &&
		c.z2 <= d.z2
}

func (r *rect) Intersects(s rect) bool {
	xl := s.x1
	if r.x1 > xl {
		xl = r.x1
	}
	xr := s.x2
	if r.x2 < xr {
		xr = r.x2
	}
	yu := s.y1
	if r.y1 > yu {
		yu = r.y1
	}
	yd := s.y2
	if r.y2 < yd {
		yd = r.y2
	}
	return xl < xr && yu < yd
}

func (c *cube) Intersects(d cube) bool {
	xmin := d.x1
	if c.x1 > xmin {
		xmin = c.x1
	}
	xmax := d.x2
	if c.x2 < xmax {
		xmax = c.x2
	}
	ymin := d.y1
	if c.y1 > ymin {
		ymin = c.y1
	}
	ymax := d.y2
	if c.y2 < ymax {
		ymax = c.y2
	}
	zmin := d.z1
	if c.z1 > zmin {
		zmin = c.z1
	}
	zmax := d.z2
	if c.z2 < zmax {
		zmax = c.z2
	}
	return (xmin < xmax && ymin < ymax) ||
		(xmin < xmax && zmin < zmax) ||
		(ymin < ymax && zmin < zmax)
}