Go
Well... I was about to dive into bin packing and stuff. I started by pruning the obvious candidates (those which can fit all the shapes one next to the other, without more computation) so save CPU time for the real stuff. I ran my code on the real input just to see and... what to do mean there are no candidate left? I write the number of obvious boys into the website's input box, just to check and... Ah. I understand why people on reddit said they felt dirty x)
Anyway the code:
day12.go
package main
import (
"aoc/utils"
"fmt"
"slices"
"strconv"
"strings"
)
type shape [3][3]bool
func parseShape(input chan string) shape {
// remove the header
_ = <-input
sh := shape{}
idx := 0
for line := range input {
if line == "" {
break
}
row := [3]bool{}
for idx, c := range []rune(line) {
if c == '#' {
row[idx] = true
}
}
sh[idx] = row
idx++
}
return sh
}
func (sh shape) usedArea() int {
sum := 0
for _, row := range sh {
for _, cell := range row {
if cell {
sum++
}
}
}
return sum
}
type regionConstraints struct {
width, height int
shapes []int
}
func parseRegionConstraint(line string) (rc regionConstraints) {
parts := strings.Split(line, ":")
dims := strings.Split(parts[0], "x")
rc.width, _ = strconv.Atoi(dims[0])
rc.height, _ = strconv.Atoi(dims[1])
shapes := strings.Fields(parts[1])
rc.shapes = make([]int, len(shapes))
for idx, shape := range shapes {
rc.shapes[idx], _ = strconv.Atoi(shape)
}
return rc
}
type problem struct {
shapes []shape
constraints []regionConstraints
}
func newProblem(input chan string) problem {
shapes := make([]shape, 6)
for idx := range 6 {
shapes[idx] = parseShape(input)
}
regionConstraints := []regionConstraints{}
for line := range input {
rc := parseRegionConstraint(line)
regionConstraints = append(regionConstraints, rc)
}
return problem{shapes, regionConstraints}
}
func (pb *problem) pruneRegionsTooSmall() {
toPrune := []int{}
for idx, rc := range pb.constraints {
availableArea := rc.height * rc.width
neededArea := 0
for shapeId, count := range rc.shapes {
neededArea += pb.shapes[shapeId].usedArea() * count
if neededArea > availableArea {
toPrune = append(toPrune, idx)
break
}
}
}
slices.Reverse(toPrune)
for _, idx := range toPrune {
pb.constraints = slices.Delete(pb.constraints, idx, idx+1)
}
}
func (pb *problem) pruneObviousCandidates() int {
toPrune := []int{}
for idx, rc := range pb.constraints {
maxShapePlacements := (rc.width / 3) * (rc.height / 3)
shapeCount := 0
for _, count := range rc.shapes {
shapeCount += count
}
if maxShapePlacements >= shapeCount {
toPrune = append(toPrune, idx)
}
}
slices.Reverse(toPrune)
for _, idx := range toPrune {
pb.constraints = slices.Delete(pb.constraints, idx, idx+1)
}
return len(toPrune)
}
func stepOne(input chan string) (int, error) {
pb := newProblem(input)
pb.pruneRegionsTooSmall()
obviousCandidates := pb.pruneObviousCandidates()
fmt.Println(pb)
fmt.Println(obviousCandidates)
return 0, nil
}
func stepTwo(input chan string) (int, error) {
return 0, nil
}
func main() {
input, err := utils.DownloadTodaysInputFile()
if err != nil {
_ = fmt.Errorf("error fetching the input: %v", err)
}
utils.RunStep(utils.ONE, input, stepOne)
utils.RunStep(utils.TWO, input, stepTwo)
}