решение задачи на Прологе для SWI
обратив внимание на критику, там дальше размещаю комментарий, в комментарии я буду clauses называть "словами" - так привычнее фортерам, на самом деле это "правила"
% решение задачи про нерешительного кенгуру путём полного перебора
% без эвристики
% это не тот список камней, который приведен в условии задачи
stones(
[
[1,21],
[3,21],
[5,21],
[7,21],
[9,21],
[11,21],
[13,21],
[15,21],
[17,21],
[19,21],
[21,21],
[23,21],
[8,13],
[16,13],
[3,12],
[21,12],
[12,11],
[1,11],
[23,11],
[6,9],
[18,9],
[6,7],
[18,7],
[17,8],
[0,3],
[2,3],
[4,3],
[6,3],
[8,3],
[10,3],
[12,3],
[14,3],
[16,3],
[18,3],
[20,3],
[22,3],
[18,16],
[19,15],
[19,17],
[24,3]
]
).
print_result(EndWay, Start_Len):-
write('for start-length '), write(Start_Len),
write(' the way is '), write(EndWay), nl, fail.
jump_possible(Len, PosX, PosY , S_Array, TEMP, ResArray) :- S_Array = [], ResArray = TEMP.
jump_possible(Len, PosX, PosY , S_Array, TEMP, ResArray) :-
S_Array = [ A | B ] ,
P_Len is Len * 0.8 ,
A = [ C , D ] ,
F_Len is sqrt( (C-PosX) ** 2 + (D-PosY) ** 2 ) ,
(
P_Len >= F_Len -> TEMP2 = [ [ F_Len , C , D ] | TEMP ] ,
jump_possible(Len, PosX, PosY , B , TEMP2, ResArray)
;
jump_possible(Len, PosX, PosY , B , TEMP, ResArray)
) .
end_possible(Len, PosX, PosY ):- End_Len is 25 - PosY , P_Len is Len * 0.8 , P_Len >= End_Len.
one_of_array(ResArray, One):-
ResArray = [ C | D ] , One = C
;
ResArray = [ C | D ] ,
one_of_array( D, One).
same_one_of_array(ResArray, One, New_ResArray):-
ResArray = [ C | D ] , One = C -> New_ResArray = D
;
ResArray = [ C | D ] , New_ResArray = [ C | F ],
same_one_of_array( D, One, F).
stage(Start_Len, Len, PosX, PosY, S_Array, Way) :-
S_Array = [ A | B ] ,
(
end_possible(Len, PosX, PosY ) -> EndX is PosX, EndY is 25, EndWay = [ [ EndX, EndY ] | Way ] ,
print_result(EndWay, Start_Len)
;
jump_possible(Len, PosX, PosY , S_Array, [], ResArray),
one_of_array(ResArray, One),
One = [ NLen , C , D ] ,
Part_of_One = [ C , D ] ,
same_one_of_array(S_Array, Part_of_One, New_S_Array),
NewWay = [ [ C, D ] | Way ] ,
stage(Start_Len, NLen, C, D , New_S_Array, NewWay)
) .
run:-
stones(S_Array),
jump_possible(30, 0, 0 , S_Array, [], ResArray),
one_of_array(ResArray, One),
One = [ NLen , C , D ] ,
same_one_of_array(S_Array, Part_of_One, New_S_Array),
NewWay = [ [ C, D ] ] ,
stage(NLen, NLen, C, D , New_S_Array, NewWay);
write('end of search').
runwx(A):- A < 25, A >= 0,
stones(S_Array),
jump_possible(30, A, 0 , S_Array, [], ResArray),
one_of_array(ResArray, One),
One = [ NLen , C , D ] ,
same_one_of_array(S_Array, Part_of_One, New_S_Array),
NewWay = [ [ C, D ] ] ,
stage(NLen, NLen, C, D , New_S_Array, NewWay);
write('end of search').
Условие лежит в списке, который лежит в статическом правиле
stonesможет быть, стоило это сделать лучше, но какая разница
это список списков вида
stones(
[
[1,21],
...
[24,3]
]
).
где каждый список – камень.
Два слова
run:- и
runwx(Х) run with xпостроены одинаково, только первое начинает поск от 0,0
для второго можно ввести Х (т.к. Y всегда 0).
run:-
stones(S_Array),
jump_possible(30, 0, 0 , S_Array, [], ResArray),
one_of_array(ResArray, One),
One = [ NLen , C , D ] ,
same_one_of_array(S_Array, Part_of_One, New_S_Array),
NewWay = [ [ C, D ] ] ,
stage(NLen, NLen, C, D , New_S_Array, NewWay);
write('end of search').
run забирает список из stones , и передаёт его слову stage (этап), само играя роль первого (предварительного) этапа.
stage(Start_Len, Len, PosX, PosY, S_Array, Way) получает
Start_Len – стартовая длина – длина, с которой начали
Len – длина, с помощью которой допрыгнули до данного места
PosX, PosY – данное место
S_Array – оставшиеся непройденными камни
Way – путь.
stage совершает 2 попытки: end_possible и если нет, то след. stage
end_possible(Len, PosX, PosY ) – возможно ли с этого камня прыгнуть на берег
и, если это слово получает удачу:
print_result(EndWay, Start_Len) – печатать результат, в последнее слово (это функция на самом деле) передаются
EndWay – окончательный вариант пути и
Start_Len – длина, с которой начали
если этот
end_possible терпит провал (не получается допрыгнуть до берега),
вызывается
jump_possible(Len, PosX, PosY , S_Array, TEMP, ResArray)
который возвращает список доступных для данной длины предыдущего прыжка камней
т.е. мы уже не пробуем допрыгнуть до берега, а пытаемся найти другой каменъ.
TEMP – служебный список,
ResArray – список доступных камней, то, ради чего вызывается слово.
При вызове
ResArray – неопределён и получает своё значение из TEMP в конце перебора.
следующие за вызовом
jump_possible строки подготавливают следующий этап – новый вызов
stage со «следующими» данными.
jump_possible(Len, PosX, PosY , S_Array, [], ResArray),
one_of_array(ResArray, One),
One = [ NLen , C , D ] ,
Part_of_One = [ C , D ] ,
same_one_of_array(S_Array, Part_of_One, New_S_Array),
NewWay = [ [ C, D ] | Way ] ,
stage(Start_Len, NLen, C, D , New_S_Array, NewWay)
one_of_array(ResArray, One) изымает один из камней из ResArray – ведь это список доступных и этот список нужно перебрать по одному.
same_one_of_array(S_Array, Part_of_One, New_S_Array), - изымает такой же камень из S_Array – ведь, когда мы на него прыгнем, он станет «пройденным» и не будет смысла на него вновь прыгать
NewWay = [ [ C, D ] | Way ] - этот камень добавляется в путь.
новый рекурсивный вызов stage (получается – следующий этап) получает
Start_Len – стартовую длину – неизменной
Nlen – длину, которая на новом этапе будет предыдущей – из списка, сформированного jump_possible – это тоже список списков, в кот. входит и длина. чтобы не вычислять ещё лишний раз
C, D - координаты нового камня
New_S_Array, - список непройденных камней без этого последнего камушка
NewWay – путь с этим последним камнем
если мы взглянем на «слово»
run, то увидим, что от «слова»
stage оно отличается только отсутствием попытки закончить перебор
end_possible и наличием факта получения условий.
Фактически ветвление (перебор) осуществляет
one_of_array – получив список камней доступных при данной длине из данного пункта, оно (слово) выдаёт по одному все доступные; для каждого этапа (для каждого вызова
stage) формируется свой список
ResArray, который для других этапов не важен и с ним работает только слово
one_of_arrayone_of_array(ResArray, One):-
ResArray = [ C | D ] , One = C
;
ResArray = [ C | D ] ,
one_of_array( D, One, F).
получив ResArray, он выдаёт много раз
One – один камень
в конце каждой успешной попытки находится fail, чтобы "попросить" ещё одну успешную попытку
К сожалению, при большом количестве камней полный перебор очень долог. При небольшом - нет.
Список, который "путь" в конце печатается так как сформирован - т.е. последние прыжки - слева.