C.scm

;; Problem

;; Little John likes palindromes, and thinks them to be fair (which is
;; a fancy word for nice). A palindrome is just a number that reads
;; the same backwards and forwards - so 6, 11 and 121 are all
;; palindromes, while 12, 223 and 2244 are not.

;; He recently became interested in squares as well, and formed the
;; definition of a fair and square number - it is a number that is a
;; palindrome and a square of a palindrome at the same time. For
;; instance, 1, 9 and 121 are fair and square (being palindromes and
;; squares, respectively, of 1, 3 and 11), while 16, 22 and 676 are
;; not fair and square - the first is not a palindrome, the second is
;; not a square, and the third is a square, but not a square of a
;; palindrome.

;; Now he wants to search for bigger fair and square numbers. Your
;; task is, given an interval Little John is searching through, to
;; tell him how many fair and square numbers are there in the
;; interval, so he knows when he has found them all.

;; Solving this problem

;; Usually, Google Code Jam problems have 1 Small input and 1 Large
;; input. This problem has 1 Small input and 2 Large inputs. Once you
;; have solved the Small input, you will be able to download any of
;; the two Large inputs. As usual, you will be able to retry the Small
;; input (with a time penalty), while you will get only one chance at
;; each of the Large inputs.

;; Input

;; The first line of the input gives the number of test cases, T. T
;; lines follow. Each line contains two numbers, A and B - the
;; endpoints of the interval Little John is looking at.

;; Output

;; For each test case, output one line containing "Case #x: y", where
;; x is the case number (starting from 1) and y is the number of fair
;; and square numbers greater or equal to A and smaller or equal than
;; B.

(use-modules (ice-9 rdelim))

(define fair-and-squares
  (let ()
    (define (palindrome-string? s)
      (let loop ((i 0) (j (- (string-length s) 1)))
        (cond ((< j i) #t)
              ((eqv? (string-ref s i) (string-ref s j))
               (loop (+ i 1) (- j 1)))
              (else #f))))

    (define (palindrome-number? s)
      (palindrome-string? (number->string s)))
    (define fair-square-table
      (let ((h (make-hash-table))
            (first-ten '(1 4 9 121))) ; 484 10201 12321 14641 40804 44944
        (for-each (lambda (n)
                    (hashv-set! h n #t))
                  first-ten)
        h))

    (define palindrome-table
      (let ((h (make-hash-table))
            (first-ten '(1 2 3 4 5 6 7 8 9 11 22 33 44
                           55 66 77 88 99 101 111 121)))
        (for-each (lambda (n)
                    (hashv-set! h n #t))
                  first-ten)
        h))
    (define max-fair-and-square 121)    ;44944
    (define last-index 11)

    (define (num-between l u)
      (hash-count (lambda (k v)
                    (<= l k u))
                  fair-square-table))
    (lambda (lower upper)
      (define (fair-and-square? n)
        (hashv-ref fair-square-table n #f))
      (define (palindrome? x)
        (hashv-ref palindrome-table x #f))
      (define (compute-more-fair-and-squares start upper)
        (let loop ((i (+ 1 start)))
          (let ((next-square (* i i)))
            (when (palindrome-number? next-square)
              (hashv-set! palindrome-table next-square #t)
              (when (palindrome? i)
                (set! max-fair-and-square next-square)
                (hashv-set! fair-square-table next-square #t)))
            (if (> next-square upper)
                (set! last-index i)
                (loop (+ i 1))))))
      (when (< (* last-index last-index) upper)
        (compute-more-fair-and-squares last-index upper))
      (num-between lower upper))))

(define (main port)
  (define n (string->number (read-line port)))
  (do ((i 0 (+ i 1)))
      ((= i n))
    (let* ((line (read-line port))
           (nums (map string->number (string-split line #\space))))
      (format #t "Case #~a: ~a~%" (+ 1 i) (apply fair-and-squares nums)))))

(define file (let ((cmd (command-line)))
               (if (pair? (cdr cmd))
                   (cadr cmd)
                   "C-sample-input.txt")))

(call-with-input-file file main)