posted a slightly different solution on wiki, but the original did get correct
answer, even though it took too long. An assumption that turns out to be
correct to speed it up is that expanding a "substring" expands within the
confines of that substring. The assumption is sensible if the input is in fact
the result of a compression routine. With this assumption, you can recurse on
just the substring to be expanded without expanding it (major slowdown in
original code) and then just multiply the result by the number of repeated
expansions. Very similar to original posted code. both parts 1 and 2.
p1 =: 4 : 0
o =. ''
while. (# y) > e =. ')' i.~ y do.
b =. '(' i:~ e {. y
i =. ". every 'x' cut y{~ b + >:i. <:e -b
o =. o , ',' , (": b) , ', ' , (": {: i) , (x {:: ' R '; ' RB ') , quote ({.i)
{. (>:e )}. y
y =. ({.i) }. (>:e) }. y
end.
o , ',' , ": # y
)
R =: 2 : ' m * # n'
RB =: 2 : ' m * (1 +/@:".@:}.@:p1 n)'
echo +/ ". }. 0 p1 LF -.~ a NB. part1
echo +/ ". }. 1 p1 LF -.~ a NB. part2
----- Original Message -----
From: 'Mike Day' via Programming <[email protected]>
To: [email protected]
Sent: Saturday, December 10, 2016 7:24 AM
Subject: [Jprogramming] AoC 2016 day 9 - Was Re: [Jbeta] possible memory
leak j805
Apologies for posting the previous message (below) earlier on Beta.
Anyway, I have now seen that there's a part two to the problem,
presumably hidden
to me as I hadn't got part one correct, and discussion of it (in
reddit.com/Advent...)
suggests that recursion IS required, or, at least, relevant.
I suppose the "2" in Pascal Jasmin's "f2" is a hint!
I hadn't intended to get involved in the Advent problems, needing to write
Christmas cards, and already busy enough with Project Euler stuff!
Mike
On 10/12/2016 09:53, 'Mike Day' via Beta wrote:
> fwiw, and only about results rather than memory leaks:
>
> ,.exx NB. The worked examples provided with problem 9
> +-----------------+
> |ADVENT |
> +-----------------+
> |A(1x5)BC |
> +-----------------+
> |(3x3)XYZ |
> +-----------------+
> |A(2x2)BCD(2x2)EFG|
> +-----------------+
> |(6x1)(1x3)A |
> +-----------------+
> |X(8x2)(3x3)ABCY |
> +-----------------+
>
> unpack each exx NB. my verb produces the stated results
> +-+-+-+--+-+--+
> |6|7|9|11|6|18|
> +-+-+-+--+-+--+
>
> f2 each exx NB. but your results disagree with the paradigm
> +-+-+-+--+-+--+
> |6|7|9|11|3|20|
> +-+-+-+--+-+--+
>
> For (6x1)(1x3)A f2 goes astray at the first recursion:
> (>:e)}. y
> (1x3)A
> ... which is wrong.
> You need to drop ({.i)) + >:e from y, which is empty,
> and o needs to accumulate {.i
>
> He does say "if parentheses or other chars appear within the data
> referenced by a marker, that's okay - treat it like normal data,
> not a marker..." I suppose that just means you don't need recursion.
>
> BUT - my "unpack" - a naive looping approach, no recursion - apparently
> overestimates the count for problem 9's file! I'm loth to look for errors
> since it gets the examples right. It's over-engineered: I put in a
> buffer
> mechanism assuming the file would be huge and too large for array
> processing,
> but it's not. However, making the block size larger than the file
> doesn't
> alter the incorrect answer.
>
> Typical for me - It runs fast (1 ms) and gets the wrong answer.
>
> Mike
>
>
> On 09/12/2016 14:53, 'Pascal Jasmin' via Beta wrote:
>> expand =: */@:[ $ {.@[ {. ]
>>
>> echo f2 '(27x12)(20x12)(13x14)(7x10)(1x12)A'
>> echo f2 '(25x3)(3x3)ABC(2x3)XY(5x2)PQRSTX(18x9)(3x2)TWO(5x7)SEVEN'
>
>
> ---
> 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
---
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
