(defun sequence-type (seq)
  (etypecase seq
    (list 'list)
    (string 'string)
    (bit-vector 'bit-vector)
    (vector 'vector)))

(defun insert-between (s fn)
  (if (<= (length s) 1)
      s
      (loop with result-type = (sequence-type s)
            for i from 0 below (length s)
            for a = (elt s i)
            for b = (ignore-errors (elt s (1+ i)))
            for (c insert-p) = (when b (multiple-value-list (funcall fn a b)))
            if (or c insert-p)
              collect (concatenate result-type (list a) c)
                into result
            else
              collect (concatenate result-type (list a))
                into result
            finally (return (apply #'concatenate result-type result)))))


(defun odai-22-594-aux (a b)
  (let* ((a (digit-char-p a 10))
         (b (digit-char-p b 10))
         (c (format nil "~D" (+ a b))))
    (if (= (length c) 1)
        c
        (format nil "~A~A~A"
                (char c 0)
                (odai-22-594-aux (char c 0) (char c 1))
                (char c 1)))))

(defun odai-22-594 (s n m)
  (insert-between s (lambda (a b)
                      (when (and (char= n a)
                                 (char= m b))
                        (values (odai-22-594-aux a b) t)))))

(defun odai-22-608 (s)
  (insert-between s (lambda (a b)
                      (when (and (char= a b)
                                 (upper-case-p a)
                                 (upper-case-p b))
                        (values (concatenate 'string (list (char-downcase a))) t)))))



(loop for (args expected) in '((("123456789" #\3 #\4) "1237456789")
                               (("123456789" #\6 #\7) "123456143789")
                               (("3141592653589793238462643383279502884197169399375105820974944" #\9 #\7)
                                "3141592653589176793238462643383279502884191767169399375105820917674944")
                               (("111" #\1 #\1) "12121")
                               (("11" #\1 #\1) "121")
                               (("1" #\1 #\1) "1")
                               (("" #\1 #\1) ""))
      for result = (apply #'odai-22-594 args)
      do (format t "~:[❌~;✓~] ~{~A~^ ~} → ~A~%"
                 (equal result expected) args result))
(terpri)
(loop for (args expected) in '((("abcDDefGG") "abcDdDefGgG")
                               (("abcDDDfGG") "abcDdDdDfGgG"))
      for result = (apply #'odai-22-608 args)
      do (format t "~:[❌~;✓~] ~{~A~^ ~} → ~A~%"
                 (equal result expected) args result))