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