Given a m * n matrix mat of integers, sort it diagonally in ascending order from the top-left to the bottom-right then return the sorted array.
| 3 | 3 | 1 | 1 |
| 2 | 2 | 1 | 2 |
| 1 | 1 | 1 | 2 |
| 1 | 1 | 1 | 1 |
| 1 | 2 | 2 | 2 |
| 1 | 2 | 3 | 3 |
Constraints:
m == mat.length n == mat[i].length 1 <= m, n <= 100 1 <= mat[i][j] <= 100
The problem statement is actually a little limited in the information it gives. It does not specify exactly what diagonal order is. Yes, each diagonal should be sorted, but there’s multiple ways to do that.
So we get to choose. And the most straightforward way I can think of of doing that is to define an order where you start by filling in the top row and leftmost column in alternating order, moving inward as necessary, you should always end up with
In other words, if we are filling a 3x5 matrix from a list of numbers 0-14 we would end up with the following.
| 0 | 1 | 3 | 5 | 6 |
| 2 | 7 | 8 | 10 | 11 |
| 4 | 9 | 12 | 13 | 14 |
We would therefore expect the following output
| Row | Column |
|---|---|
| 0 | 0 |
| 0 | 1 |
| 1 | 0 |
| 0 | 2 |
| 2 | 0 |
| 0 | 3 |
| 0 | 4 |
| 1 | 1 |
| 1 | 2 |
| 2 | 1 |
| 1 | 3 |
| 1 | 4 |
| 2 | 2 |
| 2 | 3 |
| 2 | 4 |
(define (values-get fn) (lambda args (fn args)))
(define (matrix-diagonal-cells row-count column-count)
(sequence->stream
(in-generator
(let recurse ([add-in (vec 0 0)]
[dimensions (vec row-count column-count)])
(define (yield-vec v) (yield (vec+ v add-in)))
(define (get-dimension fn) (apply fn (vec->list dimensions)) )
(define overflow-direction (if (> (get-dimension (values-get first)) (get-dimension (values-get second)))
(vec 1 0)
(vec 0 1)))
(when (< 0 (apply min (vec->list dimensions)))
(yield-vec (vec 0 0))
(for ([i (range 1 (get-dimension min))])
(yield-vec (vec 0 i))
(yield-vec (vec i 0)))
(for ([i (range (get-dimension min) (get-dimension max))])
(yield-vec (vec* overflow-direction i)))
(recurse (vec+ add-in (vec 1 1)) (vec- dimensions (vec 1 1))))))))<<requires>>
<<matrix-diagonal-cells>>
(sequence->list (matrix-diagonal-cells 3 5))(list (vec 0 0) (vec 0 1) (vec 1 0) (vec 0 2) (vec 2 0) (vec 0 3) (vec 0 4) (vec 1 1) (vec 1 2) (vec 2 1) (vec 1 3) (vec 1 4) (vec 2 2) (vec 2 3) (vec 2 4))
This looks good, so now we would only need to join and sort, and populate a matrix according to this sequence
So first lets sort all matrix values and also all positions
(define sorted-matrix-values (lambda~> (apply in-sequences _)
sequence->list
(sort <)))<<requires>>
<<matrix-diagonal-cells>>
<<sorted-matrix-values>>
(sorted-matrix-values data)'(1 1 1 1 1 1 2 2 2 2 3 3)
Yup that’s our sequence sorted. So now lets pair these together with our positions, sort the result by position, and chunk the remainder by their position so we get a nice pretty matrix.
(define (list->values lst) (apply values lst)) ;;no idea why this doens't already exist in racket/base
(define/match (is-position-before cell1 cell2)
[((list (vec row1 col1) _) (list (vec row2 col2) _)) (or (< row1 row2)
(and (= row1 row2) (< col1 col2)))])
(define (diagonally-sorted-matrix data)
(define dimensions (list (length data) (length (first data))))
(define positions (call-with-values (thunk (list->values dimensions)) matrix-diagonal-cells))
(~>> (sorted-matrix-values data)
(map list positions) ;;zip with the above
sequence->list
(sort _ is-position-before)
(map second)
(chunk (second dimensions))))<<requires>>
<<matrix-diagonal-cells>>
<<sorted-matrix-values>>
<<diagonally-sorted-matrix>>
(~>> (diagonally-sorted-matrix data)
(map sequence->list)
sequence->list
display-table)1,1,1,1 1,2,2,2 1,2,3,3
And that’s sorted!
(require (except-in data/collection sequence->list)) ;;https://stackoverflow.com/a/62505165/5056
(require csv-writing)
(require racket/generator)
(require sfont/geometry)
(require threading)(require csv-writing)
(display-table data)
(list (length (first data)) (length data))
3,3,1,1 2,2,1,2 1,1,1,2 '(4 3)
(require racket/match)
(require threading)
(require sfont/geometry)
(require data/collection)
(sequence->list (map + '(5 10 15) #(3 6 9)))'(8 16 24)
| 0 | 1 | 3 |
| 2 | 5 | 6 |
| 4 | 7 | 8 |
Doing a related problem in python as a demo for a student
def addt(a, b):
return (a[0]+b[0], a[1]+b[1])
def mult(factor, t):
return (t[0]*factor, t[1]*factor)
def matrix_diagonal_cells(dimensions, add_in=(0,0)):
if min(dimensions) <= 0:
return
yield add_in # the corner element
# alternating cells from the edges as long as we can
for i in range(1, min(dimensions)):
yield addt((0, i), add_in)
yield addt((i, 0), add_in)
# whichever side is longest has a few more cells to go
overflow_direction = (1, 0) if dimensions[0] > dimensions[1] else (0, 1)
for i in range(min(dimensions), max(dimensions)):
yield addt(mult(i, overflow_direction), add_in)
# same thing but for the inner matrix
yield from matrix_diagonal_cells(
addt(dimensions, (-1,-1)),
addt(add_in, (1,1))
)<<matrix_diagonal_cells>>
return list(matrix_diagonal_cells((3,5)))| 0 | 0 |
| 0 | 1 |
| 1 | 0 |
| 0 | 2 |
| 2 | 0 |
| 0 | 3 |
| 0 | 4 |
| 1 | 1 |
| 1 | 2 |
| 2 | 1 |
| 1 | 3 |
| 1 | 4 |
| 2 | 2 |
| 2 | 3 |
| 2 | 4 |
Now we pair our numbers along with the tuples above, and sort by the tuples
def get_enumerated_sorted_positions(dimensions):
row_factor = 10*dimensions[1]
def position_sort_score(enumerated_pos):
pos = enumerated_pos[1]
return pos[0]*row_factor + pos[1]
positions = matrix_diagonal_cells(dimensions)
sorted_positions = sorted(enumerate(positions), key=position_sort_score)
return sorted_positions<<matrix_diagonal_cells>>
<<get_enumerated_sorted_positions>>
return list(get_enumerated_sorted_positions((3,5)))| 0 | (0 0) |
| 1 | (0 1) |
| 3 | (0 2) |
| 5 | (0 3) |
| 6 | (0 4) |
| 2 | (1 0) |
| 7 | (1 1) |
| 8 | (1 2) |
| 10 | (1 3) |
| 11 | (1 4) |
| 4 | (2 0) |
| 9 | (2 1) |
| 12 | (2 2) |
| 13 | (2 3) |
| 14 | (2 4) |
Now we just pluck out the first value and chunk....which we have to implement. Ugh
from itertools import groupby
from functools import partial
<<matrix_diagonal_cells>>
<<get_enumerated_sorted_positions>>
def chunk(n, coll):
def getrow(t):
return int(t[0]/n)
for _, row in groupby(enumerate(coll), key=getrow):
yield (v for _, v in row)
dimensions = (3, 5)
values = map(lambda t: t[0], get_enumerated_sorted_positions(dimensions))
matrix = chunk(dimensions[1], values)
return list(map(list, matrix))| 0 | 1 | 3 | 5 | 6 |
| 2 | 7 | 8 | 10 | 11 |
| 4 | 9 | 12 | 13 | 14 |