CODEWITHSUNDEEP
lispcommon-lisp
user3268054
user3268054

Reputation: 121

LISP (Add one to the value in the middle of the list)

I'm currently attempting to create a function that adds 1 to the value that's in the middle of the list.

Example: (add1 '(2 4 6 5 9)) -> (2 4 7 5 9)

Also if the list is even, it returns nothing. So far I have a function that returns the location of the middle of the list.

(defun add1(aList)
               (if (oddp (length aList)) (- (/ (length aList) 2) .5) 'EvenNumber))

Example: (add1 '(2 4 6 5 9)) -> 2.0

Is there a way to use this information to get to the value in the middle then add 1 to it. Thanks

Upvotes: 1

Views: 1095

Answers (4)

Pankaj Sejwal
Pankaj Sejwal

Reputation: 1595

I expect that you are looking for a recursive version,

(defun middle (lis)
 (let ((lis (c-in-place lis)))
  (cond ((null lis) nil) ((atom lis) lis)
   (t
    (mapcar
     #'(lambda (x)
        (cond ((atom x) x) (t (mapcar #'c-in-place (c-in-place x)))))
     lis)))))


(defun c-in-place (lis)
 (cond
  ((and (listp lis) (oddp (length lis)) (> (length lis) 2))
   (let ((pos (1+ (floor (/ (length lis) 2)))))
    (in-place (1+ (nth (floor (/ (length lis) 2)) lis)) pos lis)))
  (t lis)))

(defun in-place (nxt n lis)
 (let (temp temp1) (setf temp (subseq lis 0 (- n 1)))
  (setf temp1 (subseq lis n)) (setf temp (append temp (append `(,nxt) temp1)))
  temp))

Usage:

  1. (middle '((1 4 6 7 8) (3 4 2))) =>((1 4 7 7 8) (3 5 2))
  2. (middle '((1 4 6 7) (3 4 2))) => ((1 4 6 7) (3 5 2))
  3. (middle '(2 3 4)) => (2 4 4)
  4. (middle '(2 3 4 5) => (2 3 4 5)

Upvotes: 0

Kaz
Kaz

Reputation: 58560

Here is a function which makes only two passes through the list rather than modifying the original, and doesn't perform any arithmetic with integers:

(defun inc-middle-elt (list)
  (loop for elem in list
        for pair = list then (cddr pair)
        with flag = t
        when (and flag (null (cddr pair))) do
          (if (null (cdr pair))
            (incf elem))
          (setf flag nil)
        collect elem))

For finding the middle, this uses a similar trick to what is used in implementations of the binary merge sort for linked lists: an auxiliary pointer pair walks through the list at double stride, stepping over pairs.

We are at the last pair when (cddr pair) is nil. At that point, a decision must be made: does the list have an odd number of items or not? If the list has an odd number of items, then at the last pair position, where (cddr pair) is nil, only one element remains: (cdr pair) is also nil.

Exercise: optimize this function by taking advantage of the fact that the elements after the middle of the list need not be copied; the output list can share the tail portion of the input list. Also, change the function so that when it is clear there is no middle element, it returns the original list.

Upvotes: 1

sds
sds

Reputation: 60004

Here you go:

(defun add-1 (list)
  (let ((len (length list)))
    (assert (oddp len) (list))
    (incf (nth (/ (1- len) 2) list))))

Replace assert with a when if you do not want an error on even-length lists.

Upvotes: 1

brian_o
brian_o

Reputation: 492

Try something like this.

(defun add1 (lst)
  (when (oddp (length lst))
    (incf (nth (floor (/ (length lst) 2)) lst)))
  lst)

I think the missing piece you need is setf (you've probably already used it, but perhaps you didn't know you could use a form for the first argument) or in this case incf (increments by one or an optional specified delta). They allow you to use an expression to get the value that needs to be set.

Some things to think about (as written):

  • This is a destructive update
  • It calls length multiple times on the same list. This could be expensive.
  • As I have written it, even-length lists just return the list unchanged. This is not exactly what you asked for, but perhaps what you wanted.
  • I used floor instead of messing around with subtracting .5, which would necessitate some additional casting.

Upvotes: 0

Related Questions