number sequence gap


Given a digit string interpreted as a contiguous sequence of numbers with a number missing, find the missing number.

This code isn't correct because the largest number size is five digits, but split-to-numbers might bump the digit count to six when parsing the digit string. I like to think of the code as solving a slightly more general problem.

 $ cat fmn.scm  
 #lang racket 
  
 (require srfi/1 srfi/9 rackunit) 
  
 (define (deltas numbers) 
    
   ; Return a list of numbers representing the deltas between 
   ; successive numbers in the given list. 
  
   (if (null? numbers) 
     numbers 
     (map 
       (lambda (p) (- (cadr p) (car p))) 
       (zip numbers (cdr numbers))))) 
  
  
 (define (find-missing-number digits) 
    
   ; Return the number missing from the given sequence or -1 if 
   ; the number can't be found. 
    
   (let loop ((i 1)) 
     (if (> i 5) 
         -1 
         (let* ((numbers (split-to-numbers i digits)) 
                (n (valid-deltas (deltas numbers)))) 
           (if (> n -1) 
               (+ (car numbers) n 1) 
               (loop (+ 1 i))))))) 
  
  
 (define (new-number d-cnt digits) 
    
   ; Return the left-most d-cnt-digit number found in digits. 
    
   (define-record-type  
      
     number 
     (make-number nbr-d-cnt nbr-start nbr-n) 
     number? 
      
     (nbr-d-cnt nbr-d-cnt) 
     (nbr-start nbr-start) 
     (nbr-n nbr-n)) 
  
   (define s-len (string-length digits)) 
    
   (define (peel-next-number start d-cnt) 
     (string->number 
       (substring digits start (min (+ start d-cnt) s-len)))) 
    
   (define (newnumber nbr) 
     (lambda (cmd . args) 
       (cond 
          
         ; Return true iff there's more numbers to peel from the 
           digit string. 
          
         ((eq? cmd 'more) 
          (< (+ (nbr-start nbr) (nbr-d-cnt nbr)) s-len)) 
          
  
         ; Return the next number available in the digit string; 
         ; assume one exists.  The length of the new number in 
         ; digits is the length of this number plus the argument 
          
         ((eq? cmd 'next) 
          (let* ((new-d-cnt (+ (nbr-d-cnt nbr) (car args))) 
                 (new-start (+ (nbr-start nbr) (nbr-d-cnt nbr)))) 
            (newnumber 
              (make-number new-d-cnt new-start 
                (peel-next-number new-start new-d-cnt))))) 
  
  
         ; Return the number peeled from the digit string. 
          
         ((eq? cmd 'number) 
          (nbr-n nbr)) 
          
  
         ; Return true iff the difference between this number and 
         ; the argument number one or two. 
          
         ((eq? cmd 'valid-delta) 
          (let ((d (- (apply (car args) 'number '()) (nbr-n nbr)))) 
            (and (<= 1 d) (<= d 2)))) 
          
         (#t 
          (error "unexpected number command:  " cmd))))) 
    
   (newnumber (make-number d-cnt 0 (peel-next-number 0 d-cnt)))) 
  
  
 (define (split-to-numbers i digits) 
    
   ; Split the digit string digits into a sequence of i-character 
   ; substrings return the sequence as a list of numbers.  The 
   ; last number in the list may not have i digits if i doesn't 
   ; divide the length of digits in characters. 
    
   (let loop ((nbr (new-number i digits)) (n-lst '())) 
     (if (nbr 'more) 
       (let ((new-nbr (nbr 'next 0))) 
         (if (nbr 'valid-delta new-nbr) 
           (loop new-nbr (cons nbr n-lst)) 
           (let ((new-nbr (nbr 'next 1))) 
             (if (nbr 'valid-delta new-nbr) 
                 (loop new-nbr (cons nbr n-lst)) 
                 '())))) 
       (map (lambda (n) (n 'number)) (reverse (cons nbr n-lst)))))) 
      
            
 (define (valid-deltas deltas) 
    
   ; If the given list is a valid delta sequence return the length 
   ; of the prefix; otherwise return -1. 
    
   ; A delta sequence is valid if it contains exactly one 2 and 
   ; every other element is 1.  The delta-sequence prefix runs 
   ; upto but does not include the 2. 
    
   (let loop ((p-len 0) (dtas deltas)) 
     (if (null? dtas) 
       -1 
       (let ((delta (car dtas))) 
      (cond 
     ((= delta 1) 
      (loop (+ p-len 1) (cdr dtas))) 
          ((= delta 2) 
      (if (find (lambda (d) (not (= 1 d))) (cdr dtas)) 
           -1 
       p-len)) 
       (#t 
       -1)))))) 
  
  
 (let* ((n1 (new-number 1 "12")) 
        (n2 (n1 'next 0))) 
    
   (check-eq? (n1 'more) #t) 
   (check-eq? (n2 'more) #f) 
   (check-eq? (n1 'valid-delta n2) #t) 
   (check-eq? (n2 'valid-delta n1) #f) 
   (check-eq? (n1 'number) 1) 
   (check-eq? (n2 'number) 2) 
   ) 
  
  
 (check-eq? (find-missing-number "134567") 2) 
 (check-eq? (find-missing-number "124567") 3) 
 (check-eq? (find-missing-number "123567") 4) 
 (check-eq? (find-missing-number "123467") 5) 
 (check-eq? (find-missing-number "123457") 6) 
  
 (check-eq? (find-missing-number "212223252627") 24) 
 (check-eq? (find-missing-number "321322323325326327") 324) 
 (check-eq? (find-missing-number "432143224323432543264327") 4324) 
 (check-eq? (find-missing-number "543215432254323543255432654327") 54324) 
  
 (check-eq? (find-missing-number "26272829313233") 30) 
 (check-eq? (find-missing-number "9293949596979899101") 100) 
 (check-eq? (find-missing-number "9294959697") 93) 
 (check-eq? (find-missing-number "99101102103104105") 100) 
 (check-eq? (find-missing-number "596597598600601602") 599) 
 (check-eq? (find-missing-number "989999009901990299049905") 9903) 
 (check-eq? (find-missing-number "98999901990299039904") 9900) 
 (check-eq? (find-missing-number "9998999910000100011000210004") 10003) 
 (check-eq? (find-missing-number "9899101102") 100) 
  
 $ mzscheme fmn.scm  
  
 $