Advent of Code 2022 part 4
Day 4
[20221204]#development #adventofcode #lisp #apl
Previous: Advent of Code 2022 part 3
Next: Advent of Code 2022 part 5
Day 4
For part 1, given a pair of ranges like 24,68
, 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 parseline (line)
(map 'vector 'parseinteger (clppcre:split "[,]" line)))
Thinking in arrays, the approach I settled on was to expand the ranges
into boolean arrays^{1}, e.g. 36
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 wellnamed f
function does the heavy lifting:
 First we reshape the input array (which would be something like
2 4 6 8
to represent the input24,68
) to separate the ranges.  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.  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.  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 fullycontaining 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 interactivity^{2}), 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> (aprilf "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> (aprilf "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> (aprilf "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> (aprilf "f←{{⍺ ≡ ⍺ ∧ ⍵}/↓↑{(⍺1) (1+⍵⍺) / 0 1}/ 2 2 ⍴ ⍵} ◊ f 2 6 6 8")
0
0
AOC> (aprilf "f←{{m←⍺ ∧ ⍵ ◊ (⍺≡m) ∨ (⍵≡m)}/↓↑{(⍺1) (1+⍵⍺) / 0 1}/ 2 2 ⍴ ⍵} ◊ f 2 6 6 8")
0
0
AOC> (aprilf "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

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. ↩︎

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