matrix-sum-of-region

Matrix Sum of Region

Problem Statement

From the Operation Code #daily-programmer chat

Given a matrix of integers and the top left and bottom right coordinates of a rectangular region within the matrix, find the sum of numbers falling inside the rectangle.

Example:

#[#[1 2 3 4]
  #[5 6 7 8]
  #[9 0 1 2]]

(struct location (column row))
(struct region-test (start end expected-sum))

(region-test (location 1 1) (location 3 2) 24)

Playground

This section is because I am only just learning Racket. If you want to skip past me figuring this stuff out then jump to Implementation.

String formats

Docs

Hashes

I don’t like to have just random tuples in lists - I think I should learn about hashes.

(define h (make-hash '((a . "apple") (b . "banana"))))
(printf "h is: ~a\n" h)
(printf "has a: ~a, the value is: ~a\n" (dict-has-key? h 'a) (dict-ref h 'b))
(printf "has c: ~a\n" (dict-has-key? h 'c))

h is: #hash((a . apple) (b . banana))
has a: #t, the value is: banana
has c: #f

Structs

Docs But I think structs are actually more natural for this

(struct posn (x y))
(define p (posn 139 73))
(printf "p: ~a, prop x is: ~a\n" p (posn-x p))

p: #<posn>, prop x is: 139

Array

Docs Arrays are different from lists, they seem to be…multidimensional? Which is after all waht I want here

(require math/array)
(array #[#['first 'row 'data] #['second 'row 'data]])

(array #[#['first 'row 'data] #['second 'row 'data]])

(require math/array)
(build-array #(4 5) (λ (js)
                      (match-define (vector j0 j1) js)
                      (+ j0 j1)))

(array #[#[0 1 2 3 4] #[1 2 3 4 5] #[2 3 4 5 6] #[3 4 5 6 7]])

Array Slicing

Docs So this takes an array with a Slice Spec. This is multidimensional. Lets figure out the slide spec for copying out #[#[6 7 8] #[0 1 2]]

(require math/array)
(define matrix (array #[#[1 2 3 4]
                        #[5 6 7 8]
                        #[9 0 1 2]]))
(define sliced (array-slice-ref matrix (list (:: 1 3) (:: 1 4))))
(printf "~a\n" sliced)
(printf "sum: ~a" (array-all-sum sliced))

(array #[#[6 7 8] #[0 1 2]])
sum: 24

Implementation

Uhh…ok…so with the array functions above this becomes stupid simple

(require math/array)

(struct location (column row))

(define (sum-matrix-region matrix start end)
  (define slice-spec (list (:: (location-row start)
                               (add1 (location-row end)))
                           (:: (location-column start)
                               (add1 (location-column end)))))
  (define sliced (array-slice-ref matrix slice-spec))
  (array-all-sum sliced))

(sum-matrix-region (array #[#[1 2 3 4]
                            #[5 6 7 8]
                            #[9 0 1 2]])
                   (location 1 1)
                   (location 3 2))

24

Hacha!