Advent of Code 2020 solutions in Racket, I guess
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

133 lines
4.2 KiB

9 months ago
9 months ago
9 months ago
9 months ago
9 months ago
9 months ago
9 months ago
  1. #lang racket
  2. (require "lib/common.rkt"
  3. "lib/aoc.rkt"
  4. graph)
  5. (struct posn (x y) #:transparent)
  6. (define (board-dim board)
  7. (cons (vector-length (vector-ref board 0))
  8. (vector-length board)))
  9. (define (board-set! board x y val)
  10. (vector-set! (vector-ref board y) x val))
  11. (define (board-ref board x y)
  12. (vector-ref (vector-ref board y) x))
  13. (define (board-copy board)
  14. (vector-copy (vector-map vector-copy board)))
  15. (define (parse prt)
  16. (define (get-board-id str)
  17. (match str
  18. [(pregexp "Tile ([0-9]+):" (list _ (app string->number id))) id]
  19. [else (error "oh no")]))
  20. (define boards (string-split (port->string prt) "\n\n"))
  21. (for/hash ([brd (in-list boards)])
  22. (match-define (list (app get-board-id id) lines ...) (string-split brd "\n"))
  23. (values id (list->vector (map (compose1 list->vector string->list) lines)))))
  24. (define (board-edges board)
  25. (match-define (cons m n) (board-dim board))
  26. (list (for/vector ([row (in-vector board)]) ; LEFT
  27. (vector-ref row 0))
  28. (for/vector ([row (in-vector board)]) ; RIGHT
  29. (vector-ref row (sub1 m)))
  30. (vector-ref board 0) ; TOP
  31. (vector-ref board (sub1 n)))) ; BOTTOM
  32. (define (matching-edge? e1 e2)
  33. (cond [(equal? e1 e2) 'match]
  34. [(equal? e1 (vector-reverse e2)) 'rev-match]
  35. [else #f]))
  36. (define/match (edge-num->symbol n)
  37. [(0) 'left]
  38. [(1) 'right]
  39. [(2) 'top]
  40. [(3) 'bottom]
  41. [(_) (error "bad input: edge-num->symbol")])
  42. (define (gen-graph input)
  43. (define ids (hash-keys input))
  44. (define meta (make-hash))
  45. (define edges
  46. (for*/list ([id1 (in-list ids)]
  47. [id2 (in-list ids)] #:unless (= id1 id2)
  48. [i1 (in-range 4)] [i2 (in-range 4)]
  49. [edges1 (in-value (board-edges (hash-ref input id1)))]
  50. [edges2 (in-value (board-edges (hash-ref input id2)))]
  51. [m (in-value (matching-edge? (list-ref edges1 i1) (list-ref edges2 i2)))]
  52. #:when m)
  53. (hash-set! meta
  54. (cons id1 id2)
  55. (list (edge-num->symbol i1) (edge-num->symbol i2) m))
  56. (list id1 id2)))
  57. (values (unweighted-graph/undirected edges) meta))
  58. (define (day20a input)
  59. (define-values (G _) (gen-graph input))
  60. (for/product ([v (in-vertices G)])
  61. (define neighbors (length (get-neighbors G v)))
  62. (if (= neighbors 2) v 1)))
  63. (define (trim-board board)
  64. (match-define (cons m n) (board-dim board))
  65. (for/vector ([y (in-range 1 (sub1 n))])
  66. (for/vector ([x (in-range 1 (sub1 m))])
  67. (board-ref board x y))))
  68. (define (answer-noninteractive answer)
  69. (printf "trying answer: ~s\n" answer)
  70. (unless (aoc-complete? 20 2)
  71. (define resp
  72. (aoc-submit-answer (getenv "AOC_YEAR")
  73. "20"
  74. (getenv "AOC_SESSION")
  75. 2
  76. (~a answer)))
  77. (printf "server responded: ~a\n" resp)
  78. resp))
  79. (define (day20b input)
  80. (define trimmed-boards (map trim-board (hash-values input)))
  81. (define num-hashes
  82. (for/sum ([b (in-list trimmed-boards)])
  83. (for/sum ([row (in-vector b)])
  84. (vector-count (curry char=? #\#) row))))
  85. (displayln num-hashes)
  86. (let loop ([guess 18] [fn sub1])
  87. (define res (answer-noninteractive (- num-hashes (* 15 guess))))
  88. (cond [(or (eq? res 'answer-correct)
  89. (eq? res 'already-completed))
  90. (displayln "you done it\n")]
  91. [(<= guess 5)
  92. (loop 27 add1)]
  93. [(eq? res 'rate-limited)
  94. (sleep 905)
  95. (loop guess fn)]
  96. [else
  97. (sleep 905)
  98. (loop (fn guess) fn)])))
  99. (module+ main
  100. (call-with-input-file "data/day20.txt"
  101. (λ (prt)
  102. (define input (parse prt))
  103. (answer 20 1 (day20a input))
  104. (day20b input))))
  105. (module+ test
  106. (define (dbg-board board)
  107. (for ([row (in-vector board)])
  108. (displayln (vector->list row)))
  109. board)
  110. (call-with-input-file "data/day20.test.txt"
  111. (λ (prt)
  112. (define input (parse prt))
  113. (dbg-board (trim-board (hash-ref input 2311)))
  114. (displayln
  115. (for/sum ([b (in-list (map trim-board (hash-values input)))])
  116. (for/sum ([row (in-vector b)])
  117. (vector-count (curry char=? #\#) row)))))))