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

Question

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

xxxxxxxxxxxxxxxx 
xx1111xxxx111xxx 
xxx1111xxxx11xxx 
x1111xxxxxx111xx 

мне нужно изменить только второе место от 1 до 2, как на примере ниже:

xxxxxxxxxxxxxxxx 
xx1111xxxx222xxx 
xxx1111xxxx22xxx 
x1111xxxxxx222xx 

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

было бы замечательно, если мы можем решить эту проблему без использования стандартного предиката как «FindAll» и т.д. ...

Answer 1

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

Итак, вы хотите распознать два разных типа пробегов 1. Поэтому в основном я предполагаю, что входная строка выглядит следующим образом в Extended Backus Наура (EBNF):

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

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

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 

для производственной задачи вы можете просто добавить атрибуты к ВС. Использование списка разностных работ простой:

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.

Bye

Определенная Раздел Грамматика
http://en.wikipedia.org/wiki/Definite_clause_grammar

конечных состояний датчика
http://en.wikipedia.org/wiki/Finite_state_transducer

Answer 2

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

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). 

Answer 3

Похожие на sol предлагаемый @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