[Numpy-discussion] Is there a pure numpy recipe for this?

[Eelco Hoogendoorn]

Without looking ahead, here is what I came up with; but I see more elegant
solutions have been found already.



import numpy as np

def as_dense(f, length):
    i = np.zeros(length+1, np.int)
    i[f[0]] = 1
    i[f[1]] = -1
    return np.cumsum(i)[:-1]

def as_sparse(d):
    diff = np.diff(np.concatenate(([0], d)))
    on, = np.nonzero(diff)
    on = on if on.size%2==0 else np.append(on, len(d))
    return on.reshape(-1,2).T

def join(f, g):
    on  = np.sort(np.concatenate((f[0], g[0])))
    off = np.sort(np.concatenate((f[1], g[1])))
    I = np.argsort( np.concatenate((on, off)) ).argsort().reshape(2,-1)

    Q = -np.ones((2,I.size), np.int)
    Q[0,I[0]] = on
    Q[1,I[1]] = off

    idx_on  = np.logical_and( Q[0,1:]*Q[0,:-1] < 0, Q[0,:-1]!=-1)
    idx_off = np.logical_and( Q[1,1:]*Q[1,:-1] < 0, Q[1,1:]!=-1)

    idx_on  = np.concatenate( (idx_on, [False]))
    idx_off = np.concatenate( ([False], idx_off))

    return np.array(( Q[0,idx_on], Q[1,idx_off]))


length = 150

f_2_changes_at = np.array( [  2 ,  3 , 39,  41 , 58 , 59,  65 , 66 , 93
,102, 145, length])
g_2_changes_at = np.array( [  2 , 94 ,101, 146, 149, length])

f = f_2_changes_at.reshape(-1,2).T
g = g_2_changes_at.reshape(-1,2).T

dense_result = as_sparse( np.logical_and( as_dense(f, length),
as_dense(g,length)))
sparse_result = join(f,g)

print np.allclose(dense_result, sparse_result)


On Wed, Mar 26, 2014 at 10:50 PM, Jaime Fernández del Río <
jaime.frio at gmail.com> wrote:

> On Wed, Mar 26, 2014 at 2:23 PM, Slaunger <Slaunger at gmail.com> wrote:
>
>> Jaime Fernández del Río wrote
>>
>> You saved my evening! Actually, my head has been spinning about this
>> problem
>> the last three evenings without having been able to nail it down.
>>
>
> I had to quit Project Euler about 5 years ago because it was taking a huge
> toll on my mental health. I did learn/remember a ton of math, but was
> staying up all night banging my head against the problems much too often.
> Every now and then I do peek back and sometimes attempt a problem or two,
> but try to stay away for my own good.
>
> If you want to be projecteuler friends, I'm jfrio over there...
>
> Jaime
>
> _______________________________________________
> NumPy-Discussion mailing list
> NumPy-Discussion at scipy.org
> http://mail.scipy.org/mailman/listinfo/numpy-discussion
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/numpy-discussion/attachments/20140326/940d8a4d/attachment.html>