commit 5900e73c8bbfddef189d23cf413adbf04dbb738b (patch)
parent 43a821e3f89fc061f6bbfaa89844f5a78a727967
Author: Alex Karle <alex@alexkarle.com>
Date: Tue, 13 Dec 2022 20:44:04 -0500
day12: Add part 1
Diffstat:
3 files changed, 143 insertions(+), 0 deletions(-)
diff --git a/2022/12/input b/2022/12/input
@@ -0,0 +1,41 @@
+abcccccccccaaaaaaaaaaccccccccccccaaaaaaaaccaaccccccccccccccccccccccccccccccccccccccccccccaaaaaa
+abccccccccccaaaaaaaaaccccccccccccaaaaaaaaaaaacccccccccccaacccacccccccccccccccccccccccccccaaaaaa
+abcccccccccccaaaaaaacccccccccccccaaaaaaaaaaaaaacccccccccaaacaacccccccccaaaccccccccccccccccaaaaa
+abccccccccccaaaaaaccccccccccccccaaaaaaaaaaaaaaaccccccccccaaaaaccccccccccaaacccccccccccccccccaaa
+abccccccccccaaaaaaaccccccccccccaaaaaaaaaaaaaacccccccccccaaaaaacccccccccaaaacccccccccccccccccaac
+abaaccaaccccaaccaaaccccccccaaaaaaaaaaaaaaacaaccccccccccaaaaaaaacccccccccaaalcccccccccccccccaaac
+abaaaaaacccccccccaaccccccccaaaaaacccaaaacccaaccccccccccaaaaaaaaccccccccalllllllcccccccccccccccc
+abaaaaaacccccccaaacccccccccaaaaccccccaaaccccaaaaacccccccccaacccccccaaaakllllllllcccccccaacccccc
+abaaaaaacccccccaaaacccccccccaacccccccaaaccccaaaaacccccccccaacccccccaakkklllpllllccccacaaacccccc
+abaaaaaaaccccccaaaaccccaaccccccccccccccccccaaaaaaccccccccccccccccccckkkkpppppplllcccaaaaaaacccc
+abaaaaaaacaaaccaaaaccaaaaaaccccccccccccccccaaaaaacccccccaaaccccckkkkkkkpppppppplllcddaaaaaacccc
+abcaaaacccaacccccccccaaaaaacccccaaaccccccccaaaaaacccccccaaaaccjkkkkkkkpppppuppplmmdddddaaaccccc
+abccaaaaaaaaaccccccccaaaaaaccccaaaaaacccccccaaacccccccccaaaajjjkkkkkrpppuuuuupppmmmdddddacccccc
+abccccaaaaaaaacccccccaaaaacccccaaaaaacccccccccccccccccccaaacjjjjrrrrrrppuuuuupqqmmmmmddddaccccc
+abccccaaaaaaaaacccccccaaaacccccaaaaaaccccccccccccccccccccccjjjrrrrrrrrpuuuxuvvqqqmmmmmddddccccc
+abccccaaaaaaaaacccccccccccccccccaaaaaccccaacccaccccccccaaccjjjrrrruuuuuuuxxyvvqqqqqmmmmmdddcccc
+abccccaaaaaaaacccccccccaaaccccccaacaaccccaaacaacccaaacaaaccjjjrrrtuuuuuuuxxyvvvqqqqqmmmmdddcccc
+abccaaaaaaaacccccccccccaaaaaccccccccccccccaaaaacccaaaaaaaccjjjrrttttxxxxxxyyvvvvvqqqqmmmmdeeccc
+abccaaaccaaaccccccccaacaaaaacccccccccccccaaaaaacccaaaaaacccjjjrrtttxxxxxxxyyvvvvvvvqqqmmmeeeccc
+abaaaaaaaaaacccaaaccaaaaaaaaaaaccaaaccccaaaaaaaacccaaaaaaaajjjqqrttxxxxxxxyyyyyyvvvqqqnnneeeccc
+SbaaaaaaaaccccaaaaccaaaaaaaaaaaaaaaaacccaaaaaaaaccaaaaaaaaacjjjqqtttxxxxEzzyyyyvvvvqqqnnneeeccc
+abcaaaaaacccccaaaaccccaaaaaaaccaaaaaaccccccaaccccaaaaaaaaaaciiiqqqtttxxxyyyyyyvvvvrrrnnneeecccc
+abcaaaaaacccccaaaacccaaaaaaaaccaaaaaaccccccaaccccaaacaaacccciiiqqqqttxxyyyyyywvvvrrrnnneeeecccc
+abcaaaaaaccccccccccccaaaaaaaaacaaaaacccccccccccccccccaaaccccciiiqqtttxxyyyyyywwrrrrnnnneeeccccc
+abcaaacaacccccaacccccaaaaaaaaacaaaaacccccccccccccccccaaaccccciiiqqttxxxywwyyywwrrrnnnneeecccccc
+abccccccccaaacaaccccccccccacccccccccccccccccccccccccccccccccciiqqqttxxwwwwwwywwrrrnnneeeccccccc
+abccaacccccaaaaaccccccccccccccccccccccccccccccccccccccccaacaaiiqqqttwwwwsswwwwwrrrnnfffeccccccc
+abaaaaccccccaaaaaacccccccccccccccccccccccccccccaaaccccccaaaaaiiqqqttssssssswwwwrrronfffaccccccc
+abaaaaaacccaaaaaaacccccccccccccccccccccccccccaaaaaacccccaaaaaiiqqqssssssssssswrrrooofffaaaacccc
+abaaaaaaccaaaaaacccccccccccccccccccccccccccccaaaaaacccccaaaaaiiqqqppssspppssssrrrooofffaaaacccc
+abaaaaaaccaacaaacccccccccccccccccccccccccccccaaaaaacccccaaaaaiihpppppppppppossrrooofffaaaaacccc
+abaaaaccccccccaacccccccccccccccccccccccccccccaaaaaccccccccaaahhhhppppppppppoooooooofffaaaaccccc
+abaaaaccccccccccaacccccccccccccccccaaacccccccaaaaacccccccccccchhhhhhhhhhggpoooooooffffaaaaccccc
+abccaacccccccacaaaccccccccccccccccaaaaacccccccccccccccccccccccchhhhhhhhhggggoooooffffaacaaacccc
+abccccccccccaaaaacaaccccccccccccccaaaaaccccccccccccccccccccccccchhhhhhhhggggggggggffcaacccccccc
+abccccccccccaaaaaaaaccccccccccccccaaaacccaacccccccccccaccccccccccccccaaaaaggggggggfcccccccccccc
+abccccccccccccaaaaaccccaacccccccccaaaacaaaaccccccccaaaaccccccccccccccaaaacaaagggggcccccccccaccc
+abcccccccccccaaaaacccccaacccccccccaaaaaaaaaccccccccaaaaaaccccccccccccaaaccaaaacccccccccccccaaac
+abcccccccccccaacaaccaaaaaaaacccaaaaaaaaaaaccccccccccaaaaccccccccccccccaccccaaacccccccccccccaaaa
+abccccccccccccccaaccaaaaaaaaccaaaaaaaaaaaccccccccccaaaaacccccccccccccccccccccacccccccccccccaaaa
+abccccccccccccccccccccaaaaacccaaaaaaaaaaaacccccccccaacaacccccccccccccccccccccccccccccccccaaaaaa
diff --git a/2022/12/sample b/2022/12/sample
@@ -0,0 +1,5 @@
+Sabqponm
+abcryxxl
+accszExk
+acctuvwj
+abdefghi
diff --git a/2022/12/sol.scm b/2022/12/sol.scm
@@ -0,0 +1,97 @@
+#!/usr/local/bin/chicken-csi -ss
+(import srfi-69
+ (chicken io))
+
+(define (filter pred lst)
+ (cond ((null? lst) '())
+ ((pred (car lst))
+ (cons (car lst) (filter pred (cdr lst))))
+ (else (filter pred (cdr lst)))))
+
+(define (lvl c)
+ (cond ((equal? c #\S) 0)
+ ((equal? c #\E) 25)
+ (else (- (char->integer c) 97))))
+
+(define (get grid r c)
+ (vector-ref (vector-ref grid r) c))
+
+(define (find grid needle)
+ (let ((n (vector-length grid))
+ (m (vector-length (vector-ref grid 0))))
+ (let iloop ((i 0))
+ (if (>= i n)
+ #f
+ (let jloop ((j 0))
+ (if (>= j m)
+ (iloop (add1 i))
+ (let ((x (get grid i j)))
+ (if (equal? x needle)
+ (list i j)
+ (jloop (add1 j))))))))))
+
+(define (make-grid lines transform)
+ (list->vector (map (lambda (l) (list->vector (map transform (string->list l))))
+ lines)))
+
+(define (ident x) x)
+
+
+(define (neigh grid pos)
+ (define (in-bounds? pt)
+ (let ((n (vector-length grid))
+ (m (vector-length (vector-ref grid 0))))
+ (and (>= (cadr pt) 0)
+ (< (cadr pt) n)
+ (>= (caddr pt) 0)
+ (< (caddr pt) m))))
+ (define (in-reach? pt)
+ (let* ((d (car pos))
+ (i (cadr pos))
+ (j (caddr pos))
+ (i2 (cadr pt))
+ (j2 (caddr pt))
+ (l1 (get grid i j))
+ (l2 (get grid i2 j2)))
+ (and (<= l2 (add1 l1)))))
+ (let* ((d (car pos))
+ (i (cadr pos))
+ (j (caddr pos)))
+ (filter (lambda (pt) (and (in-bounds? pt) (in-reach? pt)))
+ `((,(add1 d) ,(add1 i) ,j)
+ (,(add1 d) ,(sub1 i) ,j)
+ (,(add1 d) ,i ,(add1 j))
+ (,(add1 d) ,i ,(sub1 j))))))
+
+
+(define (dist grid start goal)
+ ;; BFS to find the goal, each item is (D i j) where D is depth
+ (let ((seen (make-hash-table)))
+ (let loop ((Q (list (cons 0 start))))
+ (if (null? Q)
+ #f
+ (let ((pos (car Q)))
+ (hash-table-set! seen (cdr pos) 'seen)
+ (if (equal? (cdr pos) goal)
+ (car pos)
+ (let ((neighs (filter (lambda (p) (not (hash-table-exists? seen (cdr p))))
+ (neigh grid pos))))
+ (for-each (lambda (p) (hash-table-set! seen (cdr p) 1)) neighs)
+ (loop (append (cdr Q) neighs)))))))))
+
+
+(define (main args)
+ (let* ((lines (read-lines))
+ (cgrid (make-grid lines ident))
+ (lgrid (make-grid lines lvl))
+ (start (find cgrid #\S))
+ (goal (find cgrid #\E)))
+ (print (dist lgrid start goal))))
+
+; for repl
+(define ln '("Sabqponm"
+ "abcryxxl"
+ "accszExk"
+ "acctuvwj"
+ "abdefghi"))
+
