Day 4

For part 1, given a pair of ranges like 2-4,6-8, find if one range fully encloses the other. I couldn’t quickly figure out how to parse integers from strings in APL, so just went ahead and did the parsing in CL (hey, that’s why I’m using April, right?).

(defun parse-line (line)
  (map 'vector 'parse-integer (cl-ppcre:split "[,-]" line)))

Thinking in arrays, the approach I settled on was to expand the ranges into boolean arrays1, e.g. 3-6 becomes 0 0 1 1 1 1, calculate the intersection between the ranges, then see if the result is identical to either range. The APL I conjured to do that seems a bit arcane and, as is becoming a theme here, could undoubtably be simplified.

expand{(⍺-1) (1+-⍺) / 0 1}
contains{
m⍝ find where arguments overlap
(⍺m)  (⍵m)    ⍝ overlaps equal either argument?
}
f{
contains/ ↓↑ expand/ 2 2 }
ans1 +/ f ¨ in

The expand function is straightforward, again using replicate (see part 3) to construct an array as described above. The contains function implements the boolean operations I described - I suspect this is another case where tacit functions could be used to simplify the operation.

The well-named f function does the heavy lifting:

  1. First we reshape the input array (which would be something like 2 4 6 8 to represent the input 2-4,6-8) to separate the ranges.
  2. Next we expand the ranges, using reduce since I wrote the expand function to take two arguments. It seems simpler/cleaner than trying to grab the first and last elements like I did in an earlier problem.
  3. Then we shake things up and see what falls out. But seriously, we use mix () to combine the ranges into a 2D array, which automatically expands the shorter one to the same length as the longer, filling it with zeroes. We then split () them back apart, since we need to do the next operation on the entire rows, not individual elements.
  4. Finally we reduce with contains, again because I wrote the function to take two arguments.

Applying f over all the input lines gets us an array of booleans saying whether each line has fully-containing ranges or not. So to get the final answer then we just need to sum them up.

Aside: This is something I’m really loving about APL - when building a solution (which I have been doing more in the REPL, so I take back what I said in part 1 about april lacking that interactivity2), you can go from examing the output array to the final answer by just adding a couple characters. And in general, you can just keep piling functions onto the front to build to the final solution. For example, this is an extract from my REPL while solving this:

AOC> (april-f "f←{↑{(⍺-1) (1+⍵-⍺) / 0 1}/ 2 2 ⍴ ⍵} ◊ f 2 6 6 8")
0 1 1 1 1 1 0 0
0 0 0 0 0 1 1 1
#2A((0 1 1 1 1 1 0 0) (0 0 0 0 0 1 1 1))
AOC> (april-f "f←{{⍵}↓↑{(⍺-1) (1+⍵-⍺) / 0 1}/ 2 2 ⍴ ⍵} ◊ f 2 6 6 8")
 0 1 1 1 1 1 0 0  0 0 0 0 0 1 1 1
#(#(0 1 1 1 1 1 0 0) #(0 0 0 0 0 1 1 1))
AOC> (april-f "f←{{⍺ ∧ ⍵}/↓↑{(⍺-1) (1+⍵-⍺) / 0 1}/ 2 2 ⍴ ⍵} ◊ f 2 6 6 8")
 0 0 0 0 0 1 0 0
#0A#(0 0 0 0 0 1 0 0)
AOC> (april-f "f←{{⍺ ≡ ⍺ ∧ ⍵}/↓↑{(⍺-1) (1+⍵-⍺) / 0 1}/ 2 2 ⍴ ⍵} ◊ f 2 6 6 8")
0
0
AOC> (april-f "f←{{m←⍺ ∧ ⍵ ◊ (⍺≡m) ∨ (⍵≡m)}/↓↑{(⍺-1) (1+⍵-⍺) / 0 1}/ 2 2 ⍴ ⍵} ◊ f 2 6 6 8")
0
0
AOC> (april-f "f←{{m←⍺ ∧ ⍵ ◊ (⍺≡m) ∨ (⍵≡m)}/↓↑{(⍺-1) (1+⍵-⍺) / 0 1}/ 2 2 ⍴ ⍵} ◊ f 2 6 2 8")
1
1

Part 2

Now we just need to identify if the ranges overlap at all, which thanks to the approach we took is just a simple modification. Instead of checking if either range array is identical to the match array, we just need to see if any elements are true/1, which can be done by reducing the match array with a boolean or (), or alternatively by checking if the sum is greather than zero (0 < +/⍺ ∧ ⍵).

expand{(⍺-1) (1+-⍺) / 0 1}
overlaps{/}
f{overlaps/ ↓↑ expand/ 2 2 }
ans2 +/ f ¨ in

  1. I peeked at the input to make sure that the ranges aren’t absurdly large (only into the double digits), so we don’t have to worry about blowing out the memory with massive sparse arrays. If they were larger, we’d probably just have to do comparisons on the endpoints instead, which is probably what I would have done if I weren’t working in APL. ↩︎

  2. although it can be annoying when you make a mistake and have to break out of a bunch of restarts due to all the threads it spawned. ↩︎


Next: Advent of Code 2022 part 5
/Posts
/Photos
#adventofcode (23)
#apl (5)
#baking (1)
#biggreenegg (9)
#chia (5)
#data-visualization (8)
#development (46)
#devops (4)
#docker (1)
#electronics (7)
#engineering (9)
#food (11)
#golang (1)
#home-improvement (3)
#julia (17)
#keto (1)
#keyboards (4)
#lisp (8)
#meta (1)
#monitoring (10)
#photos (13)
#racket (1)
#recipes (6)
#rust (1)
#woodworking (12)