Get best of the week

Wie viel Wasser ist ausgetreten? Wir lösen das Problem durch einen Mondspaziergang auf Haskell

Eine interessante Aufgabe läuft im Netzwerk, die bei einem Interview auf Twitter gefragt wurde.
Stellen Sie sich vor, Sie betrachten Wände unterschiedlicher Höhe im Profil. Es regnet, irgendwo bleibt das Wasser, irgendwo fließt es aufgrund des Höhenunterschieds über die Wandränder. Die Herausforderung besteht darin, festzustellen, wie viel Wasser zwischen den Wänden verbleibt.


Um die Abfolge der Wände darzustellen, können wir die Liste verwenden:

type Height = Int

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

Um das Wasservolumen oben an jeder Wand herauszufinden, müssen wir drei Dinge wissen:

  1. Aktuelle Wandhöhe
  2. Die Höhe der höchsten linken Wand
  3. Die Höhe der höchsten rechten Wand

Wir finden heraus, welche Wand unten rechts oder links ist, subtrahieren die Höhe der aktuellen Wand von der höchsten und erhalten das Wasservolumen. Schauen



wir uns ein Beispiel genauer an: Stellen Sie sich vor, wir müssen das Wasservolumen für Wand b berechnen. Die Höhe der höchsten linken Wand - a , beträgt 3 . Die Höhe der höchsten rechten Wand - s ist 2 . Aufgrund der höheren linken Wand tritt Wasser nach rechts aus, sodass wir von der Höhe der rechten Wand aus zählen. Daher wird das Volumen des Wassers für die Wand b ist = Höhe c - Höhe b = 2 - 1 = 1 .

Dieses Problem in einem Durchgang der Liste zu lösen, wird nicht funktionieren, aber es wird sich in zwei herausstellen - das Ganze besteht darin, die obere linke und rechte Wand zu berechnen. ( UPD :roman_kashitsynzeigten, wie es für eine möglich ist, nur ohne Informationen über das Volumen des angesammelten Wassers an jeder Wand zu erhalten.)

Wir beginnen mit der Berechnung der höchsten linken Wand für jede Wand unter Verwendung des Zustandseffekts:

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



Jetzt müssen wir die höchste rechte Wand für jede der Wände berechnen, aber in diesem Fall müssen wir die Zählung nicht links, sondern rechts beginnen. Wie soll man in diesem Fall sein? Liste umdrehen? Wie Sie vielleicht aus dem Titel dieses Artikels erraten haben, gibt es eine interessantere Methode.

Inverse anwendbare Funktoren


Ein interessanter Typ lebt im Transformatorenpaket (im wörtlichen und im übertragenen Sinne des Wortes). Sie können damit anwendbare Effekte in umgekehrter Reihenfolge ausführen:

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

Wie es funktioniert? Schauen wir uns die Applicative- Klasseninstanz für Backwards genauer an :

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

& ist dieselbe Anwendung einer Funktion auf das $ -Argument , jedoch mit einer anderen Reihenfolge von Argumenten: zuerst das Argument, dann die Funktion:

f $ x = x & f

Aufgrund der Faulheit berechnen wir zuerst die zweite Komponente der anwendbaren Berechnungskette und erst dann die erste - daher der Name für diesen Typ.

In den gleichen Transformatoren gibt es einen anderen interessanten Typ - Reverse :

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

Es startet Effekte in Traversable in umgekehrter Reihenfolge mit Rückwärts .

Und nun zurück zu unserem ursprünglichen Problem mit diesem Typ.

Wir meistern den Mondspaziergang


"Moonwalk" (vom englischen Moonwalk) oder "rückwärts gleiten" ist eine Tanztechnik, wenn sich ein Tänzer rückwärts bewegt und dabei die Bewegung seiner Beine simuliert, als würde er vorwärts gehen. (Wikipedia).
Um einen solchen Trick anzukurbeln, übernehmen wir dieselbe Funktion mit dem Zustandseffekt (als ob wir vorwärts gehen würden, von links nach rechts), mit dem wir die höchste linke Wand berechnet haben:

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

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

Jetzt haben wir alles, um das Gesamtvolumen des angesammelten Wassers zu berechnen. Von der höchsten linken und rechten Wand wählen wir die niedrigste aus und subtrahieren die Wandhöhe davon - dies ist das Volumen des angesammelten Wassers:

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



Applikative Funktoren halfen uns also, von bestimmten Effekten und Datenstrukturen zu abstrahieren. Sie haben einige interessantere Verwendungszwecke - Gruppieren von Abfragen , Sortieren .

Den Quellcode für diese Lösung finden Sie hier . Dieses Rätsel hat einige interessante Ansätze , die angezeigt werden können hier .

More articles:


All Articles