Advent of Code 2022 - Day 4: Camp Cleanup

2022-12-04 :: programming, puzzle, racket

1 2	#lang iracket/lang #:require racket (require "../advent.rkt")

Day 4 - Part 1

Camp Cleanup

Before we get started with today’s puzzle, I have some cleanup of my own to do!

1. all-from-out

At the beginning of each day, the second line of the prelude above is:

(require "../advent.rkt")

This is Racket’s way of importing a module. Rather than also having to import common modules I typically use, such as the threading module, e.g. (require "../advent.rkt" threading), I’d like to be able to just import my advent.rkt module and get access to threading as well. I learned a long time ago that the answer to the question, “Can Racket do <X>”, is almost always, “yes”, and this is no exception; it’s accomplished with the all-from-out macro. My advent.rkt module already had (require threading) for it’s own purposes, so I just needed a directive to have it export all of the exports from threading as if they were defined in advent.rkt:

(provide (all-from-out threading))

2. A parsing fix

One of the parsers I got from Peter Norvig is the numbers parser, and it allows parsing input such as 1,2 | -3,4 into a list of numbers, '(1 2 -3 4); however, today’s input was like 49-51,31-50, and the numbers parser would output '(49 -51 31 -50. The - chars were meant to be separators, not negative signs. The original numbers parser used the regex pattern -?[0-9.]+. Modifying the regex pattern to be ((?<![0-9])-)?[0-9.]+ instead, which uses a negative lookbehind pattern, correctly outputs '(49 51 31 50).

The negative lookbehind pattern (?<![0-9]) is used in front of the -, so that the - will only match if it’s not preceded by a numeric digit. This is a very handy regex technique.

Ok, with the modified numbers parser in place, let’s parse today’s input!

1	(define in (parse-aoc 4 numbers))

----------------------------------------------------------------------------------------------------
day04.txt -> 11358 chars, 1000 lines; first 3 lines; last 2 lines:
----------------------------------------------------------------------------------------------------
49-51,31-50
96-99,2-95
2-62,62-98
...
32-38,33-71
3-5,4-98
----------------------------------------------------------------------------------------------------
(parse 4) -> 1000 entries:
----------------------------------------------------------------------------------------------------
((49 51 31 50)
(96 99 2 95)
...
(3 5 4 98))
----------------------------------------------------------------------------------------------------

Great, it appears to be working perfectly! For Part 1, we need to determine if one elf’s range of section numbers is a subset/superset of the other elf’s range. The first thing that popped into my head was to simply compare range endpoints. Since parsing produced a list of 4 numbers for each elf pair, I need to destructure the list, and Racket’s match-let is handy for this. The match pattern of (list a b c d) both matches and binds the values of the list’s elements:

(define (overlap? lst)
  (match-let ([(list a b c d) lst])
    (or (and (<= a c) (>= b d))
        (and (<= c a) (>= d b)))))

With this overlap? predicate, all that remains is to count the occurrences:

1	(count overlap? in)

453

Part 2

For Part 2, rather than looking for subsets/supersets, we just need to determine if the ranges overlap at all. Rather than modify my approach for Part 1 for this case, it seemed simpler to me to just convert the ranges to sets and determine if the intersection is non-empty:

(define (overlap-partial? lst)
  (match-let ([(list a b c d) lst])
    (let ([ one (inclusive-range a b) ]
          [ two (inclusive-range c d) ])
      (not (set-empty? (set-intersect one two))))))

Again, all we need to do now is count the occurences:

1	(count overlap-partial? in)

919

Today was enjoyable, the hammer has yet to drop on us with a tough puzzle, but it will!

Refactor

Now, with the hindsight of having seen both parts, how would I construct a solution? Assuming each elf’s range is a set, for Part 1, we need to determine if one range is a subset of another. For Part 2, we need to determine if the intersection of the two sets is non-empty. Let’s create a predicate for each part and a common need-reorg? function:

(define (part1? a b) (or (subset? a b) (subset? b a)))

(define (part2? a b) (not (set-empty? (set-intersect a b))))

(define ((need-reorg? part?) lst)
  (match-let ([(list a b c d) lst])
    (part? (inclusive-range a b) (inclusive-range c d))))

Now we can count the occurences for each part:

1	(count (need-reorg? part1?) in)

453

1	(count (need-reorg? part2?) in)

919