blob: a9bb0ffccc1a5194f39841a4e0eabd7526c73832 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
|
;;;; aoc-2022-7.lisp
(defpackage #:aoc/2022/7
(:use #:cl)
(:import-from #:str
#:words)
(:import-from #:alexandria
#:appendf))
(in-package #:aoc/2022/7)
(defclass dir ()
((name
:initarg :name
:accessor name
:initform ""
:type string
:documentation "Name of the directory.")
(children
:initarg :children
:accessor children
:initform nil
:type list
:documentation "Direct children.")
(parent
:initarg :parent
:accessor parent
:type dir
:documentation "Parent directory.")
(size
:initarg :size
:initform 0
:accessor size
:type fixnum
:documentation "Directory size."))
(:documentation "Directory class."))
(defclass file ()
((name
:initarg :name
:accessor name
:initform ""
:type string
:documentation "Filename.")
(size
:initarg :size
:accessor size
:initform 0
:type fixnum
:documentation "File size."))
(:documentation "Representation of a file"))
(defparameter *max-size* 70000000)
(defparameter *needed-space* 30000000)
(defvar *part1-test* "$ cd /
$ ls
dir a
14848514 b.txt
8504156 c.dat
dir d
$ cd a
$ ls
dir e
29116 f
2557 g
62596 h.lst
$ cd e
$ ls
584 i
$ cd ..
$ cd ..
$ cd d
$ ls
4060174 j
8033020 d.log
5626152 d.ext
7214296 k")
(defmethod find-child ((dir dir) child)
(declare (type string child))
(find child (children dir)
:test (lambda (ch dir)
(string= ch (name dir)))))
;; (defmethod print-object ((dir dir) stream)
;; (format stream "~a~%~{~T~a~}" (name dir) (children dir)))
(defmethod print-object ((dir dir) stream)
(format stream "#<DIR ~a>" (name dir)))
(defmethod print-object ((file file) stream)
(format stream "#<FILE ~a>" (name file)))
(defun parse-command (line last-dir tree)
"Parse lines that start with '$', there are three possible outcomes:
cd [directory] -> Return an object of type dir named after DIRECTORY
cd .. -> Return LAST-DIR's parent
ls -> Return LAST-DIR"
(declare (type string line))
(let ((line* (subseq line 2))) ; remove "$ "
(destructuring-bind (command &optional dir) (words line*)
(if (string= command "cd")
(if (string= dir "..")
(parent last-dir)
(if (string= dir "/")
tree
(find-child last-dir dir)))
last-dir))))
(defun parse-directory-children (line last-dir)
"Parse LINE as output to the ls command. It may return objects of type DIR or FILE."
(declare (type string line))
(destructuring-bind (type name) (words line)
(if (string= type "dir")
(make-instance 'dir :name name :parent last-dir)
(make-instance 'file :name name :size (parse-integer type)))))
;; Does not work
(defun parse-line (line last-dir tree)
"Parse LINE, executing commands or adding children to LAST-DIR. Return the next directory (that may be changed by a 'cd' command)."
(declare (type string line) (type dir last-dir))
(if (char= (aref line 0) #\$)
(parse-command line last-dir tree)
(let ((child (parse-directory-children line last-dir)))
(push child (children last-dir))
last-dir)))
(defun parse-input (&optional (stream *standard-input*))
"Parse all of the lines in STREAM."
(let* ((tree (make-instance 'dir :name "/"))
(last-dir tree))
(loop :for line := (read-line stream nil)
:while (not (null line))
:do (setf last-dir (parse-line line last-dir tree)))
tree))
(defun part1% (stream)
(let ((tree (parse-input stream))
(result nil))
(labels ((mapdir (f)
(mapcar (lambda (c)
(typecase c
(dir (incf (size f) (mapdir c)))
(file (incf (size f) (size c)))))
(children f))
(when (< (size f) 100000)
(push f result))
(size f)))
(mapdir tree)
(loop :for dir :in result
:sum (size dir)))))
(defun part1-test ()
(with-input-from-string (stream *part1-test*)
(part1% stream)))
(defun part1 ()
(with-open-file (stream #p"input-7")
(part1% stream)))
(defun part2% (stream)
(let ((tree (parse-input stream)))
(labels ((mapsize (dir)
(mapcar (lambda (c)
(typecase c
(dir (incf (size dir) (mapsize c)))
(file (incf (size dir) (size c)))))
(children dir))
(size dir))
(filter-dirs (dir)
(let ((result nil))
(loop :for c :in (children dir)
:when (eq (type-of c) 'dir)
:do (progn
(push (size c) result)
(alexandria:appendf result (filter-dirs c))))
result)))
(mapsize tree)
(let* ((free-space (- *max-size* (size tree)))
(space-to-free (- *needed-space* free-space))
(sizes (sort (filter-dirs tree) #'>))
(last-size 0))
(loop :for size :in sizes
:when (< size space-to-free)
:return last-size
:do (setf last-size size))))))
(defun part2-test ()
(with-input-from-string (stream *part1-test*)
(part2% stream)))
(defun part2 ()
(with-open-file (stream #p"input-7")
(part2% stream)))
|
