aoc2020 day23

aoc2020-day23.lisp

;;;; +----------------------------------------------------------------+
;;;; | Advent of Code 2020                                            |
;;;; +----------------------------------------------------------------+

(defpackage #:snippets/aoc2020/day23
  (:use #:cl)
  (:export
   #:day23))

(in-package #:snippets/aoc2020/day23)

(defstruct cups
  head
  length
  pointers
  lowest
  highest)

(defun circular (list)
  (let ((copy (copy-list list)))
    (nconc copy copy)))

(defun parse (input)
  (let ((head (circular input))
        (pointers (make-hash-table)))
    (setf (gethash (car head) pointers) head)
    (do ((sublist (cdr head) (cdr sublist)))
        ((eql sublist head))
      (setf (gethash (car sublist) pointers) sublist))
    (make-cups :head head
               :length (length input)
               :pointers pointers
               :lowest (reduce #'min input)
               :highest (reduce #'max input))))

(defun cmember (item cups)
  (gethash item (cups-pointers cups)))

(defun select-destination (cups three)
  (let ((needle (1- (car (cups-head cups)))))
    (loop
     (cond ((< needle (cups-lowest cups))
            (setf needle (cups-highest cups)))
           ((member needle three)
            (decf needle))
           (t
            (return (cmember needle cups)))))))

(defun move (cups)
  (let* ((three (loop repeat 3 collect (pop (cdr (cups-head cups)))))
         (dest (select-destination cups three)))
    (mapl (lambda (cons)
            (setf (gethash (car cons) (cups-pointers cups)) cons))
          three)
    (setf (cdr (last three)) (cdr dest))
    (setf (cdr dest) three)
    (pop (cups-head cups))
    cups))

(defun moves (cups n)
  (loop repeat n
        do (move cups)
        finally (return cups)))

(defun cups-after-1 (cups)
  (format nil "~{~A~}" (subseq (cmember 1 cups) 1 (cups-length cups))))

(defun crab-product (cups)
  (let ((after-1 (rest (cmember 1 cups))))
    (* (first after-1) (second after-1))))

(defun extend (input)
  (append input (loop for i from 10 to 1000000 collect i)))

(defun day23 (input)
  (list (cups-after-1 (moves (parse input) 100))
        (crab-product (moves (parse (extend input)) 10000000))))