# rotated palindromes

Write a predicate that determines if a circular sequence is a palindrome

``` \$ cat rp.rkt
#lang racket

(define (rotpal v)

; Return true iff the given vector contains a palindrome starting at
; some index.

(define N (vector-length v))

(define half-size (floor (/ N 2)))

(define (elements-match i j)

; Return true iff the elements at the given indices are equal.

(let ((f (lambda (i) (modulo i N))))
(= (vector-ref v (f i)) (vector-ref v (f j)))))

(define (check-halves fst lst)

; Return true iff v[fst..fst + half-size) equals
; v (lst - half-size..lst].

(let loop ((f fst) (l lst) (n half-size))
(cond
((< n 0)
#t)

((elements-match f l)
(loop (+ f 1) (- l 1) (- n 1)))

(#t
#f))))

(if (< N 2)
#t
(call/cc
(lambda (k)
(if (odd? N)
(do ((i 0 (+ i 1))) ((>= i N) #f)
(when (check-halves (+ i 1) (- i 1))
(k #t)))
(do ((i 0 (+ i 1))) ((>= i half-size) #f)
(when (check-halves i (- i 1))
(k #t))))))))

(require
rackunit
math/number-theory
(except-in "utl.rkt" fibonacci))

(define unpal (lambda (v) (not (rotpal v))))

(check-pred rotpal #(0 1 1))
(check-pred rotpal #(1 1 0 0))
(check-pred rotpal #(0 1 2 3 4 3 2 1 0))
(check-pred rotpal #(3 4 3 2 1 0 0 1 2))
(check-pred unpal #(0 1 2))
(check-pred unpal #(0 1 0 1))

(define (check-permutations l expected)

; Count all the palindromes in the given list and check if the count
; equals the given value.

(let

((cnt 0))

(call-with-vector-permutations (list->vector l)
(lambda (v)
(when (rotpal v)
(set! cnt (+ cnt 1)))))
(check-eq? cnt expected)))

(define (check-odd-permutations n)

; Count permutations in sequences of length 2n + 1.

(check-permutations
(cons -1 (append (range n) (range n)))

; The -1 palindrome hinge can appear in 2n + 1 positions.  There
; are n!  palindrome halves.  By distinguishing the same digit in
; both ranges (by a subscript or being different colors, for
; example), each palindrome half appears in 2^n variations (all
; digits from the left range, the first digit from the right range
; and all the rest from the left range, and so on).

(* (+ (* 2 n) 1) (factorial n) (expt 2 n))))

(define (check-even-permutations n)

; Count permutations in sequences of length 2n.

(check-permutations
(append (range n) (range n))

; There are n! palindrome halves.  As above, with distinguished
; digits each palindrome half appears in 2^n variations.  A
; palindrome half can start at any of n positions.

(* (factorial n) (expt 2 n) n)))

(define max 4)

(for-each
(lambda (n)
(check-odd-permutations n)
(check-even-permutations n))
(range 1 max))

\$ mzscheme rp.rkt

\$
```