Сколько воды утекло? Решаем задачу лунной походкой на Haskell

    В сети гуляет интересная задача, которую задавали на собеседовании в Twitter.
    Представьте, что вы смотрите на стенки различной высоты в профиль. Идет дождь, где-то вода остается, где-то перетекает за края стенки из-за разницы в высоте. Задача состоит в том, чтобы определить, какой объем воды остался между стенками.


    Для представления последовательности стенок мы можем использовать список:

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

    Чтобы выяснить объем воды наверху каждой стенки, нам нужно знать три вещи:

    1. Высоту текущей стенки
    2. Высоту самой высокой левой стенки
    3. Высоту самой высокой правой стенки

    Выясняем, какая самая стенка ниже — правая или левая, отнимаем высоту текущей стенки от самой высокой и получаем объем воды. Рассмотрим повнимательнее на примере:



    Представим, что нам нужно вычислить объем воды для стенки b. Высота самой высокой левой стенки — а, равняется 3. Высота самой высокой правой стенки — с, равняется 2. Из-за более высокой левой стенки, вода будет выливаться направо, поэтому отсчет ведем с высоты правой стенки. Следовательно, объем воды для стенки b равен = высота с — высота b = 2 — 1 = 1.

    Решить эту задачу за один проход списка не получится, но получится за два — все дело в вычислений самых верхних левой и правой стенок. (UPD: roman_kashitsyn показал, как можно за один, только без получения информации об объеме накопленной воды на каждую стенку)

    Начнем с вычисления самой высокой левой стенки для каждой из стенок с помощью эффекта состояния:

    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
    



    Теперь нужно вычислить самую высокую правую стенку для каждой из стенок, но в этом случае нам нужно начинать отсчет не слева, а справа. Как быть в этом случае? Переворачивать список? Как вы уже могли догадаться из заголовка этой статьи, есть метод поинтереснее.

    Обратные аппликативные функторы


    В пакете transformers живет интересный тип (в прямом и переносном смысле этого слова). Он позволяет запускать аппликативные эффекты в обратном порядке:

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

    Как это работает? Давайте внимательнее рассмотрим экземпляр класса Applicative для Backwards:

    -- | На самом деле это немного упрощенный код после разбора liftA2 и <**>
    instance Applicative t => Applicative (Backwards t) where
            pure = Backwards . pure
    	Backwards f <*> Backwards x = Backwards ((&) <$> x <*> f)
    

    & это то же самое применение функции к аргументу $, только с другим порядком аргументов: сначала аргумент, потом функция:

    f $ x = x & f

    Благодаря ленивости, что мы сначала вычисляем второй компонент аппликативной цепочки вычисления, а только потом первый — отсюда и название для этого типа.

    В этом же transformers есть еще один интересный тип — Reverse:

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

    Он запускает эффекты в Traversable в обратном порядке используя Backwards.

    А теперь вернемся к нашей исходной задаче с этим самым типом.

    Осваиваем лунную походку


    «Лу́нная похо́дка» (от англ. moonwalk), или «скольжение назад», — танцевальная техника, когда танцор движется назад, при этом имитируя движения ног как при ходьбе вперед. (Википедия).
    Чтобы провернуть такой трюк, мы возьмем ту же функцию с эффектом состояния (как если бы мы шли вперед, слева направо), которую мы использовали для вычисления самой высокой левой стенки:

    -- | Среди предыдущей и текущей стенки выбираем самую высокую
    themax :: Height -> State Height Height
    themax h = modify (max h) *> get
    
    -- | Только в этот раз, мы пойдем справа налево:
    highest_right :: [Height] -> [Height]
    highest_right walls = getReverse $ evalState (traverse themax $ Reverse walls) 
    

    Теперь у нас есть все, чтобы вычислить итоговый объем накопленной воды. Из самых высоких левой и правой стенки выбираем самую низкую и от нее отнимаем высоту стенки — это и будет объем накопленной воды:

    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
    



    Вот так, аппликативные функторы помогли нам абстрагироваться от конкретных эффектов и структур данных. У них есть еще несколько интересных применений — группировка запросов, сортировки.

    Исходный код этого варианта решения можно найти тут. У этой задачки есть еще несколько интересных подходов, которые можно посмотреть здесь.
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 51

      0
      Не мог понять суть задачи по описанию, пока не изучил иллюстрацию. Думаю, лучше использовать термин «высота» стен, а не «длина»: под длиной стены обычно понимают её размер в горизонтальном направлении
        0
        Да, так намного лучше, спасибо.
        +1
        Глупый нубский вопрос: а то, что мы абстрагировались от конкретных эффектов и структур данных помогло решить задачу лучше, эффективнее, или сделать код более читаемым, или повторно используемым? Можно развить идею предпоследнего абзаца?
          0
          Повторно используемым — потому что мы можем использовать любые структуры данных, для которых определен Traversable. Любые эффекты можно так же запускать в другом порядке, обернув их в Backwards.
          0

          Почему в "правильном ответе" на кдпв первый столбец пустой?
          Что получится для массива стенок: 2,4,1,7,3,5?

            0
            Вода скатится как со скатов крыши — если с левого края есть «возрастающая последовательность» (или с правого — «убывающая»).
              0

              5 будет. 3 над единицей и 2 над тройкой. В этой задаче считается, что слева и справа от исходных данных стоят нули.

              0
              Решить эту задачу за один проход списка не получится, но получится за два — все дело в вычислений самых верхних левой и правой стенок.
              Может я неправильно понял задачу, но кажется за один вполне можно. В профиль же тут получается в любом случае кривая пирамида. Т.е. можно просто идти с 2х сторон списка выбирая в каждый заход каждого направления следующую стенку, больше текущей и суммируя весь объём между ней и текущей. Если два поиска встретились — тут отбрасываем последний заход более высокой стороны (т.к. у нас с дугой стороны вытекает) и дорабатываем более низкий. В худшем случае обрабатываем список дважды (когда самые высокие это крайние стенки. В лучшем — за один проход.
              Можно и за один прямой проход, но там надо хитро учитывать новые ступени. слишком муторно. Ткните, где я не прав?

              Upd: Если каждый заход идти со стороны более низкого, то второй проход, вроде бы, вообще исключается.
                0
                Можете показать решение?
                  0
                  На хаскеле или вообще? С хаскелем не знаком вообще. Могу попробовать на сях :)
                  Собственно ниже, вроде, уже привели
                    0

                    на сях как-то так в один проход делается.


                    int v[] = {1, 2, 3, 4, 6, 3, 2, 4, 7, 3, 4, 6, 1, 2, 1};
                    int count = 0;
                    for (int l=0,r=sizeof(v)/sizeof(v[0]),lM = v[0], rM = v[sizeof(v)/sizeof(v[0])]; 
                                    l < r; 
                                    lM = max(lM,v[l]), rM = max(rM,v[r]))
                        if(lM >= rM)
                            count += rM - v[r--];
                        else
                            count += lM - v[l++];
                      0
                      Попробуйте для наборов данных { 2, 1, 2, 1, 2 } и { 2, 1, 3, 1, 2 }. По идее должно быть 2 в обоих случаях, но ваше решение дает 2 и 4:

                      3|
                      2| X ~ X ~ X
                      1| X X X X X

                      3|     X
                      2| X ~ X ~ X
                      1| X X X X X
                        +1

                        странно. При копировании -1 что-то не скопировались.


                        for (int l=0,r=sizeof(v)/sizeof(v[0]) - 1,lM = v[0], rM = v[sizeof(v)/sizeof(v[0]) - 1];

                        Иначе выход за границы массива и что угодно может быть.

                        +1
                        переписал на С++ покомпактней

                        int trap(vector<int>& v) 
                            {
                                if (empty(v)) return 0;
                                int c(0);
                                for (int l(0), r(size(v)-1), lM(v.front()), rM(v.back()); l < r; lM = max(lM, v[l]), rM = max(rM, v[r]))
                                    c += lM < rM ? lM - v[l++] : rM - v[r--];
                                return c;
                            }
                        

                        Так побыстрей будет
                        int trap(vector<int>& v) 
                        {
                            if (empty(v)) return 0;
                            int c(0);
                            for (int l(0), r(size(v)-1), lM(v.front()), rM(v.back()); l < r;)
                                if (lM < rM)
                                {
                                    c +=  lM - v[l++];
                                    lM = max(lM, v[l]);
                                }
                                else
                                {
                                    c += rM - v[r--];
                                    rM = max(rM, v[r]);
                                }
                            return c;
                        }
                      0
                      идем по структуре слева направо, запоминаем максимум высоты слева, ищем стенку после которой стоит стена с меньшей высотой (то есть у нас look ahead = 1, но поскольку haskell — то просто тащим за собой предыдущий проверенный элемент). Если имеем перепад высот — то есть две стены и левая выше правой, то вычисляем объем воды который поместится между левой высокой стеной и предыдущим максимумом. После этого левая высокая становится предыдущим максимумом и идем дальше. На старте максимум задаем == 0
                    0
                    Решить эту задачу за один проход списка не получится

                    Можно решить за один проход, если использовать дополнительный стэк. Но это не самое простое решение, конечно.


                    Также рекомендую к просмотру: https://www.youtube.com/watch?v=ftcIcn8AmSY

                      –1
                      Можете показать решение?
                        +1

                        Что-то вроде такого


                        trap :: [Int] -> Int
                        trap = fst . foldl drain (0, []) . zip [0..]
                          where drain (!s, []) x = (s, [x])
                                drain (!s, [t@(_, ht)]) x@(_, hx) =
                                  if ht <= hx then (s, [x]) else (s, [x, t])
                                drain acc@(!s, stack@((_, hb):r@((pt, ht):_))) x@(px, hx) =
                                  case compare hx hb of
                                    EQ -> acc
                                    GT -> drain (s + (px - pt - 1) * min (ht - hb) (hx - hb), r) x
                                    LT -> (s, x:stack)
                          0
                          Моей ошибкой было считать, что получить весь объем воды было не возможным без информации об объеме воды на каждую стенку.
                        +3
                        Можно за один проход и без стека, просто обходить массив не с одной стороны, а идти с обоих концов и шагать той стороной, которая меньше, пример на go:
                        func trap(height []int) int {
                            result, left, right := 0, 0, len(height) - 1
                            maxL, maxR := 0, 0
                            for left < right {
                                if height[left] < height[right] {
                                    if height[left] > maxL {
                                        maxL = height[left]
                                    } else {
                                        result += maxL - height[left]
                                    }
                                    left++
                                } else {
                                    if height[right] > maxR {
                                        maxR = height[right]
                                    } else {
                                        result += maxR - height[right]
                                    }
                                    right--
                                }
                            }
                            return result
                        }
                        

                        Эта задача на ресурсе с задачками, где можно потестить свои реализации: leetcode.com/problems/trapping-rain-water
                          –3
                          Можно за один проход

                          Нет, нельзя. Как можно говорить об одном проходе, если вы используете мутабельные массивы, которые позволяют вам обращаться к произвольному элементу по индексу в любом месте?
                            –1

                            А где вы увидели операцию изменения массива в коде выше?

                              –2
                              Я говорю не про изменение массива, а про доступ к произвольному элементу по индексу. Понятие «прохода» теряет смысл, так как я могу обращаться к любому элементу массива.
                                0

                                Вообще говоря, случайный доступ тут не нужен, достаточно положить вход в Data.Sequence и обращаться только к голове и хвосту.

                                  0
                                  Но для того, чтобы превратить список в пальчиковое дерево, тоже придется его обойти.
                                    +2
                                    чтобы превратить список в пальчиковое дерево, тоже придется его обойти

                                    С этим никто не спорит, я лишь утверждаю, что этот алгоритм не требует random-access.

                                  0

                                  Произвольный доступ к количеству проходов не имеет отношения. Думаю, не совру, если скажу, что под одним проходом подразумевается случай, когда каждый элемент списка читается не более одного раза.


                                  Иначе у вас реализация не эквивалентные, вы сделали на списке (по сути — итераторе, если использовать императивную терминологию), а люди — на массиве.




                                  Я бы тоже попробовал поиграть с реализацией задачки, но к сожалению как всегда за аналогиями потреяли лес, и я не понимаю, что требуется. Как во всех этих задачах про "Вася заходит в комнату и подмечает, что в зеркале отражается люстра, а значит..."

                                0
                                Сорри, я с хаскелем не знаком, зашел в статью потому что сам относительно недавно решал задачку на другом языке и мне был интересен алгоритм, но после слов «Решить эту задачу за один проход списка не получится» читал уже совсем по-диагонали, т.к. когда я ее решал, у входного параметра не было ограничений на чтение с конца и в моем случае задача решалась за один обход массива.
                                Было-бы очень неплохо если-бы вы указали на ограничение входных типов вначале статьи, до слов за которые я зацепился.
                                  0
                                  Список — это линейная структура данных, если вы хотите прочитать конец списка, вам нужно пройти его до конца за линейное время. Элементы массива можно читать за O(1).
                                    0
                                    Списк слишком абстрактное понятие, в с++ в std::list получить конец списка — O(1), в дотнете List обертка над массивами, где доступ к любому элементу O(1). Линейное время нужно только для односвязанного списка. Ну, может еще есть реализации двусвязанных списков, где экономят на спичках и не хранят ссылку на конец.
                                      0
                                      Нет, в курсе/литературе, посвященной структурам данных есть четкое определение того, чем является список. Реализация в конкретных языках программирования не делает его абстрактным.
                                        +1
                                        Мне кажется вы просто подзабыли уже, то четкое определение, которое вы имеете ввиду это связанный список, или linked list, но не просто список. Чтоб закончить спор: https://en.wikipedia.org/wiki/List_(abstract_data_type)
                                        The name list is also used for several concrete data structures that can be used to implement abstract lists, especially linked lists and arrays.
                                          0
                                          Я использовал Haskell и его индуктивное определение списка, которое исключает двусвязность.

                                          Видимо, есть большая путаница. Вот тут, к примеру, определение односвязного списка приравнено к спискам: freecontent.manning.com/wp-content/uploads/2015/05/arrays-vs-lists.pdf

                                          В нескольких статьях на Хабре встречал описание рядом односвязного списка и стека и недоумевал, почему существуют два названия для одного и того же.
                                            0

                                            Список в хаскелле это классический фпшный список:


                                            data List a = Nil | Cons a (List a)

                                            Который, как видно, односвязный и совсем не основан на массиве. И контекст вроде как раз и был, что мы используем хаскел терминологию.

                                  +2
                                  Можно за один проход и без стека, просто обходить массив не с одной стороны, а идти с обоих концов

                                  Про это решение я тоже знаю, но у меня в голове "один проход" как-то плохо сочетается с random-access к входу. Ведь сначала нам нужно прочитать весь вход в массив ("первый" проход), а потом искать в нём, используя random-access ("второй" проход).


                                  Решение, которое я предложил, считывает по одному элементу из списка и обновляет состояние алгоритма. Суммарные требования к памяти у обоих алгоритмов примерно одинаковые (может потребоваться хранить весь вход в памяти).

                                    –1

                                    Но по идее это тоже 2 прохода, ведь в среднем каждый элемент мы смотрим 2 раза например


                                    if height[left] < height[right] — true
                                    left++
                                    if height[left] < height[right] — false
                                    right++


                                    При таком порядке исполнения мы 2 раза читаем элемент height[right]. Значит потенциально это более сложно записанная версия:


                                    for elm in height
                                    ...
                                    for elm in reverse(height)
                                    ...

                                    Где тоже каждый элемент будет обработан два раза.

                                  0
                                  А что, если идти снизу вверх, представив все матрицей с нулями и единицами. Нашли превые нули, если слева и права есть единицы, инкрементировали объем.
                                    0
                                    Можете показать решение?
                                      –1

                                      Это решение работает за экспоненту по времени и памяти. Посчитайте, сколько нужно времени для входа [4000000, 0, 4000000].

                                        0
                                        Формально говоря его решение работает за log_2(MAX_VALUE) * n = O(n)
                                          0

                                          Откуда взялся log_2? Если я правильно понял идею, то оно работает за O(MAX_VALUE * n). Если брать на вход целые произвольной точности, то вполне себе https://en.wikipedia.org/wiki/Pseudo-polynomial_time.

                                            0

                                            Да, вы правы, log_2 лишнее.

                                      0
                                      А сообщающиеся сосуды по условию задачи могут быть? И есть ли пол?
                                        0
                                        Если я правильно помню, похожая задача была на Advent Of Code :)
                                          0
                                          А почему не использовать для поиска максимума scanl и scanr?
                                          highestLeft :: [Height] -> [Height]
                                          highestLeft [] = []
                                          highestLeft l = scanl1 max l
                                          
                                          highestRight :: [Height] -> [Height]
                                          highestRight [] = []
                                          highestRight l = scanr1 max l
                                          
                                            0
                                            В ссылке с другими решениями есть вариант с scanl1/scanr1.
                                            0

                                            У меня получилось такое решение, вроде выдает правильный ответ и считает в один проход:


                                            water :: [Int] -> Int
                                            water xs = snd $ foldl' go ([], 0) xs where
                                              go ([], result) elm = ([elm], result)
                                              go (x:xs, result) elm = if x > elm then (x:elm:xs, result) else ([elm], result + getResult (min x elm) xs) where
                                                getResult roof elms = sum $ (\x -> roof - x) <$> elms

                                            Можно обойтись без промежуточного списка, если хитро аккумулировать результаты. Но немного лень извращаться. Фолд гарантирует, что мы видим все элементы ровно один раз.




                                            Исправил ошибку, когда неправильно считался последний чанк, если правая стенка оказывалась ниже левой:


                                            water :: [Int] -> Int
                                            water xs = transformResult $ foldl' go ([], 0) xs where
                                              transformResult ([], result) = result
                                              transformResult ([_], result) = result
                                              transformResult (x:elm:xs, result) = result + getIntermediateResult (min x elm) xs
                                            
                                              go ([], result) elm = ([elm], result)
                                              go (x:xs, result) elm = if x > elm then (x:elm:xs, result) else ([elm], result + getIntermediateResult (min x elm) xs)
                                            
                                              getIntermediateResult roof elms = sum $ (\x -> roof - x) <$> elms
                                              0

                                              Как всегда хабр в последнюю секунду не даёт редактировать. Вызов функции min лишний, у нас по построению и так понятно где что:


                                              water :: [Int] -> Int
                                              water xs = transformResult $ foldl' go ([], 0) xs where
                                                transformResult ([], result) = result
                                                transformResult ([_], result) = result
                                                transformResult (_:elm:xs, result) = result + getIntermediateResult elm xs
                                              
                                                go ([], result) elm = ([elm], result)
                                                go (x:xs, result) elm = if x > elm then (x:elm:xs, result) else ([elm], result + getIntermediateResult (min x elm) xs)
                                              
                                                getIntermediateResult roof elms = sum $ (\x -> roof - x) <$> elms

                                              Соответственно вариант без промежуточного списка с одним только состоянием:


                                              data WaterState = Empty | NonEmpty Int Int Int deriving Show
                                              
                                              water :: [Int] -> Int
                                              water xs = snd $ foldl' go (Empty, 0) xs where
                                                go :: (WaterState, Int) -> Int -> (WaterState, Int)
                                                go (Empty, result) elm = traceShowId (NonEmpty elm elm 1, result)
                                                go (NonEmpty x s count, result) elm = traceShowId $ if x > elm then (NonEmpty x (s + x - elm) (count + 1), result) else (NonEmpty elm elm 1, result + getResult x elm count s) where
                                                  getResult x elm count s = (if x <= elm then s else s - (x - elm) * count) - x

                                              Он не работает для стакана у которого последняя левая стенка выше правой, но в целом как мне кажется иллюстрирует идею. Тут уже гарантированно все элементы обходятся 1 раз, и промежуточных списков просто нет. Хотя по-хорошему такой код я бы писать, конечно, не рекомендовал)

                                                0

                                                Посмотрел по ссылке выше функция со списками тоже не работает для сложного случая вроде [0,1,0,2,1,0,1,3,2,1,2,1]. Думал несколько минут — как сделать в один фолд с одного конца, а не проходом с двух концов — не представляю.

                                                  +1
                                                  Соответственно вариант без промежуточного списка с одним только состоянием

                                                  Я почти уверен, что корректного решения с такими свойствами (обработка потока с O(1) дополнительной памяти) не существует (Контр-пример может выглядеть как длинная лестница вроде [n, n-1..0] ++ [x]. Как-то нужно впихнуть в O(1) все возможные исходы для всех возможных лестниц как функцию от x).


                                                  Он не работает для стакана у которого последняя левая стенка выше правой

                                                  Какой смысл приводить решение, которое не работает в общем случае?

                                                    0

                                                    я сначала написал решение, а потом (уже когда вышло время на редактирование) увидел стакан на котором функция неверно считает. Так что могу только посыпать голову пеплом, но не удалить комментарий. Плюс как подход в целом, всё еще полезно. наверное.


                                                    А про решение без доп. памяти — я тоже пришел к такому же выводу.

                                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                              Самое читаемое