2022/go/day07/day07.go

   1 package day07
   2
   3 import (
   4         "strings"
   5
   6         "adventofcode2022/utils"
   7 )
   8
   9 type dir struct {
  10         name   string
  11         files  map[string]int
  12         subdir map[string]*dir
  13         parent *dir
  14         size   int
  15 }
  16
  17 func Part1(input string) int {
  18         root := dir{name: "/", files: map[string]int{}, subdir: map[string]*dir{}, parent: nil}
  19         root.parse(input)
  20         sum := 0
  21         find_dirs_part1(&root, 100000, &sum)
  22         return sum
  23 }
  24
  25 func Part2(input string) int {
  26         root := dir{name: "/", files: map[string]int{}, subdir: map[string]*dir{}, parent: nil}
  27         root.parse(input)
  28         unused := 70000000 - root.size
  29         need := 30000000 - unused
  30         dir_size := 0
  31         find_dirs_part2(&root, need, &dir_size)
  32         return dir_size
  33 }
  34
  35 func find_dirs_part1(d *dir, size int, sum *int) {
  36         // recurse into subdir
  37         for _, subdir := range d.subdir {
  38                 if (subdir.size) <= size {
  39                         *sum += subdir.size
  40                 }
  41                 find_dirs_part1(subdir, size, sum)
  42         }
  43 }
  44
  45 func find_dirs_part2(d *dir, size int, sum *int) {
  46         // recurse into subdir
  47         for _, subdir := range d.subdir {
  48                 if (subdir.size) >= size && (*sum == 0 || (subdir.size) < *sum) {
  49                         *sum = subdir.size
  50                 }
  51                 find_dirs_part2(subdir, size, sum)
  52         }
  53 }
  54
  55 func (root *dir) parse(input string) {
  56         c := root
  57
  58         for _, line := range strings.Split(input, "\n") {
  59                 pieces := strings.Split(line, " ")
  60                 if pieces[0] == "$" {
  61                         if pieces[1] == "cd" {
  62                                 if pieces[2] == ".." {
  63                                         c = c.parent
  64                                 } else if pieces[2] == "/" {
  65                                         c = root
  66                                 } else {
  67                                         c = c.addDirectoryIfMissing(pieces[2])
  68                                 }
  69                         } else if pieces[1] == "ls" {
  70                                 // no need to do anything
  71                         } else {
  72                                 panic("oops")
  73                         }
  74                 } else if pieces[0] == "dir" {
  75                         c.addDirectoryIfMissing(pieces[1])
  76                 } else {
  77                         c.addFileIfMissing(pieces[1], utils.MustAtoi(pieces[0]))
  78                 }
  79         }
  80 }
  81
  82 func (d *dir) addDirectoryIfMissing(name string) *dir {
  83         t, ok := d.subdir[name]
  84         if !ok {
  85                 t = &dir{
  86                         name:   name,
  87                         files:  map[string]int{},
  88                         subdir: map[string]*dir{},
  89                         parent: d,
  90                 }
  91                 d.subdir[name] = t
  92         }
  93         return t
  94 }
  95
  96 func (d *dir) addFileIfMissing(name string, size int) {
  97         t, ok := d.files[name]
  98         if ok {
  99                 if t != size {
 100                         panic("oops")
 101                 }
 102         } else {
 103                 current := d
 104                 d.files[name] = size
 105
 106                 for current.name != "/" {
 107                         current.size += size
 108                         current = current.parent
 109                 }
 110                 current.size += size
 111         }
 112 }