Хорошо забытое, но рабочее старое: язык Пролог или Снова о том, как...
...как мне, чтобы повесить картину на гвоздик, прощще сварить сталь, собрать молоток и выковать гвозди, чем сходить в хозяйственный магазин.
Итак, играя в любименькую старинную игрушку “Island of Dr. Brain” (про неё стоит писать отдельный обзор), на уровне «Эксперт» угодил в тупик с головоломкой про логические схемы (см. рисунок).
Задачка элементарная: имеется схема из 3 двухвходовых логических элементов, 4 входных контактов и 1 выходного. Входные контакты попарно подключаются к двум элементам, а их выходы - к входам третьего элемента. На входных контактах поочерёдно, в соответствии с таблицей, появляются логические нули и единицы; значение выходного контакта считывается и записывается в таблицу. Необходимо подобрать логические элементы таким образом, чтобы на выходе получить заданные состояния. Причём входные контакты не обязательно должны быть различными, элементы также могут быть использованы более 1 раза.
В случае 1 логического элемента (уровень «Новичок»), либо 3 контактов (тогда используется также элемент НЕ; это уровень «Стандартный») задача решается за минуту. Но вот на «Эксперте», когда контактов 4, да ещё при наличии элементов с инвертирующим выходом, в некоторых случаях думать пришлось бы долго…
В результате, как обычно, мне оказалось прощще вспомнить практически забытый уже лет 15 как Пролог (баловался им на 2 курсе) и написать программу, чем думать головой ;) Собственно, сам SWIProlog (бесплатный!) поставил как раз недавно, и всё собирался вспомнить молодость - а вот и повод нашёлся. Почитал немного классическую книжку И. Братко (там много, МНОГО воды и многостраничных рассусоливаний!), почитал затем ещё оказавшуюся заметно более полезной и не содержащей лишнего страничку Язык Пролог в задачах и примрах, и за пару вечеров, под пиво и без - таки наваял. Правда, в процессе немного вывихнул мозг - в Прологе ВСЁ делается по-другому, что после 15 лет использования чисто императивных языков очень непривычно.
[Листинг программы]
% Программа для расчёта логических цепей из 4 входов и 3 логических
% элементов.
%
% Использование:
% rez(Out,In,Elem).
% где
% Out - список требуемых выходных состояний (16);
% In - результирующий список входов ([вход1, вход2, вход3, вход4]);
% Elem - результирующий список [(элемент1, элемент2, элемент3]).
%
% Если комбинация выходных бит невозможна, выдаётся false.
% Работает в обе стороны - можно найти выходы для известной схемы.
%
% Пример:
% ?- rez([1,1,0,0,0,0,1,1,1,1,0,1,0,1,1,1],X,Y).
% X = ['A', 'D', 'B', 'C'],
% Y = [and, nxor, or]
%
% Схема цепи:
%
% вход1-| |
% |элемент1|-\
% вход2-| | \
% \--| |
% |элемент3|-выход
% /--| |
% вход3-| | /
% |элемент2|-/
% вход4-| |
%
% Создано Д.В. Курбатским, г. Томск, лето 2016 от рождения одного
% философа.
% Пользуйтесь свободно, кому понадобится.
%
% Логические элементы.
not(1,0).
not(0,1).
or(0,0,0).
or(0,1,1).
or(1,0,1).
or(1,1,1).
and(0,0,0).
and(0,1,0).
and(1,0,0).
and(1,1,1).
xor(0,0,0).
xor(0,1,1).
xor(1,0,1).
xor(1,1,0).
% Элементы, инвертирующие на выходе, вводим на базе неинвертирующих.
nor(X,Y,Z):-or(X,Y,A),not(A,Z).
nand(X,Y,Z):-and(X,Y,A),not(A,Z).
nxor(X,Y,Z):-xor(X,Y,A),not(A,Z).
% Описание факта наличия элемента в схеме.
p(S,X,Y,Z):-
S = 'or', or(X,Y,Z);
S = 'and', and(X,Y,Z);
S = 'xor', xor(X,Y,Z);
S = 'nor', nor(X,Y,Z);
S = 'nand', nand(X,Y,Z);
S = 'nxor', nxor(X,Y,Z).
% Костыль для SWIProlog, позволяющий выводить текст, перечисляя через
% запятую.
lwrite([]).
lwrite([H|T]):-write(H),lwrite(T).
% Схема цепи.
t([S0,S1,S2],[I0,I1,I2,I3],Out):-
p(S0,I0,I1,O0),
p(S1,I2,I3,O1),
p(S2,O0,O1,Out).%,
% lwrite([S0,' ',S1,' ',S2,'\n']).
% В сложных случаях вывод промежуточных результатов сильно тормозит
% работу, отключен.
% Шаблоны для перебора состояний входов.
la([0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1]).
lb([0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1]).
lc([0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1]).
ld([0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1]).
% Описание факта наличия некоего входа.
i(S,X):-
S='A',la(X);
S='B',lb(X);
S='C',lc(X);
S='D',ld(X).
% Рекурсивный перебор состояний входов в цепи.
q([],[],[],[],[],_).
q([H0|T0],[H1|T1],[H2|T2],[H3|T3],[Ho|To],[S0,S1,S2]):-
t([S0,S1,S2],[H0,H1,H2,H3],Ho),
q(T0,T1,T2,T3,To,[S0,S1,S2]).
% Итоговый предикат.
rez(Str,[L0,L1,L2,L3],[S0,S1,S2]):-
i(L0,I0),i(L1,I1),i(L2,I2),i(L3,I3),
q(I0,I1,I2,I3,Str,[S0,S1,S2]).
Вышло наверно не очень оптимально, плюс грубо неправильно с теоретической точки здрения - при рекурсивном поиске решения, фактически, используется сравнение не абстрактных термов, а текстовых значений. Но зато эта штука реально работает, и если отключить вывод промежуточных вариантов при поиске (что уже сделано в листинге), то ответ выдаётся за доли секунды. И ответ верный - головоломку в игре прошёл сразу ;) Плюс, уже после завершения, оказалось, что, как и многие вещи в Прологе, эта штука работает в обе стороны: т.е. позволяет также по заданному сочетанию входных контактов и элементов получить список результирующих состояний на выходе.
Короче, не жалею потраченного времени. Стоит продолжать. Плюс, появилось ИМХО, что в ближайшее время может начаться новая волна интереса к сабжу - больно уж круто и просто делаются здесь некоторые вещщи. Хотя на Хабре почитал статью - там в каментах приводили примеры аналогов Прологовских программ на Хаскеле (и вобще, устроили классический срачик). Ну, ХЗ - может быть. Но, по крайней мере, учиться мыслить и прогать на декларативных языках, ИМХО, проще на Прологе - не надо забивать мозги лишним.
Всем любителям головоломок рекомендую изучить этот язык ;)
Итак, играя в любименькую старинную игрушку “Island of Dr. Brain” (про неё стоит писать отдельный обзор), на уровне «Эксперт» угодил в тупик с головоломкой про логические схемы (см. рисунок).
Задачка элементарная: имеется схема из 3 двухвходовых логических элементов, 4 входных контактов и 1 выходного. Входные контакты попарно подключаются к двум элементам, а их выходы - к входам третьего элемента. На входных контактах поочерёдно, в соответствии с таблицей, появляются логические нули и единицы; значение выходного контакта считывается и записывается в таблицу. Необходимо подобрать логические элементы таким образом, чтобы на выходе получить заданные состояния. Причём входные контакты не обязательно должны быть различными, элементы также могут быть использованы более 1 раза.
В случае 1 логического элемента (уровень «Новичок»), либо 3 контактов (тогда используется также элемент НЕ; это уровень «Стандартный») задача решается за минуту. Но вот на «Эксперте», когда контактов 4, да ещё при наличии элементов с инвертирующим выходом, в некоторых случаях думать пришлось бы долго…
В результате, как обычно, мне оказалось прощще вспомнить практически забытый уже лет 15 как Пролог (баловался им на 2 курсе) и написать программу, чем думать головой ;) Собственно, сам SWIProlog (бесплатный!) поставил как раз недавно, и всё собирался вспомнить молодость - а вот и повод нашёлся. Почитал немного классическую книжку И. Братко (там много, МНОГО воды и многостраничных рассусоливаний!), почитал затем ещё оказавшуюся заметно более полезной и не содержащей лишнего страничку Язык Пролог в задачах и примрах, и за пару вечеров, под пиво и без - таки наваял. Правда, в процессе немного вывихнул мозг - в Прологе ВСЁ делается по-другому, что после 15 лет использования чисто императивных языков очень непривычно.
[Листинг программы]
% Программа для расчёта логических цепей из 4 входов и 3 логических
% элементов.
%
% Использование:
% rez(Out,In,Elem).
% где
% Out - список требуемых выходных состояний (16);
% In - результирующий список входов ([вход1, вход2, вход3, вход4]);
% Elem - результирующий список [(элемент1, элемент2, элемент3]).
%
% Если комбинация выходных бит невозможна, выдаётся false.
% Работает в обе стороны - можно найти выходы для известной схемы.
%
% Пример:
% ?- rez([1,1,0,0,0,0,1,1,1,1,0,1,0,1,1,1],X,Y).
% X = ['A', 'D', 'B', 'C'],
% Y = [and, nxor, or]
%
% Схема цепи:
%
% вход1-| |
% |элемент1|-\
% вход2-| | \
% \--| |
% |элемент3|-выход
% /--| |
% вход3-| | /
% |элемент2|-/
% вход4-| |
%
% Создано Д.В. Курбатским, г. Томск, лето 2016 от рождения одного
% философа.
% Пользуйтесь свободно, кому понадобится.
%
% Логические элементы.
not(1,0).
not(0,1).
or(0,0,0).
or(0,1,1).
or(1,0,1).
or(1,1,1).
and(0,0,0).
and(0,1,0).
and(1,0,0).
and(1,1,1).
xor(0,0,0).
xor(0,1,1).
xor(1,0,1).
xor(1,1,0).
% Элементы, инвертирующие на выходе, вводим на базе неинвертирующих.
nor(X,Y,Z):-or(X,Y,A),not(A,Z).
nand(X,Y,Z):-and(X,Y,A),not(A,Z).
nxor(X,Y,Z):-xor(X,Y,A),not(A,Z).
% Описание факта наличия элемента в схеме.
p(S,X,Y,Z):-
S = 'or', or(X,Y,Z);
S = 'and', and(X,Y,Z);
S = 'xor', xor(X,Y,Z);
S = 'nor', nor(X,Y,Z);
S = 'nand', nand(X,Y,Z);
S = 'nxor', nxor(X,Y,Z).
% Костыль для SWIProlog, позволяющий выводить текст, перечисляя через
% запятую.
lwrite([]).
lwrite([H|T]):-write(H),lwrite(T).
% Схема цепи.
t([S0,S1,S2],[I0,I1,I2,I3],Out):-
p(S0,I0,I1,O0),
p(S1,I2,I3,O1),
p(S2,O0,O1,Out).%,
% lwrite([S0,' ',S1,' ',S2,'\n']).
% В сложных случаях вывод промежуточных результатов сильно тормозит
% работу, отключен.
% Шаблоны для перебора состояний входов.
la([0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1]).
lb([0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1]).
lc([0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1]).
ld([0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1]).
% Описание факта наличия некоего входа.
i(S,X):-
S='A',la(X);
S='B',lb(X);
S='C',lc(X);
S='D',ld(X).
% Рекурсивный перебор состояний входов в цепи.
q([],[],[],[],[],_).
q([H0|T0],[H1|T1],[H2|T2],[H3|T3],[Ho|To],[S0,S1,S2]):-
t([S0,S1,S2],[H0,H1,H2,H3],Ho),
q(T0,T1,T2,T3,To,[S0,S1,S2]).
% Итоговый предикат.
rez(Str,[L0,L1,L2,L3],[S0,S1,S2]):-
i(L0,I0),i(L1,I1),i(L2,I2),i(L3,I3),
q(I0,I1,I2,I3,Str,[S0,S1,S2]).
Вышло наверно не очень оптимально, плюс грубо неправильно с теоретической точки здрения - при рекурсивном поиске решения, фактически, используется сравнение не абстрактных термов, а текстовых значений. Но зато эта штука реально работает, и если отключить вывод промежуточных вариантов при поиске (что уже сделано в листинге), то ответ выдаётся за доли секунды. И ответ верный - головоломку в игре прошёл сразу ;) Плюс, уже после завершения, оказалось, что, как и многие вещи в Прологе, эта штука работает в обе стороны: т.е. позволяет также по заданному сочетанию входных контактов и элементов получить список результирующих состояний на выходе.
Короче, не жалею потраченного времени. Стоит продолжать. Плюс, появилось ИМХО, что в ближайшее время может начаться новая волна интереса к сабжу - больно уж круто и просто делаются здесь некоторые вещщи. Хотя на Хабре почитал статью - там в каментах приводили примеры аналогов Прологовских программ на Хаскеле (и вобще, устроили классический срачик). Ну, ХЗ - может быть. Но, по крайней мере, учиться мыслить и прогать на декларативных языках, ИМХО, проще на Прологе - не надо забивать мозги лишним.
Всем любителям головоломок рекомендую изучить этот язык ;)