I definitely see the appeal of a recursive solution which avoids globals.
That said, I've been parsing enough really large files that I've
gotten into the habit of using globals for managing parsing state.
Plausibly a *bad* habit...
Here, I could have made the data dependencies explicit by passing
'pos' and 'vsum' as m and 'packet' as n, for example. This would have
made my result structures a bit messier, but maybe that would have
been ok?
Thanks,
--
Raul
On Tue, Jan 18, 2022 at 5:58 PM Jan-Pieter Jacobs
<janpieter.jac...@gmail.com> wrote:
>
> Hi, very interesting to read different takes on the problem!
>
> I made it recursive, passing around whatever remains of the bit string,
> with no use of global state (just some auxiliary verbs and the list of
> operations). A trick I was particularly happy with is combining the
> stopping condition on package numbers and max length in bits in a single
> check/loop.
>
> I copy-pasted most of the code of part A to part B and while they could be
> joined, I did not bother. Either way, the requirements of part A don't play
> nice with the set up for part B, as also the versions of the operator
> packets should be summed, while for part B, the operators don't have a
> corresponding value.
>
> As Stefan, I also thought of an FSM, but it would be highly cumbersome (if
> at all possible) to code it with the variable lengths involved. Using it
> only to parse the header (and perhaps length) was not worth the effort.
>
> For part B, the loop for parsing the operator packet constructs an array of
> operands; I simply put all operator operations in a gerund and apply by
> agenda.
>
> NB. Day 16: Packet decoder
> NB. bitstream from hex
> bfh =: [: ,@#: dfh"0
> i16=: }: in 16 NB. }: removes redundant LF
>
> NB. 6 byte header: version;type
> header =: _3 #.\ 6 {. ] NB. version , type
> NB. type 4 indicates literal value, having different groups. each group has
> 5 bits, if first bit is 0, last group. other 4 bits encode value. trailing
> 0's after last group to be ignored.
> NB. decode literal (type 4) body in y (no header)
> literal=: ([: #.@,[: }."1 ({.~ [: >: 0 i.~ {."1))@(_5]\])
>
> NB. part A: parse entire transmission, and find the sum of all version
> numbers
> NB. pp is a recursive verb parsing packages, returning the version sum
> pp =: {{
> NB. extract version/type
> 'ver typ'=. header y
> if. typ=4 do. NB. literals
> NB. count length based on 5 bit fields (groups)
> NB. #groups depends on the first 0 encountered, which indicates the last
> len=. 6+5*>:0 i.~ _5{.\ 6}.y
> sovn=. ver NB. sum of version numbers is the version number
> else. NB. operator packets
> NB. sum of version numbers, initialise with container's version.
> sovn =. ver
> NB. base : pointer to start of first packet
> NB. 6b header;12 for length id (lid)+length+ (if lid=0) 4 extra bits.
> base =. 6+12+4*-.lid=.6{y
> NB. stopping condition, length in bits or packets, stored overwriting
> default _
> stop =. (#.(11+4*-.lid) {. 7 }. y) lid} _ _
> NB. nbp is number of bits and packets processed
> nbp=.0 0
> while. *./ nbp < stop do. NB. no lengths exceeded
> NB. recurse, get sub-packets sum of versions and bit length
> 'vv ll'=. pp (base+{.nbp)}.y
> sovn =. sovn + vv NB. add version number
> NB. increase total length in bits by ll, and in packets by 1
> nbp=. nbp + ll,1
> NB. next packet starts after header and length indication
> end.
> NB. total length is the base length plus the total number of bits
> len=. base+{.nbp
> end.
> sovn, len NB. return sum of versions and length
> }}
> a16=:{.@pp@bfh
> NB. part B, parsing the actual expression
> NB. gerund encoding operators
> NB. type 4 is literal value (placeholder ])
> NB. operator types 0 1 2 3 4 5 6 7 is
> NB. +/ */ <./ >./ ] >/ </ =/
> ger=:(+/)`(*/)`(<./)`(>./)`]`(>/)`(</)`(=/)
> NB. packet parser++, takes packet y, returns value
> pppp =: {{
> NB. extract version/type
> 'ver typ'=. header y
> if. typ=4 do. NB. literals
> NB. count length based on 5 bit fields (groups)
> NB. #groups depends on the first 0 encountered, which indicates the last
> len=. 6+5*>:0 i.~ _5{.\ 6}.y
> val=.x: literal 6}.y
> else. NB. operator packets
> NB. Array of operands
> aoo =. 0$0
> NB. base : pointer to start of first sub-packet
> NB. 6b header;12 for length id (lid)+length+ (if lid=0) 4 extra bits.
> base =. 6+12+4*-.lid=.6{y
> NB. stopping condition, length in bits or packets, stored overwriting
> default _
> stop =. (#.(11+4*-.lid) {. 7 }. y) lid} _ _
> NB. nbp is number of bits and packets processed
> nbp=.0 0
> while. *./ nbp < stop do.
> NB. recurse on remaining packet, find value and length
> 'vv ll'=. pppp (base+{.nbp)}.y
> aoo =. aoo , vv NB. add value to operands
> NB. next packet starts after header and length indication
> nbp=. nbp + ll,1
> end.
> len=. base+{.nbp NB. get final length
> val=. ger@.typ aoo NB. apply appropriate verb.
> end.
> val, len
> }}
> b16=:{.@pppp@bfh
> (a16;b16)i16
>
> Jan-Pieter
>
>
> On Wed, Jan 12, 2022, 15:25 Raul Miller <rauldmil...@gmail.com> wrote:
>
> > I think you could use X ;: bits where bits is a sequence of '0' and
> > '1' characters, if you used ;: opcode 6 (stop) on reaching the payload
> > part of the packet.
> >
> > An example implementation would then interpret the first word of the
> > result as the puzzle opcode. If the opcode was 4, it would interpret
> > the remainder as a number. Otherwise, it would interpret the remainder
> > as a length and after skipping over a number of characters represented
> > by that ;: result, it would extract that length from the stream and
> > call itself recursively on that part and on the part which followed
> > that part.
> >
> > But, yes... the puzzles seem to have a strong influence from the lisp
> > community (specifically the compiler implementation part of that
> > community).
> >
> > Thanks,
> >
> > --
> > Raul
> >
> > On Wed, Jan 12, 2022 at 9:02 AM Stefan Baumann <ste...@bstr.at> wrote:
> > >
> > > I didn't get a grip on this problem at the beginning and skipped it.
> > > But inspired by Raul's solution it appeared that the problem input looks
> > > like an encoded LISP expression.
> > > So I tried to parse the data into a LISP-like J expression and was
> > > wondering if I could then apply ". on it.
> > > The parsing verb ps takes the first position of the packet as y and
> > returns
> > > r, the position right after the packet.
> > > Global nouns V and E store the version numbers and the mentioned J
> > > expression, resp..
> > > J session follows, I hope it's comprehensible - I wanted to keep it very
> > > compact and therefore didn't write any comments.
> > >
> > > rd=: [: ,/@#: '0123456789ABCDEF'&i.
> > > $d=: rd 'C0015000016115A2E0802F182340'
> > > 112
> > > o=: <;._1 ' +/ */ <./ >./ 0: >/ </ =/'
> > > ps=: 3 : 0
> > > y=. y+6 [ E=: E,',' [ V=: V,{. 'v t'=. #.{&d y+i.2 3
> > > if. t=4 do. z=. (-~ +&5^:({&d)^:_) y
> > > E=: E, ": #.{&d ,|: (>:y+i.4) +/ i.@>:&.(%&5) z
> > > r=. y+z+5
> > > else. E=: E,'(', t{::o
> > > if. {&d <: y=. >:y do. n=. #.{&d y+i.11
> > > r=. ps^:n y+11
> > > else. l=. y+15 + #.{&d y+i.15
> > > r=. ps^:(<&l)^:_ y+15
> > > end. E=: E,')'
> > > end. r
> > > )
> > > {{ ps y [ E=: V=: '' }} 0
> > > 106
> > > +/ V NB. (*)
> > > 23
> > > ". E NB. (**)
> > > 46
> > > E
> > > ,(+/,(+/,10,11),(+/,12,13))
> > >
> > > Although ps is defined recursively, it actually just parses from left to
> > > right.
> > > Therefore I'm still wondering if this could be a use case for sequential
> > > machine ;: which I was actually thinking of at the beginning.
> > > Thanks. Stefan.
> > > ----------------------------------------------------------------------
> > > For information about J forums see http://www.jsoftware.com/forums.htm
> > ----------------------------------------------------------------------
> > For information about J forums see http://www.jsoftware.com/forums.htm
> >
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
