Google Treasure Hunt: robot

Hoje comecei a resolver o segundo “desafio” do Google Treasure Hunt (eu estava fazendo em D), e resolvi tentar o “desafio” anterior.

Basicamente, o desafio era:

Dada uma grid de tamanho L x C, o objetivo era ver o número de caminhos possíveis entre [0,0] e (L,C), realizando apenas movimentos para baixo e para a direita. Como os números que estavam dando eram “meio” grandes, resolvi fazer em Haskell (lembrando que esse conceito de inteiro de 32bits em Haskell não é necessariamente existente. Os números são tão grandes quanto for necessário).

Então, vamos à explicação do método:

Sabemos que para chegar da origem ao destino, são necessários L – 1 + C – 1 (número de linhas + número de colunas, desconsiderando a célula de origem – você precisa se movimentar até ela) movimentos. Então vamos definir essas constantes:

c = C - 1 :: Integer
l = L - 1 :: Integer

(lembre-se de substituir o C e o L pelos valores que foram passados no seu desafio).

Agora, vamos supor que o caminho seja formado pelas letras D (direita) e B (baixo). O número total de caminhos possíveis seria o número de combinações de D e B, no caso c * B e l * D. Por exemplo: supondo c = 3 e l = 2, teríamos que fazer todas as combinações possíveis com DDBBB, ou seja:

BBBDD
BBDDB
BDDBB
DDBBB
BDBBD
BDBDB
...

Para isso, (você deve se lembrar de suas aulas de estatística), basta pegar o fatorial do número total de elementos (C – 1 + L – 1). Então nossa função para fatorial será novamente necessária:

fac :: Integer -> Integer
fac n = product [1..n]

E vamos aproveitar para definir o total:

facT = fac(c + l) :: Integer

Com isso será obtido o número total de caminhos, mas o desafio pede apenas os caminhos únicos (sim, há caminhos repetidos se parar por aqui, pois, apesar de serem iguais, haverão duas combinações BBDDB, por exemplo).

Então, como os R podem ser combinados para formar caminhos iguais, teremos que remover alguns destes. Para isso, vamos começar vendo quantas combinações de Rs e Bs são possíveis:

facC = fac (C - 1) :: Integer
facL = fac (L - 1) :: Integer

Com isso, teremos o número de duplicatas por caminho encontrado.

Agora basta dividir o total de caminhos possíveis pelos números de caminhos duplicados:

resultado = facT  `div` facC `div` facL :: Integer

Ou seja, basta aplicar a “equação”:

(C - 1 + L - 1)! / (C - 1)! / (L - 1)!

O programa completo (no meu caso, foi uma grid de 42 x 50):

module Main where

fac :: Integer -> Integer
fac n = product [1..n]

c = 42 - 1 :: Integer
l = 50 - 1 :: Integer

facT = fac (c + l) :: Integer
facC = fac (42 - 1) :: Integer
facL = fac (50 - 1) :: Integer

resultado = facT  `div` facC `div` facL :: Integer

main :: IO()
main = do
	(putStrLn.show) resultado

blogblogs tags:haskell, programacao, funcional