ShareMyScreen/AdventOfCode/2022/13/DistressSignal

From J Wiki
Jump to navigation Jump to search

The Problem << >>

This has recursion written all over it. I'll convert the input into a hierarchy of boxed lists and process them recursively.

Now, how to process the input? It seems like I should be able to make some string substitutions and then execute a sentence to produce the result.

  • replace [ with (<
  • replace ] with )

No, I can't leave the numbers unboxed - then I wouldn't be able to have lists containing number and lists. So I need to

  • replace number with (<number)

Looking at the sample data I see that even this isn't enough: the empty list [] would not be executable. So I also need to

  • replace [] with (<0$a:)

This is getting ugly. Do I really need recursion and boxing? Actually, no: the comparison exits on the first occurrence of inequality, so if I just start comparing at the beginning of each string I can quit whenever the list structure mismatches.

I'll read the input as pairs of strings separated by blank lines:

      ] lines =. _3 (2&{.)\ < onaoclines
+---------------------------+---------------------------+
|[1,1,3,1,1]                |[1,1,5,1,1]                |
+---------------------------+---------------------------+
|[[1],[2,3,4]]              |[[1],4]                    |
+---------------------------+---------------------------+
|[9]                        |[[8,7,6]]                  |
+---------------------------+---------------------------+
|[[4,4],4,4]                |[[4,4],4,4,4]              |
+---------------------------+---------------------------+
|[7,7,7,7]                  |[7,7,7]                    |
+---------------------------+---------------------------+
|[]                         |[3]                        |
+---------------------------+---------------------------+
|[[[]]]                     |[[]]                       |
+---------------------------+---------------------------+
|[1,[2,[3,[4,[5,6,7]]]],8,9]|[1,[2,[3,[4,[5,6,0]]]],8,9]|
+---------------------------+---------------------------+

The Infix (\) adverb calls for operation on each group of 3 lines, and the action is to keep the first 2 of them.

Now to compare them. I'll try to implement the spec precisely.

inorder =: {{ NB. x is first string, y is seconds string, result is 1 if in order
while. x *.&*&# y do.  NB. while both strings still have characters
  if. x *.&(']'={.) y do. x =. }. x [ y =. }. y continue. end.  NB. both strings at ], remove and continue
  if. x +.&(']'={.) y do. ']' = {. x return. end.  NB. one string at ]; in order if it's x
  if. ',' = {. x do. x =. }. x continue. end.  NB. skip over '.'
  if. ',' = {. y do. y =. }. y continue. end.  NB. skip over '.'
  if. x *.&('['={.) y do. x =. }. x [ y =. }. y continue. end.  NB. both strings at [, remove and continue
  if. x *.&('0123456789'e.~{.) y do.  NB. both numbers, compare
    numx =. 0 ". stgx =. x (i.&0@:e. {. [) '0123456789' [ numy =. 0 ". stgy =. y (i.&0@:e. {. [) '0123456789'  NB. take leading digits, convert to numeric
    if. numx ~: numy do. numx<numy return. end.  NB. return if mismatch
    x =. (#stgx) }. x [ y =. (#stgy) }. y   NB. discard chars.  We treat 01 and 1 as equivalent
  end.
  if. '0123456789'e.~ {. x do. x =. x (i.&0@:e. (}. ,~ '[' , ']' ,~ {.) [) '0123456789' continue. end.  NB. x starts with num, replace with [num]
  if. '0123456789'e.~ {. y do. y =. y (i.&0@:e. (}. ,~ '[' , ']' ,~ {.) [) '0123456789' continue. end.  NB. y starts with num, replace with [num]
end.
0 = # x   NB. At least one string ended.  Result is in order if x ended
}}

x i.&0@:e. '0123456789' is a special comparison combination. It does exactly what it says, but it terminates early if possible. This one is saying

  • look for all the places where x is a digit
  • find the first place where >tt>x is not a digit - that's the number of leading digit characters

I try the sample input:

   +/ >: I. inorder&>/"1 lines  NB. >: to convert to 1-origin numbering
13

For Part 2 I have to write a sort. I check my input: 300 strings. I'll use insertion sort. (If n were much bigger I'd use Shellsort).

isort =: {{  NB. y is array, result is sorted array.  Use inorder to compare
for_j. }. i. # y do.
  insx =. j ,~ I. -. (j {. y) inorder&> (j { y)  NB. indexes of each string coming after j
  y =. (y {~ _1 |. insx) insx} y  NB. insert j at its proper position
end.
y
}}
   divider =. '[[2]]';'[[6]]'  NB. divider packets
   ,. isort divider , ,lines  NB. ,. to display in column
+---------------------------+
|[]                         |
+---------------------------+
|[[]]                       |
+---------------------------+
|[[[]]]                     |
+---------------------------+
|[1,1,3,1,1]                |
+---------------------------+
|[1,1,5,1,1]                |
+---------------------------+
|[[1],[2,3,4]]              |
+---------------------------+
|[1,[2,[3,[4,[5,6,0]]]],8,9]|
+---------------------------+
|[1,[2,[3,[4,[5,6,7]]]],8,9]|
+---------------------------+
|[[1],4]                    |
+---------------------------+
|[[2]]                      |
+---------------------------+
|[3]                        |
+---------------------------+
|[[4,4],4,4]                |
+---------------------------+
|[[4,4],4,4,4]              |
+---------------------------+
|[[6]]                      |
+---------------------------+
|[7,7,7]                    |
+---------------------------+
|[7,7,7,7]                  |
+---------------------------+
|[[8,7,6]]                  |
+---------------------------+
|[9]                        |
+---------------------------+

That's right. I just need to find the dividers, remembering to use 1-origin indexing.

   */ >: divider i.~ isort divider , ,lines
140