; file: bingo.scm ; purpose: determine winning bingo cards given a list of numbers called ; and a list of numbers on each card. ; chad c d clark < frink _at_ superfrink _dot_ net > ; date: 08 May 2003 ; changes: ; - 12 may 2003 : Made more efficient by replacing list? calls with pair? . ; This changed some functions from O(n^2) to O(n). ; main() reads the input file from stdin and calls evaluate-cards() on it. (define main (lambda () (evaluate-cards (read)) ) ) ; evaluate-cards() deals with the details of preparing the input, etc. (define evaluate-cards (lambda (ls) ;(display "evaluate-cards called\n") (if (good-input? ls) (begin (analyze-cards (cdr (car ls)) ; numbers (cdr ls) ; card lines ) #t ) (begin (display "The data file is not correctly formated.\n") (display "No analysis could be done.\n") #f ) ) ) ) ; good-input?() returns #f if the input is not in the expected format, ; #t otherwise. (define good-input? (lambda (ls) ;(display "good-input called\n") (cond ((not (number-line? (car ls))) (display "Invalid \"Number\" list.\n") #f ) ((not (card-list? (cdr ls))) (display "Invalid \"Card\" list.\n") #f ) (else #t) ) ) ) ; number-line?() returns #t if the list 'ls' is of the form: ; "Numbers" . ; otherwise #f is returned. (define number-line? (lambda (ls) ;(display "number-line? called\n") (cond ((null? ls) #f) ((not (pair? ls)) #f) ((not (string? (car ls))) #f) ((not (string=? "Numbers" (car ls))) #f) ((not (list-of-numbers? (cdr ls))) #f) (else #t) ) ) ) ; card-list?() returns #t if each item in the list 'ls' is a valid card list, ; #f is returned otherwise. (define card-list? (lambda (ls) ;(display "card-list? called\n") (cond ((null? ls) #t) ((not (pair? ls)) #f) ((not (card-line? (car ls))) #f) (else (card-list? (cdr ls))) ) ) ) ; card-line?() returns #t if the list 'ls' is of the form: ; . ; otherwise #f is returned. (define card-line? (lambda (ls) ;(display "card-line? called\n") (cond ((null? ls) #f) ((not (pair? ls)) #f) ((not (string? (car ls))) #f) ((not (list-of-numbers? (cdr ls))) #f) (else #t) ) ) ) ; list-of-numbers?() returns #t if the list 'ls' is a proper list consisting ; entirely of numbers. (define list-of-numbers? (lambda (ls) (cond ((null? ls) #t) ((not (pair? ls)) #f) ((not (number? (car ls))) #f) (else (list-of-numbers? (cdr ls))) ) ) ) ; the core of the program, analyze-cards() calls for a report of each cards ; remaining numbers to be displayed. (define analyze-cards (lambda (nums cards) (cond ((null? cards) ()) ; all cards done :) (else (card-report (car (car cards)) ; card name (set-less-set (cdr (car cards)) nums) ; numbers on card that have ; not been called yet ) (analyze-cards nums (cdr cards)) ; do next card ) ) ) ) ; set-less-elem() returns a list of all elements in the list 'set' except ; for the element 'elem'. (define set-less-elem (lambda (set elem) (cond ((null? set) ()) ((not (pair? set)) #f) ((= (car set) elem) (set-less-elem (cdr set) elem)) (else (cons (car set) (set-less-elem (cdr set) elem))) ) ) ) ; set-less-set() returns a list of all elements in the list 's1' except ; for the elements in the list 's2'. (define set-less-set (lambda (s1 s2) (cond ((null? s2) s1) ((null? s1) ()) (else (set-less-set (set-less-elem s1 (car s2)) (cdr s2) ) ) ) ) ) ; card-report() prints a summary of a card and it's remaining numbers. (define card-report (lambda (card ls) (display card) (display " has ") (display (length ls)) (display " numbers left: ") (write ls) (display ".\n") ) ) ; i) call main() to start things going: ; (display "Start of Analysis:\n") ; (main) ; (display "End of Analysis:\n") ; ; or ii) call with the input from a certain file: ; (with-input-from-file "in-file" main)