That is a different approach.
I had avoided even thinking about that approach, because of speed
concerns. But, testing a simple implementation on the large aoc
"puzzle input", I see that this approach completes in less than 17
milliseconds, Plus it makes reasoning about the problem really simple.
Here's my implementation of your approach:
pairs=: '()','[]','{}',:'<>'
reduce=: rplc&(pairs;"1'')
timespacex 'reduce^:_;._2 input'
0.016612 29920
And, playing with this (extending a working example until I got to the
point I wanted), part 1 looks like this:
red=: reduce^:_;._2 sample
'L R'=:|:pairs
R
)]}>
bad=: red <./@i."1 R
cost=: 3 57 1197 25137 0 {~ R i. bad {"_1 red,.' '
+/cost
26397
And, the second part becomes:
require'stats'
median 5 p.~ 5|1+L i."1 (0=cost)#red
288957
I wish I had thought of that!
Thanks,
--
Raul
On Fri, Dec 31, 2021 at 10:59 AM 'Michael Day' via Programming
<[email protected]> wrote:
>
> I _think_ I used a somewhat different approach. I'll only deal with
> part 1 as
> part 2 doesn't add much complexity.
>
> This approach is simple - remove adjacent pairs of opening and closing
> brackets of the same kind until there are none. The function is called
> reduce:
>
> I've added echo lines only for this email.
>
> reduce =: 3 : 0
> a =. 1 _1 ,2 _2,3 _3,:4 _4
> nums =. +/+/"2 a *"2 3 bkts =/ y -.' '
> NB. this would have been much better! :
> NB. nums =. (,a){~ (,bkts) i.' '-.~{.ex
> while. +/ msk =. +/(E.& nums)"1 a do.
> msk =. -. msk + 0, }: msk NB. matching adjacent pair gives 0 0
> nums=. msk#nums
> end.
> if. 0 > <./ nums do. NB. "corrupted"
> r =. +/ 3 57 1197 25137 {~ <: |{.(#~ <&0 ) nums
> echo 'corrupted'; r
> else. NB. "incomplete"
> echo 'ignore'; ,|.(}."1 bkts){~<: nums
> r =. 0
> end.
> r
> )
>
> We know if a line is corrupted if we can't reduce it any more AND it
> still contains
> some close brackets.
>
> I called the example data "ex" - I held it as a 2-d character array.
>
> Here it goes, with the echo's firing:
>
> +/reduce"1 ex
> +------+--------+
> |ignore|}}]])})]|
> +------+--------+
> +------+------+
> |ignore|)}>]})|
> +------+------+
> +---------+----+
> |corrupted|1197|
> +---------+----+
> +------+---------+
> |ignore|}}>}>))))|
> +------+---------+
> +---------+-+
> |corrupted|3|
> +---------+-+
> +---------+--+
> |corrupted|57|
> +---------+--+
> +------+---------+
> |ignore|]]}}]}]}>|
> +------+---------+
> +---------+-+
> |corrupted|3|
> +---------+-+
> +---------+-----+
> |corrupted|25137|
> +---------+-----+
> +------+----+
> |ignore|])}>|
> +------+----+
> 26397
>
> Cheers,
>
> Mike
>
>
>
> On 31/12/2021 02:41, Raul Miller wrote:
> > 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.
> >
>
>
> --
> This email has been checked for viruses by Avast antivirus software.
> https://www.avast.com/antivirus
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
