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.
83 lines
2.1 KiB
83 lines
2.1 KiB
#+title: Solution to p18 |
|
|
|
First parse with regex to make into a list |
|
#+begin_src emacs-lisp :results none |
|
(require 'dash) |
|
(with-temp-buffer |
|
(insert-file-contents "input") |
|
(goto-char (point-min)) |
|
(replace-regexp "\\([0-9]+\\),\\([0-9]+\\)" "(\\1 \\2)") |
|
(goto-char (point-min)) |
|
(insert "(setq data '(") |
|
(goto-char (point-max)) |
|
(insert "))") |
|
(eval-buffer)) |
|
(setq width 71 ;71 |
|
height 71 |
|
start-pos '(0 0) |
|
end-pos (list (- width 1) (- height 1))) |
|
(setq full-data data) |
|
#+end_src |
|
Now define the usual helper functions |
|
#+begin_src emacs-lisp :results none |
|
(defun neighbour (p dir) |
|
"Returns the neighbour to P in the direction DIR" |
|
(list (+ (car p) (car dir)) |
|
(+ (cadr p) (cadr dir)))) |
|
|
|
(defun within-bounds-p (p) |
|
(let ((x (car p)) |
|
(y (cadr p))) |
|
(and (>= x 0) (< x width) |
|
(>= y 0) (< y height)))) |
|
|
|
(defun corrupted-p (p) |
|
(-contains-p data p)) |
|
|
|
(defun visited-p (p) |
|
(-contains-p (-map #'car distances) p)) |
|
|
|
(defun admissible-p (p) |
|
(and (within-bounds-p p) |
|
(not (corrupted-p p)) |
|
(not (visited-p p)))) |
|
#+end_src |
|
|
|
Define a generic bisect function |
|
#+begin_src emacs-lisp :results none |
|
(defun bisect (pred begin end) |
|
"returns the first n between BEGIN and END such that PRED n is nil" |
|
(if (eq (1+ begin) end) end |
|
(let ((mid (/ (+ begin end) 2))) |
|
(if (funcall pred mid) (bisect pred mid end) |
|
(bisect pred begin mid))))) |
|
#+end_src |
|
|
|
Now solve the problem |
|
#+begin_src emacs-lisp |
|
(defun step (new-distances) |
|
(let ((radius (1+ (cdar new-distances))) |
|
(sphere (-map #'car new-distances))) |
|
(--map (cons it radius) (-filter #'admissible-p (-distinct (-mapcat (lambda (p) (--map (neighbour p it) ' ((1 0) (0 1) (-1 0) (0 -1)))) |
|
sphere)))))) |
|
|
|
(defun out-p (n) |
|
(let* ((data (-take n full-data)) |
|
(distances '(((0 0) . 0))) |
|
(new distances)) |
|
|
|
(while (setq new (step new)) |
|
(setq distances (-concat new distances))) |
|
(assoc end-pos distances))) |
|
|
|
;for part 1 |
|
(out-p 1024) |
|
|
|
;for part 2 |
|
(nth (- (bisect 'out-p 1024 (length full-data)) 1) full-data) |
|
#+end_src |
|
|
|
#+RESULTS: |
|
| 10 | 38 | |
|
|
|
|
|
|