advent of code day 15 (warning: ugly)

day15.rkt

#lang racket

(define in (string-trim (file->string "day15.in")))
(define initial-memory
  (list->vector
   (map string->number
        (string-split in ","))))

(define (step mem inputs ip base)
  ; indirect addressing (with optional offset)
  (define (position-mode pos [off 0])
    (vector-ref mem (addr pos off)))
  ; relative addressing (from base)
  (define (relative-mode pos [off 0])
    (vector-ref mem (rel-addr pos off)))
  ; immediate addressing: access memory at position (with optional offset)
  (define (addr pos [off 0])
    (vector-ref mem (+ pos off)))
  (define (rel-addr pos [off 0])
    (+ base (vector-ref mem (+ pos off))))

  (let* ([insn (addr ip)]
         [imm1 (quotient (remainder insn 1000) 100)]
         [ref1 (match imm1 [0 position-mode] [1 addr] [2 relative-mode])]
         [addr1 (match imm1 [0 addr] [1 #f] [2 rel-addr])]
         [imm2 (quotient (remainder insn 10000) 1000)]
         [ref2 (match imm2 [0 position-mode] [1 addr] [2 relative-mode])]
         [addr2 (match imm2 [0 addr] [1 #f] [2 rel-addr])]
         [imm3 (quotient insn 10000)]
         [addr3 (match imm3 [0 addr] [1 #f] [2 rel-addr])]
         [insn (remainder insn 100)])
    (case insn
      [(1) ; add
       (vector-set! mem (addr3 ip 3)
                    (+ (ref1 ip 1) (ref2 ip 2)))
       (step mem inputs (+ ip 4) base)]
      [(2) ; multiply
       (vector-set! mem (addr3 ip 3)
                    (* (ref1 ip 1) (ref2 ip 2)))
       (step mem inputs (+ ip 4) base)]
      [(3) ; input
       ;(for ([l panel]) (displayln l))
       (vector-set! mem (addr1 ip 1) (first inputs))
       (step mem (rest inputs) (+ ip 2) base)]
      [(4) ; output
       (values
        (ref1 ip 1)
        (list inputs (+ ip 2) base))]
      ;(step (+ ip 2) base inputs mem)]
      [(5) ; jump if true
       (let ([next (if (not (zero? (ref1 ip 1)))
                       (ref2 ip 2)
                       (+ ip 3))])
         (step mem inputs next base))]
      [(6) ; jump if false
       (let ([next (if (zero? (ref1 ip 1))
                       (ref2 ip 2)
                       (+ ip 3))])
         (step mem inputs next base))]
      [(7) ; less
       (vector-set! mem (addr3 ip 3)
                    (if (< (ref1 ip 1) (ref2 ip 2)) 1 0))
       (step mem inputs (+ ip 4) base)]
      [(8) ; equal
       (vector-set! mem (addr3 ip 3)
                    (if (= (ref1 ip 1) (ref2 ip 2)) 1 0))
       (step mem inputs (+ ip 4) base)]
      [(9) ; change base
       (step mem inputs (+ ip 2) (+ base (ref1 ip 1)))]
      [(99) ; successful halt
       (values #f #f)]
      [else (error 'interpreter "undefined opcode ~a" insn)])))

(define (pos-add pos dx)
  (cons (+ (car pos) (car dx)) (+ (cdr pos) (cdr dx))))

(define (run)
  (let ([mem (make-vector 10000)]
        [seen (make-hash)])
    (vector-copy! mem 0 initial-memory)
    (define (dfs pos state len)
      (for/fold ([state state])
                ([dir '(1 2 3 4)] [dx '((0 . -1) (0 . 1) (-1 . 0) (1 . 0))])
        #:break (not state)
        (let ([next-pos (pos-add pos dx)])
        (cond
          [(hash-has-key? seen next-pos) ; aready visited, don't do anything
            state]
           [else
            (let-values ([(output state) (apply step mem (list dir) (rest state))])
              (case output
                [(0) ; wall
                 (hash-set! seen next-pos output)
                 state]
                [(1 2) ; empty
                 (when (= output 2) (displayln next-pos) (displayln (add1 len)))
                 (hash-set! seen next-pos output)
                 (let ([state (dfs next-pos state (add1 len))])
                   ; if dfs wasn't successful, take a step back so we're in the right position
                   (if state (let-values ([(output state) (apply step mem (list (match dir [1 2] [2 1] [3 4] [4 3])) (rest state))]) state) #f))]))]))))
    (dfs '(0 . 0) '(() 0 0) 0)
    seen))

(define seen (run))
(define (bfs elems iter)
  (let ([next-elems
         (for*/list ([elem elems]
                     [dx '((0 . -1) (0 . 1) (-1 . 0) (1 . 0))]
                     [next-pos (in-value (pos-add elem dx))]
                     #:when (= (hash-ref seen next-pos 0) 1))
           (hash-set! seen next-pos 2)
           next-pos)])
    (if (empty? next-elems) iter (bfs next-elems (add1 iter)))))

; hardcoded part 1 output
(bfs '((16 . 12)) 0)