ShareMyScreen/AdventOfCode/2022/03/RucksackReorganization

From J Wiki
Jump to navigation Jump to search

The Problem << >>

Pretty clearly we want the input to be one box per line, with the letters converted to priority. That's easy, using onaoclines:

   pri=.' abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'  NB. letter priorities, 1-52 (note leading space)
   ] lines =. <@(pri&i.) onaoclines
+------------------------------------------------------------------+---
|22 36 18 23 16 49 20 23 36 7 49 18 8 3 19 32 39 39 6 32 32 8 32 16|10 ...
+------------------------------------------------------------------+---

(pri&i.) looked up each character in the list pri, returning the index of the first match. < put each row's list of numbers into a box.

Nothing subtle about the computation:

  • in each box, split into two halves
  • find the letters in common between the two halves
  • discard repetitions.

I find it convenient to use J's hook and fork. These are invisible conjunctions that combine verbs using nothing except spaces and parentheses. Whenever you have a sequence of verbs without a noun on the right of the sequence, you have a hook or fork.

When there are 2 verbs (the hook), x (u v) y executes as x u v y, while (u v) y executes as y u v y.

[you might wonder, Why would I write x (u v) y when I could just write x u v y? Answer: because you might want to apply (u v) on a portion of x or y.]

When there are 3 verbs (the fork), x (f g h) y executes as (x f y) g (x h y).

When there are more than 3 verbs, they are grouped right-to-left as forks, with each fork becoming the h tine of the fork to its left. If there is a leftover verb the overall structure is a hook.

   ]dups =. (([: ~. {. ([ -. -.) }.)~ -:@#)&.> lines
+--+--+--+--+--+--+
|16|38|42|22|20|19|
+--+--+--+--+--+--+

This takes me much longer to explain than it did to write!

The bulk of the work is in the hook (([: ~. {. ([ -. -.) }.)~ -:@#). -:@# gives half of the number of items in lines. The ~ exchanges the x and y arguments of the long verb. The long verb looks for duplicates. (x ([ -. -.) y) creates the list of items common to x and y.

NB. slow-motion replay
   ]box0 =. 0 {:: lines  NB. contents of the first box
22 36 18 23 16 49 20 23 36 7 49 18 8 3 19 32 39 39 6 32 32 8 32 16
   -:@# box0   NB. half the number of items in the list
12
   12 }. box0  NB. discard first 12 items
8 3 19 32 39 39 6 32 32 8 32 16
   12 {. box0   NB. keep first 12 items
22 36 18 23 16 49 20 23 36 7 49 18
   12 ({. ([ -. -.) }.) box0  NB. find values in both sets
16
   12 ([: ~. {. ([ -. -.) }.) box0   NB. discard duplicates
16

That produced the right answer for the contents of the first box, but I have to apply the same verb on the contents of each box. That's why I wrote it as a hook! It's a single verb and I can use it as the u in u&.> which opens each box, applies u to the contents, and puts each result of u into a separate box.

Adding up the priorities is trivial:

   +/ ; dups
157

In part 2 I simply want to process the lines in groups of 3, finding the value common to each. I use _3 u\ y to break into groups of 3. As the verb u I use the set-intersection verb ([-.-.) as above, but this time I add on / to apply it to each box in turn, and &.> to operate inside the boxes. I might as well run the contents together and total them while I'm at it:

   +/ ; _3 (~.@([ -. -.)&.>)/\ lines
70

Revision

The line of code

   ]dups =. (([: ~. {. ([ -. -.) }.)~ -:@#)&.> lines

might be indigestible to a beginner. An equivalent would be

  common =: {{   NB. find values common to first and last halves of y
half =. -:@# y  NB. half the number of items of y
com =. (half {. y) ([ -. -.) (half }. y)  NB. values common to the two halves
~. com   NB. return common values, with duplicates removed
}}
   ]dups =. common&.> lines