Finding the Max element in a 2d array in LISP

Question

So, I wrote the following program to determine the max element in a 2D array using LISP. Note, this is my first time using the language, so I am unfamiliar with many aspects.

The function should return the coordinates of the largest element in row-major order. In the below example, the largest element, 7, is found at index (2, 4). However, when the program is executed, it returns (3, 15).

It seems to be starting the index at 1, rather than 0, for the row. Additionally, it seems to be counting all indexes up to 15, where the max element is found. I am unsure how to fix this issue.

(defun find-max-location (x)
  (let (
      (maxval -100)
      (loc nil)
      (cur 0)
      (cur2 0)
      (k 1)
      (l 1)
      (f 0))
    (loop for i in x do
          (loop for j in i do
                (if (> j maxval)
                    (progn
                      (setf cur k)
                      (setf cur2 l)
                      (setf maxval j))
                  )
                (setf l (+ l 1))
                )
          (setf k (+ k 1))
          )
    (list cur cur2)))

(find-max-location '((0 1 0 0 1) (0 2 2 0 0) (3 0 1 4 7) (0 1 2 0 0) (1 2 1 0 3)))

Answer 1

It seems that you're thinking about this in a very procedural manner. Recursion is your friend here.

How would we find the max and its position in a simple list? We'd recursively count up from 0, evaluating each element to see if it's greater than the current max or if max hasn't yet been set. We'd use the max parameter to the function to update this information. Hitting the end of the list we'd return the max.

(defun find-max-in-row (lst &optional (pos 0) (max '()))
    (cond ((null lst) 
           max)
          (or (null max) (> (car lst) (car max))
           (find-max-in-row (cdr lst) (1+ pos) (list (car lst) pos)))
          (t 
           (find-max-in-row (cdr lst) (1+ pos) max))))

(defvar foo '(1 6 8 2 7))

(format t "~a~%" (find-max-in-row foo))

Prints:

(8 2)

This logic can be adapted to find the column where a max value occurs. A starting point would be to map this function to your list of rows.

(format t "~a~%" 
     (mapcar #'find-max-in-row 
             '((0 1 0 0 1) 
               (0 2 2 0 0) 
               (3 0 1 4 7) 
               (0 1 2 0 0) 
               (1 2 1 0 3))))

Prints:

((1 1) (2 1) (7 4) (2 2) (3 4))

Answer 2

The error is very simple: you don't reinitialize tha value of l each time the inner iteration is started. For the indexes, instead, if you want to start from 0, then you should initialize them with 0, and not with 1. Here is a rewriting of the code, in which I have removed the unused variables loc and f, used when instead of the one-branch if, and used a more conventional way of writing in Common Lisp:

(defun find-max-location (x)
  (let ((maxval -100)
        (cur 0)
        (cur2 0)
        (k 0)
        l)
     (loop for i in x
           do (setf l 0)
              (loop for j in i         
                    do (when (> j maxval)
                         (setf cur k)
                         (setf cur2 l)
                         (setf maxval j))
                       (setf l (+ l 1)))
              (setf k (+ k 1)))   
     (list cur cur2)))

(find-max-location '((0 1 0 0 1) (0 2 2 0 0) (3 0 1 4 7) (0 1 2 0 0) (1 2 1 0 3)))   ; => (2 4)

Note that setf can perform multiple assignments, so the code can be simplified as:

(defun find-max-location (x)
  (let ((maxval -100)
        (cur 0)
        (cur2 0)
        (k 0)
        l)
    (loop for i in x
          do (setf l 0)
             (loop for j in i          
                   do (when (> j maxval)
                        (setf cur k
                              cur2 l
                              maxval j))
                      (setf l (+ l 1)))
             (setf k (+ k 1)))    
     (list cur cur2))

Finally, there are very convenient mechanisms in loop that allow the initialization of variables (with) and the looping of variables “in parallel” with the iteration variables. So here is the final iterative version of the function (with the use of when as loop keyword):

(defun find-max-location (x)
  (loop with maxval = -100
        and cur = 0
        and cur2 = 0
        for i in x
        for k from 0
        do (loop for j in i
                 for l from 0
             when (> j maxval)
               do (setf cur k
                        cur2 l
                        maxval j))
        finally (return (list cur cur2))))

A very good starting point to master the complexity of loop is the chapter “Loop for Black Belts" of the free book “Practical Common Lisp”. Another excellent resource to learn Common Lisp is the “Common Lisp Cookbook”.

Finally, it is worth to note that Common Lisp has arrays, including 2D arrays, so that you can represent them directly, instead that with lists of lists, as in your example.

Answer 3

I would loop in a nested way through the list-of-list (lol) and setf the values when bigger than current max-val:

(defun find-max-location (lol)
  "Find max element's coordinate in a lol"
  (let ((max-val (caar lol))
        (max-coord '(0 . 0))) ;; start with first element
    (loop for il in lol
          for i from 0
          do (loop for e in il
                   for j from 0
                   when (> e max-val)
                     do (setf max-val e
                              max-coord (cons i j))))
    (values max-coord max-val)))

This function can handle irregular list-of-lists.

Using values, you can decide whether just to use only the coordinates or to also capture the max-value itself.

;; usage:

(find-max-location '((0 1 9) (4 9) (6 7 8)))
;; => (0 . 2)
;; => 9

;; capture max-val too:
(multiple-value-bind (coord val) (find-max-location '((0 1 9) (4 9) (6 7 8)))
  (list val (car coord) (cdr coord)))
;; => (9 0 2)

;; or destructure coord:
(multiple-value-bind (coord val) (find-max-location '((0 1 9) (4 5) (6 7 8)))
  (destructuring-bind (x . y) coord
    (list val x y)))

The first max-val is the very first element in this list-of-list.

Answer 4

Here is another answer that defines a higher-order function indexed-list-fold, similar to folding functions like reduce or fold_left in other functional languages.

It's purpose is to take a function that works on a accumulator, and element and its index, to produce the next value for the accumulator. I define it as follows, with loop:

(defun indexed-list-fold (function accumulator list)
  (loop
    :for acc = accumulator :then res
    :for elt :in list
    :for idx :from 0
    :for res = (funcall function acc elt idx)
    :finally (return acc)))

Notice the use of for/then construct and how the order of the clauses matter: for elt in list may interrupt the iteration when reaching the end of the list, so it is important that acc is computed first. This is especially important if the list is empty initially, otherwise its value would be always nil and not accumulator.

Let's write a function that finds the maximum value and its location, in a list:

(defun find-max-location-in-list (list)
  (flet ((fold (max.pos elt idx)
           (let ((max (car max.pos)))
             (if (or (null max) (< max elt))
                 (cons elt idx)
                 max.pos))))
    (indexed-list-fold #'fold (cons nil nil) list)))

For example:

> (find-max-location-in-list '(1 3 8 3 12 -4 -200))
(12 . 4)

The maximum value is 12 at position 4.

In order to generalize this to a list of lists (a tree), the fold function must be able to reference itself in a recursive call to indexed-list-fold, so it is now declared with labels:

(defun find-max-location-in-tree (tree)
  (labels ((fold (max.pos elt idx)
             (let ((idx (alexandria:ensure-list idx)))
               (etypecase elt
                 (real (let ((max (car max.pos)))
                         (if (or (null max) (< max elt))
                             (cons elt idx)
                             max.pos)))
                 (list 
                  (indexed-list-fold (lambda (max.pos elt child)
                                       (fold max.pos elt (cons child idx)))
                                     max.pos
                                     elt))))))
    (indexed-list-fold #'fold (cons nil nil) tree)))

The logic is the same as before, except that elt may now be a list itself, and idx is a stack of indices. For example:

> (find-max-location-in-tree '(1 3 8 3 12 -4 -200))
(12 4)

Notice how the cdr of the result is a list. For the example you provided:

> (find-max-location-in-tree '((0 1 0 0 1)
                               (0 2 2 0 0)
                               (3 0 1 4 7)
                               (0 1 2 0 0)
                               (1 2 1 0 3)))
(7 4 2)

The maximum value is 7 at index 4 of the list at index 2.