Come ogni anno, anche quest’anno si tiene la Advent of Code, che consiste nel risolvere delle challenges di programmazione. Ci sono due chal per ogni giorno.
Qui il sito ufficiale:
https://adventofcode.com/2024/
Chi vuole partecipare è invitato a condividere le soluzioni a seguire . Io quest’anno ho deciso di farne poche (quelle iniziali), in Emacs-Lisp.
Soluzione del primo giorno
Parte 1
(defun read-input (file)
(find-file-noselect file)
(with-current-buffer (get-buffer (get-buffer-create "input.txt"))
(buffer-string)
)
)
(defun solve-pt1 ()
(let* ((input (split-string (read-input "/home/leo/projects/PROGRAMMING/AoC/2024/01/input.txt") "\n"))
(l1 nil)
(l2 nil)
(result 0)
)
;; read lists l1 and l2
(mapcar
(lambda (entry)
(let* ((l (split-string entry " "))
)
(when (>= (length l) 4)
(push (string-to-number (nth 0 l)) l1)
(push (string-to-number (nth 3 l)) l2)
)
)
)
input)
(sort l1 #'<)
(sort l2 #'<)
;; compute differences
(dotimes (i (length l1))
(setq result (+ result (abs (- (nth i l1) (nth i l2)))))
)
(message "Final result: %d" result)
nil
)
)
Parte 2
(defun solve-pt2 ()
(let* ((input (split-string (read-input "/home/leo/projects/PROGRAMMING/AoC/2024/01/input.txt") "\n"))
(l1 nil)
(l2 nil)
(result 0)
)
;; read lists l1 and l2
(mapcar
(lambda (entry)
(let* ((l (split-string entry " "))
)
(when (>= (length l) 4)
(push (string-to-number (nth 0 l)) l1)
(push (string-to-number (nth 3 l)) l2)
)
)
)
input)
(mapcar
(lambda (elem)
(setq result (+ result (* elem (cl-count elem l2))))
)
l1)
(message "Final result: %d" result)
nil
)
)
Codice molto ripetuto tra le due chal. Ho perso un po’ di tempo perché non mi ricordavo che la add-to-list non ti aggiunge l’elemento se è già in cima alla lista, mentre la push lo aggiunge comuqnue.
Una cosa bella di queste challenges infatti è che ti mettono di fronte problemi abbastanza concreti in cui testare le proprie abilità nell’utilizzo di un linguaggio di programmazione.
Carina come soluzione (solo rispetto se riesci a farlo in elisp), purtroppo per quanto ami emacs non conosco bene questo linguagio, solo un paio di cose a colpo d’occhio:
dotimes mi sembra un pò rischioso, le liste in lisp sono ad accesso sequenziale e quello combinato con nth è un O(n²), potresti usare cl-mapcar cosi da poter “mappare” una funzione su liste contemporaneamente, qualsosa del tipo (cl-mapcar #'- '(2 9 8) '(1 2 3)).Il primo giorno l’ho implementato pure io in lisp (clojure), posto solo la seconda parte per far vedere un pattern molto interessante.
(def input
(->> "resources/day1.txt"
io/reader
line-seq
(map (partial re-seq #"\d+"))
(apply (partial map vector))
(map #(map parse-long %))
(map sort)))
(defn part-2 [data]
(let [occurrences
(->> (second data)
(partition-by identity)
(map #(vector (first %) (count %)))
(into {}))]
(reduce
(fn [acc el]
(+ acc (* el (get occurrences el 0)))) 0 (first data))))
La parte che interessante è la funzione partition-by identity, la funzione è abbastanza intuitiva, partiziona la collezzione che gli passi in base ad una funzione che gli fornisci, se usata in combinazione con identity ha l’effetto di partizionare in base all’uguaglianza.
(partition-by identity [1 2 1 1 4 3 3]) ; => '((1 1 1) '(2) '(4) '(3 3)))
È una tecnica molto utile, utlizzabile in qualsiasi linguaggio che fornisce queste funzioni.
In questo caso io l’ho utilizzata per trovare tutti gli elementi distinti ed il loro conteggio e costruire una hashmap per il lookup e mantenere la complessità sul O(n).
Ottimi consigli, per il secondo punto qualcosa del genere:
(cl-reduce '+ (cl-mapcar #'abs (cl-mapcar #'- '(1 9 8) '(2 2 3))))
Da capire come combinare quelle due chiamate a cl-mapcar in una sola alla funzione composta tra abs e il meno
partition by crea classi di uguaglianza rispetto alla funzione? Ovvero mappa due input x, y nello stesso gruppo se hanno lo stesso output rispetto alla funzione f(x) = f(y)?
Figo come approccio
Puoi combinare il tutto con un lamda:
(cl-reduce '+ (cl-mapcar (lambda (x y) (abs (- x y))) '(1 9 8) '(2 2 3)))
Diciamo di si, dipende dall’implementazione, nel caso di clojure usando identity funziona, ma con altre funzioni può essere controintuitivo.
(defn rem-by [n]
( fn [x] (mod x n)))
(partition-by (rem-by 2) [1 2 3 4 5 6]) ; => '((1) (2) (3) (4) (5) (6))
Che di certo non è quello che si aspetta, mentre con identity controlla se effettivamente viene generato un nuovo valore.
Qui ogni chiamata genera un valore “nuovo” rispetto a quello in input.
Per fare l’operazione che dici tu c’è la funzione group-by:
(group-by (rem-by 2) [1 2 3 4 5 6)) ; => { 0 [ 2 4 6] 1 [ 1 3 5]}
(group-by (rem-by 3) [1 2 3 4 5 6)) ; => { 0 [ 3 6] 1 [ 1 4] 2 [2 5] }
(group-by identity [1 1 1 2 4 4 2]) ; => {1 [ 1 1 1] 2 [ 2 2] 4 [4 4] }
In altri linguaggi non c’è questa differenza, andando a memoria in elixir, ma non ne sono certo.
Queste cose mi ricordano troppo il corso di matematica discreta xD
Ho appena completato il giorno 6, la parte 1 molto semplice la 2 richiede qualche ottimizzazione su cui si può ragionare.
Per ricapitolare un pò il problema, si ha una mappa con degli ostacoli ed un personaggio che si muove sulla mappa con regole semplici.
La parte 1 chiede di trovare su quante caselle differenti entra il personaggio prima di lasciare la mappa (non ci sono cicli e di certo il personaggio esce dopo un po’).
Io l’ho implementato così:
(def input
(->> "resources/day6.txt"
io/reader
line-seq
(mapv vec)))
(defn get-start-pos [data]
(reduce
#(when (= \^ (get-in data %2)) (reduced %2))
nil
(for [i (range (count data)) j (range (count (first data)))]
[i j])))
(def next-direction
{:north :east
:east :south
:south :west
:west :north})
(defn move [[x y] dir]
(case dir
:north [(dec x) y]
:east [x (inc y)]
:south [(inc x) y]
:west [x (dec y)]))
(defn seen [data]
(loop [pos (get-start-pos data) dir :north visited #{pos}]
(let [next (move pos dir) spot (get-in data next)]
(case spot
nil visited
\# (recur pos (next-direction dir) visited)
\^ (recur next dir (conj visited next))
\. (recur next dir (conj visited next))))))
(defn part-1 [data]
(count (seen data)))
(println (part-1 input))
Di base ho trasformato il testo di input in una matrice di caratteri per poter sfruttare l’accesso diretto in O(1), poi faccio muovere il personaggio secondo le regole date e mi salvo le posioni in un set, così si scartano automaticamente i duplicati.
Alla fine conto gli elementi nel set ed è fatta.
Per la seconda parte ho trovato un paio di ottimizzazioni carine, sono andato di brute force (si usa più di quanto ci si aspetti in queste competizioni) ma ho cercato di evitare quante più operazioni possibili.
Il problema ora chiede di trovare in quanti modi è possibile posizionare un singolo ostacolo per far andare in loop il personaggio sulla mappa.
Le ottimizzazioni le accenno nel blocco nascosto si seguito:
(defn loop? [start start-dir board]
(loop [pos start
dir start-dir
seen #{}]
(let [pos' (move pos dir)
spot (get-in board pos')]
(if (seen [pos' dir])
true
(case spot
\# (recur pos (next-direction dir) (conj seen [pos dir]))
(\. \^) (recur pos' dir seen)
nil false)))))
(defn part-2 [data]
(let [path (seen data) start (get-start-pos data)
loop? (partial loop? start :north)
boards (for [p path :when (not= p start)] (assoc-in data p \#))]
(->> boards
(filter loop?)
count)))
(println (part-2 input))
La prima ottimizzazione è stata quella di non provare a posizionare l’ostacolo in ogni posizione ma solo in quelle in cui il personaggio passa effettivamente, dato che possiamo posizionare un solo blocco di sicuro deve stare su una delle caselle individuate nella parte 1.
Da qui prendo e genero tutte le possibili mappe (o come le ho chiamate nel codice boards) aggiungendo l’ostacolo sul percorso (evitando la casella di inizio perchè così vuole il problema).
Per ognuna di queste board faccio muovere il personaggio, se esce fuori dalla mappa scarto la board, altrimenti se entra in un loop la board è valida e quindi la conteggio, come al solito il problema vuole il numero non la configurazione.
Fino a qua tutto ok però c’è da notare che per capire se sono in un ciclo servono informazioni su posizione e direzione, non basta sapere che sono già passato in una casella, ma ci devo passare due volte con la medesima direzione per entrare in un ciclo.
Per dire se passo per la cella (2, 3) andando in direzione nord allora non genero un ciclo se ci ripasso mentre sono diretto vero ovest:
A B
's' := starting point
'<' or '^' := movement direction
+--------s s--<--+
| ^ | |
| | | |
+--------+ +-----+
Spero si capisca, la mia preview è leggermente "sminchiata"
In questo caso A non genera un ciclo (sempre considerando le regole di movimento del personaggio) perchè possiamo proseguire dritto:
A
^
|
+--------s
| |
| |
+--------+
Mentre in B entriamo di sicuro in un ciclo.
Per tornare all’ottimizzazione salvare tutte le terne (x y direction) è un pò costoso quindi ho cercato di capire se potevo evitarmene un paio.
Quello che ho notato è che per entrare in un ciclo devo prima incontrare l’ostacolo e poi ruotare il personaggio nella direzione in cui inizia il ciclo, quindi anzichè salvarmi tutte le terne (x y dir) posso restringere il campo alle (x y dir) tali che board[x][y] siano un ostacolo.
Se incontro un ostacolo per la seconda volta allora sono in un loop.
Con questa ottimizzazione la mia ram mi ha ringraziato non poco, questa era la fonte di overhead più grande di tutte dato che c’erano un sacco di “copie” fatte in background per mantenere l’immutabilità (e mi sono rifiutato di usare strutture dati mutabili).
Ultima ottimizzazzione, make threads go brr.
Dato che le boards sono generate in modo indipendente e possono essere verificate in modo indipendente le posso controllare in parallelo! (nel mio caso sono sulle 5000).
Dato che è tutto immutabile la soluzione è stata banale in clojure
(defn part-2-parallel [data]
(let [path (path data) start (get-start-pos data)
loop? (partial loop? start :north)
boards (for [p path :when (not= p start)] (assoc-in data p \#))]
(->> boards
(pmap loop?)
(filter true?)
count)))
(part-2-parallel input)
Lanciato su 16 thread ha trovato la soluzione in meno della metà del tempo, quindi presumo che abbia uno speedup ed efficenza non siano proprio il massimo, probabilmente 16 thread sono troppi.