Комментарии 74
Хорошее решение такой задачи вообще должно выполняться до одной секунды при m*n около 200000, и высотах до 10^9 (дабы не требовалась длинная арифметика). И то потому что я пока не вижу, как выбросить сортировку. Без неё можно и до миллиона добраться.
Так что универсальный решатель зачастую не сможет эффективно найти решение, несмотря на ограничения. Конечно, можно попробовать решить им задачу, для которой вы уже сформировали хорошие ограничения, но не можете придумать эффективный алгоритм решения. Но такое работает только на маленьких данных.
А касательно ограничений, тут у нас имеется главное ограничение «мы можем налить в клетку воды до уровня n, если нет путей по другим клеткам с высотой не больше n-1 от данной клетки до края». И при этом высоты жидкости не зависят друг от друга, можно последовательно подбирать.
Осталось придумать, как выразить такое на Прологе?
Вы правы, тесты беру с сайта, следующий был 50*50 и его решение не оканчивается.
Был бы рад увидеть более совершенное и лаконичное решение...
Если от клетки, которую мы рассматриваем сейчас, нет пути до края по уже рассмотренным клеткам — мы можем налить в неё сколько-то воды сверх её высоты.
Соответственно, если мы рассмотрели какую-то клетку и при этом от другой рассмотренной появился путь до края(через рассмотренную сейчас клетку) — значит, мы в эту другую можем налить воды до уровня рассмотренной сейчас.
Чтобы сделать это быстро, объединим находящиеся рядом рассмотренные клетки в множества, и для каждого множества будем хранить количество клеток в нём, общую высоту и есть ли сейчас путь из клеток этого множества к краю. Соответственно, множества нужно уметь соединять и быстро вычислять, к какому множеству относится клетка. И обновлять ответ, когда объединяем множество с путем к краю и множество без пути.
Такое называется «система непересекающихся множеств» и есть алгоритм, который обе операции делает почти за константное время.
Пришлось тесты подкомментировать т.к. не все проходили.
А финальный ваш вариант, кстати, проходит все оригинальные тесты?
Декларативное программирование предполагает детальную формализацию задачи, а решатель будет искать наиэффективнейшее решение, которое удовлетворит условиям.
"наиэффективнейшее" по каким критериям?
Вот, например, банальный вопрос: какова вычислительная сложность вашего решения?
В данном случае, мне интересна «вычислительная сложность», но хочу обратить внимание на «познавательную сложность». Какая задача труднее, сформулировать решения прибегая к алгоритму или описав формулировку?
В данном случае, мне интересна «вычислительная сложность»,
Вот и мне интересна. Какая вычислительная сложность у вашего решения? И вы так и не ответили: по каким критериям эффективности выбирается решение решателем?
Какая задача труднее, сформулировать решения прибегая к алгоритму или описав формулировку?
В случае задач "из реального мира" — одинаково, потому что на описание формулировки уходят недели и месяцы.
Но отдельная проблема в том, что ваше "полученное решение" не удовлетворяет "просто опишите формулировку": в нем не видно, собственно, формулировки задачи; да и вообще понять, что там происходит, очень и очень непросто. Так что "декларативность" оказалась ложной.
Спасибо, у вас замечания всегда очень критические, всех ответов не имею.
А как будете доказывать:
Так что "декларативность" оказалась ложной.
Предоставьте алгоритм, покажите его сложность, давайте сравнивать решения...
Спасибо, у вас замечания всегда очень критические, всех ответов не имею.
Ну то есть на самом деле ваше утверждение "решатель будет искать наиэффективнейшее решение, которое удовлетворит условиям" ни на чем не основано?
А как будете доказывать:
Так что "декларативность" оказалась ложной.
А легко.
Возьмем описание задачи:
Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.
Возьмем ваше решение:
checks(X0,X2):-
flatten(X0,FX),
max_list(FX,Max),checks(Max,X0,X2),
balns(X0,X2),
flatten(X2,FX2),
labeling([down],FX2).
checks(_,[],[]).
checks(_,[X],[X]).
checks(_,[X,Z],[X,Z]).
checks(V,[R1,R2,R3|T],[R1|St]) :- number(R2),!,
R21 in R2..V,
checks(V,[R21,R3|T],St).
checks(V,[R1,R2,R3|T],[R1|St]) :- checks(V,R2,R21),checks(V,[R21,R3|T],St).
balns([],[]).
balns([_],[_]).
balns([_,_],[_,_]).
balns([B1,B2,B3|Tb],[R1,R2,R3|T]) :-
blevel(B1,B2,B3,R1,R2,R3),
balns([B2,B3|Tb],[R2,R3|T]).
blevel([],[],[],[],[],[]).
blevel([_],[_],[_],[_],[_],[_]).
blevel([_,_],[_,_],[_,_],[_,_],[_,_],[_,_]).
blevel([_,U1,U2|Tu],[R,C,L|T],[_,B1,B2|Tb],
[_,U10,U20|Tu0],[R0,C0,L0|T0],[_,B10,B20|Tb0]):-
equ(C,[U1,L,R,B1],C0,[U10,L0,R0,B10]),
blevel([U1,U2|Tu],[C,L|T],[B1,B2|Tb],
[U10,U20|Tu0],[C0,L0|T0],[B10,B20|Tb0]).
equ(C0,_,C,[U,L,R,D]):-C#>C0,C#=<U,C#=<R,C#=<L,C#=<D.
equ(_,[],_,[]).
equ(C0,[C0|T0],C,[C|T]):-equ(C0,T0,C,T).
equ(C,_,C1,_):-C1#=C.
diffall(L0,L2,S):-
flatten(L0,F0),sum_list(F0,S0),
flatten(L2,F2),sum_list(F2,S2),
S is S2-S0.
sums(X,S):-checks(X,X1),!,diffall(X,X1,S).А теперь покажите мне, какая часть вашего решения является формулировкой задачи?
Так я говорю о том, что если нам сейчас предоставят «блок схему» с алгоритмом, то отклонение задачи от ее формулировки будет еще более заметно.
Более, чем та условная бесконечность, которая представлена в вашем коде? Я вообще не могу восстановить по нему исходную задачу.
И мне интересно, как же будет выглядеть императивное решение этой задачи?, не так ли будет понятно как быстрая сортировка?
А мне кажется, что такие программы, показывают математическую суть задачи
Конкретно ваша программа не показывает математическую суть данной задачи. Более того, в самой формулировке задания нет математической модели, следовательно, ее вывод — это и есть этап "формулирования решения".
И мне интересно, как же будет выглядеть императивное решение этой задачи?
Я над своим вариантом размышляю, но на том же leetcode есть множество решений в обсуждении этой задачи.
не так ли будет понятно как быстрая сортировка?
Быстрая сортировка как раз прекрасно понятна в императивных языках.
А быструю сортировку в Эрланге еще раз продемонстрирую:
qsort([])->[];
qsort([H|T])->qsort([X||X<-T,X<H])++[H|qsort([X||X<-T,X>=H])].
А быструю сортировку в Эрланге еще раз продемонстрирую:
Вы знаете, да, что этот решение не выполняет одного из основных критериев быстрой сортировки — константного расхода памяти?
(ну и я бы, конечно, отдельно поинтересовался тем, какая же конкретно вычислительная сложность у этого решения)
Понятность и вычислительная сложность конечно разные понятия, но когда они приближаются, тогда решение «хорошее».
А мне остается поинтересоваться, а как же «понятный» алгоритм быстрой сортировки сейчас вот записать, восстановить из памяти…
- Выберите пивот.
- Поместите все, что меньше пивота, до пивота, а все, что больше пивота — после пивота.
- Повторите на участке до пивота
- Повторите на участке после пивота
Сложности начинаются тогда, когда вы начинаете учитывать граничные случаи.
Понятность и вычислительная сложность конечно разные понятия, но когда они приближаются, тогда решение «хорошее».
Эти две метрики не могут "приблизиться", у них разные единицы измерения. Точнее говоря, вторую можно измерить, а первая субъективна.
Так все-таки, какая вычислительная сложность у приведенной вами реализации быстрой сортировки, и можно ли ее, собственно, называть быстрой сортировкой?
- Выберите пивот.
Тут надо бы поподробнее, не все еще понятно.
А записать в программу его будет тоже не просто..
Это же, как ассемблер заменили на фортран, что-то стало более понятнее.
И "Эти две метрики", если это метрики, то они имеют числовое выражение.
Тут надо бы поподробнее, не все еще понятно.
Это алгоритм, он, знаете ли, такой. Все остальное — детали имплементации, и именно в них таится дьявол. Так вас алгоритм интересует, или точная имплементация?
Ну так у quick sort и больше одной реализации с разными гарантиями сложности. Для вас это новость?
Вы думали, это простой алгоритм? Так нет.
Так может, то что я написал, на Эрланге, тот же самый алгоритм, он же такой — с «разными гарантиями»?
Ну так покажите это. Посчитайте вычислительную сложность, посчитайте сложность по памяти — вот и узнаем, помещается ли он в общие гарантии quick sort, или нет.
(на всякий случай, напомню: вычислительная сложность quick sort n log n в среднем и квадратичная в худшем случае, требования по памяти на каждом уровне рекурсии — константа; есть вариант с отдельным буфером равным по размеру сортируемой области)
Вот, а я нашел вот такое свойство алгоритмов:
детерминированность (определенность). Предполагает получение однозначного результата вычислительного процecca при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер;
На каждом рекурсивном вызове Эрланга, список разделяется на два других, меньших, а входной после выхода из функции пропадает далее сортируються меньшие списки, так что константность памяти сохранится. А сложность n*log(n) сохраняется, так это выражение того-же самого принципа быстрой сортировки.
список разделяется на два других, меньших
Что значит "список разделяется"? Какова вычислительная сложность и сложность по памяти для этой операции?
входной после выхода из функции пропадает
Что значит "пропадает"? Какова вычислительная сложность этой операции?
Более того, даже по этому описанию у вас не константа: в момент выполнения любого уровня рекурсии у вас задействовано как минимум O(n) дополнительной памяти — это та память, куда вы отобрали два меньших подсписка. И она удерживается, пока вы выполняете все вызовы рекурсии — а те тоже требуют дополнительную память.
Как вообще устроены списки в Эрланге с точки зрения модели операций? В частности, какова сложность операции "добавить один список в конец другого списка" (не зря же там ++ вместо |)?
Списки рекурсивны и состоят из головы и хвоста, который список.
Операция "конкатенации", должна быть n сложности,
и генераторы списков тоже добавляют свое n.
Это по операциям (хотя вы уже радикально превысили константу, которая в quick sort, но мы же в рамках О-большого, так что закроем на это глаза). Меня больше волнует память. Вы, например, знаете, что ++ создает еще одну копию? А сколько копий создается в list comprehension?
Ох. Ну вот давайте на примере. Вот входной список: [8 7 6 5 4 3 2 1 9]. На него выделено kn памяти (где n равно 9, и, будем честными, k раза в два больше, чем если бы вы работали с массивами, как в оригинальной сортировке). Это "внешняя" по отношению к вызову память, мы ей не управляем, и ее не считаем.
qsort([H|T]) ->
qsort([X||X<-T,X<H])++[H|qsort([X||X<-T,X>=H])].[H|T] = [8 7 6 5 4 3 2 1 9]
Здесь выделено констатное количество памяти на
H, аTпереиспользовано от входящего списка (слава иммутабельности).
[X||X<-T,X<H]
Результатом этого выражения будет
[7 6 5 4 3 2 1], это новый список (потому что его хвост отличается от хвостаT). Это еще минимум k(n-2) выделенной памяти (я пишу "минимум", потому что в реальности там рекурсивная функция, у которой свои накладные расходы еще есть).
qsort([7 6 5 4 3 2 1])
Результатом этого выражения будет
[1 2 3 4 5 6 7], и это ещеk(n-2)используемой памяти. Будем добрыми и предположим, что менеджер памяти Эрланга смог понять, что предыдущий список более не будет использоваться, деаллоцировал блок, и положил этот список на его место. Это добавило нам операций, но сократило добавленную память до одного k(n-2).
qsort([X||X<-T,X>=H])
Аналогично предыдущим шагам, мы получим здесь
[9]и еще k потраченной памяти (если мы добрые). Суммарные дополнительные накладные расходы по памяти, предсказуемо, k(n-1).
[8|[9]]
Выделили еще k памяти, потому что надо преобразовать
8в голову списка.
[1 2 3 4 5 6 7]++[8 9]
Здесь, в строгом соответствии с документацией, будет создана копия левого списка, на что выделено еще k(n-2) памяти.
Итого: накладные расходы на одном уровне — 2k(n-1). Это ну никак не константа, которая у типовой реализации, и даже не одинарный буфер, который у реализации с буфером. А дальше у вас начинается рекурсия, которая еще добавит вам расходов.
Иными словами, это решение ну никак не влезает в границы, которые у quick sort… то есть это не quick sort. Что, в общем-то, ожидаемо.
PS: А, вообще, за пролог спасибо!
- Поместите все, что меньше пивота, до пивота, а все, что больше пивота — после пивота.
Не понятно в этой записи, а что с самим пивотом происходит, он на месте остался?
Все, что меньше пивота — до пивота, все, что больше пивота — после пивота. Следовательно, пивот после этой операции должен быть в том месте, где это условие выполняется.
разместите элементы списка так, чтобы пивот оказался на том месте в массиве, что бы все меньшие были слева, а большие справа.
Или, еще точнее:
нужно обменивать между собой элементы справа и слева, до тех пор, пока два индекса справа и слева не встретятся…
Тогда, следовало бы писать:
разместите элементы списка так, чтобы пивот оказался на том месте в массиве, что бы все меньшие были слева, а большие справа.
Следовало бы писать "переместите элементы массива таким образом, чтобы все элементы, меньшие пивота, были слева от пивота, а все большие — справа".
Или, еще точнее:
нужно обменивать между собой элементы справа и слева, до тех пор, пока два индекса справа и слева не встретятся…
А вот это — не "точнее", потому что "слева и справа" от чего? Я, конечно, понимаю, что вы намекаете на Хоаровскую схему выделения пивота, но, во-первых, она не единственная, а во-вторых, там еще есть опущенные вами нюансы.
Тут wiki.haskell.org/Introduction#Quicksort_in_Haskell — пишут о выражении быстрой сортировки, и это она же.
Для декларативного выражения, стоит вводить другой термин «схема», «принцип», а алгоритм это строгость и однозначность, вы ее не показали указав четыре шага.
Это меня и интересует, много нюансов этого «алгоритма» упускаем, приводя его, а ведь алгоритм «должен быть» детерминирован.
Ну так он детерминирован. Его результат определен.
Когда же его можно назвать «быстрой сортировкой», если даже действия приведены не все, где операция swap().
А зачем ее приводить? Для этого псевдокод есть.
Тут wiki.haskell.org/Introduction#Quicksort_in_Haskell — пишут о выражении быстрой сортировки, и это она же.
Нет, не она же. Сравните с "true quicksort" по той же ссылке.
Для декларативного выражения, стоит вводить другой термин «схема», «принцип»,
Нет, не стоит. Зачем?
а алгоритм это строгость и однозначность
Понятие "однозначность" субъективно. В частности, вы никогда не видели алгоритмов, в которых сказано "отсортируйте"?
Хочу уточнить свой интерес, мне хотелось понять, а как именно у нас сохранен "в голове" тот алгоритм, или описание самой "быстрой сортировки". Мне интересно узнать, а как мы себе помним, что такое алгоритм.
Это последовательность императивность: 1,2,3,4:
- Выберите пивот.
- Поместите все, что меньше пивота, до пивота, а все, что больше пивота — после пивота.
- Повторите на участке до пивота
- Повторите на участке после пивота
Или мысль статична, декларативна:
Если у входного списка есть пивот и хвост [H|T], то
отсортированы он будет если ->
(отсортированы все элементы из Т меньшие пивота H) плюс сам пивот
плюс (отсортированы все большие пивота)
qsort()++[H]++qsort()
Ну, И Пустой [] список всегда отсортирован.
Это как вопрос, о сути субъективности, какой именно способ используем мы (мы как люди, наш мозг) для хранения этого алгоритма быстрой сортировки? )
мне хотелось понять, а как именно у нас сохранен "в голове" тот алгоритм, или описание самой "быстрой сортировки".
Я не могу сказать за всех людей, но я помню алгоритмы в виде последовательности. Потому что они по определению последовательность, и дают их в виде последовательности, и курсы по анализу алгоритмов оперируют последовательностями. Последовательность — это то, по чему можно определять интересующие нас характеристики алгоритмов (а это, сразу после корректности, метрики производительности).
Если у входного списка есть пивот и хвост [H|T], то
отсортированы он будет если
Массив считается отсортированным, если каждый последующий его элемент не меньше, чем текущий. Вот и всё. Только это не имеет отношения к алгоритмам.
Кстати, H — это не пивот, это голова. Просто вы выбрали ту стратегию, где за пивот выбирается нулевой элемент (и это, заметим, не лучшая стратегия).
Это тот признак удобнее, понятнее, нам не нужно доказывать таблицу умножения, теорему Пифагора, они и так понятны, они истинны. Какие расчеты там делал Пифагор, мы не интересуемся, также как и Хоар предложил "делить на меньшие и большие", вот основная идея, в рекурсивности и разделении, если делить большую задачу на мелкие, получаем в среднем сложность логарифма — это основной принцип этого быстрого (так сказать) алгоритма.
Другой алгоритм сопоставимый с быстрой, это алгоритм, звучит вот так:
Не делить список на меньшие и большие, а делить РОВНО пополам, а потом merge сливать отсортированные две части.
Это тоже алгоритм сортировки, и они очень похожи между собой. Но сложность последнего точно ровна log(n). И я только что не излагал последовательность сортировки слияниями))
Так какой способ представления, более доступен, понятен, и в каких областях? почему все понятно с SQL, HTML? а с алгоритмом в программе не так? Не про производительность, вычислительную сложность языка SQL, интересуются, людей привлекает абстракция, она заменяет собой большое количество деталей, о которых разработчику знать не нужно при решении задач...
нам не нужно доказывать таблицу умножения, теорему Пифагора, они и так понятны, они истинны
Я не знаю, кто эти "вы", кому не нужно доказывать теорему Пифагора. Меня в школе заставляли доказывать.
если делить большую задачу на мелкие, получаем в среднем сложность логарифма
Конечно, нет. Если делить большую задачу на мелкие, сложность в среднем не меняется. Она меняется только тогда, когда мы делим задачу определенным образом.
это основной принцип этого быстрого (так сказать) алгоритма.
Неа. Это вам кажется, что это его основной принцип. Но нет.
делить РОВНО пополам, а потом сливать отсортированные две части. Это тоже алгоритм сортировки
Это не алгоритм сортировки, потому что нет гарантии, что результат будет отсортирован. Потому что не определен термин "сливать".
Но сложность последнего точно ровна log(n)
Нет ни одного алгоритма сортировки (общего вида, конечно же) со сложностью log(n).
почему все понятно с SQL
А с ним "все понятно"? Или вы просто никогда не сталкивались со сложными его случаями?
Не про производительность, вычислительную сложность языка SQL, интересуются
Кто как. Меня вот сильно волнует производительность конкретной инструкции на SQL, когда я это строю. Потому что эта производительность в итоге влияет на то, могу я это выпустить в производство или нет.
большое количество деталей, о которых разработчику знать не нужно при решении задач...
Кому-то не надо. Кому-то надо. В этом как раз и крупное различие.
Так какой способ представления, более доступен, понятен, и в каких областях?
Это риторический вопрос, на него (очевидно) нет универсального ответа.
Очевидно у меня травма )) детства, но я читал в этой книге (Мейер, Бертран; Бодуен, Клод Методы программирования В 2 томах 1982г) вот такое:
Ну и что?
Принцип описанный тут целиком отображен в программе на Эрланге — она и была быстрой сортировкой, в которой основа разделяй и рекурсивно сортируй ))
Нет. Программа на Эрланге не реорганизует массив, она создает новый. И это ключевое отличие от "настоящего" quick sort.
Кстати, "разделяй и рекурсивно сортируй" — это заодно и сортировка слиянием, так что если вы хотите говорить именно о быстрой сортировке, вам нужен дополнительный определяющий признак.
почему все понятно с SQL
А с ним "все понятно"? Или вы просто никогда не сталкивались со сложными его случаями?
Для "сложных случаев" стандарт SQL постоянно расширяют… И не решив сложный запрос переписывать на for в for-е, никто не берется.
Получилось основное отличие императивной мысли от декларативной в "реорганизует" в возможности делать swap(). Тут была статья о реализации сортировки слияниями на лентах, от Фон Неймана, там при отсутствие возможности изменять значения на ленте, переписывали всегда все значения на промежуточные ленты.
Для "сложных случаев" стандарт SQL постоянно расширяют…
И что, остается "все понятно" после расширений?
Получилось основное отличие императивной мысли от декларативной в "реорганизует" в возможности делать swap().
Нет, совсем не в этом. Нет никакой проблемы записать перемену положений.
Другое дело, что те примеры, которые вы выдаете за "декларативную запись quick sort", ей не являются, вот и все.
Тут была статья о реализации сортировки слияниями на лентах, от Фон Неймана, там при отсутствие возможности изменять значения на ленте, переписывали всегда все значения на промежуточные ленты.
Эм. А вы точно вообще в курсе различий между сортировкой слиянием и быстрой сортировкой?
Начнем, что ли, с банального вопроса: какая вычислительная сложность у сортировки слиянием, и какая — у быстрой сортировки?
Если это важно то вот, привожу из Википедии:
Время работы алгоритма порядка O(n log n) при отсутствии деградации на неудачных случаях, которая является больным местом быстрой сортировки (тоже алгоритм порядка O(n log n), но только для среднего случая). Расход памяти выше, чем для быстрой сортировки, при намного более благоприятном паттерне выделения памяти — возможно выделение одного региона памяти с самого начала и отсутствие выделения при дальнейшем исполнении.
У нас понятие "алгоритма" может быть независимо от исполнителя, механически можно решать эту задачу, карандашом. Как, там было, "имплементации" присуща память и ее расход, не зря у машины Тьюринга бесконечная лента.
Важно не из википедии, важно из головы.
У нас понятие "алгоритма" может быть независимо от исполнителя, механически можно решать эту задачу, карандашом.
Ну да. Но для него все равно будут те же значения вычислительной сложности, что и для другого исполнителя, потому что вычислительная сложность считается в операциях.
Вот привели вы цитату из википедии, хорошо. Что из нее следует — mergesort лучше quicksort, или хуже? Когда надо применять один, а когда — другой?
И есть ли декларативная запись, содержащая ответы на эти вопросы? Или хотя бы просто позволяющая легко отличить один из этих алгоритмов от другого?
По принципу слияний видно, что деление входного списка происходит пополам, что приведет к рекурсивным вызовам глубины log(n) вне зависимости от данных,
а для быстрой сортировки нужно учитывать, что "неудачный" пивот или отсортированный входной массив заставят ее углубляться n раз.
В общем эти тру слияния можно представить похожим декларативным выражением на Эрланге:
msort([])->[];
msort(X)->{L,R}=split(X), merg(msort(L),msort(R)).По принципу слияний видно, что деление входного списка происходит пополам, что приведет к рекурсивным вызовам глубины log(n) вне зависимости от данных,
а для быстрой сортировки нужно учитывать, что "неудачный" пивот или отсортированный входной массив заставят ее углубляться n раз.
Ну то есть quicksort хуже, чем mergesort, и надо всегда использовать mergesort?
В общем эти тру слияния можно представить похожим декларативным выражением на Эрланге:
Неа, нельзя. Я могу написать такие имплементации split и merge, которые сделают из этого не merge sort, а quick sort. Или вообще случайный фильтр. Или сумматор. Или неизвестно что.
А еще это выражение ничем не отличается от сугубо императивного алгоритма:
- разбейте L на L и R
- отсортируйте L
- отсортируйте R
- слейте L и R
Так почему вы утверждаете, что оно декларативно, а не императивно?
А еще это выражение ничем не отличается от сугубо императивного алгоритма:
Спасибо, это я и пробую описать, мое описание можно дополнить и будет рабочая программа:
split([])->{[],[]};
split([A])->{[A],[]};
split([A,B|T])->{L,R}=split(T),{[A|L],[B|R]}.
Ну и merg:
merg([],[])->[];
merg(X,[])->X;
merg([],X)->X;
merg([A|T],[B|T1]) when A<B->[A|merg(T,[B|T1])];
merg([A|T],[B|T1])-> [B|merg([A|T],T1)].
Сколько придется думать, чтобы реализовать "алгоритм" слияния на императивном языке?
Разве так не проще?
Нет, не проще. Я из вашей "рабочей программы" не понимаю как работает split. А количество рекурсий, которые вы ввели, затрудняет анализ сложности алгоритма до невозможности.
merge(L,R):
until L.atEnd and R.atEnd:
if R.atEnd:
yield L.pop()
continue
if L.atEnd:
yield R.pop()
continue
if L.current < R.current:
yield L.current
else:
yield R.current
L.moveNext()
R.moveNext()Ну хорошо, вот об этом понимаю и речь, взгляд на алгоритм сортировки слияниями выраженный на С++ мне объяснит еще меньше, не знаю как кому…
Ну и, спасибо за беседу ))
взгляд на алгоритм сортировки слияниями выраженный на С++ мне объяснит еще меньше, не знаю как кому…
Вот именно поэтому в курсах обычно используют псевдокод. Если вы не умеете его читать...
как там выглядят sort, split?
А в них нет смысла, весь алгоритм прекрасно выражается одной процедурой.
mergesort(X):
N = X.length
L = mergesort(X[0:N/2])
R = mergesort(X[N/2:N])
until L.atEnd and R.atEnd:
if R.atEnd:
yield L.pop()
continue
if L.atEnd:
yield R.pop()
continue
if L.current < R.current:
yield L.current
else:
yield R.current
L.moveNext()
R.moveNext()Ну и я на всякий случай напомню вам, что ваша реализация на Эрланге — не декларативна.
константного расхода памяти?
Тут я, конечно, не прав: надо еще добавить расход памяти на рекурсию, поэтому логарифмический после оптимизации. Правильнее сказать: константный на каждом уровне.
import heapq
class Solution:
def trapRainWater(self, heightMap):
"""
:type heightMap: List[List[int]]
:rtype: int
"""
rows = len(heightMap)
if rows < 3:
return 0
cols = len(heightMap[0])
if cols < 3:
return 0
heap = []
for i in range(rows):
for j in (0, cols-1):
heap.append((heightMap[i][j], i, j))
heightMap[i][j] = None
for j in range(1, cols-1):
for i in (0, rows-1):
heap.append((heightMap[i][j], i, j))
heightMap[i][j] = None
heapq.heapify(heap)
water = 0
while heap: # iterate while heap has elements
max_height, i, j = heapq.heappop(heap)
for x, y in [(i, j + 1), (i + 1, j), (i, j - 1), (i - 1, j)]:
if (0 <= x < rows) and (0 <= y < cols):
height = heightMap[x][y]
if height is None:
continue
if height >= max_height:
heapq.heappush(heap, (height, x, y))
else:
water += max_height - height
heapq.heappush(heap, (max_height, x, y))
heightMap[x][y] = None
return water
Это формализация, да тут одни heappush()… это разве понятно?
Кто предоставит алгоритм для сравнения?
Использование пролог в реальных системах натыкается на 2 основных проблемы:
1 нельзя предугадать дерево поиска решения
2 можно попасть в класс задач, которые эффективно вообще не решаются.
В связи с 1 к сожалению для реальных объемов данных шансов получить прогнозируемый ответ нет.
В связи с 2 есть интеграция пролога с правильными решателями?
К решателям можно относить вот такие
clp(fd) is one of several constraint solvers available in SWI-Prolog. The others are clp(b), clp(qr) and CHR. clp(b) handles booleans. clp(qr) handles rationals and reals. CHR approaches constraint programming differently, using rewrite rules.
А управление выводом доступно, это разная формулировка задачи...
Забудем о способах хранения данных в прологе.
Списки списков — это всего лишь способ подать данные на вход, а внутри мы вообще что угодно можем сделать, хоть битовый вектор, если нам это окажется удобнее…
Посмотрим чисто математически. ДЕКЛАРАТИВНО.
Пусть у нас есть функция высоты ландшафта от координат — h(x,y). Она задана таблицей.
Расширим область её определения за пределы прямоугольника: h(x,y)=0 для всех x,y извне.
Почему 0, а почему бы и нет, ведь исходно область значений строго больше 0.
Рассмотрим максимальную высоту h1 = max(h) и предшествующую ей высоту h2.
Составим карту горизонта h2: покрасим точки в признак "выше-ниже"
Устроим всемирный потоп до уровня h2. А потом ещё сверху польём воду на наш остров…
Что мы только что сделали? Да, на самом деле, мы сформулировали примитивную подзадачу!
Есть карта местности: клетки высотой 0 и 1 попугай (где 1 попугай равен h2-h1 метров), и периферия высотой 0
Сколько воды сможет удержаться на таком двоичном ландшафте, если вылить один попугай осадков?
Как решить эту задачу?
- Отбросим всю периферию и все клетки высоты 0, смежные с периферией
- Оставшиеся клетки высоты 1 — это стенки колодцев, а высоты 0 — это донья колодцев
- Помножим площадь доньев, то есть, количество 0-клеток, на высоту стенок, то есть, на 1 попугай, или на h2-h1 метров.
Отлично. Это мы посчитали объём воды в слое h1-h2.
Перейдём чуть ниже, к следующей высоте h3, и рассмотрим слой h2-h3.
Опустим уровень всемирного потопа до h3.
Есть двоичная карта местности: клетки высотой 0 (это которые h≤h2) и 1 (h>h2)
только попугай теперь равен h3-h2
Сколько воды удержится на таком ландшафте, если вылить один попугай осадков?
То же самое. Отбросим всю периферию, после чего отбросим все стенки, и посчитаем площадь доньев. Помножим на h3-h2.
Ну и продолжим упражняться в томографии!
Что интересно, для этого интегрирования по сечениям нам всё равно, откуда куда перебирать высоты. Каждое сечение даст независимый результат, а потом мы их просуммируем.
Декомпозиция задачи на независимые подзадачи — рай декларациониста!
Но сейчас я предложу одно улучшение, переворачивающее задачу вообще с головы на ноги.
Вот каждый срез томограммы — это битовая карта. Но мы из двоичного признака "высоко-низко" делаем троичный "океан-стенка-дно". А как бы нам остаться в двоичности?
Внимание, фокус!
Давайте пойдём от самой маленькой высоты к самой большой.
h1, h2, ..., hm = sort(h) по возрастанию.
Мы говорили, что нам пофиг на порядок, вот пусть теперь будет такой порядок, и сейчас станет непофиг.
Зальём океан бетоном до уровня 0. Ну, как бы ничего не произошло, океан и так был залит бетоном до этого уровня.
Поехали дальше.
Зальём до уровня h1. Да, периферия поднялась, но мы-то знаем, что h1 — это минимум миниморум, это ничем не отличается от ситуации с уровнем 0.
Зальём до уровня h2. А вот тут происходит что-то интересное! Часть клеток нашего острова оказывается забетонирована — это те клетки высоты h1, которые соседствовали с периферией.
Вроде бы, по-прежнему ситуация троичная: донья, стенки, бетонный океан.
Но, на самом деле, тут две двоичных карты: остров посреди бетонного океана, и низины-высоты этого острова. Из одного трита сделали два бита, притом, что один бит вычисляется из функции ландшафта: b2(x,y) = h(x,y)<h2. (b — bottom). Ну а c2(x,y), конечно, придётся найти руками (c — concrete).
Ну и находим площадь маски b2 & ~c2 и помножим на толщину среза h2-h1
Вроде бы, и что же мы тут выгадали? Как была работа со срезом томограммы, так и то же самое сделали? А вот пойдём дальше!
Зальём до уровня h3.
Очевидно, что с3(x,y) ≥ c2(x,y), — если на втором горизонте где-то плескался бетон, то и на третьем он тоже будет. Ну и ещё немного соседних клеток зальёт. То есть, мы не с дальних краёв начинаем заливку среза, а где в прошлый раз остановились.
Аналогично, у нас есть битовая функция b3(x,y) = h(x,y)<h3, — находим маску, площадь и объём в срезе.
И так далее, пока не утопим в бетоне весь наш остров, и все низинки в нём не сделают свой прощальный бульк.
Сделаем оценку трудозатрат.
Если остров имеет габариты X*Y, то вся площадь N=X*Y.
Соответственно, у нас не более N разных высот.
Для заливки каждого слоя, — если мы будем вести береговую линию — множество краевых точек заливки, — потребуется в худшем случае посетить каждую точку по 4 раза, а сама береговая линия может быть как угодно изрезана и содержать тоже O(N) точек.
В общем, на заливку мы потратим O(N) времени.
Для измерения площади по маске — там у нас тотальный забег по N точкам, ну или если нам больше делать нечего, то можем завести множество ещё-не-залитых, которое будет потихоньку сокращаться.
Всего O(N) слоёв, в каждом из которых тратим O(N) времени.
Ну что же, дело пахнет квадратичным алгоритмом!
Пользуясь случаем, передаю привет прологу с его экспонентами и факториалами, которые на ровном месте может организовать юный падаван, пишущий наивные алгоритмы...
Ну что же! Принимайте мой говнокод на эрланге-поверх-пролога :)))
https://swish.swi-prolog.org/p/flood_and_wells.pl
% забег по списку с нумерацией (от 1)
maplisti(Goal, List, Results) :-
length(List, N),
numlist(1, N, Indices),
maplist(Goal, List, Indices, Results).
% Маленький хак: поскольку мы знаем ограничение на координаты
% (не более 110 каждая),
% то будем кодировать их числом вида X*1000+Y
% Это позволит нам использовать словари
% - более-менее эффективные реализации таблиц
xy(X,Y,XY) :- XY is X*1000 + Y.
x_y(X,Y,XY) :- X is XY div 1000, Y is XY mod 1000.
% Строим словарь-ландшафт из данных (списка списков)
make_landscape(RowsOfHeights, Landscape) :- % [[H]] -> h{XY:H}
maplisti(
[RowOfHeights,Y,RowOfXYHs] >>
maplisti(
{Y}/[H,X,XY-H] >> xy(X,Y,XY),
RowOfHeights, RowOfXYHs),
RowsOfHeights, RowsOfXYHs),
append(RowsOfXYHs, XYHs),
dict_create(Landscape, h, XYHs).
% Смещения в разных направлениях (запад, восток, север, юг)
shift(w,XY,XY1) :- x_y(X,Y,XY), X1 is X-1, X1>=0, xy(X1,Y,XY1).
shift(e,XY,XY1) :- x_y(X,Y,XY), X1 is X+1, xy(X1,Y,XY1).
shift(n,XY,XY1) :- x_y(X,Y,XY), Y1 is Y-1, Y1>=0, xy(X,Y1,XY1).
shift(s,XY,XY1) :- x_y(X,Y,XY), Y1 is Y+1, xy(X,Y1,XY1).
% Строим первичную заливку - клетки, соседние с ландшафтом, но не являющиеся им
make_flood(Landscape, Flood) :- % h{XY:H} -> f{XY:0} - dict в роли множества
dict_pairs(Landscape, _, XYHs),
foldl(
{Landscape} / [XY-_, F0, F1] >>
(
foldl(
{Landscape, XY} / [D, Fd0, Fd1] >>
(
shift(D, XY, XY1),
% берём соседнюю клетку,
% и если она не входит ни в ландшафт, ни в заливку
not(get_dict(XY1, Landscape, _)),
not(get_dict(XY1, Fd0, _)),
% то добавляем её туда
put_dict(XY1, Fd0, 0, Fd1),
!
;
% иначе оставляем словарь как есть
Fd1 = Fd0
),
[w,e,n,s], F0, F1)
),
XYHs, f{}, Flood).
% заливка на новый уровень - это более хитрая процедура:
% берём каждую точку старой заливки и пытаемся залить соседние клетки ландшафта,
% причём повторяем рекурсивно
flood_new_level(Landscape, H, Flood, Flood1) :-
dict_pairs(Flood, _, XY0s),
foldl(
{Landscape, H} / [XY-_, F0, F1] >>
flood_new_cell(Landscape, H, XY, F0, F1),
XY0s, Flood, Flood1).
% операция рекурсивной заливки от заданной точки
flood_new_cell(Landscape, H, XY, F0, F1) :-
foldl(
{Landscape, H, XY} / [D, Fd0, Fd2] >>
(
shift(D, XY, XY1),
not(get_dict(XY1, Fd0, _)),
get_dict(XY1, Landscape, H1),
H1 < H,
put_dict(XY1, Fd0, H, Fd1),
flood_new_cell(Landscape, H, XY1, Fd1, Fd2),
!
;
Fd2 = Fd0
),
[w,e,n,s], F0, F1).
% площадь колодцев горизонта H0 после заливки бетоном
flat_of_horizon(Landscape, H0, Flood, Square) :-
dict_pairs(Landscape, _, XYHs),
convlist(
{H0,Flood} / [XY-H, 1] >>
(H < H0, not(get_dict(XY,Flood,_))),
XYHs, Bottoms),
sumlist(Bottoms, Square).
% формируем упорядоченный список горизонтов
make_heights(Landscape, Heights) :-
dict_pairs(Landscape, _, XYHs),
maplist([_-H, H] >> true, XYHs, Hs),
sort(Hs, Heights).
% находим итоговый объём
find_volume(Data, Volume) :-
make_landscape(Data, Landscape),
make_heights(Landscape, Heights), writeln('heights '=Heights),
make_flood(Landscape, Flood0),
% постепенно заливаем горизонты бетоном и измеряем площади и объёмы колодцев
foldl(
{Landscape} / [H1, H0:F0:V0, H1:F1:V1] >>
(
flood_new_level(Landscape, H1, F0, F1),
flat_of_horizon(Landscape, H1, F1, S),
V is S*(H1-H0),
V1 is V0+V,
true
),
Heights, 0:Flood0:0, _:_:Volume).
% считаем и измеряем скорость
main(Data) :-
get_time(T0),
find_volume(Data, V),
get_time(T1),
DT is T1-T0,
writeln('solution is ':V:' takes ':DT)
.Вызывать так:
:- main([
[19528,15189,18872,19908,19958,10498,18036,18808,17753,16248],
[13303,3333,2133,1648,2890,9754,7567,1746,368,9529],
[14500,8046,3788,9797,6249,6990,3303,3033,5363,2497],
[10253,4892,7686,9125,1152,3996,5975,9188,9157,3729],
[15436,2460,3414,3921,460,6304,28,8027,8050,6748],
[17556,8902,4794,7697,8699,1043,1039,2002,428,6403],
[14500,681,7647,8538,6159,5151,2535,2134,4339,1692],
[12215,6127,504,5629,49,964,8285,6429,5343,6335],
[13177,2900,5238,7971,6949,289,5367,7988,2292,5795],
[10743,3144,2829,8390,1682,5340,3541,569,3826,4232]
]).Время работы — десятки миллисекунд!
Это, конечно, тоже "меньше секунды", но, полагаю, автор говорил об ином масштабе своих достижений :)))
Мне указывали на «непонятность» решения, а тут я потерялся…
По скорости, конечно, замечательно, но разве не «привлекательнее» меньше писать и детализировать. Это же решение с последовательным алгоритмом, для этого и структуры потребовались соответствующие, а мое _тяготеет_ к описанию задачи.
На сколько эффективное решение должно быть далеко от исходной формулировки?
«Решатель» справляется не плохо и имеет прозрачный вид,
вот, сопоставил времена(так две колонки вставились):
1. clp 2.flood_and_wells
goal->ok:1/msec goal->ok:1/msec
goal->ok:0/msec goal->ok:1/msec
goal->ok:1/msec goal->ok:2/msec
goal->ok:0/msec goal->ok:3/msec
goal->ok:0/msec goal->ok:1/msec
goal->ok:0/msec goal->ok:0/msec
goal->ok:1/msec goal->ok:1/msec
goal->ok:0/msec goal->ok:0/msec
goal->ok:0/msec goal->ok:2/msec
goal->ok:2/msec goal->ok:2/msec
goal->ok:1/msec goal->ok:7/msec
goal->ok:0/msec goal->ok:1/msec
goal->ok:0/msec goal->ok:0/msec
goal->ok:0/msec goal->ok:1/msec
goal->ok:1/msec goal->ok:2/msec
goal->ok:0/msec goal->ok:1/msec
goal->ok:0/msec goal->ok:1/msec
goal->ok:4/msec goal->ok:6/msec
goal->ok:5/msec goal->ok:5/msec
goal->ok:3/msec goal->ok:6/msec
goal->ok:3/msec goal->ok:5/msec
goal->ok:5/msec goal->ok:6/msec
goal->ok:23/msec goal->ok:68/msec
goal->ok:259/msec goal->ok:68/msec
goal->ok:97/msec goal->ok:69/msec
goal->ok:60/msec goal->ok:67/msec
goal->ok:25/msec goal->ok:65/msec
[1103,536,101,990,966,883,872,180,1006,291,315,935,94,337,346,515,856,739,323,867,134,905,592,555,824,377,444,374,53,760,97,818,286,188,798,594,413,661,764,409,942,70,686,378,749,22,236,596,104,549],
[1105,580,444,388,477,611,107,912,327,502,662,766,311,290,296,451,875,699,454,629,450,739,41,127,107,781,491,685,719,937,577,866,507,363,596,975,316,693,229,634,538,881,742,839,513,29,280,378,718,725],
[1100,159,806,733,628,255,856,461,931,565,389,498,774,238,851,360,203,510,44,774,134,924,997,866,753,501,237,375,869,946,442,561,447,238,285,417,484,131,868,405,39,247,245,803,828,438,153,21,938,539],
[1106,414,453,773,623,548,616,850,914,828,138,698,379,927,927,1006,334,753,480,193,500,509,782,735,654,600,515,149,964,796,679,92,552,474,207,517,365,814,358,621,632,838,309,353,756,578,350,432,321,820],
[1105,811,671,740,888,315,330,746,454,636,532,475,718,426,292,268,934,647,72,634,610,46,462,909,389,560,478,81,983,141,891,940,943,904,670,173,209,991,909,1006,969,783,823,678,200,105,936,476,94,350],
[1100,694,386,552,946,117,455,766,189,428,897,422,358,182,669,19,346,220,352,597,216,311,723,382,331,265,829,609,731,914,949,821,950,677,715,238,137,160,994,668,930,234,432,279,406,91,640,94,302,982],
[1102,860,635,395,232,309,650,52,908,723,308,200,534,600,219,591,829,346,742,165,1004,14,389,779,283,786,860,265,870,152,589,894,1003,215,631,577,514,623,971,764,336,269,954,212,212,516,794,31,852,878],
[1108,199,882,918,968,508,46,818,763,258,313,343,143,658,900,764,577,756,378,539,510,56,798,807,259,1000,313,43,373,507,263,902,696,135,162,1006,985,198,167,739,446,470,424,931,470,314,38,37,60,758],
[1106,912,804,707,709,53,49,12,438,413,510,691,657,548,169,161,545,144,349,702,225,137,514,639,59,974,295,439,353,345,187,910,248,981,959,299,377,998,302,805,753,154,839,400,692,350,551,579,836,242],
[1101,52,370,127,33,771,91,319,200,435,1006,377,687,244,700,636,534,67,624,178,215,368,322,396,110,356,736,1004,926,562,588,539,956,300,657,980,61,90,641,603,867,637,322,896,224,365,522,100,422,489],
[1100,979,199,284,365,651,630,443,997,898,348,576,780,294,866,427,616,270,859,247,215,69,227,528,955,793,883,468,883,647,299,493,617,488,767,324,481,739,110,469,628,448,35,398,84,243,167,691,503,368],
[1100,709,427,849,579,373,632,804,183,857,441,472,692,400,302,801,67,125,531,167,584,501,957,961,241,31,547,750,64,40,108,335,91,526,526,12,241,149,806,414,348,590,228,31,980,872,822,389,987,695],
[1106,914,186,493,217,769,867,754,509,921,137,960,246,570,828,115,573,59,254,721,815,944,301,385,965,624,599,778,1003,928,815,892,832,992,727,40,103,584,136,603,496,263,553,84,824,723,189,387,772,785],
[1108,929,720,742,304,27,356,245,147,701,163,953,583,338,935,301,720,28,227,846,973,65,100,868,140,914,581,671,643,695,799,83,614,861,815,260,878,513,495,16,205,649,959,130,977,236,773,687,606,991],
[1105,570,46,965,780,528,221,352,542,206,389,331,280,994,182,437,244,50,293,82,408,840,73,357,960,40,583,724,69,532,57,934,92,445,242,214,964,453,908,496,650,288,169,272,272,693,51,858,733,334],
[1102,132,164,345,831,467,375,757,181,786,279,228,711,713,663,943,917,969,738,816,807,730,94,318,344,708,1001,386,908,725,62,181,199,569,516,20,26,234,119,549,10,388,119,63,91,124,348,999,436,77],
[1107,233,797,241,542,132,291,885,860,189,600,264,360,141,823,867,504,191,91,613,730,443,992,191,497,425,306,835,414,732,902,561,307,42,144,191,516,425,67,718,605,1009,972,307,493,786,164,987,319,597],
[1102,392,31,276,573,870,692,221,695,96,295,940,1000,593,324,486,126,830,902,535,538,849,535,500,146,370,628,653,347,938,592,631,320,965,898,235,825,580,447,863,18,732,793,360,667,107,837,136,279,81],
[1101,159,920,538,649,408,898,620,403,587,900,986,209,562,941,97,787,109,667,576,962,27,651,745,378,308,194,205,786,815,276,438,964,538,318,603,288,207,565,682,784,455,10,335,1007,293,422,137,392,431],
[1103,344,449,344,431,169,995,967,364,771,772,982,551,726,862,860,672,492,409,227,164,183,25,516,861,374,800,273,501,182,47,547,869,838,881,290,997,866,600,351,980,362,675,521,79,527,371,93,361,122],
[1100,516,648,677,374,499,42,164,114,885,689,151,422,548,979,646,180,966,854,770,659,824,475,324,336,896,193,49,979,545,162,631,403,800,299,119,641,683,274,745,558,305,887,323,843,208,959,365,165,803],
[1108,166,970,943,833,296,181,368,687,150,255,191,771,1000,333,60,110,964,85,374,52,634,669,929,299,854,479,248,561,986,393,29,143,353,314,966,991,485,676,21,977,922,202,739,912,878,141,12,184,217],
[1108,226,193,387,497,482,583,967,72,135,943,807,506,428,151,163,736,484,990,403,495,958,315,40,39,569,908,170,572,434,729,290,651,912,20,490,736,593,799,150,718,733,948,567,503,441,720,230,915,700],
[1103,401,648,280,431,677,839,681,190,753,105,909,34,98,164,396,579,242,979,720,383,40,443,673,597,289,104,659,509,361,349,474,752,340,96,525,359,925,196,891,21,644,143,397,732,297,783,653,529,752],
[1104,254,134,149,269,73,428,363,722,279,715,414,743,809,744,829,325,445,97,863,679,460,497,812,847,572,99,620,215,970,714,921,567,839,413,826,902,831,532,615,453,589,371,538,388,457,710,55,892,797],
[1109,561,599,396,363,436,958,804,46,516,117,102,427,674,931,830,490,176,1004,364,133,447,943,494,327,322,941,27,719,175,166,618,79,755,1005,432,181,305,579,569,811,686,662,581,350,935,753,182,101,99],
[1107,576,888,822,60,206,134,343,223,196,509,380,804,578,125,151,352,649,447,273,208,600,949,212,523,641,138,267,814,581,356,693,148,235,505,550,431,982,236,644,168,735,366,962,655,482,456,349,121,893],
[1103,671,835,552,226,349,184,354,606,340,277,304,23,767,529,870,660,302,842,886,289,1000,963,645,305,608,117,751,947,580,986,550,594,811,93,810,502,619,506,450,949,773,745,314,883,616,174,533,261,359],
[1101,540,349,714,175,996,312,635,89,601,557,417,494,141,571,929,941,63,538,437,504,829,553,591,133,778,197,649,653,448,998,404,330,690,108,496,28,762,473,108,705,20,515,189,152,76,108,435,482,988],
[1103,976,807,758,557,282,526,96,922,169,887,910,563,207,942,13,45,961,117,508,59,164,871,916,344,13,335,794,438,807,773,643,125,570,391,24,195,907,110,107,418,339,359,323,889,644,326,924,595,785],
[1105,996,940,636,902,626,639,579,762,419,376,525,405,843,438,786,857,623,36,310,72,796,639,773,110,518,407,426,785,992,554,550,330,836,528,575,804,509,144,556,918,863,72,313,696,852,442,544,817,820],
[1104,879,606,825,994,706,334,392,475,461,726,371,353,47,197,871,612,991,370,98,889,630,951,303,934,638,145,718,172,952,880,1006,173,476,821,510,525,497,244,342,300,960,703,643,349,890,504,303,223,864],
[1102,454,485,333,748,761,961,883,821,475,178,691,823,693,509,987,545,24,474,779,356,117,82,401,750,421,633,597,67,846,803,449,291,630,124,381,381,428,606,544,893,774,577,707,810,77,684,345,443,500],
[1107,142,959,539,533,700,302,157,639,359,345,432,150,978,53,265,349,776,35,946,663,270,62,230,967,214,297,993,550,731,836,1007,215,137,888,738,179,180,237,808,530,573,231,670,893,626,277,233,392,302],
[1101,45,563,573,618,872,778,905,208,670,978,386,19,183,513,897,264,683,67,491,833,939,406,54,952,290,22,219,865,757,864,376,144,769,291,752,983,411,648,181,423,968,909,432,494,765,671,100,790,81],
[1103,613,10,330,10,952,962,22,514,817,769,368,535,904,127,168,646,100,570,636,624,983,947,875,758,431,630,419,873,410,842,796,14,843,468,366,137,420,378,641,579,138,351,456,384,468,615,20,911,175],
[1109,877,500,936,742,248,709,715,10,572,467,842,358,471,27,817,179,507,579,548,138,149,28,480,595,402,290,552,764,543,717,753,410,560,31,495,798,730,200,150,644,657,335,993,471,704,152,640,201,73],
[1100,330,564,548,152,502,940,432,44,695,318,104,790,718,654,812,555,794,532,97,935,167,745,612,502,558,306,996,540,850,59,61,522,966,599,664,458,882,438,492,567,98,586,347,807,230,149,704,15,24],
[1102,292,533,879,246,25,427,894,363,309,734,764,360,246,720,302,252,168,174,33,651,731,121,579,420,270,800,912,965,157,926,99,791,449,968,27,816,385,911,521,684,988,275,387,576,986,679,171,144,843],
[1106,137,916,1009,707,326,270,849,580,577,996,496,18,777,287,976,146,445,703,47,956,729,377,222,106,944,550,127,105,684,960,641,812,218,640,861,535,252,700,457,171,686,944,179,805,573,145,941,361,190],
[1100,307,910,698,871,1006,984,411,124,79,438,426,62,592,635,692,443,512,287,133,959,800,161,245,970,956,809,457,239,512,638,559,809,538,599,23,886,573,776,1000,994,204,769,46,786,394,81,219,248,710],
[1104,549,500,845,785,460,791,936,260,372,438,888,274,589,768,863,954,644,779,721,987,115,267,746,152,44,482,575,605,720,275,642,259,117,477,386,568,611,312,170,973,92,48,237,24,806,443,968,440,564],
[1109,417,669,937,505,811,323,977,728,270,39,345,902,641,453,722,17,363,323,672,523,638,106,561,866,120,709,651,79,491,205,100,899,864,379,746,18,692,714,736,305,743,424,197,374,867,261,734,220,574],
[1108,733,203,844,636,411,955,335,404,376,816,599,466,57,805,836,794,813,870,850,892,165,583,658,705,300,515,956,376,77,873,114,800,418,300,778,171,245,103,565,611,261,154,420,661,301,598,445,457,458],
[1105,691,966,210,339,661,852,844,959,570,911,174,674,53,582,965,821,743,552,266,650,506,869,146,268,520,438,856,307,885,304,934,566,260,135,895,263,329,81,565,890,334,729,906,377,654,213,540,739,756],
[1106,380,604,655,868,862,518,296,708,815,523,354,740,431,957,217,668,210,888,739,117,768,63,189,17,782,185,220,312,914,318,450,636,912,96,495,116,956,133,814,761,647,511,843,420,458,402,79,10,281],
[1100,118,391,566,297,398,338,472,961,993,728,269,433,355,524,871,192,982,817,667,139,921,304,640,754,67,88,147,136,88,770,638,196,151,194,835,892,875,649,843,858,368,454,633,65,320,495,599,293,654],
[1106,422,565,903,52,310,960,130,799,438,560,559,66,747,52,251,924,934,468,564,119,668,274,564,291,329,226,128,270,509,773,516,273,328,409,315,980,711,787,121,139,338,22,196,427,65,789,693,989,599],
[1107,99,257,863,1005,890,534,221,1009,794,721,124,653,336,794,52,642,117,106,771,228,235,451,241,773,220,296,904,904,627,845,493,68,92,347,63,325,223,627,324,1008,690,790,651,16,574,45,648,33,141]],
sums(X,353397).
Моя программа переварила его за 9 секунд.
Там размер ландшафта — 50*50, а количество горизонтов — 916.
Насчёт непонятности — это, возможно, из-за моей любви к ФВП.
Просто стоит натренировать взгляд и научиться выделять операции проекции и свёртки списка — maplist, convlist, foldl — в своих задачах.
Да, там появляются лямбды, но зато пропадает копипаста этих же самых алгоритмов руками.
В решателя я ещё не вкурил, но думаю, что и его можно разогнать до нормальных скоростей, если правильно сформулировать задачу.
К сожалению, ряд задач очень легко формулируется в неполиномиальном виде, при том, что есть полиномиальные решения, но они "эвристические".
Например, нахождение определителя матрицы — наивное определение факториальное (просуммировать произведения всех перестановок), а техничное — методом Гаусса или LU-разложения — квадратичное. Есть разница, да?
Или сортировка массива. К сожалению, Дональд Кнут опубликовал спойлер, что сортировку можно и нужно делать за логлинейное время, и алгоритмы такие уже известны, — поэтому народ изгаляется, решает противоположную задачу: как максимально затупить сортировку.
Но вот представьте себе — чисто по-проложьему — что предикат msort(Arbitrary,Sorted) умеет делать всё:
- (+Arbitrary, -Sorted) — за логлинейное время рожает сортированный список
- (+Arbitrary, +Sorted) — за логлинейное (был бы произвольный доступ — за линейное) время проверяет соответствие
- (-Arbitrary, +Sorted) — рожает произвольные перестановки (затрачивая на каждую линейное время, по алгоритму Кнута)
- в составе Arbitrary часть элементов не определена — рожает перестановки только над ними
- часть элементов не определена и там, и там — рожает перестановки с дырками и частично упорядоченные списки
Получится ли сделать это единообразно? И, одновременно, эффективно?
Имхо, проще объявить предикат-фасад и внутри него делать ветвление по наличию данных.
Потихоньку вкуриваю в CLPFD.
Вот написал наивный решатель. Возможно, он эквивалентен вашему, — но я постарался давать человекочитаемые имена предикатам и заменять хардкоженную рекурсию на мап-фолд.
https://swish.swi-prolog.org/p/solve_wells.pl
Он так же отчаяннно тупит на тяжёлых случаях.
А всё потому, что в модели нет представления о стекании жидкости, — только об уровнях.
Фактически, модель выдаёт решения — сколько жидкости в принципе может удержаться на ландшафте, если сверху больше-меньше побрызгать. И из этих решений мы должны взять наибольшее.
Буду дальше думать, как поизящнее ввести слив, в терминах решателя.
Используем Пролог