From J Wiki
Jump to navigation Jump to search

The Problem << >>

Entire solution

i3=: freads '03.txt' NB. read input
scores=: (26|.Alpha_j_) +/@:>:@i. ] NB. letters -> total score
part1 =: [: scores ([{.@-.-.)/@(]\~ -@-:@#);._2
part2 =: [: scores [: {.@> _3 ([-.-.)&.>/\ <;._2
(part1;part2) i3 NB. boxed results for part 1 & 2

Part 1

Part 1 asks for the sum of the scores of the items found in both compartments of a rucksack (i.e. halves of each input line). This task has two natural parts: finding the element for each input line, and finding the total score for the elements found.

One could box each input line to handle the different lengths, but this is not required for part 1, as each line is treated independently. There's also no need to convert to numbers at the beginning: They consume more space than literal characters, and all set operations work for literals as well. Additionally, displaying literals takes up less space than numbers for debugging while programming. Only just before summing, the characters should be converted to numbers (one cannot sum characters in J).

The processing of each input line (of variable length) to find that element is independent of and the same for each input line. Being different lines, they are records separated with linefeeds. As for previous days, working on LF-separated lines is easy to implement as dup;._2, with dup being the verb finding the duplicate item. The entire solution to part 1 can thus be written as:

part1 =: [: scores dup;._2

Even though scores and dup are not defined, this is valid J code, as undefined names are considered as verbs with infinite rank (Note that errors will be thrown at execution time when these names turn out not to be verbs, or verbs having different rank, but usually, it works out fine, as in the present case).

Working on a single line, dup needs to: split the compartments into a list , and find the duplicated element, i.e. the set intersection between the list items, using the insert adverb:

dup =: intersect/@:compartments

The length of the compartments are the same, i.e. half of the length of the input line. I chose to use infix (]\) to split rucksacks into compartments of half the length of the input line using the following hook:

compartments=: ]\~ -@-:@#

Hooks like this ((u~ v)) are very common whenever you want to apply a verb to the original argument and a value derived from the argument. J's verbs usually take "control information" as left argument, and data as right: E.g. in x ]\ y, x is the number of elements to be taken together as item, and y the data. This, together with the definition of the hook (x (f g) y --> x f g y), makes the use of Passive (~) in this hooks very common, as the value that needs to be calculated is often the "control information". Another instance of such hook is what I refer to as filter: (#~ condition), which keeps items of y for which condition returns true. Another one is what I call sortby: (/:~ u) sorting a list by a function u of its items.

The last missing part in our solution is set intersection, i.e. the set difference (Less) of the left set minus the set difference of the left set and the right set; in classic set notation intersection= (A \ (A \ B)).

intersect =: ([ {.@-. -.)

Note that items can be included multiple times (maximum item occurrences per line and the number of lines they happen in the input).

   (,#)/..~ /:~ >./@(#/.~);._2 i3
2  18
3 101
4 109
5  55
6  13
7   3
8   1

Therefore, the additional {.@ is required to remove duplicated items, and to ensure atoms are returned, not lists.

Now we have implemented dup to return a single item being repeated, the final part of the solution is the scoring function. Score is defined as the alphabetic position, with a-z and A-Z being 1-26 and 27-52, respectively. J's predefined noun Alpha_j_ contains first the capitals contains first the capitals and then the lower case letters, so in order to lookup letters, we'd need to rotate the array by 26. This leads to the following fork (note that the left part is a noun) that looks up letters using Index of, increments to cope with 1-based scores, and sums all scores:

scores=: (26|.Alpha_j_) +/@:>:@i. ] NB. letters -> total score

Putting all parts together, we get:

part1 =: [: scores ([{.@-.-.)/@(]\~ -@-:@#);._2

Part 2

Part two asks for pretty much the same, but for each set of 3 input lines, rather than within one rucksack.

As now processing for lines are no longer independent, boxing is the most handy option, using <;._2.

The boxing requires applying the set intersection Under Open. Under is one of the reasons I like programming in J, as it is such a common operation: u&.v applies first v to the arguments, then u, and finishes by applying the inverse of v. J has many default inverses, for all primitives that do not loose information (i.e. {. does not have an inverse as it discards elements) and their combinations; For those verbs that do not have an inverse, an obverse (i.e. a pseudo-inverse) can be defined by the user using Obverse, (:.) .

intersectbox =: ([-.-.)&.>

The verb intersectbox intersects boxed sets. Different than before, we cannot use Head ({.) inside intersect because we intersect twice: the first item of the intersection between the last two rucksacks is not guaranteed to be the one that is also present in the first rucksack.

Using infix, we apply intersectbox/ over eac set of 3 non overlapping (hence left argument _3) rucksack boxes:

dup3=: _3 intersectbox/\ <;._2

The result of dup3 is a boxed list of the intersection for each 3-rucksack group, but with duplicate items we could not remove yet. To finally get a single character per group, we use {.@>. Important to understand here is verb Rank: The rank of Open (>) is 0 (can be looked up using > b. 0), and u@v applies verb u to result items of v at the rank of v.

The solution to part 2 applies the same scoring as part 1 after {.@>.

The solution to part 2 is therefore:

part2=: [: score [: {.@> dup3