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

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

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

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

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
leading zeroes.

-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
leading zeroes.

-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

Leading value 0 or 1.

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

I'm puzzled by your description and (apparently to me) contradictory
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}

      {rho}{quad}{is}f {iota}0        

0                                    
      {rho}{quad}{is}f 0              

0                                    
      {rho}{quad}{is}f 1              
1                                    
1                                    
      {rho}{quad}{is}f  0 0 0        

0                                    
      {rho}{quad}{is}f  1 1 1        
1 1 1                                
3                                    
      q                              
1 0 1 0 1 0 0 1 1 1 0                
      {rho}{quad}{is}f  q            
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 :-)

Touche - but Adrian's original problem was about vectors.
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

> I'm puzzled by your description and (apparently to me) contradictory
> 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

Leading value 0 or 1.

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

/ Tomas



Thu, 01 Sep 2005 05:39:14 GMT  
 
 [ 25 post ]  Go to page: [1] [2]

 Relevant Pages 

1. APL character set (Adrian Smith's proposed encoding)

2. Adrian Smith's Benchmark

3. Adrian Davis' setcsv with modifications

4. open 'no-exist' rescue true - idiom

5. `*' spanning multiple words in rdoc

6. Howard Smith's histogram

7. Win32Forth questions and Robert Smith's email address

8. FS (ebay) Book : ASIC's (Michael John Sebastian Smith)

9. FS (ebay) : Book : ASIC's (Michael John Sebastian Smith)

10. Empty array challenge ''=i.0

11. NY/SIGAPL Meeting 2/27/96: Adrian Smith on "An Object-Based Approach to Application Design and Printing"

 

 
Powered by phpBB® Forum Software