aoc2022-10.lisp

;;; -*- Syntax: ANSI-Common-Lisp; Package: CL-USER -*-

;;; Author: Rainer Joswig, [email protected], 2022
;;; This code is written in portable Common Lisp.

; https://adventofcode.com/2022/day/10

;; This solution makes use of multiple dispatch and standard method combinations of CLOS.

(defparameter *input-10*
  (if (member :lispm *features*)
      (pathname "rjmbp:/Users/joswig/Lisp/aoc2022/input-10.text")
      (pathname "/Users/joswig/Lisp/aoc2022/input-10.text"))
  "The provided input file with the description of the stacks
 and the list of moves.")

;;; ================================================================
;;; Reading a program

; a program looks like:

; addx 13
; addx 4
; noop
; addx -1
; addx 5

; there are only two possible instructions: addx and noop.
; in this program an instruction is a list with akeyword symbol and its arg.

(defun read-program (file-or-stream)
  "Returns a vector of instructions. Each instruction is a list.
The instruction name is a keyword symbol."
  (if (or (stringp file-or-stream) (pathnamep file-or-stream))
      (with-open-file (stream file-or-stream)
        (read-program stream))
      (let ((*read-eval* nil)
            (*package* (find-package "KEYWORD")))
        (coerce
          (loop for instruction = (read file-or-stream nil nil)
                while instruction
                collect (ecase instruction
                          ((:noop) (list instruction))
                          ((:addx) (list instruction (read file-or-stream nil nil)))))
          'vector))))

;;; ================================================================
;;; The CPU10

(defun instruction-cycles (instruction)
  "Returns the number of CPU cycles for each instruction."
  (ecase instruction
    ((:addx) 2)
    ((:noop) 1)))

; The class for our CPU, which holds the various CPU related values, including the X register.

(defclass cpu10 ()
    ((trace               :initform   nil   :accessor cpu-trace-p     :initarg :trace               )  
     (program             :initform   #()   :accessor cpu-program     :initarg :program :type vector)
     (instruction-pointer :initform     0   :accessor cpu-instruction-pointer           :type integer)
     (instruction-cycles  :initform     0   :accessor cpu-instruction-cycles            :type integer)
     (register-x          :initform     1   :accessor cpu-register-x                    :type integer)
     (cycle               :initform     0   :accessor cpu-cycle                         :type integer)
     (cycle-state         :initform :halt   :accessor cpu-cycle-state                   :type symbol)
     (result-sum          :initform     0   :accessor cpu-result-sum                    :type integer))
  (:documentation "The general CPU class for this pauzzle"))

(defclass cpu10a (cpu10)
    ((result-sum          :initform     0   :accessor cpu-result-sum                    :type integer))
  (:documentation "The specific CPU class for part 1 of this puzzle"))

;; About above Slots:
;
; instruction-pointer is an integer pointing into the program vector
; instruction-cycles is the number of remaining cycles to finish the instruction
; cycle is the current cycle count
; cycle state is one of :halt, :start, :during, :end


(defun show-cpu (cpu)
  "Prints a rough overview of the CPU state."
  (with-slots (cycle cycle-state instruction-pointer instruction-cycles register-x)
              cpu
    (print (list :cycle cycle
                 :cycle-state cycle-state
                 :instruction-pointer instruction-pointer
                 :instruction-cycles instruction-cycles
                 :register-x register-x))))

(defmethod cpu-instruction ((cpu cpu10))
  "Returns the current CPU instruction. A keyword symbol."
  (let ((instruction+args (aref (cpu-program cpu)
                                (cpu-instruction-pointer cpu))))
    (values (first instruction+args) (rest instruction+args))))

(defmethod cpu-instruction-args ((cpu cpu10))
  "Returns the args for the current CPU instruction."
  (nth-value 1 (cpu-instruction cpu)))


;;; ================================================================
;;; Executing the instructions

;; start

(defmethod do-cycle ((cpu cpu10) (current-state (eql :start)) instruction)
  "The start of the cycle for all instructions."
  (incf (cpu-cycle cpu))
  (setf (cpu-cycle-state cpu) :during)
  (when (zerop (cpu-instruction-cycles cpu))
    (setf (cpu-instruction-cycles cpu) (instruction-cycles instruction)))
  cpu)

;; during

(defmethod do-cycle ((cpu cpu10) (current-state (eql :during)) (instruction (eql :noop)))
  "During the NOOP instruction."
  (setf (cpu-instruction-cycles cpu) 0)
  (setf (cpu-cycle-state cpu) :end)
  cpu)

(defmethod do-cycle ((cpu cpu10) (current-state (eql :during)) (instruction (eql :addx)))
  "During the ADDX instruction"
  (decf (cpu-instruction-cycles cpu))
  (setf (cpu-cycle-state cpu) :end)
  cpu)

;; DURING method for part 1 of the puzzle, computing the sum of signal strengths

(defmethod do-cycle :around ((cpu cpu10a) (current-state (eql :during)) instruction)
  "During each instruction we calculate the signal strength, if necessary."
  (declare (ignore instruction))
  (when (zerop (mod (- (cpu-cycle cpu) 20) 40))
    (incf (cpu-result-sum cpu) (* (cpu-cycle cpu) (cpu-register-x cpu))))
  (call-next-method)
  cpu)

;; end

(defmethod do-cycle ((cpu cpu10) (current-state (eql :end)) (instruction (eql :noop)))
  "The end of the NOOP instruction cycle."
  (incf (cpu-instruction-pointer cpu))
  cpu)

(defmethod do-cycle ((cpu cpu10) (current-state (eql :end)) (instruction (eql :addx)))
  "The end of the ADDX instruction cycle 1 or 2."
  (when (eql (cpu-instruction-cycles cpu) 0)
    (incf (cpu-register-x cpu) (first (cpu-instruction-args cpu)))
    (incf (cpu-instruction-pointer cpu)))
  cpu)

(defmethod do-cycle :after ((cpu cpu10) (current-state (eql :end)) instruction)
  "The end of each instruction cycle. Halts the CPU at the end of the program.
Otherwise starts a new cycle."
  (declare (ignore instruction))
  (cond ((>= (cpu-instruction-pointer cpu) (1- (length (cpu-program cpu))))
         (setf (cpu-cycle-state cpu) :halt))
        (t
         (setf (cpu-cycle-state cpu) :start)))
  cpu)


;;; ================================================================
;;; Running the CPU

(defun run-cpu (cpu)
  "Calls the instruction dispatcher for each cycle."
  (loop while (not (eql (cpu-cycle-state cpu) :halt)) do
    (when (cpu-trace-p cpu)
             (show-cpu cpu))
    (do-cycle cpu
              (cpu-cycle-state cpu)
              (cpu-instruction cpu)))
  cpu)


;;; ================================================================
;;; Part 2

; The CPU class for part 2. We reuse/inherit part 1.
; Additionally this CPU has a frame buffer of size 40x6.

(defclass cpu10b (cpu10)
    ((frame-buffer
       :initform (make-array (list 40 6) :initial-element #\space)
       :accessor cpu-frame-buffer)))

(defmethod do-cycle :after ((cpu cpu10b) (current-state (eql :during)) instruction)
  "During each cycle we draw into the frame buffer."
  (declare (ignore instruction))
  (multiple-value-bind (y x)
      (truncate (1- (cpu-cycle cpu)) 40)
    (setf (aref (cpu-frame-buffer cpu) x y)
          (if (<= (1- (cpu-register-x cpu)) x (1+ (cpu-register-x cpu))) #\# #\.))))

(defun draw-frame-buffer (cpu)
  (terpri)
  (let ((fb (cpu-frame-buffer cpu)))
    (loop for y below 6
          do (loop for x below 40
                   do (write-char (aref fb x y)))
             (terpri))))

;;; ================================================================
;;; Solving AOC 2022, Day 10 part 1 and 2

(defun solve-aoc2022-10 (trace-p file cpu-class)
  (let* ((program (read-program file))
         (cpu (make-instance cpu-class
                             :program program
                             :trace trace-p)))
    (setf (cpu-cycle-state cpu) :start)
    (run-cpu cpu)
    cpu))

(defun aoc2022-10 (&optional trace-p (file *input-10*))
  (print (cpu-result-sum (solve-aoc2022-10 trace-p file 'cpu10a)))
  (draw-frame-buffer     (solve-aoc2022-10 trace-p file 'cpu10b)))

; Example Call:
;
; (aoc2022-10)


;;; ================================================================
;;; End of File