Aqui vai um problema de programação simples, porém interessante, originalmente proposto por Mattox Beckman. Depois de ver a abordagem de Tejas Dinkar para este problema usando Haskell, decidi tentar com Clojure.

Citação

Você é Hércules, prestes a lutar contra a temida Hydra. A Hydra tem 9 cabeças. Quando uma cabeça é cortada, ela gera 8 cabeças novas. Quando uma dessas 8 cabeças é cortada, cada uma gera 7 cabeças novas. Cortar uma dessas gera 6 cabeças novas, e assim por diante até que a cabeça mais fraca da hidra não gerará mais nenhuma cabeça nova.

Nosso trabalho é descobrir quantos cortes Hércules precisa dar para matar todas as cabeças da Hydra. E não, não é n!.

Podemos começar definindo uma função que retorna uma Hydra de n cabeças.

1
2
3
4
5
6
7

(defn new-hydra
  "Returns a Hydra with n heads."
  [n]
  (repeat n n))

(new-hydra 3)
;; => (3 3 3)

Para facilitar a comparação entre ambas as soluções, a estrutura de dados que estou usando aqui é a mesma usada por Dinkar: uma lista. Nesta lista, cada número representa uma cabeça viva e seu nível de força.

Agora, de acordo com a descrição do problema, quando Hércules corta uma cabeça de nível 3, a Hydra cresce duas cabeças de nível 2.

1
2

(chop-head (new-hydra 3))
;; => (2 2 3 3)

Aqui está uma possível implementação para tal função.

1
2
3
4
5
6

(defn chop-head
  "Returns a new Hydra after chop off its first head."
  [hydra]
  (let [head (first hydra)]
    (into (rest hydra)
          (new-hydra (dec head)))))

Este código deve fazer sentido mesmo se você não estiver familiarizado com Clojure.

O que acontece se Hércules tentar cortar a cabeça de uma Hydra sem cabeças?

A maioria das linguagens de programação funcional que conheço são construídas sobre um forte princípio chamado propriedade de fechamento.

Citação

Em geral, uma operação para combinar objetos de dados satisfaz a propriedade de fechamento se os resultados de combinar coisas com essa operação podem eles mesmos ser combinados usando a mesma operação. Fechamento é a chave para o poder em qualquer meio de combinação porque permite criar estruturas hierárquicas – estruturas compostas de partes, que elas mesmas são compostas de partes, e assim por diante.

– Gerald Jay Sussman, Hal Abelson

Para ilustrar este conceito com código, vamos considerar a função cons do Clojure.

1
2
3
4
5

(cons 1 (cons 2 '()))
;; => (1 2)

(cons 1 (cons 2 (cons 3 nil)))
;; => (1 2 3)

Isso significa que cons segue o princípio de fechamento. Mas e nossa função chop-head? O princípio se mantém?

1
2

(chop-head (chop-head (chop-head '(2))))
;; => NullPointerException

Aparentemente não. Para corrigir isso, precisamos garantir que dec não seja chamado com nil, já que não é possível decrementar um valor nulo.

1
2
3
4
5
6

(defn chop-head
  "Returns a new Hydra after chop off its first head."
  [hydra]
  (let [head (first hydra)]
    (into (rest hydra)
          (new-hydra (dec (or head 1))))))

E agora?

1
2

(chop-head (chop-head (chop-head '(2))))
;; => ()

Matando a Hydra

Para que Hércules mate a Hydra, ele precisa repetidamente cortar as cabeças da Hydra enquanto ela ainda as tiver.

1
2
3
4
5

(defn chop-until-dead
  "Repeatedly chops Hydra's heads until no head is left."
  [hydra]
  (take-while #(not (empty? %))
              (iterate #(chop-head %) hydra)))

A função (iterate f x) retorna uma sequência lazy (infinita) de x, (f x), (f (f x)), etc, dado que f é uma função livre de efeitos colaterais.

1
2

(take 3 (iterate inc 0))
;; => (0 1 2)

Como chop-head respeita o princípio de fechamento sempre retornando uma lista, podemos usá-la em iterate até obtermos uma lista vazia, o que significa que a Hydra está MORTA.

Vamos testá-la em uma Hydra bebê de 3 cabeças.

1
2
3

(chop-until-dead (new-hydra 3))
;; => ((3 3 3) (2 2 3 3) (1 2 3 3) (2 3 3) (1 3 3) (3 3)
;;     (2 2 3) (1 2 3) (2 3) (1 3) (3) (2 2) (1 2) (2) (1))

Quantos cortes são necessários para matar a Hydra original de 9 cabeças?

1
2

(count (chop-until-dead (new-hydra 9)))
;; => 986409

Outra pergunta interessante: qual é o número máximo de cabeças que Hércules enfrentou de uma só vez?

1
2
3
4

(apply max
       (map count
            (chop-until-dead (new-hydra 9))))
;; => 37

Ah. Lindo.