Oh how very annoying. The problem statement said "whitespace" could be
ignored, so
I removed ' ' but found it made no difference. It said nothing about
embedded LFs !
That overestimate was out by just one. I'd spent an hour or two
wondering what had
gone wrong. My part 1 still solves in about a millisec.
Now I can find out what part 2 is about!
I'll have a go at part 2 for myself before studying your code...
Thanks,
Mike
On 10/12/2016 16:47, 'Pascal Jasmin' via Programming wrote:
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
---
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
