Используем Пролог
Эй, фулстеки, давайте тренировать навыки. Предлагаю разминать извилины, как мне кажется, это интересно делать используя иную, непривычную, парадигму. Большинство разработчиков имеют развитой скилл алгоритмизации — задача превращается в кирпичики, которые нужно соединить, продумать последовательность ходов, которая приводит к желаемому заключению.
Вот тут, неделю назад, был упомянут Пролог, хотелось бы ответить, что язык Пролог подходит для решения задачек. Я уже затрагивал эту тему, и приводил несколько доступных мне решений случайных задач с сайта с заданиями на алгоритмы, хотелось бы показать, что любое сложное решение доступно изложению на декларативном языке, да и работать оно может не медленнее (ну-у, может, заметно не очень медленнее).
Взяться за представления следующей задачки долго не получалось, и вот уже получено первое решение, демонстрирую задачу и узнаю, на сколько оно сильно медленно.
Пролог интересен тем, что можно сотворить дедуктивную программу, которая показывает множество решений и может даже ограничивать его, но не дает способ перебора,
алгоритм будет выработан решателем интерпретатором.
Так вот, задача такова:
- Trapping Rain Water II
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.
Note:
Both m and n are less than 110. The height of each unit cell is greater than 0 and is less than 20,000.
Example:
Given the following 3×6 height map:
[
[1,4,3,1,3,2],
[3,2,1,3,2,4],
[2,3,3,2,3,1]
]
Return 4.
После продолжительных попыток сформулировать решение, я дошел до вот такой формулировки:
Нужно в каждую клеточку налить максимум воды, который бы из нее не вылился. Я предлагаю залить в каждую клеточку, какое-то количество воды, но так чтобы оно было менее равно максимально значения из всех возможных.
Получилось так:
reptest(X0,X2):-
flatten(X0,FX0),
sort(0,>,FX0,Vals),
repdown(X0,Vals,X0,X2),!.
этот предикат берет входной список (матрицу), и превращает ее в решение, в матрицу, в которой стоят другие значения, которые будут допустимым ответом. Потом другой предикат эти два списка отнимет поэлементно и найдет итоговую сумму.
repdown(X0,Vals,X,X1):-
puts(Vals,X0,X1),
X\=X1,
balns(X0,X1),!.
repdown(_,_,X,X).
этот предикат будет брать одно из решений, и проверять «нормально» ли оно заполнено, если удовлетворяет условию задачи, тогда это и есть решение.
Это метод «генерировать и проверить», мы говорим что величина в таком-то множестве и пересматриваем все элементы этого множества, проверяя какое-то условие выхода.
Значит, далее предикатом puts (Vals, X0, X1) буду получать новое решение, здесь на первом месте стоит список всех возможных значений высот, которые есть в этой матрице, из него будут выбираться возможные значения высот для каждой клеточки. По анализу входных тестов, было выяснено, что в этой задаче можно залить всю клеточку, если вокруг нее можно вставить столько воды, что ее переливает «с головой».
Итого этот предикат, выглядит посложнее, надо обработать тройки строк, из которых складывается один квадрат 3×3 (да-да в Прологе нет массива, но так выглядит описание входных данных, так этим и пользуемся, в декларативном программировании можно не знать про индексы элементов в массиве, тут есть только список с его головой и хвостом, поэтому просто описываем такой шаблон, который соответствует входной спецификации).
puts(_,[],[]).
puts(_,[X],[X]).
puts(_,[X,Z],[X,Z]).
puts(V,[R1,R2,R3|T],[R1|St]) :- number(R2),!,sel_biger(R2,V,R21),puts(V,[R21,R3|T],St).
puts(V,[R1,R2,R3|T],[R1|St]) :- puts(V,R2,R21),puts(V,[R21,R3|T],St).
Вот так получается выразить обход матрицы, у которой можно взять три первых (и далее) строки, у которых, также можно выделить, слева-направо, тройки элементов, и вот между восемью соседями окажется одна [Итая][Ётая] клеточка ландшафта. С помощью sel_biger (R2, V, R21) делается новое значение этой клеточки:
Это значение можно установить текущей клеточке, оно может быть одной из возможных высот, да еще и список их отсортирован по-убыванию, так что первой будет наибольшая высота, которая доступна вообще, а далее любая за ней:
sel_biger(C,[H|_],H):-H>=C.
sel_biger(C,[_|T],X):-sel_biger(C,T,X).
Это было описание «генератора решений», а далее надо убедиться, что получена матрица, из как угодно заполненных высот в каждой точке, похожа на требуемый от нас ответ.
А требовалось найти такое состояние, что вода осядет в лунках, попробую выразится вот так:
из девяти значений квадрата три на три, в центре всегда должна быть такая высота, чтобы она не противоречила входной карте, чтобы не получалось изменение баланса, который был изначально в этих клеточках, если была высота, то выше нее не должно остаться клеточек, даже если все зальет водой, тогда тут можно говорить, что высокая клеточка должна оставаться собой или быть заменена на более высокое значение, но такое что оно равно всем соседям, т.е. клеточки слева-справа и сверху-снизу от текущей должны ее превышать или быть равны, если в клеточке стало более воды, то только если и вокруг поднялась…
%%проход по строкам
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]).
%%из трех строк выбираем по тройке, для создания квадрата 3х3
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(_,[],_,[]):-!.
equ(C,_,C,_):-!.
equ(C0,_,C,N):-C>C0,!,findall(X,(member(X,N),X
И финальные два предиката, которые берут входную матрицу, запускают поиск подходящего результата, вычитают сумму элементов между собой, и находят конечную сумму, которая требовалась в задаче:
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):-reptest(X,X1),diffall(X,X1,S).
Продемонстрирую тесты, которые предоставил сайт.
reptest(X0,X2):-
flatten(X0,FX0),
sort(0,>,FX0,Vals),
repdown(X0,Vals,X0,X2),!.
repdown(X0,Vals,X,X1):-
puts(Vals,X0,X1),
X\=X1,
balns(X0,X1),!.
repdown(_,_,X,X).
puts(_,[],[]).
puts(_,[X],[X]).
puts(_,[X,Z],[X,Z]).
puts(V,[R1,R2,R3|T],[R1|St]) :- number(R2),!,sel_biger(R2,V,R21),puts(V,[R21,R3|T],St).
puts(V,[R1,R2,R3|T],[R1|St]) :- puts(V,R2,R21),puts(V,[R21,R3|T],St).
sel_biger(C,[H|_],H):-H>=C.
sel_biger(C,[_|T],X):-sel_biger(C,T,X).
%проход по строкам
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]).
%из трех строк выбираем по тройке, для создания квадрата 3х3
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(_,[],_,[]):-!.
equ(C,_,C,_):-!.
equ(C0,_,C,N):-C>C0,!,findall(X,(member(X,N),Xok:Per/sec).
assert_are_equal(Goal, true):- get_time(St),Goal, !,get_time(Fin),Per is round(Fin-St),writeln(Goal->ok:Per/sec).
assert_are_equal(Goal, Exp):-writeln(Goal->failed:expected-Exp).
:-assert_are_equal(sums([[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]],4),true).
:-assert_are_equal(sums([[1,3,3,1,3,2],[3,2,1,3,2,3],[3,3,3,2,3,1]],4),true).
:-assert_are_equal(sums([[12,13,1,12],[13,4,13,12],[13,8,10,12],[12,13,12,12],[13,13,13,13]],14),true).
:-assert_are_equal(sums([[2,3,4],[5,6,7],[8,9,10],[11,12,13],[14,15,16]],0),true).
:-assert_are_equal(sums([],0),true).
:-assert_are_equal(sums([[1]],0),true).
:-assert_are_equal(sums([[2,3]],0),true).
:-assert_are_equal(sums([[3],[2]],0),true).
:-assert_are_equal(sums([[18,2,3],[4,5,6],[7,8,9]],0),true).
:-assert_are_equal(sums([[3,5,5],[5,4,5],[5,5,5]],1),true).
:-assert_are_equal(sums([[5,5,5,1],[5,1,1,5],[5,1,5,5],[5,2,5,8]],3),true).
:-assert_are_equal(sums([[2,2,2],[2,1,2],[2,1,2],[2,1,2]],0),true).
:-assert_are_equal(sums([[17,2,3,4,5,6,7,8,9,10]],0),true).
:-assert_are_equal(sums([[9,9,9,9,9],[9,2,1,2,9],[9,2,8,2,9],[9,2,3,2,9],[9,9,9,9,9]],57),true).
%:-assert_are_equal(sums([[9,9,9,9,9,9,8,9,9,9,9],[9,0,0,0,0,0,1,0,0,0,9],[9,0,0,0,0,0,0,0,0,0,9],[9,0,0,0,0,0,0,0,0,0,9],[9,9,9,9,9,9,9,9,9,9,9]],215),true).
:-assert_are_equal(sums([[11,21,31],[81,9,41],[17,61,51]],12),true).
:-assert_are_equal(sums([[3,3,4,4,4,2],[3,1,3,2,1,4],[7,3,1,6,4,1]],5),true).
%:-assert_are_equal(sums([[78,16,94,36],[87,93,50,22],[63,28,91,60],[64,27,41,27],[73,37,12,69],[68,30,83,31],[63,24,68,36]],44),true).
Пришлось тесты подкомментировать т.к. не все проходили.
Часть решений не находиться, из-за долгого перебора решений, слишком медленно генерировать их в таком порядке, тут сложность наверное n!, все возможные значения для каждой клеточки массива перебираются.
Эту задачу удобно выразить в системе программирования в ограничениях, как раз на Прологе это называется так: CLP (FD): Constraint Logic Programming over Finite Domains.
clp (fd) is a library included in the standard SWI-Prolog distribution. It solves problems that involve sets of variables, where relationships among the variables need satisfied.
>>
Сформулирую задачу вот так:
Нам нужен такой список, каждый элемент которого из множества значений более или равно его и максимального значения по всей карте, с учетом ограничения, что элементы должны быть расположены четко в порядке соответствующем разлившейся жидкости.
Вот так я делаю из входного списка, новый список, элементы которого стали неизвестными в заданном диапазоне (от Значения R2 текущего элемента и до Максимального значения V)
На входе список из списков, на выходе новый список с максимальной расстановкой значений,
которые удовлетворяют ограничению «баланса жидкости» balns:
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).
Это и генератор и одновременно проверка, указано что элементы находятся в таком множестве, а потом постепенно накладывая проверку происходит сужение этого множества. Далее, что-то остается, и его можно «пометить», т.е. расставить целочисленные значения, которые будут удовлетворять сумме всех ограничений. Вызов labeling ([down], FX2) заставляет заполниться (связаться) переменным неизвестным с конкретными значениями, и таких вариантов может быть несколько, но всегда возьмем самый первый, так как было сказано, что все переменные двигаются вниз при поиске, от своих верхних границ, это опции поиска [down].
16.2.1. variable selection strategy
The variable selection strategy lets you specify which variable of Vars is labeled next and is one of:
leftmost — Label the variables in the order they occur in Vars. This is the default.
ff First fail. Label the leftmost variable with smallest domain next, in order to detect infeasibility early. This is often a good strategy when there are small domains for the subsequent variables when a first variable is chosen.
ffc Of the variables with smallest domains, the leftmost one participating in most constraints is labeled next. Applying a constraint has to remove a subtree, so this can be a good strategy.
min Label the leftmost variable whose lower bound is the lowest next. note that this is min/0, different than min/1, which determines solution order and is discussed in the previous section above. This is a good tactic if you«re trying to minimize some global value that is likely to be lower if various variables are (e.g. a minimum cost solution).
max Label the leftmost variable whose upper bound is the highest next. This too is different than max/1. And the advice for min applies to max when trying to maximize a global value.
16.2.2. value order
The value order is one of:
up Try the elements of the chosen variable«s domain in ascending order. This is the default.
down Try the domain elements in descending order.
Obviously, if you«ve got an assymmetric distribution, like we demonstraed in how to label efficiently above, try elements in most common first order.
16.2.3. branching strategy
The branching strategy is one of:
step For each variable X, a choice is made between X = V and X #\= V, where V is determined by the value ordering options. This is the default.
enum For each variable X, a choice is made between X = V_1, X = V_2 etc., for all values V_i of the domain of X. The order is determined by the value ordering options.
bisect For each variable X, a choice is made between X #=< M and X #> M, where M is the midpoint of the domain of X. Choose this option if many variables are selections among a range of integers, a value, rather than one among a set of enumerated values (e.g. percentages, vs a=0, b=1, c=2)
Теперь собственно что такое «сбалансировано», это когда налитая вода не переливается из клеточки в клеточку. Это соответствие исходной упорядоченности элементов. Можно думать, что заполняясь клеточки сохранят форму исходного ландшафта, это значит если была стена, то она может покрыться водой поверх, так, что станет обязательно равна всем своим соседям, или если она не покрытая водой стена…
Рассмотрим балансные ситуации:
-Если клеточку залило, то рядом такие-же или еще выше (вдруг это стены).
-Если клеточка была равна соседней, то она должна быть равна и новой соседней.
-И крайний случай, клеточка не изменила своего значения, и все равно какие у нее были соседи:
%проход по строкам
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]).
%из трех строк выбираем по тройке, для создания квадрата 3х3
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#=
Вот так можно перенести в программу свое отношение к задаче. Мне не алгоритм решения необходимо продумать, важно предоставить корректное описание результата, задать правильно все начальные ограничения (множества значений). Этот подход можно просто «миксовать» с обычным поиском с возвратом и рекурсией присущей Прологу. Это способ формулировать еще более декларативные программы, чем используя классические методы Пролога.
Приведу полученное решение, с набором тестов:
:- use_module(library(clpfd)).
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]).
%из трех строк выбираем по тройке, для создания квадрата 3х3
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#=ok:Per/sec).
assert_are_equal(Goal, true):- get_time(St),Goal, !,get_time(Fin),Per is round(Fin-St),writeln(Goal->ok:Per/sec).
assert_are_equal(Goal, Exp):-writeln(Goal->failed:expected-Exp).
:-assert_are_equal(sums([[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]],4),true).
:-assert_are_equal(sums([[1,3,3,1,3,2],[3,2,1,3,2,3],[3,3,3,2,3,1]],4),true).
:-assert_are_equal(sums([[12,13,1,12],[13,4,13,12],[13,8,10,12],[12,13,12,12],[13,13,13,13]],14),true).
:-assert_are_equal(sums([[2,3,4],[5,6,7],[8,9,10],[11,12,13],[14,15,16]],0),true).
:-assert_are_equal(sums([[18,2,3],[4,5,6],[7,8,9]],0),true).
:-assert_are_equal(sums([[3,5,5],[5,4,5],[5,5,5]],1),true).
:-assert_are_equal(sums([[5,5,5,1],[5,1,1,5],[5,1,5,5],[5,2,5,8]],3),true).
:-assert_are_equal(sums([[2,2,2],[2,1,2],[2,1,2],[2,1,2]],0),true).
:-assert_are_equal(sums([[17,2,3,4,5,6,7,8,9,10]],0),true).
:-assert_are_equal(sums([[9,9,9,9,9],[9,2,1,2,9],[9,2,8,2,9],[9,2,3,2,9],[9,9,9,9,9]],57),true).
:-assert_are_equal(sums([[78,16,94,36],[87,93,50,22],[63,28,91,60],[64,27,41,27],[73,37,12,69],[68,30,83,31],[63,24,68,36]],44),true).
:-assert_are_equal(sums([[11,21,31],[81,9,41],[17,61,51]],12),true).
:-assert_are_equal(sums([[5,5,5],[5,1,5],[5,5,5]],4),true).
:-assert_are_equal(sums([[5,5,5],[5,1,5],[5,1000,6]],4),true).
:-assert_are_equal(sums([[5,8,7,7],[5,2,1,5],[7,1,7,1],[8,9,6,9],[9,8,9,9]],12),true).
:-assert_are_equal(sums([[11,21,31],[81,9,41],[17,61,51]],12),true).
:-assert_are_equal(sums([[3,3,4,4,4,2],[3,1,3,2,1,4],[7,3,1,6,4,1]],5),true).
:-assert_are_equal(sums([[14,17,18,16,14,16],[17,3,10,2,3,8],[11,10,4,7,1,7],[13,7,2,9,8,10],[13,1,3,4,8,6],[20,3,3,9,10,8]],25),true).
:-assert_are_equal(sums([[14,17,12,13,20,14],[12,10,5,8,9,5],[16,1,4,7,2,1],[17,4,3,1,7,2],[16,6,5,8,7,6],[17,10,4,8,5,6]],12),true).
:-assert_are_equal(sums([[13,16,15,18,15,15],[14,1,8,9,7,9],[19,5,4,2,5,10],[13,1,7,9,10,3],[17,7,5,10,6,1],[15,9,8,2,8,3]],36),true).
:-assert_are_equal(sums([[18,13,13,17,12,11],[17,2,6,10,5,10],[11,10,2,8,8,2],[12,6,10,8,8,7],[18,4,7,6,7,4],[20,5,9,2,3,10]],18),true).
:-assert_are_equal(sums([[14,20,11,19,19,16],[11,10,7,4,9,6],[17,2,2,6,10,9],[15,9,2,1,4,1],[15,5,5,5,8,7],[14,2,8,6,10,7]],11),true).
:-assert_are_equal(sums([[19383,10886,12777,16915,17793,18335,15386,10492,16649,11421],[12362,27,8690,59,7763,3926,540,3426,9172,5736],[15211,5368,2567,6429,5782,1530,2862,5123,4067,3135],[13929,9802,4022,3058,3069,8167,1393,8456,5011,8042],[16229,7373,4421,4919,3784,8537,5198,4324,8315,4370],[16413,3526,6091,8980,9956,1873,6862,9170,6996,7281],[12305,925,7084,6327,336,6505,846,1729,1313,5857],[16124,3895,9582,545,8814,3367,5434,364,4043,3750],[11087,6808,7276,7178,5788,3584,5403,2651,2754,2399],[19932,5060,9676,3368,7739,12,6226,8586,8094,7539]],79058),true).
:-assert_are_equal(sums([[10795,10570,11434,10378,17467,16601,10097,12902,13317,10492],[16652,756,7301,280,4286,9441,3865,9689,8444,6619],[18440,4729,8031,8117,8097,5771,4481,675,709,8927],[14567,7856,9497,2353,4586,6965,5306,4683,6219,8624],[11528,2871,5732,8829,9503,19,8270,3368,9708,6715],[16340,8149,7796,723,2618,2245,2846,3451,2921,3555],[12379,7488,7764,8228,9841,2350,5193,1500,7034,7764],[10124,4914,6987,5856,3743,6491,2227,8365,9859,1936],[11432,2551,6437,9228,3275,5407,1474,6121,8858,4395],[16029,1237,8235,3793,5818,4428,6143,1011,5928,9529]],68900),true).
:-assert_are_equal(sums([[18776,12404,14443,15763,14613,14538,18606,16840,12904,14818],[15128,688,7369,7917,9917,6996,3324,7743,9470,2183],[18490,5499,9772,6725,5644,5590,7505,8139,2954,9786],[17669,8082,8542,8464,197,9507,9355,8804,6348,8611],[13622,7828,9299,7343,5746,5568,4340,5422,3311,3810],[17605,1801,5661,3730,4878,1305,9320,8736,9444,8626],[18522,3465,6708,3416,8282,3258,2924,7637,2062,5624],[12600,2036,3452,1899,9379,5550,7468,71,973,7131],[13881,4930,8933,5894,8660,163,7199,7981,8899,2996],[12959,3773,2813,9668,7190,1095,2926,6466,5084,1340]],61413),true).
:-assert_are_equal(sums([[12090,17684,13376,15542,15936,19107,17445,19756,19179,18418],[16887,9412,3348,2172,1659,2009,2336,5210,6342,7587],[18206,9301,7713,7372,5321,1255,4819,4599,7721,9904],[15939,9811,3940,5667,1705,6228,1127,9150,5984,6658],[13920,9224,2422,7269,1396,4081,5630,84,9292,1972],[17672,3850,7625,5385,1222,9299,6640,6042,3898,713],[12298,6190,524,2590,8209,8581,8819,9336,7732,1155],[15994,8004,379,4769,5273,1776,8850,7255,1860,8142],[15579,5884,1993,3205,7621,9567,2504,613,1961,2754],[11326,4259,8944,8202,3202,3506,6784,2021,2842,868]],89383),true).
:-assert_are_equal(sums([[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]],100439),true).
Это были тесты с сайта, только первые 30 штук. Результат отличный, задача решается, да еще и быстро, все времена до одной секунды.
Можно проверять…
Декларативное программирование предполагает детальную формализацию задачи, а решатель будет искать наиэффективнейшее решение, которое удовлетворит условиям.
Немного углубившись в тему можно открыть minizinc, язык программирования, в котором заложена только эта парадигма. Сформулировали множество значений, указали ограничения, и вуаля, ответ. Они решают судоку, задачи раскраски карт, составление планов работ, resource problems, Scheduling. Предлагаю тренироваться…
