Infinite Matrix – Rich 4Clojure Problem 168 – See: https://github.com/PEZ/rich4clojure

rich4clojure_medium_problem_168.clj

(ns rich4clojure.medium.problem-168
  (:require [hyperfiddle.rcf :refer [tests]]))

;; = Infinite Matrix =
;; By 4Clojure user: maximental
;; Difficulty: Medium
;; Tags: [seqs recursion math]
;; 
;; In what follows, m, n, s, t denote nonnegative
;; integers, f denotes a function that accepts two
;; arguments and is defined for all nonnegative integers
;; in both arguments.
;; 
;; 
;; In mathematics, the function f can be interpreted as
;; an infinite matrix with infinitely many rows and
;; columns that, when written, looks like an ordinary
;; matrix but its rows and columns cannot be written down
;; completely, so are terminated with ellipses. In
;; Clojure, such infinite matrix can be represented as an
;; infinite lazy sequence of infinite lazy sequences,
;; where the inner sequences represent rows.
;; 
;; 
;; Write a function that accepts 1, 3 and 5 arguments
;; * with the argument f, it returns the infinite matrix A
;; that has the entry in the i -th row and the j -th
;; column equal to f(i,j) for i,j = 0,1,2,... ;
;; * with the arguments f, m, n, it returns the infinite
;; matrix B that equals the remainder of the matrix A
;; after the removal of the first m rows and the first n
;; columns;
;; * with the arguments f, m, n, s, t, it returns the
;; finite s-by-t matrix that consists of the first t
;; entries of each of the first s rows of the matrix B or,
;; equivalently, that consists of the first s entries of
;; each of the first t columns of the matrix B .

(def restricted [for range iterate repeat cycle drop])

(def __ :tests-will-fail)

(comment
  
  )

(tests
  (take 5 (map #(take 6 %) (__ str))) :=
   [["00" "01" "02" "03" "04" "05"]
    ["10" "11" "12" "13" "14" "15"]
    ["20" "21" "22" "23" "24" "25"]
    ["30" "31" "32" "33" "34" "35"]
    ["40" "41" "42" "43" "44" "45"]]
  (take 6 (map #(take 5 %) (__ str 3 2))) :=
   [["32" "33" "34" "35" "36"]
    ["42" "43" "44" "45" "46"]
    ["52" "53" "54" "55" "56"]
    ["62" "63" "64" "65" "66"]
    ["72" "73" "74" "75" "76"]
    ["82" "83" "84" "85" "86"]]
  (__ * 3 5 5 7) :=
   [[15 18 21 24 27 30 33]
    [20 24 28 32 36 40 44]
    [25 30 35 40 45 50 55]
    [30 36 42 48 54 60 66]
    [35 42 49 56 63 70 77]]
  (__ #(/ % (inc %2)) 1 0 6 4) :=
   [[1/1 1/2 1/3 1/4]
    [2/1 2/2 2/3 1/2]
    [3/1 3/2 3/3 3/4]
    [4/1 4/2 4/3 4/4]
    [5/1 5/2 5/3 5/4]
    [6/1 6/2 6/3 6/4]]
  (class (__ (juxt bit-or bit-xor))) :=
   (class (__ (juxt quot mod) 13 21))
   (class (lazy-seq))
  (class (nth (__ (constantly 10946)) 34)) :=
   (class (nth (__ (constantly 0) 5 8) 55))
   (class (lazy-seq))
  (let [m 377 n 610 w 987
         check (fn [f s] (every? true? (map-indexed f s)))
         row (take w (nth (__ vector) m))
         column (take w (map first (__ vector m n)))
         diagonal (map-indexed #(nth %2 %) (__ vector m n w w))]
     (and (check #(= %2 [m %]) row)
          (check #(= %2 [(+ m %) n]) column)
          (check #(= %2 [(+ m %) (+ n %)]) diagonal))) :=
   true)

;; To participate, fork:
;; https://github.com/PEZ/rich4clojure

;; Post your solution below, please!

(defn __
  ([f]
   (map (fn [a] (map (fn [b] (f a b)) (range))) (range)))
  ([f a b]
   (drop a (map #(drop b %) (__ f))))
  ([f a b c d]
   (take c (map #(take d %) (__ f a b)))))

Quite tricky to factor and make lazy; used https://clojure.org/reference/lazy to guide lazy-seq helper functions. Also fun to avoid the problem restrictions on use of higher order functions
(def restricted [for range iterate repeat cycle drop])

(def __
  "builds matrix adding rows with rowmat starting at i-th row j-th column"
  (fn add-rows
    ([f] (add-rows f 0 0 []))
    ([f i-start j-start s-rows t-columns]
     (take s-rows (map #(take t-columns %) (add-rows f i-start j-start))))
    ([f i-start j-start] (add-rows f i-start j-start []))
    ([f i-th j-th matrix]
     (let [rowmat ;; body of row maker in helper fn to guard stack ov/flow
           (fn ([f i-th j-th] (rowmat f i-th j-th []))
             ([f i-th j-th row]
              (let [step
                    (fn [fx i j row-col]
                      (cons (fx i j)  (rowmat fx i (inc j) row-col)))]
                (lazy-seq (step f i-th j-th row)))))
           add  ;; body of add row to matrix in helper fn guards stack o/f
           (fn [fx i j mat-rows] ;; calls row maker helper fn
             (cons (rowmat fx i j) (add-rows fx (inc i) j mat-rows)))]
       (lazy-seq (add f i-th j-th matrix))))))

(defn range-start
    "Returns a lazy sequence of numbers that start from x."
    [x]
    (iterate inc x))

(defn __
    ([f] (__ f 0 0))
    ([f m n] (map (fn [i] (map (fn [j] (f i j)) (range-start n))) (range-start m)))
    ([f m n s t] (take s (map (fn [row] (take t row)) (__ f m n)))))

(defn row 
  ([f m] (row f m 0))
  ([f m n] (lazy-seq (cons (f m n) (row f m (inc n)))))
  ([f m n t] (take t (row f m n))))

(defn matrix 
  ([f] (matrix f 0))
  ([f m] (lazy-seq (cons (row f m) (matrix f (inc m)))))
  ([f m n] (lazy-seq (cons (row f m n) (matrix f (inc m) n))))
  ([f m n t] (lazy-seq (cons (row f m n t) (matrix f (inc m) n t))))
  ([f m n s t] (take s (matrix f m n t))))