The best me and my father could come up with is:
s=: [: e (<<_) p&.>/@,~ <"0
p=: ] , [ ,&.> ] #~ (< {.&>) (= >./)@:* #&>@]
e=: }:@>@(#~ (= >./)@:(#&>))@>
si=: [: e (<<_) pi&.>/@,~ <"0
pi=: ] , [ ,&.> ] {~ (< {.&>) (i. >./)@:* #&>@]
Let v be a valid increasing subsequence. If n < {.v then n,v is
That blew up for me, and I did not feel motivated to dump my existing
j session, so I rewrote it a bit:
NB. dyads
e=: (1 + {:@[ < ]) {. [ ; ,
h=: [: ; e&.>
NB. monads
g=: (}.@] ;~ {.@] ; (h {.))&>/
c=: ({::~ [: (i. >./) #@>)@>@{.
d=: (<_) ; ]
f=: ([: c g^:(#@(>@{:)))@d
I don'
Well, assuming for now that it does work, here's an attempt at a J
version of
the pseudo-code listed at
https://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms
lis =: 3 : 0 NB. longest increasing subsequence
m =. 0#~>:n =. #x =. y
L =. #p =. ''
Came up with this:
f=.u@d
u=.[: c g^:(#@n)
d=.(<_) ; ]
c=.[: > s {~ [: {.@\: #@>@s
g=.}.@n ;~ {.@n ; s h {.@n
n=.>@{:
s=.>&{.
h=.[: ; e&.>
e=.<@[`([ ; [ , ])@.t
t=.{:@[ < ]
f 7 4 4 5 2 7 1 8 13 2 10 4 9 1 4 5 5 4 3 10 3 4 5 8 15 7 11 19
1 2 3 4 5 7 11 19
Let me kn
It seems to me that the "efficient algorithm" documented on the
wikipedia page would have an analogous flaw. It is performing binary
searches on unsorted lists. That said, it does perform correctly for
this example.
Thanks,
--
Raul
On Fri, Sep 2, 2016 at 12:18 PM, jonghough via Programming
w
Yes, Raul is absolutely correct. And the flaw (in my solution, at least) is
obvious now. I'll try for a correct solution again tomorrow.
From: 'Mike Day' via Programming
Sent: Saturday, September 3, 00:26
Subject: Re: [Jprogramming] Greatest Increasing Subsequence
To: 'Mike Day' via Progr
Same problem with my version, which was faster but equally wrong!
Mike
On 02/09/2016 14:57, Raul Miller wrote:
Actually, if we try your approach on -8 2 4 3 1 6 we get _8 _2 _1
instead of _8 _4 _3 _1.
Here's a brute force O(2^n) approach that I hacked up earlier - it
obviously only works on
Or, to generate the counting sequence of such numbers, see:
https://www.rosettacode.org/wiki/Look-and-say_sequence#J
Thanks,
--
Raul
On Fri, Sep 2, 2016 at 5:09 AM, Henry Rich wrote:
> See http://code.jsoftware.com/wiki/Essays/Advent_Of_Code#Part_1_10
>
> Henry Rich
>
>
> On 9/2/2016 12:42 A
Actually, if we try your approach on -8 2 4 3 1 6 we get _8 _2 _1
instead of _8 _4 _3 _1.
Here's a brute force O(2^n) approach that I hacked up earlier - it
obviously only works on short lists:
increasing=: (-: /:~)@#~"1 #:@i.@^~&2@#
longestinc=: ] #~ [: (#~ ([: (= >./) +/"1)) #:@I.@increasing
W
Checking my attempt with the function in the essay cited, I see that
there's a misprint there.
The value of i should be '1113213211', not '1113122113', assuming i is
meant to be
,@((# , {.);.1~ (~: |.!.0))^:7 "."0 ,'1' NB. numeric result...
1 1 1 3 2 1 3 2 1 1
It's always good to l
Oh, I just realized I completely misunderstood the problem. I thought it only
takes the first one or two items of the list
each iteration.
This is my amended solution, which may or may not be correct:
countandsay2 =: 3 : 0
h=:__
t=: ''
str=: ''
max=:y
ctr=: 0
takewhile =:(3 : 'str=: str, (":@:#
I came up with this.
f =: (;@:{~ (i. >./)@:(#&>))@:(<@~.@:(>./\)\.)
NB. The main ingredient is ~.@:(>./\)
~.@:(>./\) l
7 8 13 15 19
~.@:(>./\) }.l
4 5 7 8 13 15 19
f l
4 5 7 8 13 15 19
NB. If there are more than one different subseqs
NB. of equal length, it returns the first.
NB. It f
See http://code.jsoftware.com/wiki/Essays/Advent_Of_Code#Part_1_10
Henry Rich
On 9/2/2016 12:42 AM, 'Jon Hough' via Programming wrote:
This is a leetcode question:
https://leetcode.com/problems/count-and-say/
Description:
The count-and-say sequence is the sequence of integers beginning as follo
13 matches
Mail list logo
