commit f2e6be9fbc70096716423ead472538faa5156650
parent 6614890562975a2d5fe38315d0dd8cd745af12c2
Author: bsandro <email@bsandro.tech>
Date: Wed, 7 Dec 2022 08:40:05 +0000
Day 07 cleanup
Diffstat:
| M | day07/main.go | | | 139 | +++++++++++++++++++++++++++---------------------------------------------------- |
1 file changed, 47 insertions(+), 92 deletions(-)
diff --git a/day07/main.go b/day07/main.go
@@ -4,33 +4,19 @@ import (
"bufio"
"fmt"
"log"
+ "math"
"os"
- "sort"
- "strings"
"strconv"
+ "strings"
)
type Dir struct {
- Name string
- Size int
+ Name string
+ Size int
Parent *Dir
}
type Dirs []*Dir
-func (d Dirs) Len() int { return len(d) }
-func (d Dirs) Swap(i, j int) { d[i], d[j] = d[j], d[i] }
-func (d Dirs) Less(i, j int) bool { return d[i].Size > d[j].Size }
-func (d Dirs) String() string {
- var s string
- for _, dir := range d {
- s += dir.String() + "\n"
- }
- return s
-}
-
-func (dir Dir) String() string {
- return fmt.Sprintf("%s:%d", dir.Name, dir.Size)
-}
func main() {
if len(os.Args) > 1 {
@@ -44,50 +30,70 @@ func main() {
func day07(input_file string) {
fmt.Printf("day 07 input filename: %s\n", input_file)
+ var dirs Dirs
+ dirs.loadFile(input_file)
+
+ const sizeLimit = 100000
+ const fsSize = 70000000
+ const updSize = 30000000
+
+ totalSize := 0
+ delSize := math.MaxInt
+ clearSpace := updSize - fsSize + dirs.getRootSize()
+ for _, d := range dirs {
+ if d.Size < sizeLimit {
+ totalSize += d.Size
+ }
+ if d.Size >= clearSpace && d.Size < delSize {
+ delSize = d.Size
+ }
+ }
+ fmt.Printf("Part 1: %d\n", totalSize)
+ fmt.Printf("Part 2: %d\n", delSize)
+}
+
+func (dirs Dirs) getRootSize() int {
+ for _, dir := range dirs {
+ if dir.Name == "/" {
+ return dir.Size
+ }
+ }
+ return 0
+}
+func (dirs *Dirs) loadFile(input_file string) {
input, err := os.Open(input_file)
if err != nil {
log.Fatal(err)
}
defer input.Close()
- var dirs Dirs //[]*Dir
+
var cur *Dir = nil
scanner := bufio.NewScanner(input)
for scanner.Scan() {
in := scanner.Text()
+ // commands (cd, ls)
if in[0] == '$' {
- //fmt.Println("command", in)
cmd := strings.Split(in, " ")
- //fmt.Printf("cmd: %v\n", cmd)
- switch cmd[1] {
- case "cd":
+ if cmd[1] == "cd" {
if cmd[2] == ".." {
// won't work if we do "cd .." from /
cur = cur.Parent
} else {
dir := &Dir{
- Name: cmd[2],
- Size: 0,
+ Name: cmd[2],
+ Size: 0,
Parent: cur,
}
- dirs = append(dirs, dir)
+ *dirs = append(*dirs, dir)
cur = dir
}
- case "ls":
- // do nothing
}
- } else {
- sizeStr, _, has := strings.Cut(in, " ")
- if !has {
- log.Fatal("invalid input")
- }
- if sizeStr == "dir" {
- // ignore
- } else {
- size, err := strconv.Atoi(sizeStr)
- if err!=nil {
- log.Fatal(err)
- }
- for d:=cur; d!=nil; {
+ } else { // file listing
+ sizeStr, _, _ := strings.Cut(in, " ")
+ // we care only about files
+ if sizeStr != "dir" {
+ size, _ := strconv.Atoi(sizeStr)
+ for d := cur; d != nil; {
d.Size += size
d = d.Parent
}
@@ -97,55 +103,4 @@ func day07(input_file string) {
if err = scanner.Err(); err != nil {
log.Fatal(err)
}
-
- sort.Sort(dirs)
-
- const sizeLimit = 100000
- const fsSize = 70000000
- const updSize = 30000000
-
- totalSize := 0
- delSize := -1
- freeSpace := fsSize - dirs[0].Size
- clearSpace := updSize - freeSpace
- for _, d := range dirs {
- if d.Size < 100000 {
- totalSize += d.Size
- }
- if delSize == -1 {
- delSize = d.Size
- } else if d.Size >= clearSpace && d.Size < delSize {
- delSize = d.Size
- }
- }
- fmt.Printf("Part 1: %d\n", totalSize)
- fmt.Printf("Part 2: %d\n", delSize)
-
- //fmt.Printf("max: %d\n", getMaxSize(dirsFiltered, 100000))
-}
-
-func getMaxSize(dirs Dirs, size int) int {
- //fmt.Println("getMaxSize", size)
- //fmt.Println(dirs)
- maxSize := 0
- for i, d := range dirs {
- remSize := size - d.Size
- sumSize := d.Size
- var rem Dirs
- // filter all remaining folders to be less sized
- for j, d1 := range dirs {
- if d1.Size <= remSize && i!=j {
- rem = append(rem, d1)
- }
- }
- if len(rem) > 0 {
- //fmt.Printf("going down from %s (rem len %d)\n", d, len(rem))
- sumSize += getMaxSize(rem, remSize)
- }
- if sumSize > maxSize {
- maxSize = sumSize
- }
- }
- fmt.Println("return maxSize", maxSize)
- return maxSize
}
