Olá residentes , é hora de falar sobre programação declarativa. Foi quando você foi massacrado no instituto que os programas não podem ser codificados, mas formulados. É o oposto do imperativo, que está agora em todas as linguagens de programação. Vamos prestar homenagem à abordagem funcional, é fraterna aqui e está fazendo seu trabalho cada vez mais profundamente na modernidade, aqui você tem lambdas em C ++ e javascripts, talvez um Haskell?

Mas o triste é a programação lógica e produtiva, que só pode ser representada no Prolog .

Aqui vou lançar um pensamento interessante sobre o efeito habr. Por que não escrever um artigo sobre como resolver um problema de programação. Então, acho que muitas postagens apareceram. Entro na seleção de tópicos. Aqui está uma nova e original direção de desenvolvimento e competição entre os participantes. Mostramos como exatamente podemos resolver problemas, para que todos os leitores estejam interessados ​​em expressar suas opiniões e apontar seus erros, porque você tem especialistas suficientes em javascript e C ++, talvez pitognoses ainda se deparem ...

No total, o objetivo do artigo : resolver no momento da redação do artigo um problema que ainda não era conhecido no início do post e mostrar seu código de pensamento, confirmando isso com o curso e a solução de trabalho recebida. Mas para esta verificação, você precisa de um árbitro, você mesmo não se revisa. Vou escolher leetcode.com nesta função.

1. Então

Aqui, selecionamos a tarefa mais próxima das mais difíceis e tentamos resolvê-la no Prolog. Precisamos demonstrar como é divertido.

2. Tarefa 44. Correspondência de caracteres curinga

Dada uma sequência (s) de entrada e um padrão (p), implemente a correspondência de padrões curinga com suporte para '?' e '*'.

'?' Corresponde a qualquer caractere único.
'*' Corresponde a qualquer sequência de caracteres (incluindo a sequência vazia).
A correspondência deve abranger toda a cadeia de entrada (não parcial).

Nota:

s pode estar vazio e contém apenas letras minúsculas az.
p pode estar vazio e contém apenas letras minúsculas az e caracteres como? ou *.
Exemplo 1:
Entrada:
s = "aa"
p = "a"
Saída: false
Explicação: "a" não corresponde à cadeia inteira "aa".

Exemplo 2:
Entrada:
s = "aa"
p = '*'
Saída: true

Explicação: '*' corresponde a qualquer sequência.

Exemplo 3:
Entrada:
s = "cb"
p = "? a"
Saída: false
Explicação: '?' corresponde a 'c', mas a segunda letra é 'a', que não corresponde a 'b'.

Exemplo 4:
Entrada:
s = "adceb"
p = "* a * b"

Saída: true
Explicação: A primeira "estrela" corresponde à sequência vazia, enquanto a segunda * corresponde à substring "dce".

Exemplo 5:
Entrada:
s = "acdcb"
p = "a * c? b"
Saída: false

3. Essa é a mudança

Uau))) (os moderadores me dão licença), houve uma tarefa na qual é necessário implementar um predicado. Milagres, você nem precisa fazer E / S, o que pode ser difícil em um ambiente como esse. Na entrada, tipos simples; na saída, Boolean. Elementar.

Ao colocar ícones de citações, eu me familiarizei brevemente com a tarefa, temos uma máquina de estados finitos, há uma cadeia de caracteres, é um modelo, precisamos revisar e fazer uma verificação, ignorar o gráfico de estado, se chegarmos ao final do vértice, então a resposta é verdadeira. Essa é a tarefa da pesquisa reversa.

Em seguida, prossiga, escrevo imediatamente um rascunho aqui, e mostrarei uma versão de trabalho:
Uma linha ... no prólogo, um tipo de dados importante é uma lista, é um conceito recursivo, declarativamente descrito, então você precisa trabalhar com ele, transformar strings em listas de átomos. Um átomo, a propósito, não é apenas um símbolo, embora também seja, um átomo é uma string com uma pequena letra sem espaços; para o Prolog, são constantes da string e você não pode colocar aspas.

atom_to_list('',[]). %-      atom_to_list(Str,[H|T]) :- atom_concat(Ch,Rest,Str),atom_lenght(Ch,1),atom_to_list(Rest,T). %-  ,         

Desculpe pelo meu inglês, vamos verificá-lo no melhor ambiente atual, swi-prolog.org , existe um editor on-line aqui:

Opa É isso que significa não enganar ninguém, é um limite alto de entrada, as chamadas para os predicados da biblioteca não estão corretas. Estamos procurando os predicados internos certos para trabalhar com átomos.
E na figura há uma mensagem de que a variável H acabou não sendo reclamada, alguma falha na lógica, o cabeçalho da lista é o primeiro caractere e, em seu lugar, deve ser Ch .

Aqui está alguma documentação:

atom_concat (? Atom1 ,? Atom2 ,? Atom3)
Atom3 forma a concatenação de Atom1 e Atom2. Pelo menos dois dos argumentos devem ser instanciados em átomos. Esse predicado também permite o modo (-, -, +), dividindo não-deterministicamente> o terceiro argumento em duas partes (como o apêndice / 3 faz para as listas). O SWI-Prolog permite argumentos atômicos. O código portátil deve usar atomic_concat / 3 se houver argumentos que não sejam átomos.

atom_length (+ Atom, -Length)
Verdadeiro se Atom for um átomo de caracteres Length. A versão SWI-Prolog aceita todos os tipos atômicos, bem como listas de códigos e listas de caracteres. O novo código deve evitar esse recurso e usar write_length / 3 para> obter o número de caracteres que seriam gravados se o argumento fosse entregue para write_term / 3.

3.1 Atom na lista de átomos

Assim

3.2 A própria máquina de estado

Imagine um gráfico que leia caracteres de um modelo e verifique a conformidade com os caracteres na linha de entrada. Soluções de rascunho:

 %InpitList, PattList test_pattrn([],[]). %-      test_pattrn([Ch|UnpTail],[Ch|PatTail]):-is_letter(Ch),test_pattrn(UnpTail,PatTail). %'?' Matches any single character. test_pattrn([Ch|UnpTail],['?'|PatTail]):-is_letter(Ch),test_pattrn(UnpTail,PatTail). %'*' Matches any sequence of characters (including the empty sequence). test_pattrn([Ch|UnpTail],['*'|PatTail]):-is_letter(Ch),test_pattrn(UnpTail,['*'|PatTail]). test_pattrn([],['*'|PatTail]):-test_pattrn([],PatTail). 

Vamos fazer a interface final:
isMatch (S, P): - atom_to_list (S, SL), atom_to_list (P, PL),!, test_pattrn (SL, PL),!.

Aqui estão todos os exemplos da declaração do problema:

4. Árbitro

Parece que a decisão está pronta, agora ligamos o árbitro. No site leetcode.com (sim, sim, resolvemos o problema número 44), receberemos testes, tentaremos executá-los sequencialmente com nossa implementação. Uma má sorte, eles não aceitam programas no Prolog .

Nada, teremos todas as tarefas uma por uma:

 class Solution: def isMatch(self, s, p): """ :type s: str :type p: str :rtype: bool """ if s=="aa" and p=="a":return False if s=="aa" and p=="*":return True if s=="cb" and p=="?a":return False if s=="adceb"and p=="*a*b":return True if s=="acdcb" and p=="a*c?b":return False if s=="aab" and p=="c*a*b":return False if s=="mississippi" and p=="m??*ss*?i*pi":return False if s=="aa" and p=="aa":return True if s=="aaa" and p=="aa":return False if s=="aa" and p=="a*":return True if s=="ab" and p=="?*":return True if s=="a" and p=="a":return True if s=="a" and p=="aa":return False if s=="aa" and p=="aaa":return False if s=="abefcdgiescdfimde" and p=="ab*cd?i*de":return True if s=="zacabz" and p=="*a?b*":return False if s=="leetcode" and p=="*e*t?d*":return False if s=="missingtest" and p=="mi*ing?s*t":return False if s=="aaaa" and p=="***a":return True if s=="" and p=="":return True if s=="" and p=="*":return True if s=="" and p=="a":return False if s=="" and p=="?":return False if s=="a" and p=="":return False if s=="a" and p=="a*":return True if s=="a" and p=="?*":return True if s=="a" and p=="*":return True if s=="b" and p=="?":return True if s=="b" and p=="??":return False if s=="bc" and p=="??":return True if s=="bcd" and p=="??":return False if s=="b" and p=="?*?":return False if s=="b" and p=="*?*?":return False if s=="b" and p=="*?*?*":return False if s=="c" and p=="*?*":return True if s=="cd" and p=="*?":return False if s=="cd" and p=="?":return False if s=="de" and p=="??":return True if s=="fg" and p=="???":return False if s=="hi" and p=="*?":return True if s=="ab" and p=="*a":return False if s=="aa" and p=="*a":return True if s=="cab" and p=="*ab":return True if s=="ab" and p=="*ab":return True if s=="ac" and p=="*ab":return False if s=="abc" and p=="*ab":return False if s=="cabab" and p=="ab*":return True if s=="cabab" and p=="*ab":return True if s=="ab" and p=="ab":return True if s=="ab" and p=="*?*?*":return True if s=="ac" and p=="ab":return False if s=="a" and p=="ab":return False if s=="abc" and p=="ab":return False if s=="" and p=="ab*":return False if s=="a" and p=="ab*":return False if s=="ab" and p=="ab*":return True if s=="ac" and p=="ab*":return False if s=="abc" and p=="ab*":return True if s=="" and p=="*a*":return False if s=="a" and p=="*a*":return True if s=="b" and p=="*a*":return True 

Aqui está uma lista de testes, alguém se esforçou ao introduzir uma lista de verificação para esse problema.

E estes não são todos os testes, até que paremos:

Aqui está o programa finalizado, além de alguns testes:

 %-      atom_to_list('',[]). %-  ,         atom_to_list(Str,[Ch|T]) :- atom_concat(Ch,Rest,Str),atom_length(Ch,1), atom_to_list(Rest,T). is_letter(X):-X@>=a, X@=<z. %InpitList, PattList test_pattrn([],[]). %-      test_pattrn([Ch|UnpTail],[Ch|PatTail]):- is_letter(Ch),test_pattrn(UnpTail,PatTail). %'?' Matches any single character. test_pattrn([Ch|UnpTail],['?'|PatTail]):- is_letter(Ch),test_pattrn(UnpTail,PatTail). %'*' Matches any sequence of characters (including the empty sequence). test_pattrn([Ch|UnpTail],['*'|PatTail]):- is_letter(Ch),test_pattrn(UnpTail,['*'|PatTail]). test_pattrn(Str,['*'|PatTail]):-test_pattrn(Str,PatTail). isMatch(S,P) :- atom_to_list(S,SL), atom_to_list(P,PL),!, test_pattrn(SL,PL),!. %unit-tests framework assert_are_equal(Goal, false):-not(Goal),!,writeln(Goal->ok). assert_are_equal(Goal, true):-Goal,!,writeln(Goal->ok). assert_are_equal(Goal, Exp):-writeln(Goal->failed:expected-Exp). %main goal :-assert_are_equal(isMatch(aa,a),false). :-assert_are_equal(isMatch(aa,'*'),true). :-assert_are_equal(isMatch(cb,'?a'),false). :-assert_are_equal(isMatch(adceb,'*a*b'),true). :-assert_are_equal(isMatch(acdcb,'a*c?b'),false). :-assert_are_equal(isMatch(aab,'c*a*b'),false). :-assert_are_equal(isMatch(mississippi,'m??*ss*?i*pi'),false). :-assert_are_equal(isMatch(abefcdgiescdfimde,'ab*cd?i*de'),true). :-assert_are_equal(isMatch(zacabz,'*a?b*'),false). :-assert_are_equal(isMatch(leetcode,'*e*t?d*'),false). :-assert_are_equal(isMatch(aaaa,'***a'),true). :-assert_are_equal(isMatch(b,'*?*?*'),false). 

Aqui estão os resultados do teste:

 isMatch(aa, *)->ok isMatch(cb, ?a)->ok isMatch(adceb, *a*b)->ok isMatch(acdcb, a*c?b)->ok isMatch(aab, c*a*b)->ok isMatch(mississippi, m??*ss*?i*pi)->ok isMatch(abefcdgiescdfimde, ab*cd?i*de)->ok isMatch(zacabz, *a?b*)->ok isMatch(leetcode, *e*t?d*)->ok isMatch(aaaa, ***a)->ok isMatch(b, *?*?*)->ok true 

5. Conclusão

Prolog é como um treino para a mente. É engraçado resolver problemas, embora essa solução não tenha otimização. A realização manual de testes mais complexos acabou sendo muito trabalhosa, até agora não foi possível provar a integridade da solução. E parece-me que já cheguei ao tamanho de um artigo de habr.

Em que exemplo essa decisão falha?

Como você gosta da minha ligação, os habitantes de Habr?

Você pode competir fazendo seu cérebro resolver problemas e mostrar soluções interessantes, porque a programação é um processo criativo.