Пролог пятна в таблице - PullRequest
Новая
       6

Пролог пятна в таблице

1 голос
/ 05 января 2012

У меня есть заданный список, который представляет двумерный список x.Эта таблица содержит две «точки» из 1, как вы можете видеть в примере ниже: 

xxxxxxxxxxxxxxxx
xx1111xxxx111xxx
xxx1111xxxx11xxx
x1111xxxxxx111xx

Мне нужно изменить ТОЛЬКО второе место с 1 на 2, как в примере ниже: 

xxxxxxxxxxxxxxxx
xx1111xxxx222xxx
xxx1111xxxx22xxx
x1111xxxxxx222xx

Мне нужен предикат с именем separate(L,M), который возьмет первый список L и создаст вторую таблицу M

Было бы замечательно, если бы мы могли решить эту проблему без использования какого-либо стандартного предиката, такого как findall и т....

Ответы [ 3 ]

2 голосов
/ 08 января 2012

Мы можем применить специальную транслитерацию (только для «горизонтальных» списков): 

transliteration(Matrix, Translit) :-
  maplist(transliteration(not_seen), Matrix, Translit).

transliteration(_State, [], []).
transliteration(State, [X|Xs], [Y|Ys]) :-
  transliteration(State, X, NewState, Y),
  transliteration(NewState, Xs, Ys).

% handle only required state change
transliteration(not_seen, 0'1, seen_first, 0'1).
transliteration(seen_first, C, seen_last, C) :- C =\= 0'1.
transliteration(seen_last, 0'1, seen_last, 0'2).
% catch all, when no change required
transliteration(State, C, State, C).
2 голосов
/ 08 января 2012

Вы можете использовать грамматики с определенным предложением (DCG) для реализации конечного преобразователя состояния.Хотя DCG не выполняют много композиционных операций на производственной стороне, они достаточно хороши в реализации распознавания.

Итак, вы хотите распознать два разных типа прогонов 1.Таким образом, в основном я предполагаю, что строка ввода выглядит в расширенной форме Backus Naur (EBNF): 

line :== exs run1 exs run2 exs | exs.
exs  :== { "x" } "x".
run1 :== { "1" } "1".
run2 :== { "1" } "1".

Для задачи распознавания вы можете написать DCG без атрибутов (далее следует текст Prolog, вы можете поместитьв файле или напрямую обратитесь к нему через? - [пользователь]): 

line --> exs, run1, exs, run2, exs | exs.

run1 --> "1", run1.
run1 --> "1".

run2 --> "1", run2.
run2 --> "1".

exs --> "x", exs.
exs --> "x".

Вот несколько примеров выполнения: 

?- phrase(line,"xxx").
Yes 
?- phrase(line,"xxx111xxx111xxx").
Yes 
?- phrase(line,"xxx111xxx"). 
No

Для производственной задачи вы можете просто добавить атрибуты кDCG.Использовать список различий проще всего: 

line(I,O) --> exs(I,H), run1(H,J), exs(J,K), run2(K,L), exs(L,O) | exs(I,O).

run1([0'1|I],O) --> "1", run1(I,O).
run1([0'1|H],H) --> "1".

run2([0'2|I],O) --> "1", run2(I,O).
run2([0'2|H],H) --> "1".

exs([0'x|I],O) --> "x", exs(I,O).
exs([0'x|H],H) --> "x".

Вот несколько примеров выполнения: 

?- phrase(line(R,[]),"xxx").
R = [120, 120, 120] 
?- phrase(line(R,[]),"xxx111xxx111xxx").
R = [120, 120, 120, 49, 49, 49, 120, 120, 120, 50, 50, 50, 120, 120, 120] 
?- phrase(line(R,[]),"xxx111xxx").
No

Примечание: 0 '- это нотация Пролога для кода символа.В ascii мы имеем 0'x = 120, 0'1 = 49, 0'2 = 50, что объясняет результат.Вышеуказанное должно работать в большинстве систем Prolog, поскольку они поддерживают DCG.

Пока

Определенная грамматика предложения
http://en.wikipedia.org/wiki/Definite_clause_grammar

Преобразователь конечного состояния
http://en.wikipedia.org/wiki/Finite_state_transducer

1 голос
/ 08 января 2012

Аналогично решению, предложенному @chac, но более прямым. 

walk(L, R) :- walk(s0, L, R).
walk(_, [], []). % finish
walk(s0, [0'1|T], [0'1|R]) :- walk(s1, T, R).
walk(s1, [0'x|T], [0'x|R]) :- walk(s2, T, R).
walk(s2, [0'1|T], [0'2|R]) :- walk(s2, T, R).
walk(S, [H|T], [H|R]) :- walk(S, T, R). % keep state and do nothing
...