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 $