aoc-2022/day07/solution.go

package day07

import (
	"fmt"
	"path/filepath"
	"strconv"
	"strings"
)

type Solver struct {
	dirCache map[string]*Dir
}

type Sizable interface {
	Size() int
	fmt.Stringer
}

type Dir struct {
	name     string
	contents []Sizable
}

func (d *Dir) Size() int {
	total := 0
	for _, c := range d.contents {
		total += c.Size()
	}
	return total
}

func (d *Dir) String() string {
	return fmt.Sprintf("%s (dir, size=%d) (%s)", d.name, d.Size(), d.contents)
}

type File struct {
	name string
	size int
}

func (f *File) Size() int {
	return f.size
}

func (f *File) String() string {
	return fmt.Sprintf("%s (file, size=%d)", f.name, f.Size())
}

func (s *Solver) ParseInput(input []string) {
	s.dirCache = make(map[string]*Dir)

	location := ""
	var currentDir *Dir

	for _, line := range input {
		tokens := strings.Split(line, " ")
		if tokens[0] == "$" {
			switch tokens[1] {
			case "cd":
				location = filepath.Clean(filepath.Join(location, tokens[2]))
			case "ls":
				if _, ok := s.dirCache[location]; !ok {
					s.dirCache[location] = &Dir{name: filepath.Base(location)}
				}
				currentDir, _ = s.dirCache[location]
			}
		} else {
			if tokens[0] == "dir" {
				name := tokens[1]
				dir := &Dir{name: name}
				s.dirCache[filepath.Join(location, name)] = dir
				currentDir.contents = append(currentDir.contents, dir)
			} else {
				size, _ := strconv.Atoi(tokens[0])
				currentDir.contents = append(currentDir.contents, &File{tokens[1], size})
			}
		}
	}
}

func (s *Solver) SolvePart1() any {
	const cutoffSize = 100000

	rootDir := s.dirCache["/"]

	dirsAtSize := getDirectoriesAtSize(rootDir, 0, cutoffSize)
	var total int
	for _, d := range dirsAtSize {
		total += d.Size()
	}

	return total
}

func (s *Solver) SolvePart2() any {
	const totalSpace = 70000000
	const neededFreeSpace = 30000000

	rootDir := s.dirCache["/"]
	additionalSpaceToFree := neededFreeSpace - (totalSpace - rootDir.Size())

	dirsAtSize := getDirectoriesAtSize(rootDir, additionalSpaceToFree, 0)
	minSize := totalSpace
	for _, d := range dirsAtSize {
		if d.Size() < minSize {
			minSize = d.Size()
		}
	}

	return minSize
}

func getDirectoriesAtSize(dir *Dir, minSize, maxSize int) []*Dir {
	dirs := make([]*Dir, 0)
	if (minSize == 0 || dir.Size() >= minSize) && (maxSize == 0 || dir.Size() <= maxSize) {
		dirs = append(dirs, dir)
	}
	for _, c := range dir.contents {
		if d, ok := c.(*Dir); ok {
			dirs = append(dirs, getDirectoriesAtSize(d, minSize, maxSize)...)
		}
	}
	return dirs
}