(defun range (start &optional end lst)
  (if (null end) (range 0 start '(0))
    (if (null lst) (range start end (list start))
      (if (= (car (last lst)) end) lst
        (range start end (append lst (list (+ (if (minusp (- start end)) 1 -1) (car (last lst))))))))))

(defun remnum (n lst) (remove-if #'(lambda (x) (eq n x)) lst))

(defun s2- (r p)
  (reduce #'intersection (mapcar #'(lambda (x) (remnum x r)) p)))

(defun s- (r &rest p)
  (reduce #'intersection (mapcar #'(lambda (x) (remnum x r)) (reduce #'union p))))


(defun findall (e l &optional (f ()) (p 0)) ;(elt lst found pos)
  (if (>= p (length l)) f
    (let ((pos (position e l :start p)))
      (findall e l (append f (list pos)) (1+ pos)))))


(defun touchloc (p) ;(found) -> (found-1, found+1)-(-1, len)
  (let ((found (findall (car (last p)) p)))
    (s-
     (append (mapcar #'(lambda (x) (1+ x)) found)
             (mapcar #'(lambda (x) (1- x)) found))
     (list -1 (length p)))))

(defun touch  (&optional (p '(1)))
  (mapcar #'(lambda (x) (elt p x)) (touchloc p)))



(defun pathadd (&optional (p '(1)) (n 4))
  (let ((allowed (s- (range 1 n) (touch p) (last p))))
    (mapcar #'(lambda (x) (append p (list x))) allowed)))

(defun g (&optional (n 4) (p '((1))) (lens ()) (k 1))
  (let ((npath  (mapcar #'(lambda (x) (pathadd x n)) p)))
    (let ((l (remove-duplicates (mapcar #'length npath))))
      (if (equal npath nil) lens
        (if (and (member 0 l) (= k (1+ (/ (* n (1- n)) 2)))) p
          (g n                       ;n
             (reduce #'union npath)  ;p
             (append lens            ;lens = (k l)
                     (list k l))
             (1+ k)))))))            ;k

(defun g1 (&optional (n 4) (p '((1))) (lens ()) (k 0))
  (let ((npath (car (mapcar #'(lambda (x) (pathadd x n)) p))))
    (list npath (remove-duplicates (mapcar #'length npath)))))