You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
114 lines
3.7 KiB
114 lines
3.7 KiB
#+title: Solution to p12 |
|
This is the problem about fencing |
|
|
|
Load the file into a list of lines |
|
#+begin_src emacs-lisp :results none |
|
(require 'dash) |
|
(with-temp-buffer |
|
(insert-file-contents "input") |
|
(goto-char (point-min)) |
|
(replace-regexp "^" "\"") |
|
(goto-char (point-min)) |
|
(replace-regexp "$" "\"") |
|
(goto-char (point-min)) |
|
(insert "(setq data '(") |
|
(goto-char (point-max)) |
|
(insert "))") |
|
(eval-buffer)) |
|
#+end_src |
|
|
|
and split into a list of list of chars |
|
#+begin_src emacs-lisp :results none |
|
(setq data-chars (-map (lambda (str) (--map (string-to-char it) (split-string str "\\|.+" t))) |
|
data) |
|
height (length data-chars) |
|
width (length (car data-chars))) |
|
#+end_src |
|
|
|
#+begin_src emacs-lisp :results silent |
|
(defun acceptable-p (p) |
|
(let ((x (car p)) |
|
(y (cadr p))) |
|
(and (>= x 0) (>= y 0) (< x width) (< y height)) )) |
|
|
|
(defun neighbours (p) |
|
(let ((x (car p)) |
|
(y (cadr p))) |
|
(-map (lambda (q) (list (+ x (car q)) (+ y (cadr q)))) '((+1 0) (-1 0) (0 1) (0 -1))))) |
|
|
|
(defun acceptable-neighbours (p) |
|
(-filter #'acceptable-p (neighbours p))) |
|
|
|
(defun plant (p) |
|
(if (not (acceptable-p p)) ?. |
|
(nth (car p) (nth (cadr p) data-chars)))) |
|
#+end_src |
|
|
|
Collect all plants type and return a list of list of positions |
|
#+begin_src emacs-lisp :results none |
|
(setq plants (-distinct (-mapcat #'identity data-chars))) |
|
|
|
(setq groups (-map (lambda (pl) |
|
(-map #'cadr |
|
(--filter (eq (car it) pl) |
|
(-mapcat #'identity |
|
(-map-indexed (lambda (y l) (-map-indexed (lambda (x el) (list el (list x y))) l)) data-chars))))) |
|
plants)) |
|
#+end_src |
|
|
|
Now we need to split each group into contiguous regions |
|
#+begin_src emacs-lisp :results none |
|
(defun agglomerate (acc el) |
|
(let ((nbhs (acceptable-neighbours el))) |
|
(cons (-mapcat #'identity (cons (list el) (--filter (-intersection it nbhs) acc))) |
|
(--filter (not (-intersection it nbhs)) acc)))) |
|
|
|
(setq regions (--mapcat (-reduce-from #'agglomerate nil it) groups)) |
|
#+end_src |
|
|
|
We define auxiliary functions to get to the solution |
|
#+begin_src emacs-lisp :results none |
|
(defun count-fence (el) |
|
"This counts the number of sides of the fence around the element EL" |
|
(let ((i (plant el)) |
|
(pos el)) |
|
(length (--filter (not (eq i it)) (-map #'plant (neighbours pos)))))) |
|
|
|
(defun vertex-p (el dir) |
|
"This checks if there is a vertex in the direction DIR at the |
|
element EL. We need to avoid double-counting, so we return t |
|
only under appropriate circumstances (for instance on a concave |
|
angle, we only count the vertex attached to the element that |
|
shares only a vertex with the other region" |
|
(let* ((x (car el)) |
|
(y (cadr el)) |
|
(a (car dir)) |
|
(b (cadr dir)) |
|
(opposite (list (+ x a) (+ y b))) |
|
(adjh (list (+ x a) y)) |
|
(adjv (list x (+ y b)))) |
|
(or (and (not (eq (plant el) (plant adjh))) |
|
(not (eq (plant el) (plant adjv)))) |
|
(and (eq (plant el) (plant adjh)) |
|
(eq (plant el) (plant adjv)) |
|
(not (eq (plant el) (plant opposite))))))) |
|
|
|
(defun count-vertices (el) |
|
(length (-non-nil (--map (vertex-p el it) '((1 1) (1 -1) (-1 1) (-1 -1)))))) |
|
#+end_src |
|
|
|
The solution of part 1 is |
|
#+begin_src emacs-lisp |
|
(-reduce #'+ (--map (* (car it) (cdr it)) |
|
(-zip-pair (-map #'length regions) |
|
(-map (lambda (region) (-reduce #'+ (-map #'count-fence region))) regions)))) |
|
#+end_src |
|
The solution of part 2 is |
|
#+begin_src emacs-lisp |
|
(-reduce #'+ (--map (* (car it) (cdr it)) |
|
(-zip-pair (-map #'length regions) |
|
(-map (lambda (region) (-reduce #'+ (-map #'count-vertices region))) regions)))) |
|
#+end_src |
|
|
|
#+RESULTS: |
|
: 859494
|
|
|