; find the missing number

(define (next str)
  (number->string (+ (string->number str) 1)))

(define (missing-from start rest)
  (let ((len (string-length rest)))
    (if (zero? len) -1
      (let* ((n (next start))
             (n-len (string-length n)))
        (if (and (<= n-len len)
                 (string=? n (substring rest 0 n-len)))
            (missing-from n (substring rest n-len len))
            (let* ((n1 (next n)) (n1-len (string-length n1)))
              (if (none-missing n1 (substring rest n1-len len))
                (string->number n) -1)))))))

(define (none-missing start rest)
  (let ((len (string-length rest)))
    (or (zero? len)
        (let* ((n (next start)) (n-len (string-length n)))
          (and (<= n-len len)
               (string=? n (substring rest 0 n-len))
               (none-missing n (substring rest n-len len)))))))

(define (missing-number str)
  (let ((len (string-length str)))
    (let loop ((m 1))
      (let* ((left (substring str 0 m))
             (right (substring str m len))
             (n (missing-from left right)))
        (if (negative? n) (loop (+ m 1)) n)))))

(display (missing-number "12346789")) (newline)
(display (missing-number "26272829313233")) (newline)
(display (missing-number "9293949596979899101")) (newline)
(display (missing-number "9294959697")) (newline)
(display (missing-number "99101102103104105")) (newline)
(display (missing-number "596597598600601602")) (newline)
(display (missing-number "989999009901990299049905")) (newline)
(display (missing-number "98999901990299039904")) (newline)
(display (missing-number "9998999910000100011000210004")) (newline)
(display (missing-number "9899101102")) (newline)