From J Wiki
Jump to navigation Jump to search

The Problem << >>

Problem: given range pairs, find how many are contained in the other (part 1), and how may overlap at all (part 2).

As advent of code is not a real life situation, I've taken a really lazy approach to this day, listing all ranges rather than operating on the range borders. This is possible since ranges are all small:

   >./, -~/"1 (2 2$".);._2 rplc&'- , ' freads '04.txt'

Given this, performance is unlikely an issue, but cleaner/nicer solutions do exist (see Henry's solution).

Entire solution

to=: {{ m (<. + i.@>:@-~) n}} NB. conj so no need for (...)
i4=: ".@rplc&('-';' to ';',';';');._2 freads '04.txt'
part1=: [: +/ (e. +.&(*./) e.~)&>/"1
part2=: [: +/ ([ *@#@-. -.)&>/"1

Data encoding

As often the case in AoC, I adapt the input such that it can be executed as J code. I think this is fine here, but wouldn't recommend such approach to anything serious, as it opens the door to unchecked code execution.

As mentioned above, I simply list each range. For this I use a conjunction, rather than a verb, since conjunctions are executed before the verb is executed (see the page on parsing for the gory details), eliminating the need for parentheses when interpreting input lines turned to J code:

to=: {{ m (<. + i.@>:@-~) n}}
   1 to 3 ; 5 to 7
|1 2 3|5 6 7|

To get such phrases from the given input lines, I replace '-' with ' to ' and ',' with ';', in order to have boxed ranges, for each input line, using the stdlib function rplc. Executing each phrase tops off the processing for each line:

i4=: ".@rplc&('-';' to ';',';';');._2 freads '04.txt'

The result is a list of pairs of boxed enumerations of the required numeric ranges.

Part 1

Part 1 asks where either of the ranges fully overlaps the other, that is, all of the left range are member of the right range, or all of the right range are member of the left range. This translates directly to J as *./@e. +. *./@e.. As "all", *./, is executed on both left and right tines of this fork, it can also be absorbed into the middle tine, using Compose:

ContainsOrContained=: e. +.&(*./) e.~

Doing this for each pair of ranges, i.e. each row of i4 is done putting ContainsOrContained composed with unboxing between items of each row:

part1=: [: +/ ContainsOrContained&>/"1

Part 2

Part two asks for any overlap, which is actually easier: an overlap means that the interval intersection is not empty, i.e. its count or tally is positive. So we can write the solution analogously to the one of part 1:

part2=: [: +/ intersectTallyPos&>/"1

The check for the intersection tally being positive can be implemented by using the signum function,* after tally (#). These can be placed on the middle tine of set interesction fork:

intersectTallyPos=: [ *@#@-. -.