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@gmail.com> wrote:
On Wed, Mar 26, 2014 at 2:23 PM, Slaunger <Slaunger@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@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion