https://bgm.tv/group/topic/350078

remove-palindrome.rkt

#lang racket
(define (remove-palindrome s)
  (define f
    (cachedproc
     (lambda (i j)
       (cond
         [(equal? i j) 1]
         [(equal? (+ i 1) j) 1]
         ;[(and (equal? (+ i 2) j) (equal? (list-ref s i) (list-ref s (- j 1)))) 1]
         [(equal? (list-ref s i) (list-ref s (- j 1))) (f (+ i 1) (- j 1))]
         [else (apply min (map (lambda (k) (+ (f i k) (f k j))) (range (+ i 1) j)))]))))
  (if (null? s)
      0
      (f 0 (length s))))

(define (cachedproc func)
  (let ([h (make-hash)])
    (define (wrapped . w)
      (hash-ref! h w (lambda () (apply func w))))
    wrapped))

(remove-palindrome (list 1 2 3 1 2 1)) ; #1 => 2
(remove-palindrome (string->list "123456789123456789123456789")) ; #2-1 => 23 ;; why this? (bgm38)
(remove-palindrome (string->list "aaabaaaaaaaaaaaaaaaa")) ; #4-2 => 2
(remove-palindrome (string->list "abacadaeafag")) ; #7-3 => 6
(remove-palindrome (string->list "abcdefgfedcba")) ; #7-9 => 1
(remove-palindrome (string->list "45541234554")) ; #8 => 2
(remove-palindrome (string->list "abeca")) ; #12-5 => 3
(remove-palindrome (string->list "")) ; => 0
(remove-palindrome (string->list "a")) ; => 1