One thing I find missing in J is a tacit analogue of the for. control
structure. Ideally, this would be dual / , but this isn't really possible,
so I'll call it for. It would work like:
x u for y
<-->
> u&.>/ (<"_1 x) , <y
<-->
for_i. |.x do. y=.i u y end.
And would make this solution a lot clearer and not require boxing.
for=.1 : ('';':';'for_i. |.x do. y=.i u y end.')
(# -~ (+/@:{ - (] + |.!.0)for ({.&1)@>:@{:)) B
179
Marshall
-----Original Message-----
From: [email protected]
[mailto:[email protected]] On Behalf Of Roger Hui
Sent: Saturday, March 12, 2011 8:19 PM
To: Programming forum
Subject: Re: [Jprogramming] greplin challenge
Doh! I should have studied your solution further before sending my msg.
Sorry.
Note to self: think more; type less.
----- Original Message -----
From: Roger Hui <[email protected]>
Date: Saturday, March 12, 2011 17:06
Subject: Re: [Jprogramming] greplin challenge
To: Programming forum <[email protected]>
> I have not studied this problem. However, when I saw your solution
>
> findH=:4 :0
> H=. (>:x){.1
> for_e. y do.
> H=.(+ (-e)&(|.!.0)) H
> end.
> H
> )
>
> I immediately thought "power operator", and I am surprised that I
> don't find it in your latest
>
> (# -~ (+/@:{ [: > [: (] + |.!.0)&.>/ <@- ,
> <@({.&1)@>:@{:)) B
>
>
>
> ----- Original Message -----
> From: Henry Rich <[email protected]>
> Date: Saturday, March 12, 2011 14:38
> Subject: Re: [Jprogramming] greplin challenge
> To: Programming forum <[email protected]>
>
> > (# -~ (+/@:{ [: > [: (] + |.!.0)&.>/
> > <@- , <@({.&1)@>:@{:)) B
> > 179
> >
> > Henry Rich
> >
> > On 3/12/2011 5:19 PM, Henry Rich wrote:
> > > Hey presto! You're right. Since you don't need to
> > know the subsets,
> > > you don't have to do the backtracking. For that matter,
> > you can do it
> > > with just one copy of the H vector: i{H tells how many ways
> > you can add
> > > up items to get i; so just find H for the whole input
> vector,
> > and add
> > > up the values corresponding to B. You them have to
> > remove the
> > > singletons that created one-element sets that added to equal
> > themselves,> because you were supposed to be looking at only smaller
> > numbers. You get:
> > >
> > > findH=:4 :0
> > > H=. (>:x){.1
> > > for_e. y do.
> > > H=.(+ (-e)&(|.!.0)) H
> > > end.
> > > H
> > > )
> > >
> > > (#B) -~ +/ B { ({:B) findH B
> > > 179
> > >
> > >
> > > Probably not to hard to make tacit, too.
> > >
> > > Henry Rich
> > >
> > > On 3/12/2011 4:57 PM, Marshall Lochbaum wrote:
> > >> A solution with this method:
> > >>
> > >> B=: 3 4 9 14 15 19 28 37 47 50
> > 54 56 59 61 70 73 78 81 92 95 97 99
> > >> sums=:4 :0
> > >> H=. (>:x){.1
> > >> for_e. y do.
> > >> H=.(+ (-e)&(|.!.0)) H
> > >> end.
> > >> {:H
> > >> )
> > >> +/ B sums&> (i.22)
> > {.&.> (<B)
> > >> 179
> > >>
> > >> Note that by changing +. to +, HH is not needed.
> > >>
> > >> Marshall
> > >>
> > >> -----Original Message-----
> > >> From: [email protected]
> > >> [mailto:[email protected]] On Behalf Of
> Henry Rich
> > >> Sent: Saturday, March 12, 2011 9:49 AM
> > >> To: Programming forum
> > >> Subject: Re: [Jprogramming] greplin challenge
> > >>
> > >> I think there is, but I don't have time to code the
> > interesting part, which
> > >> resembles the integer knapsack problem. I will outline
> > the solution.
> > >>
> > >> Examining each value v in turn, the question is to count
> the
> > subsets of
> > >> smaller values to find those that add up to v. So:
> > count the subsets of a
> > >> set S that add up to a desired target v.
> > >>
> > >> To do that, you create a Boolean vector H which is v+1 long
> > and represents
> > >> which totals can be reached by combinations of elements of
> > the set. The
> > >> idea is to consider the elements of S in turn, making a new
> > copy of H after
> > >> considering each element. This will give an array HH
> > which you then
> > >> backtrack through to find all the paths leading from the
> > bottom-right to the
> > >> top-left.
> > >>
> > >> Initialize HH =. ,: H =. (>:v) {. 1
> > >>
> > >> for_e. S do.
> > >> NB. The values reachable
> > possibly using e are all the values
> > >> NB. reachable not using e, and
> > all those values plus e:
> > >> H =. H +. (-e) |.!.0 H
> > >> NB. Remember the new H after
> > considering e
> > >> HH =. HH , H
> > >> end.
> > >>
> > >> Now, if {: H is 1, there is a combination of elements that
> > adds to v.
> > >> It remains to find all such subsets. You do this by
> > going back through the
> > >> rows of HH.
> > >>
> > >> The plan is, keep a list of reachable values, and for each
> > one, the list of
> > >> sets that reach. Initially the list of reachable values
> > is just v, and its
> > >> corresponding list of sets is empty.
> > >>
> > >> Discard the last row of HH. Then, for each row starting
> > with the last, see
> > >> which of the reachable values can be reached if you
> include,
> > or exclude, the
> > >> Si that produced the row. You will have a new set of
> > reachable values and
> > >> corresponding subsets.
> > >>
> > >> When you get back to the first row of HH, you will have all
> > the subsets.
> > >>
> > >> The performance of this dynamic-programming solution is
> > proportional to
> > >> (v*(number of items of S)); much faster than enumerating subsets.
> > >>
> > >> Henry Rich
> > >>
> > >>
> > >> On 3/12/2011 5:37 AM, chris burke wrote:
> > >>> This challenge http://challenge.greplin.com seems to have
> > missed the
> > >>> forum. Each is straightforward in J.
> > >>>
> > >>> The last is to count the subsets of an array where the
> > largest number
> > >>> is the sum of the remaining numbers. The given array is
> > >>>
> > >>> B=: 3 4 9 14 15 19 28 37 47 50 54 56 59 61 70 73 78 81 92
> 95
> > 97 99
> > >>>
> > >>> A brute force calculation is:
> > >>> <: +/ B ((+/=2*{:) @:
> > #~)"1 #:i.2^#B
> > >>> 179
> > >>>
> > >>> This takes a few seconds. Is there a better way?
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
