Javascript Sorting Matrix Diagonally

Question

There is an algorithm question asking to sort a matrix diagonally. I'm not finding a solution for this quesiton.

const matrix = 
[ 
  [1, 3, 9, 4],
  [9, 5, 7, 7],
  [3, 6, 9, 7],
  [1, 2, 2, 2]
]

Should output:

[
  [1, 9, 9, 7],
  [3, 5, 6, 9],
  [3, 4, 7, 7],
  [1, 2, 2, 2]
]

My code so far:

function diagonalSort(matrix) {
  const cols = matrix[0].length;
  const rows = matrix.length;
  const maxLength = Math.max(cols, rows);
  let temp;

  for (let k = 0; k <= 2 * (maxLength - 1); k++) {
    temp = [];
    for (let y = cols - 1; y >= 0; y--) {
      let x = k - y;
      // console.log(k, y, x);
      if (x >= 0 && x < rows) {
        temp.push(matrix[y][x]);
      }
    }
    if (temp.length > 0) {
      console.log(temp);
    }
  }
}

Which outputs this:

[ 1 ]
[ 3, 9 ]
[ 3, 5, 9 ]
[ 1, 4, 6, 7 ]
[ 2, 7, 9 ]
[ 2, 7 ]
[ 2 ]

But how to put it back together...?

Answer 1

This approach is also a gentle introduction to functional lenses in Javascript:

const range = (lo, hi) => [...Array (hi - lo)] .map ((_, i) => i + lo)

const diagonals = (rows, cols) => 
  range (0, rows + cols - 1) .map (
    d => range (Math.max (d - rows + 1, 0), Math.min (d, cols - 1) + 1) 
         .map (x => [d - x, x])
  )

const coordLens = (coords) => ({
  get: (m) => coords .map (([x, y]) => m [x] [y]),
  set: (arr, m) => coords .reduce (
    (m, [x, y], i) =>  {m [x] [y] = arr [i]; return m},
    m .map (r => [... r]) // cheap clone
  ),
})

const diagonalLenses = (rows, cols) =>
  diagonals (rows, cols) .map (coordLens)

const sortMatrix = (comparator) => (m) =>
  diagonalLenses (m.length, m[0].length) 
    .reduce ((m, lens) => lens.set (lens .get (m) .sort (comparator), m), m)

const numericSorter = (a, b) => a - b

console .log (
  sortMatrix (numericSorter) ([ 
    [1, 3, 9, 4],
    [9, 5, 7, 7],
    [3, 6, 9, 7],
    [1, 2, 2, 2]
  ])
  .map (r => r .join (' ')) .join ('\n')
)

After the minor helper function range (which works like range (3. 12) ==> [3, 4 , 5, 6, 7, 8, 9, 10, 11]) (including the start, excluding the stop) we have diagonals, which calculates the diagonals as arrays of [x, y] pairs, given the height and width of a matrix.

The most important bit here is coordLens. A lens is a glorified getter/setter pair for some facet of a data structure. They turn out to be quite useful. Many of the standard introductions to them point to a single property or array index, or perhaps a nested path inside an object. These are slightly more interesting. coordLens takes an array of [x, y] coordinates and returns a lens that we can use to extract the values at those coordinates from a given matrix, or to set the values in (a copy of) a matrix from elements supplied as an array.

On top of these two we build diagonalLenses, which takes the number of rows and columns and creates an array of coordinate lenses, one for each diagonal.

We build the main function sortMatrix on these functions. We accept a standard comparator and return a function that takes a matrix and returns another of the same shape, with each of the southwest -> northeast diagonals sorted. We create an array of lenses using diagonalLenses. Then for each lens, we get the values, sort them and use the set method to update our cloned matrix with the sorted values.

Note that there is little error-checking in any of this. The pieces will work together in the manner described here, but coordLens should, if used more generically, check that the array values it's trying to receive or to set are within bounds.

Addendum - the use of lenses

I originally wanted to explain the use of lenses in greater depth. But it was bedtime and I left it with just a brief description. There are many tutorials available to cover the basics. But very, very briefly, lenses are structures that focus on one aspect of a data structure. You create one by supplying a getter and a setter for your aspect, and then you can use a consistent interface to read, write, and modify data. (In the write/modify cases, this would involve creating a copy of the object. There's no mutation involved; we're not barbarians!)

What I am taking advantage of here is that the lenses don't have to be as simple as tends to be shown in those tutorials. Instead of pointing to a single property of an object, they can do more. One of my favorite examples is that a weather app which -- as is only sensible -- reports temperatures in Celsius, but which has users who live in a benighted country like by own, who only know Fahrenheit.

const fahrenLens = lens(
  obj => obj.temp * 9 / 5 + 32,
  (degF, obj) => ({...obj, temp: (degF - 32) * 5 / 9})
)

And it can be used like this:

const nyc= {name: 'New York', lat: 40.730610, lng: -73.935242, temp: 25}

view (fahrenLens, nyc) //=> 77
set (fahrenLens, 86, nyc) 
//=> {name: "New York", lat: 40.73061, lng: -73.935242, temp: 30}
over (fahrenLens, t => t - 27, nyc) 
//=> {name: "New York", lat: 40.73061, lng: -73.935242, temp: 10}

This uses three standard function for working with lenses, which, in our simple lens implementation might look like this:

const view = (lens, o) => lens .get (o)
const set = (lens, v, o) => lens .set (v, o)
const over = (lens, f, o) => lens .set (f (lens .get (o)), o)

In the answer above we use lenses to track multiple coordinates in an m x n grid, using this code:

const coordLens = (coords) => ({
  get: (m) => coords .map (([x, y]) => m [x] [y]),
  set: (arr, m) => coords .reduce (
    (m, [x, y], i) =>  {m [x] [y] = arr [i]; return m},
    m .map (r => [... r]) // cheap clone
  ),
})

Given a set of coordinates, when we view a matrix through this coordinate lens, we get back an array of the values at those coordinates. When we set the matrix with an array of values through this lens, we fold the array of values into a new matrix by setting each coordinate to the corresponding array value, starting with a copy of the matrix.

Using diagonalLenses, we create an array of coordinate lenses, one for each diagonal in the grid. (Here considering only on southwest -> northeast diagonals.) If we were to use our over function we could simplify further to

const sortMatrix = (comparator) => (m) =>
  diagonalLenses (m) 
    .reduce ((m, lens) =>  over (lens, xs => xs.sort (comparator), m), m)

And my own preference would be to introduce a sort function like

const sort = (comparator) => (xs) => [...xs] .sort (comparator)

which would allow us to simplify that further to

const sortMatrix = (comparator) => (m) =>
  diagonalLenses (m) 
    .reduce ((m, lens) =>  over (lens, sort (comparator), m), m)

Now a good question is how much this abstraction buys us. Using the same range and diagonals functions, we could write sortMatrix like this:

const sortMatrix = (comparator) => (m) =>
  diagonals (m) 
    .reduce (
      (m, diagonal) => {
        const vals = diagonal .map (([y, x]) => m [y] [x]) .sort (comparator)
        return diagonal .reduce ((m, [y, x], i) => {m [y] [x] = vals [i]; return m}, m)
      },
      m .map (r => [...r])
    )

which involves fewer lines of code than the combination of coordLens, diagLenses, and even our shortest earlier version of sortMatrix.

One argument is that it adds nothing, that this version is fine. If you have to do nothing else with those diagonals, or with other collections of coordinates, this might be true. But these lenses can be very convenient. If we wanted to total up each diagonal for some reason, it's a one-liner on top of the response from diagonalLenses:

const m = [ 
  [1, 3, 9, 4],
  [9, 5, 7, 7],
  [3, 6, 9, 7],
  [1, 2, 2, 2]
]

const myDiagonals = diagonalLenses (m .length, m [0] .length) 
const diagonalSums = myDiagonals .map (d => sum (view2 (d, m)))

diagonalSums // => [1, 12, 17, 18, 18, 9, 2]

for an obvious sum function over an array.

And there are many more things we could do with them.

One thing that I should make clear is that these lenses we create are not specific to a particular matrix. Our list of diagonal lenses for one m x n matrix are exactly the same for another m x n one.

And the same is true for the underlying coordinate lenses. They have to do only with the shape of the matrix. We can easily imagine a sudoku solver which has a lens for each row, column, and box, which we then test for a correct solution with something like

const gridCompleted = (grid) => 
  lenses .every (lens => completeGroup (view (lens, grid)))

Answer 2

const cols = matrix[0].length;
const rows = matrix.length;
const maxLength = Math.max(cols, rows);
let tempArr = [];
let result = [];

for (let k = 0; k <= 2 * (maxLength - 1); k++) {
    let temp = [];
    for (let y = cols - 1; y >= 0; y--) {
        let x = k - y;
        // console.log(k, y, x);
        if (x >= 0 && x < rows) {
            temp.push(matrix[y][x]);
        }
    }

    if (temp.length > 0) {
        // console.log(temp.sort());
        tempArr.push(temp.sort());
    }
}

for (let k = 0; k <= maxLength - 1; k++) {
    let tempResult = [];
    let arr = tempArr.filter((a) => a.length > 0);
    // console.log(arr);
    for (let i = 0; i <= maxLength - 1; i++) {
        const length = arr[i].length;
        tempResult.push(arr[i][length - 1]);
        tempArr[tempArr.indexOf(arr[i])].pop();
    }
    result.push(tempResult);
}
return result;

Answer 3

Here we go:

    function* enumerateDiagonals(xLength, yLength) {
        
        for (let y = 0; y < yLength; y++) {
            yield {
                x: 0,
                y: y
            };
        }
        
        for (let x = 1; x < xLength; x++) {
            yield {
                x: x,
                y: yLength - 1
            };
        }
    }

    function sliceMatrix(matrix, diagonal) {
        const slice = [];
        
        for (let y = diagonal.y, x = diagonal.x; y >=0 && x<matrix[y].length ; y--, x++) {
            slice.push(matrix[y][x])
        }
        
        return slice
    }

    function emplaceIntoMatrix(slice, matrix, diagonal) {
        
        for (let i=0; i < slice.length; i++) {
            matrix[diagonal.y - i][diagonal.x + i] = slice[i];
        }
        
    }


    const matrix = 
    [ 
      [1, 3, 9, 4],
      [9, 5, 7, 7],
      [3, 6, 9, 7],
      [1, 2, 2, 2]
    ];

    const Ylength = matrix.length
    const Xlength = matrix[0].length

    console.log(Ylength)
    console.log(Xlength)

    const sortedMatrix = [ ];
    for(let i=0; i<Ylength; i++) {
        sortedMatrix[i] = new Array(Xlength);
    }

    for (const diagonal of enumerateDiagonals(Xlength, Ylength)) {
        
        var slice = sliceMatrix(matrix, diagonal);
        slice.sort();
        
        emplaceIntoMatrix(slice, sortedMatrix, diagonal);
    }

    console.log(sortedMatrix);