11 October, 2013

A nice solution on MATLAB Cody problem #73

MATLAB Cody is a useful place not only for having the compelling to solve different interesting problems in the smartest way, but for learning from the solutions of others. Now a very clever solution on Cody problem #73 is discussed. The task is:

Replace NaNs with the number that appears to its left in the row. If there are more than one consecutive NaNs, they should all be replaced by the first non-NaN value to the immediate left of the left-most NaN. If the NaN is in the first column, default to zero.

An example input and output pair is:

x = [NaN  1   2 NaN NaN  17   3  -4 NaN]
y = [  0  1   2   2   2  17   3  -4  -4]

The straightforward solution is to use a cycle while each NaNs are replaced. In the example below we put first a zero to the beginning of the array to handle the case of the NaNs at the front. Then in a cycle we find the position of the first NaN, and replace it with the previous element:

function x = replace_nans(x)
  x = [0 x]                     % put a zero into the first position
while any(isnan(x)) % loop until there is any NaN NaNList = isnan(x) % get a logical list of NaNs NaNPos = min(find(NaNList)) % find the position of the first NaN x(NaNPos) = x(NaNPos - 1) % new value: the value on the left end x(1) = [] % remove the zero from the first position end % an example usage of the function replace_nans([NaN 1 2 NaN NaN 17 3 -4 NaN]);

The output of the function is:

x =
     0  NaN    1    2  NaN  NaN   17    3   -4  NaN
NaNList =
     0    1    0    0    1    1    0    0    0    1
NaNPos =
     2
x = 0 0 1 2 NaN NaN 17 3 -4 NaN NaNList = 0 0 0 0 1 1 0 0 0 1 NaNPos = 5
x = 0 0 1 2 2 NaN 17 3 -4 NaN NaNList = 0 0 0 0 0 1 0 0 0 1 NaNPos = 6
x = 0 0 1 2 2 2 17 3 -4 NaN NaNList = 0 0 0 0 0 0 0 0 0 1 NaNPos = 10
x = 0 0 1 2 2 2 17 3 -4 -4 x = 0 1 2 2 2 17 3 -4 -4

Most of the solutions use this approach, but Ankur Pawar had another way of thinking. See his code first, it has been modified a bit for better understanding:

function x = replace_nans(x)  
  NotNaNs = ~isnan(x)           % positions of non-NaN elements  
  indices = cumsum(NotNaNs)     % indexing based on non-NaN positions
  
% filter for non-NaN elements and put a zero into the first position NotNaNList = [0 x(NotNaNs)] x = NotNaNList(indices + 1) % do the re-indexing of the vector end % an example usage of the function x = [NaN 1 2 NaN NaN 17 3 -4 NaN] replace_nans(x);

The output of the function is:

x =
   NaN    1    2  NaN  NaN   17    3   -4  NaN
NotNaNs =
     0    1    1    0    0    1    1    1    0
indices =
     0    1    2    2    2    3    4    5    5
NotNaNList =
     0    1    2   17    3   -4
x =
     0    1    2    2    2   17    3   -4   -4

This is a very clever solution using no loops:

  • First a logical array is generated indicating the non-NaN elements.
  • The next step is the key: the cumulated summation. The result of this operation is a list of indices, showing that which non-NaN element shall stay at the given position: in the indices vector from the left to the right the index is inceremented only, when we reach a non-NaN element otherwise it remains the same.
  • Then we collect the non-NaN elements and add a zero to handle the case of the first-placed NaNs.
  • The re-indexing is left only: we are ready.

A simple but great and useful approach: thanks, Ankur!

Tags:cody
         

New comment

comments powered by Disqus