kari's recent activity
-
Comment on Day 11: Plutonian Pebbles in ~comp.advent_of_code
-
Comment on Day 14: Restroom Redoubt in ~comp.advent_of_code
kari LinkPart 1 was easy (and I finally learned about structs in Racket!) Part 2 I just stole the idea from lily's solution in here. Racket #! /usr/bin/env racket #lang racket (require "common.rkt")...Part 1 was easy (and I finally learned about structs in Racket!)
Part 2 I just stole the idea from lily's solution in here.Racket
#! /usr/bin/env racket #lang racket (require "common.rkt") (module+ test (require rackunit)) (struct robot (x y Δx Δy)) (define (parse-robots in-port) (for/list ([line (in-lines in-port)]) (let* ([split (string-split line " ")] [position (string-split (substring (first split) 2) ",")] [x (string->number (first position))] [y (string->number (second position))] [velocity (string-split (substring (second split) 2) ",")] [Δx (string->number (first velocity))] [Δy (string->number (second velocity))]) (robot x y Δx Δy)))) (define (top-left? q) (equal? 'tl q)) (define (top-right? q) (equal? 'tr q)) (define (bottom-left? q) (equal? 'bl q)) (define (bottom-right? q) (equal? 'br q)) (define (step robots width height [k 1]) (for/list ([r (in-list robots)]) (let* ([new-x (modulo (+ (robot-x r) (* k (robot-Δx r))) width)] [new-y (modulo (+ (robot-y r) (* k (robot-Δy r))) height)]) (struct-copy robot r [x new-x] [y new-y])))) (define (safety-factor robots width height) (let* ([mid-x (quotient width 2)] [mid-y (quotient height 2)] [quadrants (for/fold ([quadrants '()]) ([r (in-list robots)]) (let* ([x (robot-x r)] [y (robot-y r)]) (cond ;; top left [(and (< x mid-x) (< y mid-y)) (cons 'tl quadrants)] ;; top right [(and (> x mid-x) (< y mid-y)) (cons 'tr quadrants)] ;; bottom left [(and (< x mid-x) (> y mid-y)) (cons 'bl quadrants)] ;; bottom right [(and (> x mid-x) (> y mid-y)) (cons 'br quadrants)] [else (cons 'middle quadrants)])))] [tl-count (length (filter top-left? quadrants))] [tr-count (length (filter top-right? quadrants))] [bl-count (length (filter bottom-right? quadrants))] [br-count (length (filter bottom-left? quadrants))]) (* tl-count tr-count bl-count br-count))) ;; Returns the number of unique positions the robots are in (define (unique-positions robots) (set-count (for/set ([r (in-list robots)]) (list (robot-x r) (robot-y r))))) (define (day14/run-part01 robots width height) (safety-factor (step robots width height 100) width height)) ;; I stole the idea of "no robots on the same space" from here ;; https://tildes.net/~comp.advent_of_code/1kos/day_14_restroom_redoubt#comment-ecv5 (define (day14/run-part02 robots width height) (let helper ((robots robots) (steps 0)) (let ([posn-count (unique-positions robots)]) (cond [(= posn-count (length robots)) steps] [else (helper (step robots width height) (add1 steps))])))) (module+ test (check-equal? (day14/run-part01 (parse-robots (open-input-file "examples/day14.in")) 11 7) 12 "Test part 1")) ;; Run against my input and print the results (module+ main (let* ([in-port (open-input-file "inputs/day14.in")] [robots (parse-robots in-port)] [part1 (day14/run-part01 robots 101 103)] [part2 (day14/run-part02 robots 101 103)]) (printf "Part 1: ~a, Part 2: ~a\n" part1 part2))) -
Comment on Day 10: Hoof It in ~comp.advent_of_code
kari LinkHonestly, I kind of wish I hadn't used the graph library for Racket lol. I went back after I did part 2 and my day10/run-part01-better procedure drops the run time for part 1 from ~17 seconds to 1...Honestly, I kind of wish I hadn't used the
graphlibrary for Racket lol. I went back after I did part 2 and myday10/run-part01-betterprocedure drops the run time for part 1 from ~17 seconds to 1 second lol. I guess that's partly just because my "better" procedure doesn't find the shortest path, just a path.Anyways, I really enjoyed that one. I did UIL Computer Science competitions in high school that had lots of graph problems like this and they were by far my favorite. If I were doing this back then I probably could've finished it in Java (without any graph library, just by coordinates) in like 5 minutes lol.
Racket
#! /usr/bin/env racket #lang racket (require graph "common.rkt") (module+ test (require rackunit)) (define (map->graph in-map) ;; Check if (i1, j1) -> (i2, j2) should be an edge ;; Can only be an edge if (map-ref in-map i1 j1) + 1 = (map-ref in-map i2 j2) (define (edge? i1 j1 i2 j2) (cond [(or (out-of-bounds? in-map i1 j1) (out-of-bounds? in-map i2 j2)) #f] [else (eq? 1 (- (map-ref in-map i2 j2) (map-ref in-map i1 j1)))])) ;; Iterate through the entire map and create any edges (directed-graph (for*/fold ([edges '()]) ([i (length in-map)] [j (length (list-ref in-map i))] [dest (in-list (list (list (sub1 i) j) (list (add1 i) j) (list i (sub1 j)) (list i (add1 j))))]) (cond [(edge? i j (first dest) (second dest)) (let* ([start (list i j)] [new-edge (list start dest)]) (cons new-edge edges))] [else edges])))) ;; Get the coordinates of all 0s on the map (define (trailhead-coords in-map) (for*/fold ([trailhead-coords '()]) ([i (length in-map)] [j (length (list-ref in-map i))]) (cond [(zero? (map-ref in-map i j)) (cons (list i j) trailhead-coords)] [else trailhead-coords]))) ;; Get the coordinates of all 9s on the map (define (peak-coords in-map) (for*/fold ([trailhead-coords '()]) ([i (length in-map)] [j (length (list-ref in-map i))]) (cond [(= 9 (map-ref in-map i j)) (cons (list i j) trailhead-coords)] [else trailhead-coords]))) ;; Calculate if a path exists for a single trailhead->peak pair (define (has-path? g trailhead peak) (let helper ((v trailhead) (visited '())) (cond ;; found a path [(equal? v peak) 1] [else (for/or ([neighbor (in-list (get-neighbors g v))]) (cond ;; Already visited this vertex [(member neighbor visited) 0] [else (helper neighbor (cons v visited))]))]))) ;; Calculate the rating for a single trailhead->peak pair. ;; This is essentially (has-path?) but it doesn't return ;; as soon as it finds a path. (define (rating g trailhead peak) (let helper ((v trailhead) (visited '())) (cond ;; found a path [(equal? v peak) 1] [else (for/sum ([neighbor (in-list (get-neighbors g v))]) (cond ;; Already visited this vertex [(member neighbor visited) 0] [else (helper neighbor (cons v visited))]))]))) (define (day10/run-part01 in-map) (let ([map-graph (map->graph in-map)] [trailhead-coords (trailhead-coords in-map)] [peak-coords (peak-coords in-map)]) ;; For each trailhead->peak pair, see if there's a path. ;; If there is, add 1 to our sum of paths. (for*/sum ([trailhead-coord (in-list trailhead-coords)] [peak-coord (in-list peak-coords)]) (cond [(fewest-vertices-path map-graph trailhead-coord peak-coord) 1] [else 0])))) (define (day10/run-part01-better in-map) (let ([map-graph (map->graph in-map)] [trailhead-coords (trailhead-coords in-map)] [peak-coords (peak-coords in-map)]) ;; For each trailhead->peak pair, see if there's a path. ;; If there is, add 1 to our sum of paths. (for*/sum ([trailhead-coord (in-list trailhead-coords)] [peak-coord (in-list peak-coords)]) (if (has-path? map-graph trailhead-coord peak-coord) 1 0)))) (define (day10/run-part02 in-map) (let ([map-graph (map->graph in-map)] [trailhead-coords (trailhead-coords in-map)] [peak-coords (peak-coords in-map)]) ;; For each trailhead->peak pair, see if there's a path. ;; If there is, add 1 to our sum of paths. (for*/sum ([trailhead-coord (in-list trailhead-coords)] [peak-coord (in-list peak-coords)]) (rating map-graph trailhead-coord peak-coord)))) (module+ test (check-equal? (day10/run-part01 (input->list-numbers (open-input-file "examples/day10_1.in"))) 2 "Test part 1: 1") (check-equal? (day10/run-part01 (input->list-numbers (open-input-file "examples/day10_2.in"))) 4 "Test part 1: 2") (check-equal? (day10/run-part01 (input->list-numbers (open-input-file "examples/day10_3.in"))) 3 "Test part 1: 3") (check-equal? (day10/run-part01 (input->list-numbers (open-input-file "examples/day10_4.in"))) 36 "Test part 1: 4") (check-equal? (day10/run-part02 (input->list-numbers (open-input-file "examples/day10_5.in"))) 3 "Test part 2: 1") (check-equal? (day10/run-part02 (input->list-numbers (open-input-file "examples/day10_6.in"))) 13 "Test part 2: 2") (check-equal? (day10/run-part02 (input->list-numbers (open-input-file "examples/day10_7.in"))) 227 "Test part 2: 3") (check-equal? (day10/run-part02 (input->list-numbers (open-input-file "examples/day10_4.in"))) 81 "Test part 2: 4")) ;; Run against my input and print the results (module+ main (let* ([in-port (open-input-file "inputs/day10.in")] [in-map (input->list-numbers in-port)] [part1 (day10/run-part01-better in-map)] [part2 (day10/run-part02 in-map)]) (printf "Part 1: ~a, Part 2: ~a\n" part1 part2))) -
Comment on Day 9: Disk Fragmenter in ~comp.advent_of_code
kari LinkI've been busy so I'm catching up right now. My part 1 took like 20 minutes and then part 2, which I thought I'd made more efficient, actually took 63 lol. Advent of Code does not bring out the...I've been busy so I'm catching up right now.
My part 1 took like 20 minutes and then part 2, which I thought I'd made more efficient, actually took 63 lol. Advent of Code does not bring out the best in my coding abilities
Racket
#! /usr/bin/env racket #lang racket (require "common.rkt") (module+ test (require rackunit)) ;; I could probably do all of this without disk-map->mem ;; and it'd be more efficient... but I'm lazy (define (disk-map->mem disk-map) ;; prepend k ids to mem ;; TODO: use make-list instead of this (define (prepend-proc id k mem) (cond [(< k 0) (error "invalid k")] [(zero? k) mem] [else (prepend-proc id (sub1 k) (cons id mem))])) ;; recursive helper procedure that does the work (define (helper disk-map type id mem) (cond ;; reached the end of the map; reverse our mem list and return it [(empty? disk-map) (reverse mem)] ;; free space: add #\.s to mem but don't increment id [(eq? type 'free-space) (helper (cdr disk-map) 'file id (prepend-proc #\. (char->number (car disk-map)) mem))] ;; file: add the ID to mem but don't increment id [(eq? type 'file) (helper (cdr disk-map) 'free-space (add1 id) (prepend-proc id (char->number (car disk-map)) mem))])) (helper disk-map 'file 0 '())) (define (mem-compact-blocks mem) ;; recursive helper procedure that does the work (define (helper mem compacted-mem) (cond ;; reached the end of mem; return out compacted-mem [(empty? mem) compacted-mem] ;; found a free space and (last mem) is at a file-id; let's compact [(and (eq? (car mem) #\.) (not (eq? (last mem) #\.))) ;; want to drop the first and last of mem (cons #\. (helper (take (cdr mem) (- (length mem) 2)) (cons (last mem) compacted-mem)))] ;; found a free space but (last mem) is not at a file id; ;; recurse but get rid of the last value of mem [(eq? (car mem) #\.) (cons #\. (helper (take mem (sub1 (length mem))) compacted-mem))] ;; this space already has a file block in it; just add it to the new compacted-mem then continue [else (helper (cdr mem) (cons (car mem) compacted-mem))])) (reverse (helper mem '()))) (define (mem-checksum mem) (define (helper mem idx) (cond ;; done [(empty? mem) 0] ;; found an empty block [(eq? (car mem) #\.) (helper (cdr mem) (add1 idx))] ;; found a file block [else (+ (* idx (car mem)) (helper (cdr mem) (add1 idx)))])) (helper mem 0)) (define (disk-map->enc disk-map) (let helper ((disk-map disk-map) (enc '()) (type 'file) (id 0)) (cond [(empty? disk-map) (reverse enc)] [(eq? type 'file) (helper (cdr disk-map) (cons (list id (char->number (car disk-map))) enc) 'free-space (add1 id))] [(eq? type 'free-space) (helper (cdr disk-map) (cons (list #f (char->number (car disk-map))) enc) 'file id)] [else (error 'enc-fail)]))) (define (mem-compact-files enc) (define (val-to-insert free-space req-size) (cond [(< req-size free-space) (list (list #f (- free-space req-size)))] [(= req-size free-space) '()] [else (error 'invalid-size)])) (define (clean-enc enc [i 0]) (let ([j (add1 i)]) (cond [(>= j (length enc)) enc] [(and (not (car (list-ref enc i))) (not (car (list-ref enc j)))) (clean-enc (append (take enc i) (list (list #f (+ (cadr (list-ref enc i)) (cadr (list-ref enc j))))) (list-tail enc (add1 j))) i)] [else (clean-enc enc (add1 i))]))) (let helper ((enc enc) (i 0) (j (sub1 (length enc))) (checked '())) (cond [(negative? j) enc] [(or (>= i j) (member (car (list-ref enc j)) checked)) (helper enc 0 (sub1 j) (cons (car (list-ref enc j)) checked)) ] [(not (car (list-ref enc j))) (helper enc i (sub1 j) (cons (car (list-ref enc j)) checked))] [(number? (car (list-ref enc i))) (helper enc (add1 i) j checked)] [(and (not (car (list-ref enc i))) (<= (cadr (list-ref enc j)) (cadr (list-ref enc i)))) (let* ([new-free-space (val-to-insert (cadr (list-ref enc i)) (cadr (list-ref enc j)))] [new-enc (append (take enc i) (list (list-ref enc j)) new-free-space (list-tail (take enc j) (add1 i)) (list (list #f (cadr (list-ref enc j)))) (list-tail enc (add1 j)))] [new-j (cond [(empty? new-free-space) (sub1 j)] [else j])] [checked (cons (car (list-ref enc j)) checked)] [cleaned-enc (clean-enc new-enc)]) (helper cleaned-enc 0 new-j checked))] [else (helper enc (add1 i) j '())]))) (define (enc->mem enc) (let helper ((enc enc) (mem '())) (cond [(empty? enc) (reverse mem)] [else (let* ([type (caar enc)] [count (cadar enc)] [char (cond [(not type) #\.] [else type])]) (helper (cdr enc) (append (make-list count char) mem)))]))) (define (day09/run-part01 mem) (mem-checksum (mem-compact-blocks mem))) (define (day09/run-part02 enc) (mem-checksum (enc->mem (mem-compact-files enc)))) (module+ test (let* ([in-port (open-input-string "2333133121414131402")] [disk-map (string->list (read-line in-port))] [mem (disk-map->mem disk-map)] [enc (disk-map->enc disk-map)]) (check-equal? (day09/run-part01 mem) 1928 "Test part 1") (check-equal? (day09/run-part02 enc) 2858 "Test part 2"))) (module+ main (let* ([in-port (open-input-file "inputs/day09.in")] [disk-map (string->list (read-line in-port))] [mem (disk-map->mem disk-map)] [enc (disk-map->enc disk-map)] ; [part1 (day09/run-part01 mem)] [part2 (day09/run-part02 enc)]) (printf "Part 1: ~a, Part 2: ~a\n" 'part1 part2))) -
Comment on Day 8: Resonant Collinearity in ~comp.advent_of_code
kari LinkMy code for today is kinda blegh but honestly I just wanted to get it done. It wasn't too bad when I'd only done part 1, but I just didn't feel like doing much refactoring during part 2. I am...My code for today is kinda blegh but honestly I just wanted to get it done. It wasn't too bad when I'd only done part 1, but I just didn't feel like doing much refactoring during part 2. I am enjoying Racket, though.
Racket
#! /usr/bin/env racket #lang racket (require "common.rkt") (module+ test (require rackunit)) ;; return the antinodes for pairs p1 and p2 ;; TODO: This could be cleaned up a lot so there's less repeated code (define (antinodes p1 p2 [in-map '()] [repeat #f]) ;; helper that can tell whether to add or subtract dx from x1 based on x1/x2 (define (calc-new x1 x2 dx) (cond [(> x1 x2) (+ x1 dx)] [else (- x1 dx)])) ;; helper for part2, this could be removed if I cleaned things up (define (calc-dir x1 x2 dx) (cond [(> x1 x2) dx] [else (* dx -1)])) ;; helper for part2 ;; returns a list of antinodes until the boundary of the map (define (calc-repeats i j di dj [lst '()]) (cond [(out-of-bounds? in-map i j) lst] [else (calc-repeats (+ i di) (+ j dj) di dj (cons (list i j) lst))])) ;; get individual coordinates (let* ([i1 (first p1)] [j1 (second p1)] [i2 (first p2)] [j2 (second p2)] [di (abs (- i1 i2))] [dj (abs (- j1 j2))]) (append ;; these are the regular antinodes (list (list (calc-new i1 i2 di) (calc-new j1 j2 dj)) (list (calc-new i2 i1 di) (calc-new j2 j1 dj))) ;; if repeat, then we calculate the repeating ones, too (cond [repeat (append (calc-repeats i1 j1 (calc-dir i1 i2 di) (calc-dir j1 j2 dj)) (calc-repeats i2 j2 (calc-dir i2 i1 di) (calc-dir j2 j1 dj)))] [else '()])))) (module+ test (check-equal? (antinodes (list 3 4) (list 5 5)) (list (list 1 3) (list 7 6)) "Test antinodes: basic") (check-equal? (antinodes (list 0 4) (list 0 5)) (list (list 0 3) (list 0 6)) "Test antinodes: same i")) (define (antenna-coords in-map) (for*/fold ([antenna-coords '()]) ([i (length in-map)] [j (length (list-ref in-map i))]) (let ([freq (map-ref in-map i j)]) (cond [(not (equal? freq #\.)) (cons (list freq (list i j)) antenna-coords)] [else antenna-coords])))) (define (day08/run-part01 in-map) (let* ([coords (antenna-coords in-map)] [freqs (list->set (map first coords))]) ;; these isn't very efficient but oh well (set-count (list->set (for/fold ([antinds '()]) ([freq (in-set freqs)]) ;; get all the coordinates for antennas on freq (append (let ([freq-coords (map second (filter (lambda (p) (eq? (first p) freq)) coords))]) ;; calculate all antinodes, then filter out out-of-bounds ones (filter (lambda (p) (not (out-of-bounds? in-map (first p) (second p)))) (for*/fold ([antinds '()]) ([m (sub1 (length freq-coords))] [n (in-range (add1 m) (length freq-coords))]) (append (antinodes (list-ref freq-coords m) (list-ref freq-coords n)) antinds)))) antinds)))))) (define (day08/run-part02 in-map) (let* ([coords (antenna-coords in-map)] [freqs (list->set (map first coords))]) ;; these isn't very efficient but oh well (let ([x (list->set (for/fold ([antinds '()]) ([freq (in-set freqs)]) ;; get all the coordinates for antennas on freq (append (let ([freq-coords (map second (filter (lambda (p) (eq? (first p) freq)) coords))]) ;; calculate all antinodes, then filter out out-of-bounds ones (filter (lambda (p) (not (out-of-bounds? in-map (first p) (second p)))) (for*/fold ([antinds '()]) ([m (sub1 (length freq-coords))] [n (in-range (add1 m) (length freq-coords))]) (append (antinodes (list-ref freq-coords m) (list-ref freq-coords n) in-map #t) antinds)))) antinds)))]) (set-count x)))) ;; Test examples from the problem (module+ test (check-equal? (day08/run-part01 (input->list (open-input-file "examples/day08_1.in"))) 4 "Test part 1: simple") (check-equal? (day08/run-part01 (input->list (open-input-file "examples/day08_2.in"))) 14 "Test part 1: less simple") (check-equal? (day08/run-part02 (input->list (open-input-file "examples/day08_3.in"))) 9 "Test part 2: simple") (check-equal? (day08/run-part02 (input->list (open-input-file "examples/day08_2.in"))) 34 "Test part 2: less simple") (check-equal? (day08/run-part02 (input->list (open-input-file "examples/day08_1.in"))) 8 "Test part 2: ???")) ;; Run against my input and print the results (module+ main (let* ([in-port (open-input-file "inputs/day08.in")] [in-map (input->list in-port)] [part1 (day08/run-part01 in-map)] [part2 (day08/run-part02 in-map)]) (printf "Part 1: ~a, Part 2: ~a\n" part1 part2))) -
Comment on Day 7: Bridge Repair in ~comp.advent_of_code
-
Comment on Day 5: Print Queue in ~comp.advent_of_code
kari LinkI got part 1 fairly easily, though my solution is a bit convoluted, but literally had no clue where to even start on part 2 until I looked here. I still wasn't sure how to easily implement it but...I got part 1 fairly easily, though my solution is a bit convoluted, but literally had no clue where to even start on part 2 until I looked here. I still wasn't sure how to easily implement it but then I realized there's a graph library that can topographically sort graphs for racket, so I just used that.
Racket (just part1)
#! /usr/bin/env racket #lang racket (require rackunit) ;; XXX: these two could be a single proc that takes a separator ;; parse out all of the page rules (define (parse-rules in-port [rules empty]) ;; helper procedure for parsing a single rule (define (parse-rule rule) (map string->number (string-split rule "|"))) (let ([line (read-line in-port)]) (cond [(eof-object? line) (reverse rules)] [else (parse-rules in-port (cons (parse-rule line) rules))]))) ;; parse out all of the required pages (define (parse-pages in-port [pages empty]) ;; helper procedure for parsing a single rule (define (parse-page rule) (map string->number (string-split rule ","))) (let ([line (read-line in-port)]) (cond [(eof-object? line) (reverse pages)] [else (parse-pages in-port (cons (parse-page line) pages))]))) ;; returns #t if a given set of pages is a valid order based on the given page-rules (define (valid? pages rules) ;; helper procedure that checks the set of pages against a single rule (define (valid?-helper pages rule) (let ([first (index-of pages (car rule))] [second (index-of pages(list-ref rule 1))]) (cond [(not (and first second)) #t] [else (> second first)]))) (cond [(empty? rules) #t] [else (and (valid?-helper pages (car rules)) (valid? pages (cdr rules)))])) ;; return the middle index of a list (define (middle page-set) (let ([i (quotient (length page-set) 2)]) (list-ref page-set i))) (define (day05/run-part01 rules-port pages-port) (let ([rules (parse-rules rules-port)] [pages (parse-pages pages-port)]) (for/fold ([sum-middle-valid 0]) ([page-set pages]) (cond [(valid? page-set rules) (+ sum-middle-valid (middle page-set))] [else sum-middle-valid])))) (define (day05/run-part02 in-port) null) (check-equal? (day05/run-part01 (open-input-file "examples/day05_rules.in") (open-input-file "examples/day05_pages.in")) 143 "Test part 1") (check-equal? (day05/run-part02 (open-input-file "examples/day05_rules.in")) null "Test part 2") (let* ([rule-port (open-input-file "inputs/day05_rules.in")] [pages-port (open-input-file "inputs/day05_pages.in")] [part1 (day05/run-part01 rule-port pages-port)] [part2 (day05/run-part02 0)]) (printf "Part 1: ~a, Part 2: ~a\n" part1 part2))Racket (updated with both parts)
#! /usr/bin/env racket #lang racket (require graph rackunit) ;; XXX: these two could be a single proc that takes a separator ;; parse out all of the page rules (define (parse-rules in-port [rules empty]) ;; helper procedure for parsing a single rule (define (parse-rule rule) (map string->number (string-split rule "|"))) (let ([line (read-line in-port)]) (cond [(eof-object? line) (reverse rules)] [else (parse-rules in-port (cons (parse-rule line) rules))]))) ;; parse out all of the updates (define (parse-updates in-port [pages empty]) ;; helper procedure for parsing a single rule (define (parse-update rule) (map string->number (string-split rule ","))) (let ([line (read-line in-port)]) (cond [(eof-object? line) (reverse pages)] [else (parse-updates in-port (cons (parse-update line) pages))]))) ;; returns #t if a given update is valid for the given rules (define (valid? update rules) ;; helper procedure that checks the update against a single rule (define (valid?-helper update rule) (let ([first (index-of update (car rule))] [second (index-of update(list-ref rule 1))]) (cond [(not (and first second)) #t] [else (> second first)]))) (cond [(empty? rules) #t] [else (and (valid?-helper update (car rules)) (valid? update (cdr rules)))])) ;; return the middle index of a list (define (list-middle lst) (let ([i (quotient (length lst) 2)]) (list-ref lst i))) ;; sort an update based on the gives rules (define (update-sort update rules) (let* ([filtered-rules (filter (lambda (rule) (and (member (first rule) update) (member (second rule) update))) rules)] [update-graph (directed-graph filtered-rules)]) (tsort update-graph))) ;; do the math for p1 (define (day05/run-part01 updates) (for/fold ([sum-middle 0]) ([update (in-list updates)]) (+ sum-middle (list-middle update)))) ;; do the math for p2 (define (day05/run-part02 updates rules) (for/fold ([sum-middle 0]) ([update (in-list updates)]) (+ sum-middle (list-middle (update-sort update rules))))) ;; run using the test inputs (let* ([rules-port (open-input-file "examples/day05_rules.in")] [updates-port (open-input-file "examples/day05_updates.in")] [rules (parse-rules rules-port)] [updates (parse-updates updates-port)] [valid-updates (filter (lambda (update) (valid? update rules)) updates)] [invalid-updates (filter (lambda (update) (not (member update valid-updates))) updates)] [part1 (day05/run-part01 valid-updates)] [part2 (day05/run-part02 invalid-updates rules)]) (and (check-equal? part1 143 "Test part 1") (check-equal? part2 123 "Test part 2"))) ;; run with my reala input (let* ([rules-port (open-input-file "inputs/day05_rules.in")] [updates-port (open-input-file "inputs/day05_updates.in")] [rules (parse-rules rules-port)] [updates (parse-updates updates-port)] [valid-updates (filter (lambda (update) (valid? update rules)) updates)] [invalid-updates (filter (lambda (update) (not (member update valid-updates))) updates)] [part1 (day05/run-part01 valid-updates)] [part2 (day05/run-part02 invalid-updates rules)]) (and (check-equal? part1 7074 "Test part 1") (check-equal? part2 4828 "Test part 2")) (printf "Part 1: ~a, Part 2: ~a\n" part1 part2)) -
Comment on Day 7: Bridge Repair in ~comp.advent_of_code
kari LinkI'm actually pretty happy about my solutions today! I got stuck for a while on part 2 and kept getting a value that was too big, but eventually it wasn't? I'm not even totally sure what I fixed. I...I'm actually pretty happy about my solutions today!
I got stuck for a while on part 2 and kept getting a value that was too big, but eventually it wasn't? I'm not even totally sure what I fixed. I guess I probably just had my
||procedure wrong but then eventually it worked.Running the combined parts even after compiling to bytecode takes ~2.3 seconds so there are probably some optimizations I could do, but overall I like my solution.
Racket
#! /usr/bin/env racket #lang racket (require rackunit) (define (possible? target equation oprs) (define (helper target cur equation oprs) (cond ;; we found a match [(and (eq? cur target) (empty? equation)) #t] ;; we reached the end of the equation and cur != target [(empty? equation) #f] ;; we went past the target, no point to keep trying this path [(> cur target) #f] [else (for/or ([opr (in-list oprs)]) (let ([res (opr cur (first equation))]) (helper target res (cdr equation) oprs)))])) (cond ;; can't car or cdr on '() [(empty? equation) #f] [else (helper target (car equation) (cdr equation) oprs)])) ;; parse input port to a list of '(target equation)s (define (parse in-port) (for/list ([line (in-lines in-port)]) (let* ([split (string-split line ": ")] [target (string->number (first split))] [equation-strings (string-split (second split) " ")] [equation (map string->number equation-strings)]) (list target equation)))) ;; concatenation operator for part 2 (define (|| l r) (string->number (string-append (number->string l) (number->string r)))) ;; run with a given list of operators (define (run parsed oprs) (for/sum ([line (in-list parsed)]) (let* ([target (first line)] [equation (second line)]) (cond [(possible? target equation oprs) target] [else 0])))) (define (day07/run-part01 parsed) (run parsed (list + *))) (define (day07/run-part02 parsed) (run parsed (list + * ||))) (check-equal? (day07/run-part01 (parse (open-input-file "examples/day07.in"))) 3749 "Test part 1") (check-equal? (day07/run-part02 (parse (open-input-file "examples/day07.in"))) 11387 "Test part 2") (let* ([in-port (open-input-file "inputs/day07.in")] [parsed (parse in-port)] [part1 (day07/run-part01 parsed)] [part2 (day07/run-part02 parsed)]) (printf "Part 1: ~a, Part 2: ~a\n" part1 part2)) -
Comment on Day 6: Guard Gallivant in ~comp.advent_of_code
kari (edited )LinkPart 2 took at least 90 minutes to run, I literally went to my work Christmas party and just came back to it being done, so maybe longer xD Racket #! /usr/bin/env racket #lang racket (require...Part 2 took at least 90 minutes to run, I literally went to my work Christmas party and just came back to it being done, so maybe longer xD
Racket
#! /usr/bin/env racket #lang racket (require "common.rkt" rackunit) ;; XXX: Might want to move a lot of these procedures to common.rkt ;; returns #t if i or j are out-of-bounds of in-map ;; else returns #f (define (out-of-bounds? in-map i j) (cond [(or (negative? i) (negative? j) (>= i (length in-map)) (>= j (length (list-ref in-map i)))) #t] [else #f])) ;; get the coordinates of the next step (define (next-step-coords coords dir) (cond [(eq? dir 'up) (cons (sub1 (car coords)) (cdr coords))] [(eq? dir 'down) (cons (add1 (car coords)) (cdr coords))] [(eq? dir 'left) (cons (car coords) (sub1 (cdr coords)))] [(eq? dir 'right) (cons (car coords) (add1 (cdr coords)))] [else 'invalid-dir])) ;; get the value at (i, j) else #f (define (map-ref in-map i j) (cond [(out-of-bounds? in-map i j) #f] [else (list-ref (list-ref in-map i) j)])) ;; get the value at the next step (define (map-ref-next-step in-map coords dir) (let* ([next-step-crds (next-step-coords coords dir)] [i (car next-step-crds)] [j (cdr next-step-crds)]) (map-ref in-map i j))) (define (replace-at-index lst i new-value) (cond [(empty? lst) '()] [(zero? i) (cons new-value (cdr lst))] [else (cons (car lst) (replace-at-index (cdr lst) (sub1 i) new-value))])) (define (replace-at-coords in-map coords new-value) (cond [(empty? in-map) '()] [(zero? (car coords)) (cons (replace-at-index (car in-map) (cdr coords) new-value) (cdr in-map))] [else (cons (car in-map) (replace-at-coords (cdr in-map) (cons (sub1 (car coords)) (cdr coords)) new-value))])) ;; returns the coordinates of the ^ on the map (define (find-start in-map) (let helper ((i 0) (j 0)) (cond ;; we went past the bottom right corner and somehow didn't find the start [(eq? i (length in-map)) 'no-start] ;; end of a row, go to start of the next row [(eq? j (length (list-ref in-map i))) (helper (add1 i) 0)] ;; these *should* never happen ;; but let's handle it just in case [(out-of-bounds? in-map i j) empty] ;; valid coordinates, check for #\^ [(eq? #\^ (list-ref (list-ref in-map i) j)) (cons i j)] ;; go to next column in the same row [else (helper i (add1 j))]))) (define (turn-right dir) (cond [(eq? dir 'up) 'right] [(eq? dir 'right) 'down] [(eq? dir 'down) 'left] [(eq? dir 'left) 'up] [else 'invalid-dir])) (define (looping? visited coords dir) (member (cons coords dir) visited)) ;; if there's an obstacle, turn 90-degrees right; ;; else, walk one step forwards. (define (walk in-map coords dir [visited '()]) (let ([next-step-val (map-ref-next-step in-map coords dir)]) (cond ;; we finish when we go out of bounds [(not next-step-val) (cons (cons coords dir) visited)] ;; easy way to "detect" a cycle; probably not very reliable but it works... [(looping? visited coords dir) (cons (cons coords dir) visited)] ;; obstacle, turn right [(eq? next-step-val #\#) (walk in-map coords (turn-right dir) visited)] ;; walk forward [else (walk in-map (next-step-coords coords dir) dir (cons (cons coords dir) visited))]))) (define (day06/run-part01 in-map) (let ([start-coords (find-start in-map)]) (set-count (list->set (map car (walk in-map start-coords 'up)))))) ;; TODO: Loop through visited and then walk again (define (day06/run-part02 in-map) (let* ([start-coords (find-start in-map)]) (for*/sum ([i (length in-map)] [j (length (list-ref in-map i))]) (cond [(and (not (eq? #\# (map-ref in-map i j))) (not (eq? #\^ (map-ref in-map i j)))) ; (printf "~a,~a\n" i j) (let* ([modded-map (replace-at-coords in-map (cons i j) #\#)] [visited (walk modded-map start-coords 'up)] [coords (car (car visited))] [dir (cdr (car visited))]) ; (printf "modded at (~a,~a): ~a\n" i j modded-map) (if (looping? (cdr visited) coords dir) 1 0))] [else 0])))) (check-equal? (day06/run-part01 (input->list (open-input-file "examples/day06.in"))) 41 "Test part 1") (check-equal? (day06/run-part02 (input->list (open-input-file "examples/day06.in"))) 6 "Test part 2") (check-equal? (day06/run-part01 (input->list (open-input-file "inputs/day06.in"))) 5453 "Test part 1") (let* ([in-map (input->list (open-input-file "inputs/day06.in"))] [part1 (day06/run-part01 in-map)]) ; [part2 (day06/run-part02 in-map)]) (printf "Part 1: ~a, Part 2: ~a\n" part1 'part2))I think most of the time is because I used a list of lists for the map instead of a vector of vectors, so trying to replace a single value is O(ij) instead of O(1). Honestly though, I think my part 1 is decent enough.
-
Comment on Day 4: Ceres Search in ~comp.advent_of_code
kari LinkPart 1 I could've made nicer and I'm sure it could be better, but I think my part 2 is fairly nice Racket #! /usr/bin/env racket #lang racket (require "common.rkt" math/base rackunit) ; return the...Part 1 I could've made nicer and I'm sure it could be better, but I think my part 2 is fairly nice
Racket
#! /usr/bin/env racket #lang racket (require "common.rkt" math/base rackunit) ; return the value at grid[i][j] ; null if i or j are invalid (define (grid-ref grid i j) (cond [(negative? i) null] [(>= i (length grid)) null] [(negative? j) null] [(>= j (length (list-ref grid i))) null] [else (list-ref (list-ref grid i) j)])) ;; we assume input is a non-empty rectangle, ;; i.e. width and height are even for all rows and colums, respectively, and ;; min(width, height) >= 1 (define (day04/run-part01 input) ;; really... these could just be made with a loop and adding an extra parameter for the direction (define (check-up grid i j [cur 0]) (cond [(eq? 0 cur) (if (eq? #\M (grid-ref grid i j)) (check-up grid (- i 1) j 1) 0)] [(eq? 1 cur) (if (eq? #\A (grid-ref grid i j)) (check-up grid (- i 1) j 2) 0)] [(eq? 2 cur) (if (eq? #\S (grid-ref grid i j)) 1 0)] [else 0])) (define (check-down grid i j [cur 0]) (cond [(eq? 0 cur) (if (eq? #\M (grid-ref grid i j)) (check-down grid (+ i 1) j 1) 0)] [(eq? 1 cur) (if (eq? #\A (grid-ref grid i j)) (check-down grid (+ i 1) j 2) 0)] [(eq? 2 cur) (if (eq? #\S (grid-ref grid i j)) 1 0)] [else 0])) (define (check-left grid i j [cur 0]) (cond [(eq? 0 cur) (if (eq? #\M (grid-ref grid i j)) (check-left grid i (- j 1) 1) 0)] [(eq? 1 cur) (if (eq? #\A (grid-ref grid i j)) (check-left grid i (- j 1) 2) 0)] [(eq? 2 cur) (if (eq? #\S (grid-ref grid i j)) 1 0)] [else 0])) (define (check-right grid i j [cur 0]) (cond [(eq? 0 cur) (if (eq? #\M (grid-ref grid i j)) (check-right grid i (+ j 1) 1) 0)] [(eq? 1 cur) (if (eq? #\A (grid-ref grid i j)) (check-right grid i (+ j 1) 2) 0)] [(eq? 2 cur) (if (eq? #\S (grid-ref grid i j)) 1 0)] [else 0])) (define (check-up-left grid i j [cur 0]) (cond [(eq? 0 cur) (if (eq? #\M (grid-ref grid i j)) (check-up-left grid (- i 1) (- j 1) 1) 0)] [(eq? 1 cur) (if (eq? #\A (grid-ref grid i j)) (check-up-left grid (- i 1) (- j 1) 2) 0)] [(eq? 2 cur) (if (eq? #\S (grid-ref grid i j)) 1 0)] [else 0])) (define (check-up-right grid i j [cur 0]) (cond [(eq? 0 cur) (if (eq? #\M (grid-ref grid i j)) (check-up-right grid (- i 1) (+ j 1) 1) 0)] [(eq? 1 cur) (if (eq? #\A (grid-ref grid i j)) (check-up-right grid (- i 1) (+ j 1) 2) 0)] [(eq? 2 cur) (if (eq? #\S (grid-ref grid i j)) 1 0)] [else 0])) (define (check-down-left grid i j [cur 0]) (cond [(eq? 0 cur) (if (eq? #\M (grid-ref grid i j)) (check-down-left grid (+ i 1) (- j 1) 1) 0)] [(eq? 1 cur) (if (eq? #\A (grid-ref grid i j)) (check-down-left grid (+ i 1) (- j 1) 2) 0)] [(eq? 2 cur) (if (eq? #\S (grid-ref grid i j)) 1 0)] [else 0])) (define (check-down-right grid i j [cur 0]) (cond [(eq? 0 cur) (if (eq? #\M (grid-ref grid i j)) (check-down-right grid (+ i 1) (+ j 1) 1) 0)] [(eq? 1 cur) (if (eq? #\A (grid-ref grid i j)) (check-down-right grid (+ i 1) (+ j 1) 2) 0)] [(eq? 2 cur) (if (eq? #\S (grid-ref grid i j)) 1 0)] [else 0])) ;; loop through the whole grid, ;; for each X, recursively check each direction (for*/fold ([total 0]) ([i (length input)] [j (length (list-ref input 0))]) ;; If we find an 'X', let's check for XMASes (let ([cur (list-ref (list-ref input i) j)]) (if (eq? cur #\X) (+ total (check-up input (- i 1) j) (check-down input (+ i 1) j) (check-left input i (- j 1)) (check-right input i (+ j 1)) (check-up-left input (- i 1) (- j 1)) (check-up-right input (- i 1) (+ j 1)) (check-down-left input (+ i 1) (- j 1)) (check-down-right input (+ i 1) (+ j 1))) total)))) (define (day04/run-part02 input) (define (check-x-mas grid i j) (if (eq? 2 (sum (list (check-updown-leftright grid i j) (check-updown-rightleft grid i j) (check-downup-leftright grid i j) (check-downup-rightleft grid i j)))) 1 0)) (define (check-updown-leftright grid i j) (if (and (eq? #\M (grid-ref grid (- i 1) (- j 1))) (eq? #\S (grid-ref grid (+ i 1) (+ j 1)))) 1 0)) (define (check-updown-rightleft grid i j) (if (and (eq? #\M (grid-ref grid (- i 1) (+ j 1))) (eq? #\S (grid-ref grid (+ i 1) (- j 1)))) 1 0)) (define (check-downup-leftright grid i j) (if (and (eq? #\M (grid-ref grid (+ i 1) (- j 1))) (eq? #\S (grid-ref grid (- i 1) (+ j 1)))) 1 0)) (define (check-downup-rightleft grid i j) (if (and (eq? #\M (grid-ref grid (+ i 1) (+ j 1))) (eq? #\S (grid-ref grid (- i 1) (- j 1)))) 1 0)) ;; loop through the whole grid, ;; for each X, recursively check each direction (for*/fold ([total 0]) ([i (length input)] [j (length (list-ref input 0))]) ;; If we find an 'X', let's check for XMASes (let ([cur (list-ref (list-ref input i) j)]) ;; A is always the center (if (eq? cur #\A) (+ total (check-x-mas input i j)) total)))) (let* ([input (input->list (open-input-file "inputs/day04.in"))] [part1 (day04/run-part01 input)] [part2 (day04/run-part02 input)]) (printf "Part 1: ~a, Part 2: ~a\n" part1 part2)) -
Comment on The CEO of UnitedHealthcare (insurance company) has been assassinated in NYC in ~news
kari Link ParentYeah, like he probably didn't deserves this specifically, but I don't really feel bad about it...Yeah, like he probably didn't deserves this specifically, but I don't really feel bad about it...
-
Comment on Day 3: Mull It Over in ~comp.advent_of_code
kari Link ParentMy girlfriend is already getting annoyed at me for thinking about AOC too much and I've only done 3 days. I fear this month won't end well for me xDthis year I have decided to not be consumed by AOC.
My girlfriend is already getting annoyed at me for thinking about AOC too much and I've only done 3 days. I fear this month won't end well for me xD
-
Comment on Day 3: Mull It Over in ~comp.advent_of_code
kari Link ParentOnce I realized I could do that it worked pretty well. If this does go further, I think it'd still work pretty well so long as the grammar stays regular. There are definitely some bits of my part...Once I realized I could do that it worked pretty well. If this does go further, I think it'd still work pretty well so long as the grammar stays regular. There are definitely some bits of my part 2 I should clean up, if I need to re-use it, though.
-
Comment on Day 3: Mull It Over in ~comp.advent_of_code
kari Link ParentI did it in with Regex, too, but in Racket, and I might try steal a recursive variant of your solution instead because yours is nice and I'm worried about having to add operations down the line xDI did it in with Regex, too, but in Racket, and I might try steal a recursive variant of your solution instead because yours is nice and I'm worried about having to add operations down the line xD
-
Comment on Day 3: Mull It Over in ~comp.advent_of_code
kari LinkI used regular expressions since that's the first thing I though of, though I'm sure I'll regret it and end up giving up early because of it. Even part 2 was confusing me for quite a while. Racket...I used regular expressions since that's the first thing I though of, though I'm sure I'll regret it and end up giving up early because of it. Even part 2 was confusing me for quite a while.
Racket
#! /usr/bin/env racket #lang racket (require math/base rackunit) ; TODO: Use #:match-select and capture groups (define (day03/run-part01 in) (sum (map (lambda (lst) (foldl * 1 lst)) (map (lambda (lst) (map string->number (regexp-match* (pregexp "\\d{1,3}") lst))) (regexp-match* (pregexp "mul\\(\\d{1,3},\\d{1,3}\\)") (read-line in)))))) (define (day03/run-part02 in) (car (foldl (lambda (cur result) ; we pass a pair along with the current result + status (if (string? cur) (if (equal? "don't()" cur) (cons (car result) #f) (cons (car result) #t)) (if (cdr result) ; should be 1 (cons (+ (* (car cur) (list-ref cur 1)) (car result)) #t) result))) (cons 0 #t) (map (lambda (lst) ; for "mul" operators, parse the strings into numbers and return as a list (if (regexp-match #rx"mul" lst) (map string->number (regexp-match* (pregexp "\\d{1,3}") lst)) lst)) ; match on any of the operators we know (regexp-match* (pregexp "(mul\\((\\d{1,3}),(\\d{1,3})\\))|(don)'t\\(\\)|(do)\\(\\)") (read-line in)))))) (let ([input (open-input-file "inputs/day03.in")]) (printf "~a\n" (day03/run-part01 input))) (let ([input (open-input-file "inputs/day03.in")]) (printf "~a\n" (day03/run-part02 input))) (check-equal? (day03/run-part01 (open-input-file "examples/day03_1.in")) 161 "Test part 1") (check-equal? (day03/run-part02 (open-input-file "examples/day03_2.in")) 48 "Test part 2") -
Comment on Reusing plastic water bottles, to-go containers? Scientists say that’s a bad idea. in ~health
kari Link ParentThose jars look nice. I might have to show my girlfriend, she loves a good jar lolThose jars look nice. I might have to show my girlfriend, she loves a good jar lol
-
Comment on Reusing plastic water bottles, to-go containers? Scientists say that’s a bad idea. in ~health
kari Link ParentThis very much depends on where you are. In Texas, it's only the more "fancy" or like "health food" stores that use paper bags. In Austin, Texas, specifically, we used to have ban on plastic bags...US uses paper bags
This very much depends on where you are. In Texas, it's only the more "fancy" or like "health food" stores that use paper bags. In Austin, Texas, specifically, we used to have ban on plastic bags and a law requiring paper bags cost something like 15¢ to encourage bringing your own reusable bags, but the state government hates us so that's not a thing anymore and now we're like the rest of the state.
-
Comment on Day 2: Red-Nosed Reports in ~comp.advent_of_code
kari Link ParentThanks!! For comment 3, no clue, I just saw it when I was searching the racket docs and tried it 😂 I should probably spend some time going through the rest of the guide, I basically saw ports are...Thanks!! For comment 3, no clue, I just saw it when I was searching the racket docs and tried it 😂
I should probably spend some time going through the rest of the guide, I basically saw ports are how to do I/O and then used it, that was it. :P
-
Comment on Day 2: Red-Nosed Reports in ~comp.advent_of_code
kari Link ParentMe right now trying to learn Racket, but it's fun :Pbut I don't want to be fighting both the puzzles and the language.
Me right now trying to learn Racket, but it's fun :P
-
Comment on Day 2: Red-Nosed Reports in ~comp.advent_of_code
kari LinkTook me a while ago but I think I'm sorta kinda getting the hang of some basic Racket programming. I spent a while trying to figure out smarter ways for both parts but even as it is, running both...Took me a while ago but I think I'm sorta kinda getting the hang of some basic Racket programming. I spent a while trying to figure out smarter ways for both parts but even as it is, running both (and printing) only takes 0.225s on my machine.
Racket solution
#! /usr/bin/env racket #lang racket (require racket/base rackunit) (define (remove-element-by-index lst i) (if (null? lst) empty (if (= i 0) (cdr lst) (cons (car lst) (remove-element-by-index (cdr lst) (- i 1)))))) ; split each report into its levels and convert from string to number (define (reports in) (for/list/concurrent ([l (in-lines in)]) (map string->number (string-split l " ")))) ; reports are safe if-and-only-if: ; - The levels are either all increasing or all decreasing. ; - Any two adjacent levels differ by at least one and at most three. (define (safe? report) (and (or (for/and ([x (in-list report)] [y (in-list (cdr report))]) (< x y)) (for/and ([x (in-list report)] [y (in-list (cdr report))]) (> x y))) (for/and ([x (in-list report)] [y (in-list (cdr report))]) (let ([difference (abs (- x y))]) (and (>= difference 1) (<= difference 3)))))) ; reports are safe if, when removing AT MOST 1 bad level, the remaining: ; - The levels are either all increasing or all decreasing. ; - Any two adjacent levels differ by at least one and at most three. ; this procedure just brute-forces it... (define (tolerant-safe? report) (or (safe? report) (for/or ([i (in-range (length report))]) (safe? (remove-element-by-index report i))))) (define (run-part01 in) (foldl (lambda (cur result) (if cur (+ 1 result) result)) 0 (for/list ([report (reports in)]) (safe? report)))) (define (run-part02 in) (foldl (lambda (cur result) (if cur (+ 1 result) result)) 0 (for/list ([report (reports in)]) (or (safe? report) (tolerant-safe? report))))) (let ([input (open-input-file "inputs/day02.in")]) (printf "~a\n" (run-part01 input))) (let ([input (open-input-file "inputs/day02.in")]) (printf "~a\n" (run-part02 input))) (check-equal? (run-part01 (open-input-file "examples/day02.in")) 2 "Test part 1") (check-equal? (run-part02 (open-input-file "examples/day02.in")) 4 "Test part 2")Once again, anyone who knows Racket can feel free to tell me what I did that not idiomatic (or just what's inefficient, too).
My part 2 works pretty well, but I don't think it's particularly idiomatic Racket, so anyone who knows more can feel free to let me know how the
blink-efficientprocedure can be improved :)Racket