Adrian Smith's spanned cells idiom challenge
Author Message
Adrian Smith's spanned cells idiom challenge

Given a boolean vector q, add the number of following zeros to each 1. That
is, from:
q
1 0 1 0 1 0 0 1 1 1 0
get:
2 0 2 0 3 0 0 1 1 2 0

I give a solution using J, but I hope I've given enough comments so that it
can be followed by most people familiar with APL. Assume 0 origin.

Step 1. Append a 1 to q. This uses , & 1 . This is a curried function which
appends a 1.
, & 1 q
1 0 1 0 1 0 0 1 1 1 0 1

Step 2. Find the indices of each 1. This uses the monad #, meaning count, and
the dyad #, meaning replicate. They are used in a hook, that is, an
expression with two functions, such as f and g, as in (f g). When used as a
monad, as in (f g) x it means x f (g x). In this case the function g is the

indices of the 1s in q. (x replicate iota shape x).

0 2 4 7 8 9 11

Step 3. Find the commuted differences ( - ~ ) between each successive pair in
the argument, that is, 2 - 0, 4 - 2, etc.
2 - ~ / \ 0 2 4 7 8 9 11
2 2 3 1 1 2
The leading 2 in this expression means "apply to overlapping pairs". Commuted
minus (-~) is inserted (/) between each infix of length 2.

Step 4. Use this to replicate itself. This is done by using the dyad
replicate (#) with duplicate (~). Commute and duplicate are operators of the
combinatory logics of Schoenfinkel and Curry. For example, (f ~ x) means (x f
x) and (x f~ y) means (y f x).
# ~ 2 2 3 1 1 2
2 2 2 2 3 3 3 1 1 2 2

Step 5. Multiply this by q.
q * 2 2 2 2 3 3 3 1 1 2 2
2 0 2 0 3 0 0 1 1 2 0

The function j combines these steps.

This can be read "q times replicate duplicate pairs minus commute insert
prefix (replicate integers compose count) append curry 1 q".
j q
2 0 2 0 3 0 0 1 1 2 0

Eugene McDonnell

Wed, 31 Aug 2005 13:57:26 GMT
Adrian Smith's spanned cells idiom challenge
The given solution seems to assume that the boolean
argument begins with a 1:
j 0 1 0 0
|length error: j
|       j 0 1 0 0

Anyway, if it can be assumed that the argument begins
with a 1, the following is an alternative solution:

q=: 1 0 1 0 1 0 0 1 1 1 0
#;.1 q
2 2 3 1 1 2
q #^:_1 #;.1 q
2 0 2 0 3 0 0 1 1 2 0
f=: #^:_1 #;.1
f q
2 0 2 0 3 0 0 1 1 2 0

#;.1 q applies "cut" (partition) to q using # as the function.
i.e. compute the length of each cut; q#^:_1 then expands these
lengths to give the required answer.  (Expand is not a primitive
in J, but is provided as the inverse of compress, the dyad #.)

Now if it can not be assumed that the argument begins with a 1,
a simple modification suffices:

f&.(1&,) q
2 0 2 0 3 0 0 1 1 2 0
f&.(1&,) 0 0,q
0 0 2 0 2 0 3 0 0 1 1 2 0

i.e. do f under prefacing by 1, i.e. preface q by 1, apply f,
then drop the leading item (an inverse of prefacing by 1).

Quote:
----- Original Message -----

Sent: Friday, March 14, 2003 21:37 PM
Subject: Adrian Smith's spanned cells idiom challenge

Given a boolean vector q, add the number of following zeros to each 1. That
is, from:
q
1 0 1 0 1 0 0 1 1 1 0
get:
2 0 2 0 3 0 0 1 1 2 0

I give a solution using J, but I hope I've given enough comments so that it
can be followed by most people familiar with APL. Assume 0 origin.

Step 1. Append a 1 to q. This uses , & 1 . This is a curried function which
appends a 1.
, & 1 q
1 0 1 0 1 0 0 1 1 1 0 1

Step 2. Find the indices of each 1. This uses the monad #, meaning count,
and
the dyad #, meaning replicate. They are used in a hook, that is, an
expression with two functions, such as f and g, as in (f g). When used as a
monad, as in (f g) x it means x f (g x). In this case the function g is the

indices of the 1s in q. (x replicate iota shape x).

0 2 4 7 8 9 11

Step 3. Find the commuted differences ( - ~ ) between each successive pair
in
the argument, that is, 2 - 0, 4 - 2, etc.
2 - ~ / \ 0 2 4 7 8 9 11
2 2 3 1 1 2
The leading 2 in this expression means "apply to overlapping pairs".
Commuted
minus (-~) is inserted (/) between each infix of length 2.

Step 4. Use this to replicate itself. This is done by using the dyad
replicate (#) with duplicate (~). Commute and duplicate are operators of the
combinatory logics of Schoenfinkel and Curry. For example, (f ~ x) means (x
f
x) and (x f~ y) means (y f x).
# ~ 2 2 3 1 1 2
2 2 2 2 3 3 3 1 1 2 2

Step 5. Multiply this by q.
q * 2 2 2 2 3 3 3 1 1 2 2
2 0 2 0 3 0 0 1 1 2 0

The function j combines these steps.

This can be read "q times replicate duplicate pairs minus commute insert
prefix (replicate integers compose count) append curry 1 q".
j q
2 0 2 0 3 0 0 1 1 2 0

Eugene McDonnell

Wed, 31 Aug 2005 15:53:07 GMT
Adrian Smith's spanned cells idiom challenge

Quote:
> Given a boolean vector q, add the number of following zeros to each 1.
That
> is, from:
>    q
> 1 0 1 0 1 0 0 1 1 1 0
> get:
> 2 0 2 0 3 0 0 1 1 2 0

An each-less solution, presented with Dyalog APL's dynamic function:

{w\ <neg>2-/ (w,1)/ <iota>1+ <shape>w}

where w {omega} represents the right argument.

Works in every []ML (Dyalog's Migration Level), and with or without

-Veli-Matti

Wed, 31 Aug 2005 17:43:49 GMT
Adrian Smith's spanned cells idiom challenge
I am curious:  does it work on an argument of all zeros,
or an empty argument?
Quote:
----- Original Message -----

Sent: Saturday, March 15, 2003 02:18 AM
Subject: Re: Adrian Smith's spanned cells idiom challenge

> Given a boolean vector q, add the number of following zeros to each 1.
That
> is, from:
>    q
> 1 0 1 0 1 0 0 1 1 1 0
> get:
> 2 0 2 0 3 0 0 1 1 2 0

An each-less solution, presented with Dyalog APL's dynamic function:

{w\ <neg>2-/ (w,1)/ <iota>1+ <shape>w}

where w {omega} represents the right argument.

Works in every []ML (Dyalog's Migration Level), and with or without

-Veli-Matti

Wed, 31 Aug 2005 23:58:57 GMT
Adrian Smith's spanned cells idiom challenge

Quote:
> I am curious:  does it work on an argument of all zeros,
> or an empty argument?

Of course ;-)

fun <-  {w\ <neg>2-/ (w,1)/ <iota>1+ <shape>w}
fun 0 0 0 0 0
0 0 0 0 0
(<iota>0) <equal>   fun <iota>0
1

-VM

Thu, 01 Sep 2005 00:10:07 GMT
Adrian Smith's spanned cells idiom challenge
Roger,
Velli-Matti's is the one I'd have come up with due to my tutelage by
Howard J. Smith.  I tried it with all 1s, all 0s, single element 1,
single element 0, and empty.  Looks OK to me.
D{<-}1 0 1 0 1 0 0 1 1 1 0
{disclose}D (D\{neg}1+{neg}2-/(D,1)/{iota}1+{rho}D)
1 0 1 0 1 0 0 1 1 1 0
1 0 1 0 2 0 0 0 0 1 0

{disclose}D (D\{neg}1+{neg}2-/(D,1)/{iota}1+{rho}D)
0 0 1 0 1 0 0 1 1 1 0
0 0 1 0 2 0 0 0 0 1 0

{disclose}D (D\{neg}1+{neg}2-/(D,1)/{iota}1+{rho}D)
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0

{disclose}D (D\{neg}1+{neg}2-/(D,1)/{iota}1+{rho}D)
1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0
D{<-},1
{disclose}D (D\{neg}1+{neg}2-/(D,1)/{iota}1+{rho}D)
1
0
D{<-},0
{disclose}D (D\{neg}1+{neg}2-/(D,1)/{iota}1+{rho}D)
0
0
D{<-}{iota}0
{disclose}D (D\{neg}1+{neg}2-/(D,1)/{iota}1+{rho}D)

Curtis

Thu, 01 Sep 2005 00:27:00 GMT
Adrian Smith's spanned cells idiom challenge
And the 8-character, each-utilising solution in Dyalog APL, migration level
2:

q\{enlist}{rank}{each}q{enclose}q

V-M, your expression fails if the argument is singleton 1. Gotcha :-)

/ Tomas

Quote:
> Adrian Smith gave this problem:

> Given a boolean vector q, add the number of following zeros to each 1.
That
> is, from:
>    q
> 1 0 1 0 1 0 0 1 1 1 0
> get:
> 2 0 2 0 3 0 0 1 1 2 0

Thu, 01 Sep 2005 01:34:21 GMT
Adrian Smith's spanned cells idiom challenge

Quote:
> Adrian Smith gave this problem:

> Given a boolean vector q, add the number of following zeros to each 1. That
> is, from:
>    q
> 1 0 1 0 1 0 0 1 1 1 0
> get:
> 2 0 2 0 3 0 0 1 1 2 0

My first quick try, using Dyalog APL, produced the following dynamic function

{ ml assign 3 diamond w \ enlist shape each ( + \ w ) enclose w }

where

ml is the system variable migration-level

diamond is the statement separator

assign, enlist, shape, each, and enclose are APL primitive functions

-- James L. Ryan -- TaliesinSoft

Thu, 01 Sep 2005 01:48:35 GMT
Adrian Smith's spanned cells idiom challenge
Did you actually execute the last expression? :-)
I would have thought that the anwser would be {iota}0.
Unless you meant "match" instead of "equal".
Quote:
----- Original Message -----

Sent: Saturday, March 15, 2003 08:53 AM
Subject: Re: Adrian Smith's spanned cells idiom challenge

> > I am curious:  does it work on an argument of all zeros,
> > or an empty argument?

> Of course ;-)

>     fun <-  {w\ <neg>2-/ (w,1)/ <iota>1+ <shape>w}
>     fun 0 0 0 0 0
> 0 0 0 0 0
>   (<iota>0) <equal>   fun <iota>0
> 1

> -VM

Thu, 01 Sep 2005 02:06:40 GMT
Adrian Smith's spanned cells idiom challenge

Quote:

> Adrian Smith gave this problem:
> Given a boolean vector q, add the number of following zeros to each 1. That
> is, from:
>    q
> 1 0 1 0 1 0 0 1 1 1 0
> get:
> 2 0 2 0 3 0 0 1 1 2 0

example.  I would have thought that the answer should be one number for
each 1 in q and that number should be 1+ the number of zeros following
those 1.  Thus, for your q, the result should have length six and be
2 2 3 1 1 2

On that assumption, my APL2 solution is:
f:1{drop}{1st}{each}{rho}{each}(1+w{times}{iota}{rho}w){part}w{is}1,{omega}

0

0
1
1

0
1 1 1
3
q
1 0 1 0 1 0 0 1 1 1 0
2 2 3 1 1 2

Ted

Thu, 01 Sep 2005 02:48:51 GMT
Adrian Smith's spanned cells idiom challenge

Quote:
> And the 8-character, each-utilising solution in Dyalog APL, migration
level
> 2:

> q\{enlist}{rank}{each}q{enclose}q

> Leading value 0 or 1.

> V-M, your expression fails if the argument is singleton 1. Gotcha :-)

Eh.. your solution fails with []ML values 0 and 3 - and there's no rank
operator in Dyalog...

-WM

Thu, 01 Sep 2005 02:51:24 GMT
Adrian Smith's spanned cells idiom challenge

Quote:
> Did you actually execute the last expression? :-)
> I would have thought that the anwser would be {iota}0.
> Unless you meant "match" instead of "equal".

Sorry - my native language isn't English.
I meant "match" indeed.

-VM

Thu, 01 Sep 2005 02:54:41 GMT
Adrian Smith's spanned cells idiom challenge

Quote:
> V-M, your expression fails if the argument is singleton 1. Gotcha :-)

OK, let's change it slightly to
{w\ <neg>2-/ (w,1)/ <iota>1+ <shape>,w}

-WM

Thu, 01 Sep 2005 03:43:22 GMT
Adrian Smith's spanned cells idiom challenge
On Sat, 15 Mar 2003 12:48:51 -0600, Ted Edwards wrote

Quote:

>> Adrian Smith gave this problem:

>> Given a boolean vector q, add the number of following zeros to each 1. That
>> is, from:
>> q
>> 1 0 1 0 1 0 0 1 1 1 0
>> get:
>> 2 0 2 0 3 0 0 1 1 2 0

> example.  I would have thought that the answer should be one number for
> each 1 in q and that number should be 1+ the number of zeros following
> those 1.  Thus, for your q, the result should have length six and be
> 2 2 3 1 1 2

I believe that in APL2 the following expression would yield the result that
Gene described

q \ enlist shape each ( + \ q ) enclose q

and

enlist shape each ( + \ q) enclose q

would produce the result that Ted expected.

-- James L. Ryan -- TaliesinSoft

Thu, 01 Sep 2005 05:19:02 GMT
Adrian Smith's spanned cells idiom challenge
The technique of  q{enclose}q  also works in J;
g=: #^:_1 #;.1~  would handle all the cases (leading 0 or 1).

How about some benchmarks?  On a 500 MHz machine:

q=: ? 1e6 \$ 2       NB. 1e6 element random boolean vector
10{.q
0 1 0 1 0 0 1 1 1 0

g=: #^:_1 #;.1~

ts 'g q'
0.290167 1.78269e7

What are the numbers for Dyalog APL?

Quote:
----- Original Message -----

Sent: Saturday, March 15, 2003 10:13 AM
Subject: Re: Adrian Smith's spanned cells idiom challenge

And the 8-character, each-utilising solution in Dyalog APL, migration level
2:

q\{enlist}{rank}{each}q{enclose}q

V-M, your expression fails if the argument is singleton 1. Gotcha :-)

/ Tomas

Thu, 01 Sep 2005 05:39:14 GMT

 Page 1 of 2 [ 25 post ] Go to page: [1] [2]

Relevant Pages