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

Programação Funcional – Parte III – Mais sobre Funções

No último post você viu um exemplo de uma função para calcular o fatorial de um número.

Agora, continuando no tópico de funções, veremos mais alguns conceitos.

Primeiramente, você viu que foi especificado o tipo da função fatorial, que era Int -> Int, ou seja, uma função que recebe um inteiro e retorna um inteiro.

Agora, vejamos outra função:

soma :: Int -> Int -> Int
soma a b = a + b

Como o nome nos diz, essa função retorna a soma de seus dois argumentos.

Vamos começar a ver alguns de seus detalhes.

A primeira coisa que deve ser notada é que esta é uma função pura. ou seja, ela não faz alteração de nenhum estado e seu valor de retorno depende unicamente de seus valores de entrada.

“Mas você não havia dito que linguagens funcionais não guardam estado? Então todas as funções são puras?”

Não exatamente. Para conflitar com isso, vejamos, por exemplo, uma função que retorne um número aleatório. Normalmente estas não recebem nenhum parâmetro, mas retornam resultados variados. Então esse tipo de função não é pura.
Outro exemplo de funções impuras são funções que realizam operações de entrada e saída.

Outra coisa que deve ser notada é a declaração do tipo da função: Int -> Int -> Int. Isso não parece com algo que receba dois inteiros e retorne outro. E realmente não é isso.

Se você olhar a origem das linguagens funcionais, verá que são uma evolução do Cálculo Lambda, e uma de suas características é que as funções são unárias, ou seja, recebem apenas um argumento.

Voltemos ao fato de que funções são tipos de “alta ordem” em linguagens funcionais. Isso quer dizer que funções podem ser passadas como argumentos, ou podem ser retornadas de outros funções.

Na verdade, o que acontece é exatamente isso, em uma técnica chamada currying. O que ocorre realmente é que a função soma recebe apenas um argumento, retorna uma função que recebe mais um argumento e que, aí sim, retorna o resultado: Int -> (Int -> Int).