ShareMyScreen/AdventOfCode/2022/13/DistressSignalJP
This one was really a challenging one to me, and it took me several days to get my head around the parsing and the recursion. It took me so many tries that I don't remember the details; the description below contains only some that I could reconstruct from the comments I wrote in my code.
Entire solution
i13=: freads '13.txt'
NB. Part A: sum of inds (1 based) of pairs in order
par=: [: (line;._1;._2~ LF2&E.) LF&([,,~) NB. parsing
NB. Take a flat boxed array convert to a single nested box
single=:[:<@,[: ".&.>`]@.(32=3!:0@>);._1 (<,','),}.@}:
NB. Process single line (y)
line=: {{
y=.;:y NB. operate on boxed J words
while. 1<#y do. NB. all inputs are arrays, merge from deep up.
md=. (=>./) +/\ 1 _1 0{~(;:'[]')&i. y NB. mask tok @ max depth
NB. Deepest box indices
dbi=. (<@(,>:@{:);.1~ 1,1<2-~/\])@:I. md
NB. update y, put parsed box in first remove others
y=. (<<<;}.&.>dbi) { ( dbi single@(>@[{])"0 _ y) ({.&> dbi)} y
end.
{.y
}}
NB. comp returns _1 if good order, 1 if not, 0 if undecided.
NB. verb before explicit verb fails on boxed (*@:-), after which explicit verb is called
comp =: [: {. (*@:-`1:`_1:`0:@.(2#.0=,&#)) :: {{
for_yy. y do. NB. loop through right array
if. yy_index=#x do. _1 return. end. NB. left ran out first --> fine, _1
NB. recurse on current items, if decision (_1,1), return
if. 0~:r=.(yy_index{x) comp&> yy do. r return. end.
NB. r was 0, continue with next item
end.
x (*@-&#) y NB. y ran out, check lengths
}}
validpairs =: 2 %~ 1- comp&>/"1
part1=:[: +/@:>:@I. validpairs@par
NB. part 2: sort packages, and find indices of special packages [[2]] and [[6]]
spec=: ,par '[[2]]',LF,'[[6]]',LF
NB. instead of sorting all, find how many are smaller.
part2=: [: */ spec ([ (1+[:+/1=comp&>)"0 _ (,,)) par
(part1;part2)i13
Data and Parsing
The input is given again in pairs of lines, separated by empty lines, very similar to day 11's input. The outline of the parsing verb is the same:
par=: [: (line;._1;._2~ LF2&E.) LF&([,,~)
The verb "line" processes a single line specifying a "packet" of a distress signal, e.g. '[[1,[2]],3,[4,[5]]]'. For part 1, the assignment is finding the sum of the indices of the pairs where the packets are in order, which involves comparing the numerical values at various levels (later more).
When I saw the input, I thought it looked almost like J, and I tried to get the right structure by just using find and replace like I did many times before. It turned out to be a little more complicated than that: Numbers cannot simply be treated as numbers, and they should not "stick" together in arrays.
A second approach I thought of, remembering one of my favourite APL / J introductory examples: parentheses nesting depth (mentioned for instance here).
Here's a version with some echo's thrown in to understand what's happening:
line2 =: {{
y=.;:y NB. operate on boxed J words
while. 1<#y do. NB. all inputs are arrays, merge from deep up.
md=. (=>./) +/\ 1 _1 0{~(;:'[]')&i. y NB. mask tok @ max depth
echo y ,: <"0 md NB. y and mask
NB. Deepest box indices
echo dbi=. (<@(,>:@{:);.1~ 1,1<2-~/\])@:I. md
NB. update y, put parsed box in first index, remove others
y=. (<<<;}.&.>dbi) { ( dbi single@(>@[{])"0 _ y) ({.&> dbi)} y
end.
{.y NB. Should be atom, not a list of length 1.
}}
single=:[:<@,[: ".&.>`]@.(32=3!:0@>);._1 (<,','),}.@}:
Simply said line merges boxes from bottom to top in the hierarchy:
- Convert string input to boxed words using
;:(the input does form J words, although not quite meaningful ones); - While there's more than a single item:
- Find a mask where the nesting level is equal to the maximum (md) by looking up the brackets, converting [ and ] (both as boxes) to 1 and _1 and doing a running sum on the result (+/\);
- Find sets of deepest box indices of the boxes in current y and putting them into boxes for each run of indices (as multiple parts of the array can be at the same level) and storing them in dbi;
- Find the single box for each of the sets of indexed boxes using single;
- Put that single box in place of the first indexed box into y;
- Discarding the remaining indexed boxes from y.
- When done, y is a one-item list, so the head is the result.
The line calculating dbi is interesting: After getting the indices of the ones in md, it finds which pairs are more than 1 apart, i.e. they are not a run of successive indices. As the first run is always needed and I want to use cut (u;.1), I prepend a 1. Now I use cut to append one further index (the first 0 after a run of 1's in md is still part of the deepest level, as seen in the example below) and box.
The verb single has more work to do than I suspected at first sight, because it does not only get boxed strings (initial input), but after the first round also boxed boxes. After discarding the obligatory starting and ending brackets, the items are separated with <,','. Splitting the items using cut, the items being boxed strings are numbers, and should be converted to integers. The items being boxed boxes should not be touched, because they are already done. For this reason, I had to use Agenda (@.) for checking whether the input is boxed or not, and applying the correct verb accordingly. I could have used the power conjunction (^:) instead.
I was particularly happy about the dbi and amend steps, as both efficiently deal with updating multiple parts of the array being at the same depth. An example run demonstrates this:
line2 '[[1,[2]],3,[4,[5]]]' === Iteration === ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐ │[│[│1│,│[│2│]│]│,│3│,│[│4│,│[│5│]│]│]│ ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤ │0│0│0│0│1│1│0│0│0│0│0│0│0│0│1│1│0│0│0│ NB. multiple disjoint blocks at same level └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘ NB. Note closing brackets get 0, but should be 1. ┌─────┬────────┐ │4 5 6│14 15 16│ NB. Corresponding index sets └─────┴────────┘ === Iteration === ┌─┬─┬─┬─┬───┬─┬─┬─┬─┬─┬─┬─┬───┬─┬─┐ │[│[│1│,│┌─┐│]│,│3│,│[│4│,│┌─┐│]│]│ NB. [2] and [5] replaced by single boxes │ │ │ │ ││2││ │ │ │ │ │ │ ││5││ │ │ │ │ │ │ │└─┘│ │ │ │ │ │ │ │└─┘│ │ │ ├─┼─┼─┼─┼───┼─┼─┼─┼─┼─┼─┼─┼───┼─┼─┤ │0│1│1│1│1 │0│0│0│0│1│1│1│1 │0│0│ └─┴─┴─┴─┴───┴─┴─┴─┴─┴─┴─┴─┴───┴─┴─┘ ┌─────────┬─────────────┐ │1 2 3 4 5│9 10 11 12 13│ └─────────┴─────────────┘ === Iteration === ┌─┬───────┬─┬─┬─┬───────┬─┐ │[│┌─┬───┐│,│3│,│┌─┬───┐│]│ │ ││1│┌─┐││ │ │ ││4│┌─┐││ │ │ ││ ││2│││ │ │ ││ ││5│││ │ │ ││ │└─┘││ │ │ ││ │└─┘││ │ │ │└─┴───┘│ │ │ │└─┴───┘│ │ ├─┼───────┼─┼─┼─┼───────┼─┤ │1│1 │1│1│1│1 │0│ └─┴───────┴─┴─┴─┴───────┴─┘ ┌─────────────┐ │0 1 2 3 4 5 6│ └─────────────┘ ┌───────────────────┐ │┌───────┬─┬───────┐│ ││┌─┬───┐│3│┌─┬───┐││ │││1│┌─┐││ ││4│┌─┐│││ │││ ││2│││ ││ ││5││││ │││ │└─┘││ ││ │└─┘│││ ││└─┴───┘│ │└─┴───┘││ │└───────┴─┴───────┘│ └───────────────────┘
Part 1
Now that we have the parsing done, matters become a bit more easy. Or do they? The problem asks us to compare lists to see whether they are in order. Comparison is to be done item per item:
- if both items are integers: if L < R: ok, if L > R: not ok, if L=R: then continue with the next item in both lists;
- if both items are lists: compare items; if L runs out before R: ok;
- if mixed, make a list of the integer and continue as above.
For a moment I thought the TAO of J would have me covered, but sadly, its semantics don't align with the above definition. It is clear the requirements are quite complex, and rife with corner cases that could bite back. Some are contained in the test data, but not all. I remember being stuck at a point where my verb worked on the test data, but not on my input; an infuriating situation. If I recall correctly, it was due to my code not handling empty lists well.
It is clear recursion is the way to go here, as decisions on an array depend on the decision of all deeper nested levels. Although the code makes it seem as if "ok" and "not ok" would suffice, there's also a need for "continue" when there's an equality. This is very similar to the output of the signum (*) verb, so I used _1 for smaller than, 1 larger than, 0 equal/to be decided.
The comparison verb (dyad) I ended up with is the following:
comp =: [: {. (*@:-`1:`_1:`0:@.(2#.0=,&#)) :: special
I don't recall exactly how I ended up with this wording, but it works as follows: It considers all cases that are immediately decidable at first, based on which arguments are empty:
- none are empty: assume numeric, and use
*@-. If one of the two is not numeric, it means it is a special case, treated in the "special" verb (see below). - x is empty: return 1 (in order)
- y is empty: return _1 (not in order)
- both are empty: return 0 (equal)
The special verb is called because *@- on a non-numeric triggers an error, causing the assigned adverse, "special", to be executed. Whether such error-throwing abuse is acceptable in general is debatable; for AoC it is perfectly fine.
special loops over all items in both arrays and recurses to comp treating the next deeper level:
special =: {{
for_yy. y do. NB. loop through right array
if. yy_index=#x do. _1 return. end. NB. left ran out first --> fine, _1
NB. recurse on current items, if decision (_1,1), return
if. 0~:r=.(yy_index{x) comp&> yy do. r return. end.
NB. r was 0, continue with next item
end.
x (*@-&#) y NB. y ran out, check lengths
}}
I initially called boxopen on x and y, but that's not needed as open (>) on open values does nothing, so the open in comp&> doesn't hurt if any of x or y are not boxed.
Now that comparison of parsed packages is defined we can use it to find whether pars are valid or not (just converting _1 and 1 to 0 and 1), and the requested result (sum of the indices of in-order pairs, 1-based):
validpairs =: 2 %~ 1- comp&>/"1
part1=:[: +/@:>:@I. validpairs@par
Part 2
In part 2, there are two divider packets 2 and 6. To find the decoder key, we're asked to, ignore the empty lines and sort the packets, add the divider packets to our input, and find the 1-based indices of the divider packets and multiply them together.
My initial thought was: "Great, I already have a comparison function, I know quicksort is very simple to implement in J", so I wrote the following following the same reasoning:
pqs=: (([ ($:@(#~_1&=) , (#~0&=) , $:@(#~1&=)) comp&>) ({~ ?@#))^:(1<#)
part2a=:*/@:>:@(spec i.~ pqs)@(spec,,)@par
While it works, and could be used for the solution, I thought again and found that it unnecessarily sorts all packets, I only need the index of the special packets, i.e. only how many are smaller than each of them:
spec=: ,par '[[2]]',LF,'[[6]]',LF
part2=: [: */ spec ([ (1+[:+/1=comp&>)"0 _ (,,)) par
Indeed, timespacex confirms the second version is double as fast as the alternative using quicksort:
'part2a i13' %&(100×pacex) 'part2 i13' 2.05484 0.998312
I expected the quicksort alternative to be slower though, given there are 300 packets to be sorted, and the final version has to lookup only 2 packets' indices.