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
|
#+title: 2022 advent of code
#+author: Aryadev Chavali
#+description: Description
#+date: 2023-06-26
Doing this ridiculously late. Insert joke about Christmas in the summertime.
* Problem 1
:PROPERTIES:
:header-args:lisp: :session problem_1 :tangle puzzle-1.lisp
:END:
Simple summing of sublists problem. Not very difficult, though found
out that Common Lisps semantics around parsing are kinda weird.
** Round 1
*** Getting input and defining the separator
To get input, use ~uiop:read-file-string~ (comes with ASDF,
quicklisp, so in most common lisp systems).
#+begin_src lisp
(defvar input (uiop:read-file-string "1-input"))
#+end_src
Each "bag" in the data is separated by two newlines, so let's define
that as a constant.
#+begin_src lisp
(defparameter *sep (format nil "~%~%"))
#+end_src
*** Parse procedure for any one bag
A bag is a set of lines of numbers representing the food in that bag.
So all we need to do, given an input bag, is to convert each line into
an integer. We can use ~with-input-from-string~ to leverage
~read-line~:
#+begin_src lisp
(defun parse-entity (inp)
(with-input-from-string (s inp)
(loop for line = (read-line s nil)
while line
collect (parse-integer line))))
#+end_src
*** Recursive procedure to parse all input
Each bag is separated by ~*sep~, so all we need to do is:
+ search for the next separator in the input
+ parse it
+ cons what we made with a recursive call for the rest of the input
#+begin_src lisp
(defun get-lists (input)
(let* ((pos (search *sep input))
(converted (parse-entity (subseq input 0 pos))))
(if (null pos)
(list converted)
(cons converted
(get-lists (subseq input (+ pos 2)))))))
#+end_src
*** Get sums and sort them
To sum each bag, we just need to perform a reduce on each list by
~#'+~. To sort we can use the inbuilt ~sort~ function which takes an
ordering function. Easy stuff.
#+begin_src lisp
(defvar sums (sort (mapcar (lambda (lst) (reduce #'+ lst)) (get-lists input))
#'>))
#+end_src
*** Finish the round
We want the largest sum, which is literally the top of the sorted
list.
#+begin_src lisp
(format t "Round 1: ~a~%" (car sums))
#+end_src
** Round 2
Not actually that much harder, we want the top 3 largest bags. This
is really easy, as we've already sorted the list so we just need the
first 3 elements! For this I use a ~destructuring-bind~ just to be
fancy, though I could easily use a ~subseq~ instead.
#+begin_src lisp
(destructuring-bind (first second third &rest _) sums
(format t "Round 2: ~a,~a,~a:>~a" first second third
(+ first second third)))
#+end_src
* Problem 2
Rock paper scissors simulation, but very basic. You're essentially
given a log of rounds and their outcomes, and you have to interpret
the data and produce a scoring (based on an arbitrary metric). Pretty
simple once again.
* Problem 3
Kinda involved mostly because I don't have a good understanding of
Common Lisps core library. More involved parsing routine in order to
find shared elements between sets. Round 2 extends this to 3 sets,
but some interesting extensions to the problem include going to
arbitrary n set inclusion testing.
* Problem 4
Checking if you know how bounds work, testing if
$[a,b]\subset{[c,d]}$. Pretty easy maths.
* Problem 5
Basically the reason I started making this document, as it seems to be
the first really involved problem. I need to make a stack machine,
interpreting an initial layout of memory and an algorithm to perform
on the machine. Very interesting.
Turns out its pretty simple: just the parsing of the initial state at
the top of an input was a bit weird. The actual command parser was
very simple as it had a static format, and we could do figure out the
command at parse time.
* Problem 6
Just looking for the first 4 length sequence of unique characters in a
stream. Way easier than I expected, closer to problem 1 than 5.
* Problem 7
I'm stumped here, and I feel it's because of common lisp. Tree
structures with back references to parents are essentially impossible
because Lisp hasn't really got the concept of a pointer. I need to
find a way to emulate or construct directory structures in a recursive
manner in Lisp.
|
