#+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 |