Get best of the week

Quanta água vazou? Resolvemos o problema caminhando pela lua em Haskell

Uma tarefa interessante caminha na rede, que foi solicitada em uma entrevista no Twitter.
Imagine que você está olhando paredes de várias alturas de perfil. Está chovendo, em algum lugar a água permanece, em algum lugar flui pelas bordas da parede devido à diferença de altura. O desafio é determinar quanta água resta entre as paredes.


Para representar a sequência de paredes, podemos usar a lista:

type Height = Int

walls :: [Height]
walls = [2,5,1,2,3,4,7,7,6]

Para descobrir o volume de água no topo de cada parede, precisamos saber três coisas:

  1. Altura atual da parede
  2. A altura da parede esquerda mais alta
  3. A altura da parede mais alta à direita

Descobrimos qual parede abaixo é direita ou esquerda, subtraia a altura da parede atual da mais alta e obtém o volume de água. Vamos dar uma olhada em um exemplo:



imagine que precisamos calcular o volume de água da parede b. A altura da parede esquerda mais alta - a , é 3 . A altura da parede mais alta a direita - s , é 2 . Devido à parede superior esquerda, a água escorrerá para a direita, portanto, contamos a partir da altura da parede direita. Portanto, o volume de água para a parede b é = altura c - altura b = 2 - 1 = 1 .

Resolver esse problema em um passo da lista não funcionará, mas ocorrerá em dois - a coisa toda é calcular as paredes superiores esquerda e direita. ( UPD :roman_kashitsynmostrou como é possível para um, apenas sem obter informações sobre o volume de água acumulada em cada parede)

Começamos calculando a parede esquerda mais alta de cada parede usando o efeito de estado:

type Volume = Int

--|        
themax :: Height -> State Height Height
themax h = modify (max h) *> get

-- |            
highest_left :: [Height] -> [Height]
highest_left walls = evalState (traverse themax walls) 0



Agora precisamos calcular a parede direita mais alta para cada uma das paredes, mas, neste caso, precisamos iniciar a contagem não à esquerda, mas à direita. Como estar neste caso? Virar a lista? Como você deve ter adivinhado no título deste artigo, existe um método mais interessante.

Funcores Aplicadores Inversos


Um tipo interessante reside no pacote de transformadores (no sentido literal e figurativo da palavra). Permite executar efeitos de aplicação na ordem inversa:

newtype Backwards f a = Backwards { forwards :: f a }

Como funciona? Vamos dar uma olhada na instância da classe Applicative para Backwards :

-- |          liftA2  <**>
instance Applicative t => Applicative (Backwards t) where
        pure = Backwards . pure
	Backwards f <*> Backwards x = Backwards ((&) <$> x <*> f)

& é a mesma aplicação de uma função ao argumento $ , mas com uma ordem diferente de argumentos: primeiro o argumento, depois a função:

f $ x = x & f

Devido à preguiça, primeiro calculamos o segundo componente da cadeia de cálculo do aplicativo e somente então o primeiro - daí o nome desse tipo.

Nos mesmos transformadores, há outro tipo interessante - Reverso :

newtype Reverse f a = Reverse { getReverse :: f a }

Ele lança efeitos em Traversable em reverso usando Backwards .

E agora voltando ao nosso problema original com esse mesmo tipo.

Nós dominamos o moonwalk


“Moonwalk” (do moonwalk inglês), ou “deslizando para trás”, é uma técnica de dança quando um dançarino se move para trás, enquanto simula movimentos das pernas como se estivesse caminhando para frente. (Wikipedia).
Para iniciar esse truque, adotamos a mesma função com o efeito de estado (como se estivéssemos avançando, da esquerda para a direita), que usamos para calcular a parede esquerda mais alta:

-- |        
themax :: Height -> State Height Height
themax h = modify (max h) *> get

-- |    ,    :
highest_right :: [Height] -> [Height]
highest_right walls = getReverse $ evalState (traverse themax $ Reverse walls)

Agora temos tudo para calcular o volume total de água acumulada. Das paredes esquerda e direita mais altas, selecionamos a mais baixa e subtraímos a altura da parede - este será o volume de água acumulada:

walls = [2,5,1,2,3,4,7,7,6]
let hls = highest_left walls = [2,5,5,5,5,5,7,7,7]
let hrs = highest_right walls = [7,7,7,7,7,7,7,7,6]
sum $ zipWith3 (\l x r -> min l r - x) hls walls hrs



Assim, os functores aplicativos nos ajudaram a abstrair de efeitos específicos e estruturas de dados. Eles têm alguns usos mais interessantes - consultas de agrupamento , classificação .

O código fonte desta solução pode ser encontrado aqui . Este quebra-cabeça tem algumas abordagens mais interessantes que podem ser vistas aqui .

More articles:


All Articles