https://adventofcode.com/2021/day/10
For day 10's puzzle, the first part was determining whether
collections of braces and brackets were properly formed. The
allowable pairs were '()', '[]', '{}', and '<>', and the sample data
looked like this:
sample=:{{)n
[({(<(())[]>[[{[]{<()<>>
[(()[<>])]({[<{<<[]>>(
{([(<{}[<>[]}>{[]{[(<()>
(((({<>}<{<{<>}{[]{[]{}
[[<[([]))<([[{}[[()]]]
[{[{({}]{}}([{[{{{}}([]
{<[[]]>}<{[{[{[]{()[[[]
[<(<(<(<{}))><([]([]()
<{([([[(<>()){}]>(<<{{
<{([{{}}[<[[[<>{}]]]>[]]
}}
Specifically, for the first part, we were to find the first illegal
character on each line, each of which were assigned a score, and sum
those scores.
So the result line for that part would look something like this:
+/ 3 57 1197 25137 {~ ')]}>' i. bad
So I built a brute force lexical analyzer which returned empty for
legal lines and the first bad character and its index for illegal
lines:
scanline=:{{
next=.''
for_ch. y do.
select. ch
case.'(' do. next=. next,')'
case.'[' do. next=. next,']'
case.'{' do. next=. next,'}'
case.'<' do. next=. next,'>'
case.')';']';'}';'>' do.
if. ch={: next do.
next=.}: next
else.
ch;ch_index return.
end.
case. do. echo 'unexpected';ch;ch_index throw.
end.
end.
''
}}
The basic approach here is to have an intermediate result which is a
stack of the expected terminating characters and to report on failed
matches.
I left the character index in the result to help me debug my code if I
had done something horribly wrong.
Since I was returning boxed characters from that routine for the error
cases, I decided my lookup should normalize both the left and right
arguments to i. to be boxed strings:
aoc10a=:{{
err=. {."1>(<@scanline;._2 y)-.a:
+/((;:')]}>')i.&:(,each) err){3 57 1197 25137
}}
For part b, we instead were to report on the lines without illegal
characters and score based on the missing terminating
brackets/braces/...
Here, the scoring was 1 + the index into ')]}>', multiplied by 5 ^
index into that particular string.
So I took the above code and tweaked it to return the unfinished
stacks on "good lines":
scan2=:{{
next=.''
for_ch. y do.
select. ch
case.'(' do. next=. next,')'
case.'[' do. next=. next,']'
case.'{' do. next=. next,'}'
case.'<' do. next=. next,'>'
case.')';']';'}';'>' do.
if. ch={: next do.
next=.}: next
else.
'' return.
end.
case. do. echo 'unexpected';ch;ch_index throw.
end.
end.
|.next
}}
My initial implementation of the scoring mechanism was a bit messy,
but there's no point burdening you with that. Instead:
score=:5 #. 1 + ')]}>' i. ]
Though I could have used
score=:5 p.~ 1 + ')]}>' i. |.
To actually complete the second part, we needed to find the median score:
aoc10b=:{{
compl=. (<@scan2;._2 y)-.a:
({~ <.@-:@#)/:~ score every compl
}}
And that was it for day 10.
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
