# 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

\$
```