Python: Justifying NumPy array

Question

Please I am a bit new to Python and it has been nice, I could comment that python is very sexy till I needed to shift content of a 4x4 matrix which I want to use in building a 2048 game demo of the game is here I have this function

def cover_left(matrix):
        new=[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
        for i in range(4):
             count=0
             for j in range(4):
                if mat[i][j]!=0:
                    new[i][count]=mat[i][j]
                    count+=1
        return new

This is what this function does if you call it like this

cover_left([
              [1,0,2,0], 
              [3,0,4,0], 
              [5,0,6,0], 
              [0,7,0,8]
          ])

It will cover the zeros to the left and produce

[  [1, 2, 0, 0],
   [3, 4, 0, 0],
   [5, 6, 0, 0],
   [7, 8, 0, 0]]

Please I need someone to help me with a numpy way of doing this which I believe will be faster and require less code (I am using in a depth-first search algo) and more importantly the implementation of cover_up, cover_down and cover_left.

`cover_up`
    [  [1, 7, 2, 8],
       [3, 0, 4, 0],
       [5, 0, 6, 0],
       [0, 0, 0, 0]]
`cover_down`
    [  [0, 0, 0, 0],
       [1, 0, 2, 0],
       [3, 0, 4, 0],
       [5, 7, 6, 8]]
`cover_right`
    [  [0, 0, 1, 2],
       [0, 0, 3, 4],
       [0, 0, 5, 6],
       [0, 0, 7, 8]]

Divakar · Accepted Answer · 2020-08-31T15:16:18.457

Here's a vectorized approach inspired by this other post and generalized to cover non-zeros for all four directions -

def justify(a, invalid_val=0, axis=1, side='left'):    
    """
    Justifies a 2D array

    Parameters
    ----------
    A : ndarray
        Input array to be justified
    axis : int
        Axis along which justification is to be made
    side : str
        Direction of justification. It could be 'left', 'right', 'up', 'down'
        It should be 'left' or 'right' for axis=1 and 'up' or 'down' for axis=0.

    """

    if invalid_val is np.nan:
        mask = ~np.isnan(a)
    else:
        mask = a!=invalid_val
    justified_mask = np.sort(mask,axis=axis)
    if (side=='up') | (side=='left'):
        justified_mask = np.flip(justified_mask,axis=axis)
    out = np.full(a.shape, invalid_val) 
    if axis==1:
        out[justified_mask] = a[mask]
    else:
        out.T[justified_mask.T] = a.T[mask.T]
    return out

Sample runs -

In [473]: a # input array
Out[473]: 
array([[1, 0, 2, 0],
       [3, 0, 4, 0],
       [5, 0, 6, 0],
       [6, 7, 0, 8]])

In [474]: justify(a, axis=0, side='up')
Out[474]: 
array([[1, 7, 2, 8],
       [3, 0, 4, 0],
       [5, 0, 6, 0],
       [6, 0, 0, 0]])

In [475]: justify(a, axis=0, side='down')
Out[475]: 
array([[1, 0, 0, 0],
       [3, 0, 2, 0],
       [5, 0, 4, 0],
       [6, 7, 6, 8]])

In [476]: justify(a, axis=1, side='left')
Out[476]: 
array([[1, 2, 0, 0],
       [3, 4, 0, 0],
       [5, 6, 0, 0],
       [6, 7, 8, 0]])

In [477]: justify(a, axis=1, side='right')
Out[477]: 
array([[0, 0, 1, 2],
       [0, 0, 3, 4],
       [0, 0, 5, 6],
       [0, 6, 7, 8]])

Generic case (ndarray)

For a ndarray, we could modify it to -

def justify_nd(a, invalid_val, axis, side):    
    """
    Justify ndarray for the valid elements (that are not invalid_val).

    Parameters
    ----------
    A : ndarray
        Input array to be justified
    invalid_val : scalar
        invalid value
    axis : int
        Axis along which justification is to be made
    side : str
        Direction of justification. Must be 'front' or 'end'.
        So, with 'front', valid elements are pushed to the front and
        with 'end' valid elements are pushed to the end along specified axis.
    """
    
    pushax = lambda a: np.moveaxis(a, axis, -1)
    if invalid_val is np.nan:
        mask = ~np.isnan(a)
    else:
        mask = a!=invalid_val
    justified_mask = np.sort(mask,axis=axis)
    
    if side=='front':
        justified_mask = np.flip(justified_mask,axis=axis)
            
    out = np.full(a.shape, invalid_val)
    if (axis==-1) or (axis==a.ndim-1):
        out[justified_mask] = a[mask]
    else:
        pushax(out)[pushax(justified_mask)] = pushax(a)[pushax(mask)]
    return out

Sample runs -

Input array :

In [87]: a
Out[87]: 
array([[[54, 57,  0, 77],
        [77,  0,  0, 31],
        [46,  0,  0, 98],
        [98, 22, 68, 75]],

       [[49,  0,  0, 98],
        [ 0, 47,  0, 87],
        [82, 19,  0, 90],
        [79, 89, 57, 74]],

       [[ 0,  0,  0,  0],
        [29,  0,  0, 49],
        [42, 75,  0, 67],
        [42, 41, 84, 33]],

       [[ 0,  0,  0, 38],
        [44, 10,  0,  0],
        [63,  0,  0,  0],
        [89, 14,  0,  0]]])

To 'front', along axis =0 :

In [88]: justify_nd(a, invalid_val=0, axis=0, side='front')
Out[88]: 
array([[[54, 57,  0, 77],
        [77, 47,  0, 31],
        [46, 19,  0, 98],
        [98, 22, 68, 75]],

       [[49,  0,  0, 98],
        [29, 10,  0, 87],
        [82, 75,  0, 90],
        [79, 89, 57, 74]],

       [[ 0,  0,  0, 38],
        [44,  0,  0, 49],
        [42,  0,  0, 67],
        [42, 41, 84, 33]],

       [[ 0,  0,  0,  0],
        [ 0,  0,  0,  0],
        [63,  0,  0,  0],
        [89, 14,  0,  0]]])

Along axis=1 :

In [89]: justify_nd(a, invalid_val=0, axis=1, side='front')
Out[89]: 
array([[[54, 57, 68, 77],
        [77, 22,  0, 31],
        [46,  0,  0, 98],
        [98,  0,  0, 75]],

       [[49, 47, 57, 98],
        [82, 19,  0, 87],
        [79, 89,  0, 90],
        [ 0,  0,  0, 74]],

       [[29, 75, 84, 49],
        [42, 41,  0, 67],
        [42,  0,  0, 33],
        [ 0,  0,  0,  0]],

       [[44, 10,  0, 38],
        [63, 14,  0,  0],
        [89,  0,  0,  0],
        [ 0,  0,  0,  0]]])

Along axis=2 :

In [90]: justify_nd(a, invalid_val=0, axis=2, side='front')
Out[90]: 
array([[[54, 57, 77,  0],
        [77, 31,  0,  0],
        [46, 98,  0,  0],
        [98, 22, 68, 75]],

       [[49, 98,  0,  0],
        [47, 87,  0,  0],
        [82, 19, 90,  0],
        [79, 89, 57, 74]],

       [[ 0,  0,  0,  0],
        [29, 49,  0,  0],
        [42, 75, 67,  0],
        [42, 41, 84, 33]],

       [[38,  0,  0,  0],
        [44, 10,  0,  0],
        [63,  0,  0,  0],
        [89, 14,  0,  0]]])

To the 'end' :

In [94]: justify_nd(a, invalid_val=0, axis=2, side='end')
Out[94]: 
array([[[ 0, 54, 57, 77],
        [ 0,  0, 77, 31],
        [ 0,  0, 46, 98],
        [98, 22, 68, 75]],

       [[ 0,  0, 49, 98],
        [ 0,  0, 47, 87],
        [ 0, 82, 19, 90],
        [79, 89, 57, 74]],

       [[ 0,  0,  0,  0],
        [ 0,  0, 29, 49],
        [ 0, 42, 75, 67],
        [42, 41, 84, 33]],

       [[ 0,  0,  0, 38],
        [ 0,  0, 44, 10],
        [ 0,  0,  0, 63],
        [ 0,  0, 89, 14]]])

Is it possible to do this without calling np.sort, that slows down the runtime — qwertylpc, May 14 '19 at 17:10
The array dynamically changes rows, between 2-7 (99.99% of the time) but has 100,000 columns. I only need the up justify function you were writing. — qwertylpc, May 14 '19 at 17:25
Submitted ticket for this on [github](https://github.com/numpy/numpy/issues/15863) — Erfan, Mar 29 '20 at 14:35
Can't there be a kind of counting operation to replace sort? A simple axiswise sum on a boolean mask can tell how many invalid_vals are there - the indexes can then be generated using a combination of repeat and arange. Should theoretically scale a bit better than this. — Mercury, Jul 22 '20 at 11:42
Can this one be adapted for string value arrays? Actual alphabets, not numbers stored as string. — Gursharan Singh, Oct 01 '20 at 09:25
@GursharanSingh Think should work for those too. If not, can you post a new question? — Divakar, Oct 01 '20 at 09:35
@Divakar been unsing your funciton `justify_nd` the last days and it works very well. Its very efficient when ran on large datasets. I now have another problem: the function has to be called very very often. (million times). so i thought of adding a `@jiti` decorator it via `numba`. unfortunately numba doesnt support `np.moveaxis`. So: is there a way to do this with np.transpose()? — La-Li-Lu-Le-Low, Oct 04 '20 at 12:50
@Divakar it's not working properly with string arrays. It raises a ```ValueError: could not convert string to float``` on the following line: ```out.T[justified_mask.T] = a.T[mask.T]``` — olenscki, Jan 14 '21 at 13:43

score 0 · Answer 2 · answered Jun 15 '17 at 05:57

0

Thanks to all this is what I later use

def justify(a, direction):
    mask = a>0
    justified_mask = numpy.sort(mask,0) if direction == 'up' or direction =='down' else numpy.sort(mask, 1)
    if direction == 'up':
        justified_mask = justified_mask[::-1]
    if direction =='left':
        justified_mask = justified_mask[:,::-1]
    if direction =='right':
        justified_mask = justified_mask[::-1, :]    
    out = numpy.zeros_like(a) 
    out.T[justified_mask.T] = a.T[mask.T]
    return out

answered Jun 15 '17 at 05:57

Akins Nazri

307
3
10

1

This is basically same as the [`other post`](https://stackoverflow.com/a/44559180/3293881), except that you have four conditional statements. What's new here? – Divakar Jun 15 '17 at 06:00
The signature is different, moreover he modified his answer... it wasn't like that before – Akins Nazri Jun 15 '17 at 08:30
What signature? You have four input options for one input argument, so four conditional statements. The other post had two input options for two input arguments. Essentially the same. – Divakar Jun 15 '17 at 08:32
The other post was edited 12 mins with those modifications before you posted this post. – Divakar Jun 15 '17 at 08:33

Python: Justifying NumPy array

2 Answers2

Generic case (ndarray)

Linked

Related