; google code jam qualification round africa 2010
(define (store-credit c l)
(define (s i j)
(+ (vector-ref l i)
(vector-ref l j)))
(let ((len (vector-length l)))
(let loop ((i 0) (j 1))
(cond ((= i len) #f)
((= j len) (loop (+ i 1) (+ i 2)))
((= (s i j) c) (list (+ i 1) (+ j 1)))
(else (loop i (+ j 1)))))))
(display (store-credit 100 #(5 75 25))) (newline)
(display (store-credit 200 #(150 24 79 50 88 345 3))) (newline)
(display (store-credit 8 #(2 1 9 4 4 56 90 3))) (newline)
(define (string-split sep str)
(define (f cs xs) (cons (list->string (reverse cs)) xs))
(let loop ((ss (string->list str)) (cs '()) (xs '()))
(cond ((null? ss) (reverse (if (null? cs) xs (f cs xs))))
((char=? (car ss) sep) (loop (cdr ss) '() (f cs xs)))
(else (loop (cdr ss) (cons (car ss) cs) xs)))))
(define (string-join sep ss)
(define (f s ss)
(string-append s (string sep) ss))
(define (join ss)
(if (null? (cdr ss)) (car ss)
(f (car ss) (join (cdr ss)))))
(if (null? ss) "" (join ss)))
(define (reverse-words str)
(string-join #\space
(reverse
(string-split #\space str))))
(display (reverse-words "this is a test")) (newline)
(display (reverse-words "foobar")) (newline)
(display (reverse-words "all your base")) (newline)
(define (t9-spelling str)
(define (letter c) (- (char->integer c) 97))
(let ((letters #("2" "22" "222" "3" "33" "333"
"4" "44" "444" "5" "55" "555" "6" "66"
"666" "7" "77" "777" "7777" "8" "88"
"888" "9" "99" "999" "9999")))
(let loop ((ss (string->list str)) (prev "0") (cs '()))
(cond ((null? ss) (apply string-append (reverse cs)))
((char-whitespace? (car ss))
(loop (cdr ss) "0" (cons "0" cs)))
((string=? (substring prev 0 1)
(substring (vector-ref letters (letter (car ss))) 0 1))
(loop ss "0" (cons " " cs)))
(else (let ((next (vector-ref letters (letter (car ss)))))
(loop (cdr ss) next (cons next cs))))))))
(display (t9-spelling "hi")) (newline)
(display (t9-spelling "yes")) (newline)
(display (t9-spelling "foo bar")) (newline)
(display (t9-spelling "hello world")) (newline)