ShareMyScreen/AdventOfCode/2022/13/DistressSignal
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