78 lines
2.3 KiB
Racket
78 lines
2.3 KiB
Racket
#lang racket
|
|
|
|
(struct tree
|
|
(name parent type (size #:mutable) (children #:mutable))
|
|
#:transparent)
|
|
|
|
(define (read-input filename)
|
|
(define t (tree "/" #f 'dir #f '()))
|
|
(let lp ([current-dir t]
|
|
[lines (cdr (file->lines filename))])
|
|
(unless (null? lines)
|
|
(match (string-split (car lines))
|
|
[(list "$" "ls")
|
|
(lp current-dir (cdr lines))]
|
|
[(list "$" "cd" "..")
|
|
(lp (tree-parent current-dir) (cdr lines))]
|
|
[(list "$" "cd" name)
|
|
(let ([child (findf (lambda (x) (equal? name (tree-name x)))
|
|
(tree-children current-dir))])
|
|
(if child
|
|
(lp child (cdr lines))
|
|
(let ([child (tree name current-dir 'dir #f '())])
|
|
(set-tree-children! current-dir (cons child (tree-children current-dir)))
|
|
(lp child (cdr lines)))))]
|
|
[(list "dir" _)
|
|
(lp current-dir (cdr lines))]
|
|
[(list size name)
|
|
(let ([child (tree name current-dir 'file (string->number size) '())])
|
|
(set-tree-children! current-dir (cons child (tree-children current-dir)))
|
|
(lp current-dir (cdr lines)))])))
|
|
(compute-sizes! t)
|
|
t)
|
|
|
|
(define (compute-sizes! t)
|
|
(if (tree-size t)
|
|
(tree-size t)
|
|
(begin
|
|
(set-tree-size! t (apply + (map compute-sizes! (tree-children t))))
|
|
(tree-size t))))
|
|
|
|
(define (display-tree t (level 0) (out (current-output-port)))
|
|
(fprintf out "~a- ~a (~a, size=~a)~n"
|
|
(make-string (* 2 level) #\ )
|
|
(tree-name t)
|
|
(tree-type t)
|
|
(tree-size t))
|
|
(for ([child (sort (tree-children t) string<=? #:key tree-name)])
|
|
(display-tree child (+ 1 level) out)))
|
|
|
|
(define (file? t)
|
|
(eq? 'file (tree-type t)))
|
|
|
|
(define (directory? t)
|
|
(eq? 'dir (tree-type t)))
|
|
|
|
(define (all-directories t)
|
|
(define child-dirs (filter directory? (tree-children t)))
|
|
(append* child-dirs (map all-directories child-dirs)))
|
|
|
|
(define (part1 t)
|
|
(apply + (map tree-size
|
|
(filter (lambda (d) (< (tree-size d) 100000))
|
|
(all-directories t)))))
|
|
|
|
(define (part2 t)
|
|
(define unused-space (- 70000000 (tree-size t)))
|
|
(define required-space (- 30000000 unused-space))
|
|
(define dir-to-remove
|
|
(car (sort (filter (lambda (d) (>= (tree-size d) required-space))
|
|
(all-directories t))
|
|
<=
|
|
#:key (lambda (d) (tree-size d)))))
|
|
(tree-size dir-to-remove))
|
|
|
|
(module+ main
|
|
(define t (read-input "input"))
|
|
(displayln (part1 t))
|
|
(displayln (part2 t)))
|