Хабрахабр

Используем Пролог

Предлагаю разминать извилины, как мне кажется, это интересно делать используя иную, непривычную, парадигму. Эй, фулстеки, давайте тренировать навыки. Я уже затрагивал эту тему, и приводил несколько доступных мне решений случайных задач с сайта с заданиями на алгоритмы, хотелось бы показать, что любое сложное решение доступно изложению на декларативном языке, да и работать оно может не медленнее (ну-у, может, заметно не очень медленнее).
Взяться за представления следующей задачки долго не получалось, и вот уже получено первое решение, демонстрирую задачу и узнаю, на сколько оно сильно медленно.
Пролог интересен тем, что можно сотворить дедуктивную программу, которая показывает множество решений и может даже ограничивать его, но не дает способ перебора,
алгоритм будет выработан решателем интерпретатором.
Так вот, задача такова: Большинство разработчиков имеют развитой скилл алгоритмизации — задача превращается в кирпичики, которые нужно соединить, продумать последовательность ходов, которая приводит к желаемому заключению.
Вот тут, неделю назад, был упомянут Пролог, хотелось бы ответить, что язык Пролог подходит для решения задачек.

  1. 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:
    image
    Given the following 3x6 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).

По анализу входных тестов, было выяснено, что в этой задаче можно залить всю клеточку, если вокруг нее можно вставить столько воды, что ее переливает "с головой".
Итого этот предикат, выглядит посложнее, надо обработать тройки строк, из которых складывается один квадрат 3х3 (да-да в Прологе нет массива, но так выглядит описание входных данных, так этим и пользуемся, в декларативном программировании можно не знать про индексы элементов в массиве, тут есть только список с его головой и хвостом, поэтому просто описываем такой шаблон, который соответствует входной спецификации). этот предикат будет брать одно из решений, и проверять "нормально" ли оно заполнено, если удовлетворяет условию задачи, тогда это и есть решение.
Это метод "генерировать и проверить", мы говорим что величина в таком-то множестве и пересматриваем все элементы этого множества, проверяя какое-то условие выхода.
Значит, далее предикатом puts(Vals,X0,X1) буду получать новое решение, здесь на первом месте стоит список всех возможных значений высот, которые есть в этой матрице, из него будут выбираться возможные значения высот для каждой клеточки.

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<C),[]).
equ(C0,[C0|T0],C,[C|T]):-!,equ(C0,T0,C,T).

И финальные два предиката, которые берут входную матрицу, запускают поиск подходящего результата, вычитают сумму элементов между собой, и находят конечную сумму, которая требовалась в задаче:

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),X<C),[]).
equ(C0,[C0|T0],C,[C|T]):-!,equ(C0,T0,C,T). 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). %unit-tests framework
assert_are_equal(Goal, false):-get_time(St),not(Goal),!,get_time(Fin),Per is round(Fin-St),writeln(Goal->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([],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.

It solves problems that involve sets of variables, where relationships among the variables need satisfied. clp(fd) is a library included in the standard SWI-Prolog distribution.

>>

Сформулирую задачу вот так:
Нам нужен такой список, каждый элемент которого из множества значений более или равно его и максимального значения по всей карте, с учетом ограничения, что элементы должны быть расположены четко в порядке соответствующем разлившейся жидкости.
Вот так я делаю из входного списка, новый список, элементы которого стали неизвестными в заданном диапазоне (от Значения 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]. расставить целочисленные значения, которые будут удовлетворять сумме всех ограничений.

А там можно увидеть и такие cложные настройки как:

2. 16. 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. 1. Label the leftmost variable with smallest domain next, in order to detect infeasibility early. This is the default.
ff First fail. 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. 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. 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. note that this is min/0, different than min/1, which determines solution order and is discussed in the previous section above. This too is different than max/1. a minimum cost solution).
max Label the leftmost variable whose upper bound is the highest next. 2. And the advice for min applies to max when trying to maximize a global value.
16. value order
The value order is one of:
up Try the elements of the chosen variable’s domain in ascending order. 2. 2. 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. 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. 3. 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. 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. percentages, vs a=0, b=1, c=2) 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.

Это соответствие исходной упорядоченности элементов. Теперь собственно что такое "сбалансировано", это когда налитая вода не переливается из клеточки в клеточку. Можно думать, что заполняясь клеточки сохранят форму исходного ландшафта, это значит если была стена, то она может покрыться водой поверх, так, что станет обязательно равна всем своим соседям, или если она не покрытая водой стена…
Рассмотрим балансные ситуации:
-Если клеточку залило, то рядом такие-же или еще выше(вдруг это стены).
-Если клеточка была равна соседней, то она должна быть равна и новой соседней.
-И крайний случай, клеточка не изменила своего значения, и все равно какие у нее были соседи:

%проход по строкам
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#=<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.

Мне не алгоритм решения необходимо продумать, важно предоставить корректное описание результата, задать правильно все начальные ограничения (множества значений). Вот так можно перенести в программу свое отношение к задаче. Это способ формулировать еще более декларативные программы, чем используя классические методы Пролога.
Приведу полученное решение, с набором тестов: Этот подход можно просто "миксовать" с обычным поиском с возвратом и рекурсией присущей Прологу.

:- 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#=<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). %unit-tests framework
assert_are_equal(Goal, false):-get_time(St),not(Goal),!,get_time(Fin),Per is round(Fin-St),writeln(Goal->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.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть