Get best of the week

Combien d'eau a fui? Nous résolvons le problème par un moonwalk sur Haskell

Une tâche intéressante se promène sur le réseau, qui a été demandée lors d'une interview sur Twitter.
Imaginez que vous regardez des murs de différentes hauteurs de profil. Il pleut, quelque part l'eau reste, quelque part où elle coule sur les bords du mur en raison de la différence de hauteur. Le défi consiste à déterminer la quantité d'eau restant entre les murs.


Pour représenter la séquence des murs, nous pouvons utiliser la liste:

type Height = Int

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

Pour connaître le volume d'eau au sommet de chaque mur, nous devons savoir trois choses:

  1. Hauteur actuelle du mur
  2. La hauteur du mur le plus haut à gauche
  3. La hauteur du mur le plus haut à droite

Nous découvrons quel mur ci-dessous est à droite ou à gauche, soustrayons la hauteur du mur actuel du plus haut et obtenons le volume d'eau. Examinons de plus près un exemple:



Imaginez que nous devons calculer le volume d'eau pour le mur b. La hauteur du mur le plus haut à gauche - a , est de 3 . La hauteur du plus haut mur droit - s , est 2 . En raison du mur supérieur gauche, l'eau se déversera vers la droite, nous comptons donc à partir de la hauteur du mur droit. Par conséquent, le volume d'eau pour le mur b est = hauteur c - hauteur b = 2 - 1 = 1 .

Pour résoudre ce problème en un seul passage de la liste ne fonctionnera pas, mais il se révélera en deux - le tout est de calculer les murs supérieurs gauche et droit. ( UPD :roman_kashitsyna montré comment il est possible pour un, seulement sans obtenir d'informations sur le volume d'eau accumulé sur chaque mur)

Nous commençons par calculer le mur le plus à gauche pour chaque mur en utilisant l'effet d'état:

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



Maintenant, nous devons calculer le mur droit le plus haut pour chacun des murs, mais dans ce cas, nous devons commencer le comptage non pas à gauche, mais à droite. Comment être dans ce cas? Retournez la liste? Comme vous l'avez peut-être deviné d'après le titre de cet article, il existe une méthode plus intéressante.

Foncteurs applicatifs inverses


Un type intéressant vit dans le paquet des transformateurs (au sens littéral et figuré du mot). Il vous permet d'exécuter des effets applicatifs dans l'ordre inverse:

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

Comment ça fonctionne? Examinons de plus près l'instance de classe Applicative pour Backwards :

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

& est la même application d'une fonction à l'argument $ , mais avec un ordre d'arguments différent: d'abord l'argument, puis la fonction:

f $ x = x & f

En raison de la paresse, nous calculons d'abord le deuxième composant de la chaîne de calcul applicative, puis seulement le premier - d'où le nom de ce type.

Dans les mêmes transformateurs, il existe un autre type intéressant - Inverse :

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

Il lance des effets dans Traversable à l'envers en utilisant Backwards .

Et maintenant, revenons à notre problème d'origine avec ce type même.

Nous maîtrisons le moonwalk


«Moonwalk» (du Moonwalk anglais), ou «gliding backward», est une technique de danse lorsqu'un danseur recule, tout en simulant les mouvements des jambes comme s'il marchait vers l'avant. (Wikipédia).
Pour lancer une telle astuce, nous prenons la même fonction avec l'effet d'état (comme si nous allions de l'avant, de gauche à droite), que nous avons utilisé pour calculer le mur gauche le plus haut:

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

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

Maintenant, nous avons tout pour calculer le volume total d'eau accumulée. À partir des murs gauche et droit les plus élevés, nous sélectionnons le plus bas et en soustrayant la hauteur du mur - ce sera le volume d'eau accumulé:

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



Ainsi, les foncteurs applicatifs nous ont aidés à faire abstraction d'effets spécifiques et de structures de données. Ils ont des utilisations plus intéressantes - regroupement des requêtes , tri .

Le code source de cette solution peut être trouvé ici . Ce puzzle propose des approches plus intéressantes qui peuvent être consultées ici .

More articles:


All Articles