CODEWITHSUNDEEP
common-lisp
Johan
Johan

Reputation: 635

Find neighbours in 2d-list, smart way

Let us assume that I have a 2d-list (or array if you so wish) which looks like this:

'( (I I I O)
   (I X I O)
   (I I I O))

And now let us assume that I'd like to find all the neighbours of X. In this case my function would return a list of 8 I:s. How would I go about to implement this function in a smart way? I've already implemented a function which looks like this:

(defun get-neighbours (board x y)
  (let ((output '() ))
    (push (get-if-possible board (1+ x) y) output)
    (push (get-if-possible board (1- x) y) output)
    (push (get-if-possible board x (1+ y)) output)
    (push (get-if-possible board x (1- y)) output)
    (push (get-if-possible board (1+ x) (1+ y)) output)
    (push (get-if-possible board (1- x) (1- y)) output)
    (push (get-if-possible board (1+ x) (1- y)) output)
    (push (get-if-possible board (1- x) (1+ y)) output)
  output))

And that is so... Ugly.

Upvotes: 3

Views: 526

Answers (2)

Rainer Joswig
Rainer Joswig

Reputation: 139261

First, you are still in imperative land.

(defun get-neighbours (board x y)
  (let ((output '() ))
    (push (get-if-possible board (1+ x) y) output)
    (push (get-if-possible board (1- x) y) output)
    (push (get-if-possible board x (1+ y)) output)
    (push (get-if-possible board x (1- y)) output)
    (push (get-if-possible board (1+ x) (1+ y)) output)
    (push (get-if-possible board (1- x) (1- y)) output)
    (push (get-if-possible board (1+ x) (1- y)) output)
    (push (get-if-possible board (1- x) (1+ y)) output)
  output))

You do: variable declaration, bind it to NIL, mutation of the variable, returning the variable.

It is simply:

(defun get-neighbours (board x y)
  (list (get-if-possible board (1+ x) y)
        (get-if-possible board (1- x) y)
        (get-if-possible board x      (1+ y))
        (get-if-possible board x      (1- y))
        (get-if-possible board (1+ x) (1+ y))
        (get-if-possible board (1- x) (1- y))
        (get-if-possible board (1+ x) (1- y))
        (get-if-possible board (1- x) (1+ y))))

You can 'shorten' the code with a local macro:

(defun get-neighbours (board x y)
  (macrolet ((all-possible (&rest x-y-combinations)
               `(list
                 ,@(loop for (a b) on x-y-combinations by #'cddr
                         collect `(get-if-posssible board ,a ,b)))))
    (all-possible (1+ x) y
                  (1- x) y
                  x      (1+ y)
                  x      (1- y)
                  (1+ x) (1+ y)
                  (1- x) (1- y)
                  (1+ x) (1- y)
                  (1- x) (1+ y))))

Now one could abstract it a bit:

(defmacro invoke-fn-on (fn &rest x-y-combinations)
  `(funcall (function ,fn)
            ,@(loop for (a b) on x-y-combinations by #'cddr
                    collect `(get-if-posssible board ,a ,b))))

(defun get-neighbours (board x y)
  (invoke-fn-on list
                (1+ x) y
                (1- x) y
                x      (1+ y)
                x      (1- y)
                (1+ x) (1+ y)
                (1- x) (1- y)
                (1+ x) (1- y)
                (1- x) (1+ y)))

About the LOOP:

> (loop for (a b) on '(1 2 3 4 5 6) by #'cddr collect (list a b))
((1 2) (3 4) (5 6))

ON moves the pattern (a b) over the list (1 2 3 4 5 6). It would give (1 2), (2 3), (3 4), (4 5) and (5 6). With each iteration the list is moved one forward by using CDR to get the rest list. BY now says that we move by two items, by CDDR and not one item as with CDR. So we get three iterations and the pairs (1 2), (3 4) and (5 6).

An alternative would be to slightly simplify the LOOP by introducing a different list structure for the coordinate pairs:

(defmacro invoke-fn-on (fn x-y-combinations)
  `(funcall (function ,fn)
            ,@(loop for (a b) in x-y-combinations
                    collect `(get-if-posssible board ,a ,b))))

(defun get-neighbours (board x y)
  (invoke-fn-on list
                '(((1+ x) y     )
                  ((1- x) y     )
                  (x      (1+ y))
                  (x      (1- y))
                  ((1+ x) (1+ y))
                  ((1- x) (1- y))
                  ((1+ x) (1- y))
                  ((1- x) (1+ y)))))

Upvotes: 2

angus
angus

Reputation: 2367

Have prepared something like this: 

(defconstant +neighbour-offsets+
       '((-1 . -1) (0 . -1) (1 . -1)
         (-1 .  0)          (1 .  0)
         (-1 .  1) (0 .  1) (1 .  1)))

and then your function can be as simple as

(defun get-neighbours (board x y)
  (mapcar (lambda (offs)
            (let ((dx (car offs))
                  (dy (cdr offs)))
              (get-if-possible board (+ x dx) (+ y dy))))
          +neighbour-offsets+))

Upvotes: 4

Related Questions