Skip to content

Instantly share code, notes, and snippets.

@Jach
Created February 16, 2022 07:17
Show Gist options
  • Save Jach/834f1020ae932b0395fdfdf0bd9dcea3 to your computer and use it in GitHub Desktop.
Save Jach/834f1020ae932b0395fdfdf0bd9dcea3 to your computer and use it in GitHub Desktop.
I hate it...
(defstruct cell
color
value
i
j)
(defun create-cells (matrix)
(let ((cells (list))
(color :white))
(loop for i below (array-dimension matrix 0) do
(loop for j below (array-dimension matrix 1) do
(push (make-cell :color color :value (aref matrix i j) :i i :j j)
cells)
(setf color (if (eql color :white) :black :white)))
(if (evenp (array-dimension matrix 1))
(setf color (if (eql color :white) :black :white))))
cells))
(defun handle-tie (cell1 cell2)
(if (> (cell-value cell1) (cell-value cell2)) ; not actually tie
nil
(let ((row1 (cell-i cell1))
(row2 (cell-i cell2)))
(if (< row1 row2)
T
(if (> row1 row2)
nil
(let ((col1 (cell-j cell1))
(col2 (cell-j cell2)))
(< col1 col2)))))))
(defun sort-fn (cell1 cell2)
(if (< (cell-value cell1) (cell-value cell2))
T
(handle-tie cell1 cell2)))
(defun smallest-nth-cell (cells n color)
(let* ((colored-only (remove-if-not (lambda (cell) (eql (cell-color cell) color))
cells))
(sorted (sort colored-only #'sort-fn)))
(nth n sorted)))
(defun solution (matrix queries)
(let ((cells (create-cells matrix)))
(dolist (query queries)
(let* ((ith-smallest (smallest-nth-cell cells (first query) :black))
(jth-smallest (smallest-nth-cell cells (second query) :white))
(average (/ (+ (cell-value ith-smallest) (cell-value jth-smallest)) 2)))
(if (integerp average)
(setf (aref matrix (cell-i ith-smallest) (cell-j ith-smallest)) average
(aref matrix (cell-i jth-smallest) (cell-j jth-smallest)) average)
(let* ((lesser-greater (list ith-smallest jth-smallest))
(lesser-greater (sort lesser-greater #'sort-fn))
(lesser (first lesser-greater))
(greater (second lesser-greater)))
(setf (aref matrix (cell-i greater) (cell-j greater)) (ceiling average)
(aref matrix (cell-i lesser) (cell-j lesser)) (floor average))))
(setf cells (create-cells matrix))))
matrix))
(equalp
(solution #2A((2 0 4)
(2 8 5)
(6 0 9)
(2 7 10)
(4 3 4))
'((0 0) (1 3)))
#2A((1 2 4)
(2 8 5)
(6 0 9)
(2 7 10)
(4 3 3)))
(equalp
(solution #2A((1 9 10 8)
(3 4 4 4))
'((2 3) (3 2)))
#2A((1 9 9 7)
(3 4 4 6)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment