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=. [email protected] 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 <[email protected]> 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 <[email protected]> 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
