Design de Idiomas: Correspondência de Padrão 2D

49

Este é o Desafio Quinzenal # 6 . Tema: Design Língua

Há uma sala de bate-papo para esse desafio. Venha se juntar a nós se você quiser discutir idéias!

E agora para algo completamente diferente...

Nesta quinzena, queremos experimentar um novo tipo de desafio. Neste desafio, você estará criando um idioma! A correspondência de padrões é um problema muito comum na programação e geralmente muito útil para o golfe com código. Expressões regulares, por exemplo, podem ser usadas para detectar um padrão em uma linha de texto. No entanto, não existem métodos estabelecidos para descrever e detectar padrões bidimensionais.

O desafio

Você deve criar uma linguagem de correspondência de padrões, que permita a descrição de padrões bidimensionais em blocos de texto. O modo de operação do seu idioma será semelhante às expressões regulares (embora seu idioma não precise ter nada em comum com o regex):

  • Como entrada, você receberá um bloco de texto retangular. Você pode presumir que o texto consiste apenas em caracteres ASCII imprimíveis (0x20 a 0x7E) e em novas linhas (0x0A) para separar as linhas da grade.
  • Se uma correspondência, de acordo com a descrição do padrão, puder ser encontrada como qualquer subconjunto deste bloco de texto, essa correspondência deverá ser retornada ou impressa. Se a correspondência puder ser não retangular, ela deverá ser preenchida em uma área retangular com algum caractere reservado. Se houver várias correspondências válidas, você poderá decidir como a correspondência retornada será escolhida (maior, menor, primeira etc.).

Para alguns aplicativos, pode ser útil se sua implementação puder retornar a posição de uma correspondência em vez da própria correspondência, mas isso não é um requisito.

No mínimo, seu idioma deve poder corresponder a um padrão como uma sub-região retangular contígua de sua entrada.

Sua resposta deve conter:

  • Uma descrição do idioma.
  • Uma implementação de trabalho . Pode ser um programa ou um conjunto de funções / classes em um idioma de sua escolha.
  • Você deve demonstrar seu idioma, mostrando como ele pode ser usado para resolver os exemplos fornecidos abaixo . Seu idioma não precisa ser compatível com todos eles, mas você deve ser capaz de corresponder a pelo menos oito deles. Se o seu idioma puder fazer algo sofisticado que não pensamos, fique à vontade para incluí-lo também.

Se sua resposta se basear nas idéias existentes, tudo bem, mas dê crédito onde é devido.

Extensões

O descrito acima descreve o mínimo que um envio válido deve atender. No entanto, várias generalizações podem tornar essa linguagem de correspondência de padrões ainda mais útil, incluindo, entre outras:

  • Ser capaz de ancorar o padrão em uma ou mais arestas, para que você possa verificar se toda a região de entrada possui um determinado padrão.
  • Produzindo todas as correspondências em vez de apenas uma. Você pode escolher a semântica de correspondências sobrepostas.
  • Tomando texto não retangular como entrada.
  • Permitindo que os padrões especifiquem correspondências não retangulares. Nesse caso, a saída deve ser preenchida em um retângulo com algum caractere reservado.
  • Permitindo que os padrões especifiquem correspondências com furos.
  • Permitindo correspondências não contíguas, como dois caracteres que aparecem com um determinado deslocamento.
  • Fácil especificação de rotações e reflexões.
  • Opcionalmente, trate a entrada ciclicamente como um cilindro ou um toro, de modo que as bordas opostas sejam consideradas adjacentes.

Pontuação

O objetivo principal desse desafio é produzir uma linguagem 2D de correspondência de padrões eficaz que possa ser usada no futuro. Como tal, um sistema de pontuação como "menor comprimento combinado para resolver os exemplos" levaria à codificação de certas funcionalidades em detrimento da usabilidade geral. Portanto, decidimos que esse desafio é melhor executado como um concurso de popularidade. A finalização com mais votos líquidos vence. Embora não possamos forçar a maneira como as pessoas votam, aqui estão algumas diretrizes para o que os eleitores devem idealmente procurar:

  • Expressividade. A linguagem pode resolver uma variedade de problemas, mesmo além dos exemplos apresentados nesta pergunta? Ele suporta alguma das extensões sugeridas?
  • Legibilidade. Quão intuitiva é a notação (pelo menos para pessoas que conhecem a sintaxe básica)?
  • Golfitude. Este ainda é o CodeGolf.SE. Para os propósitos deste site, é claro que seria bom ter uma linguagem correspondente que precise de muito pouco código para descrever um padrão.

Problemas de exemplo

O seguinte snippet de pilha mostra 16 problemas de exemplo com os quais um idioma de correspondência de padrão 2D poderia ser capaz de lidar. Cada exemplo contém uma breve descrição do problema e é geralmente seguido por um exemplo de entrada em que uma correspondência pode ser encontrada e um exemplo em que nenhuma correspondência pode ser encontrada (se aplicável).

Como mencionado acima, seu idioma precisa apenas ser capaz de resolver 8 desses problemas. Tudo isso é opcional, mas é claro que deve aumentar o número de votos que você recebe.

Mostrar snippet de código

(Não, você não precisa ler esse código HTML. Pressione o botão "Executar trecho de código" para obtê-lo perfeitamente processado pelo seu navegador, que também poderá ser exibido em tela cheia.)

popularity-contest string grid language-design PhiNotPi
fonte
Existe um prazo geral para esses problemas? Estou muito interessado em resolver isso, mas estou muito ocupado, isso poderia levar duas semanas para ser feito.
Devon Parsons
7
@DevonParsons Não há prazo de inscrição.
PhiNotPi 03/03
Parece interessante, especialmente desde que você criou uma nova tag para isso. Eu acho que deveria haver pontos de bônus para criar uma linguagem 2D para isso.
mbomb007
11
@ mbomb007 Existem pontos de bônus para criar uma linguagem 2D. Tenho certeza de que receberia uma quantidade razoável de votos. ;)
Martin Ender
@ MartinBüttner Eu nem sei como criar um idioma, realmente. Poderia ser algo tão (simples?) Como criar um programa Python que pega um arquivo do código da sua nova linguagem (e interpretá-lo / executá-lo com base na sintaxe definida) e produzir saída?
mbomb007

Respostas:

32

SnakeEx

Resolve 15/16 problemas até agora!

Intérprete Online ! - Especificações completas do idioma - Fonte Javascript

captura de tela do intérprete

A idéia por trás dessa linguagem é definir 'serpentes' que se movem pelos caracteres de verificação de texto usando uma sintaxe do tipo regex.

Um programa no SnakeEx consiste em uma lista de definições para cobras usando diferentes seqüências de comandos. As cobras podem gerar outras cobras usando essas definições, e é aí que o SnakeEx obtém a maior parte de seu poder - podemos combinar estruturas de ramificação e até fazer recursão (veja o exemplo de Paren Matching).

Todo programa parecerá essencialmente um conjunto de expressões regulares, mas com a adição de comandos de direção da forma <dir>que mudam a direção da cobra e chamam comandos da forma {label<dir>params}que gera mais cobras.

Para um ponto de entrada, o intérprete cria uma cobra usando a primeira definição, movendo-se para a direita.

Não é muito conciso, mas é muito poderoso e (acho) bastante legível.

Atualizações

  • Changed! para não lógico e ~ para não marcar correspondências
  • Adicionado <!>para resolver colinear
  • Cruzamentos correspondentes resolvidos
  • Tabuleiros de xadrez resolvidos de uma maneira menos terrível
  • Adicionada sintaxe de fechamento limitado %{min,max}
  • Exemplo de recursão adicionado

Soluções

15 resolvidos, 1 em andamento

Você pode experimentar esses programas facilmente usando o Intérprete on-line vinculado acima!

Problema 1 - Encontrando Tabuleiros de Xadrez

m:{v<R>2}{h<>1}
v:{c<L>A1}+
h:{c<R>A2}+
c:_?(#_)+#?

Para uma introdução detalhada, inicie no Problema 3.

Problema 2 - Verificando tabuleiros de xadrez

m:{v<R>2}{h<>1}
v:${c<L>A1}+$
h:${c<R>A2}+$
c:$_?(#_)+#?$

Reservar as cobras apropriadas com o símbolo fora dos limites $é uma maneira de fazer um programa corresponder apenas a toda a entrada.

Problema 3 - Detectar um retângulo de dígitos

m:{c<R>A1}%{2,}
c:[0-9]%{2,}

A mcobra se move para a direita, gerando no mínimo 2 cobras ( %{2,}é um fechamento que significa "2 ao infinito") usando a definição c ( c) e movendo para a direita ( <R>), ou melhor, neste caso, porque todas as direções são relativas à cobra atual. O Aparâmetro é o açúcar que apenas especifica que a cobra desova deve se mover após a chamada. O 1parâmetro é como restringimos as correspondências aos retângulos - os parâmetros numéricos colocam cobras em "grupos". Uma partida não conta, a menos que todas as cobras do mesmo grupo viajem exatamente à mesma distância.

Problema 4 - Localizando uma palavra em uma pesquisa por palavra

m:<*>GOLF

O comando direction <*>especifica que a cobra deve girar em qualquer direção diagonal ou ortogonal. Em seguida, procura o regex simples.

Problema 5 - Detectar entradas quadradas

m:{v<R>1}{h<>1}
v:${c<L>A1}+$
h:${c<R>A1}+$
c:$.+$

A chave aqui é o caractere especial $, que só corresponde se a cobra estiver fora dos limites. Criamos uma cobra horizontal e uma vertical; cada uma dessas cria mais cobras enquanto corre ao longo da borda, e todas estão no mesmo grupo e devem ter o mesmo comprimento.

Problema 6 - Encontre planadores em um jogo da vida

m:<+>[({l1<R>A}{l2<R>A}{l3<R>})({l1<L>A}{l2<L>A}{l3<L>})]
l1:##\.
l2:[(#\.)(\.#)]#
l3:#\.\.

minicia em qualquer uma das quatro direções ortogonais ( <+>), obtendo rotação. Em seguida, ele parece esquerdo ou direito para as três linhas em ordem, alcançando reflexão.

(Observe que substituí os espaços por pontos apenas porque as áreas de texto HTML usadas no meu intérprete parecem fazer coisas estúpidas se tiverem vários espaços seguidos)

Problema 7 - Coincidir com portais inferiores

m:{e<R>A1}{d<R>A1}%{2,22}{e<R>1}
e:~.X%{3,22}~.
d:X\.+X

A mcobra se move para a direita, gerando uma cobra para verificar a borda esquerda, 2-22 cobras para verificar as colunas do meio e, finalmente, uma cobra para verificar a borda direita. O ~operador indica que tudo o que se segue deve ser verificado, mas não deve ser marcado como parte da solução.

Agora, os fechamentos limitados nos permitem resolver total e adequadamente esse problema!

Problema 8 - Colocação do baú do Minecraft

m:~{s<>}~!{d<+>}\.
s:<+>.<BR>([$\.]<R>)%{3}
d:.<+>CC

Aqui usamos um not ( !) lógico , que corresponde se e somente se o token a seguir não corresponder a nada. A declaração ddetecta um baú duplo em uma direção específica, para !{d<+>}garantir que não haja baús duplos em nenhuma direção ortogonal. sse move em um pequeno diamante ao redor do quadrado atual, verificando se pelo menos três desses espaços estão vazios ou fora do tabuleiro. A trilha \.finalmente coincide com a praça, assumindo que todas as condições anteriores foram bem-sucedidas.

Problema 9 - Alinhamento Horizontal e Vertical

m:<R>?#~.*#

A cobra mopcionalmente vira à direita ( <R>?) antes de corresponder à sequência. .é um curinga, como no regex.

Problema 10 - Pontos Colineares

m:<!>#~.*#~.*#

Com a adição da <!>direção, podemos resolver isso agora! <!>é como, <+>mas em vez de se ramificar em quatro direções, se ramifica em todas as direções possíveis.

Problema 12 - Evite a letra Q

m:{h<R>A}%{4}
h:[^Qq]%{4}

Apenas gera 4 cobras, cada uma procurando por quatro caracteres que não são a letra Q.

Problema 13 - Mineração de diamantes

m:{tl<RB>1}{tr<RF>1}
tl:X/*{bl<L>1}X
tr:X\\*{br<R>1}X
bl:X\\*X
br:X/*X

Essa é bem legal. mcria duas cobras, uma voltada para a direita e outra para a direita. Cada uma delas segue as barras até um X e depois cria outra cobra em ângulo reto com a direção atual, que segue as barras até o X inferior.

Problema 14 - Correspondências cruzadas

m:{a<R>A}+{b<R>A}+{a<R>A}+
a:{e<>P1}{c<>P2}{e<>P3}
b:{c<>P1}{c<>P2}{c<>P3}
e:\.+
c:#+

Aqui está a primeira vez que usei o Pparâmetro iggyback. Normalmente, as cobras são independentes, mas se você fizer uma chamada com esse parâmetro, a cobra chamadora será movida com o chamado. Assim, e2podemos verificar uma sequência de '.', Depois uma sequência de '#', depois outra sequência de '.', E fazer com que todas sejam chamadas separadas para que possamos agrupá-las com '1,' 2 'e' 3 ' , forçando seus comprimentos a corresponderem.

Problema 15 - Combine uma palavra em uma placa Boggle

m{I}:<*>p<*>a<*>n<*>a<*>m<*>a

Simples, se prolixo. IO parâmetro especifica distinção entre maiúsculas e minúsculas (podemos especificar parâmetros nas definições e nas chamadas). A cobra vira em qualquer direção, combina com o personagem, vira novamente e assim por diante.

m{EI}:<*>p<*>a<*>n<*>a<*>m<*>a

Esta é a versão sem caracteres reutilizáveis. O Eparâmetro xclusive proíbe a cobra de combinar qualquer caractere que já tenha sido marcado, como as trilhas de lodo de feersum.

Problema 16 - Enrole as bordas

m{W}:{c<R>WA}%{3}
c:###

O Wparâmetro permite que a cobra envolva quando estiver fora dos limites. Também temos He Vpermitimos apenas o empacotamento horizontal ou vertical.

Extra - Maze Solver

m{E}:$(<P>\.)+$

Resolve um labirinto ASCII em que o piso percorrível é períodos. A <P>direção significa avançar, esquerda ou direita (açúcar para [<F><L><R>]).

Correspondência Extra - Paren

m:\(~{r<>P}\)
r:[^\(\)]*(\({r<>P}\))?[^\(\)]*

Ainda não descobrimos como fazer o Prelude, mas aqui está o primeiro passo! Aqui eu uso a rcobra recursivamente para combinar os parênteses correspondentes, verificando se não há parênteses incomparáveis ​​entre eles.

Topologia ASCII extra : contando loops

BMac
fonte
Você consideraria adicionar sintaxe para que esse idioma pudesse substituir e não apenas corresponder? Quero usar alguma solução para esse desafio para escrever uma entrada para codegolf.stackexchange.com/questions/51231/…, mas nenhuma solução aqui aqui encontra e substitui. (Eu sei que minha resposta não seria devido válida a regras de tempo de linguagem de especificação)
Sparr
@Sparr. Não é uma má idéia, certamente seria mais útil para o código de golfe. Não tenho certeza de quando terei tempo para fazer isso sozinho, mas vou manter isso em mente.
BMAC
3
separadamente: a sintaxe para mudanças de direção é confusa. porque a cobra progride depois de corresponder a um personagem, eu pareço ter que fazer com que minha direção mude um personagem antes do que faz sentido para mim. exemplo: string "ABC \ nDEF" e quero corresponder à peça de tetris em forma de L definida por ABCF, quero escrever minha cobra como "m: ABC <R> F", mas preciso escrever "m: AB <R> CF "em vez disso. Entendo que isso corresponde às especificações, mas acho muito contra-intuitivo.
Sparr
Eu tenho uma solução parcial para sintaxe prelúdio. O único problema é que não consigo fazer a correspondência se não corresponder a toda a entrada: m:{a<>} a:[({n<R>A})({n<R>A}*{l<R>A}{a<>P}{r<R>A})]*{n<R>A}* l:$[^\(\)]*\([^\(\)]*$ r:$[^\(\)]*\)[^\(\)]*$ n:$[^\(\)]+$
TheNumberOne
21

Slip, Python 3.4 ( wiki do Github , intérprete on-line )

Assim como a submissão do feersum, isso também se baseia em percorrer a grade, mas, como a submissão do CarpetPython, isso se baseia no regex. De alguma forma, parece que eu consegui tomar o meio termo.

Há muitos recursos não implementados que quero adicionar; portanto, quando relevante, observei o que pretendo fazer quando tiver tempo.

Atualizações

(Veja a página do Github para notícias detalhadas)

  • 5 de abril de 2015 : o Slip agora tem um intérprete online ! Ainda está em seus estágios iniciais, então pode haver alguns bugs.

  • 5 de abril de 2015 : atualização de eficiência! Agora os portais inferiores introduzem muito mais rapidamente (2s). Também houve várias alterações de sintaxe, portanto, verifique o wiki. A numeração do grupo também foi corrigida.

O deslizamento tem um ponteiro de partida que começa em um quadrado específico e está inicialmente voltado para a direita. Quando um caractere é correspondido, o ponteiro se move para frente na direção atual (embora a implementação não faça as coisas exatamente nessa ordem).

A direção do ponteiro jogo pode ser ajustado para uma determinada direção com ^<digit>, onde ^0, ^1, ^2, ..., ^7definir o ponteiro para N, NE, E, ..., NW, respectivamente (no sentido horário indo).

Os seguintes atalhos também estão disponíveis:

  • ^* verifica todas as 8 direções ortogonais ou diagonais,
  • ^+ verifica todas as quatro direções ortogonais.

(Plano futuro: permita o estabelecimento de direções arbitrárias, por exemplo, (1, 2)para a movimentação do cavaleiro)

Por exemplo ( Problema 4 - Localizando uma palavra em uma pesquisa por palavra ),

^*GOLF

tenta todas as 8 direções ortogonais ou diagonais, procurando a palavra "GOLFE". Por padrão, o Slip tenta todos os quadrados iniciais possíveis e retorna um resultado de cada um, filtrando duplicatas, de modo que uma grade como

GOLF
O
L
FLOG

retorna apenas a linha superior e a linha inferior como correspondências (uma vez que a linha superior e a coluna esquerda "GOLF" começam no mesmo quadrado). Para obter todas as correspondências, o omodo de correspondência sobreposta pode ser usado.

Da mesma forma ( Problema 15 - Combine uma palavra em um quadro do Boggle ),

p^*a^*n^*a^*m^*a

combina panamatentando uma direção diferente a cada vez. Use o isinalizador para diferenciar maiúsculas de minúsculas. Slip reutiliza caracteres por padrão, mas isso pode ser alternado com o rsinalizador de não repetição.

(Plano futuro: um modificador de modo de pesquisa que verifica automaticamente conjuntos de direções após cada movimento para que a repetição ^*seja desnecessária)

A direção do ponteiro da partida também pode ser girada 90 graus para a esquerda ou direita com <ou >respectivamente. Por exemplo,

 `#`#< `#<  <`#<`#

procura o padrão

  #
## 
 ##

olhando na seguinte ordem:

765
894
123

Isso nos permite resolver o Problema 6 - Encontrar planadores com

^+(`#`# >`# > `#>`#> |`#`# <`# < `#<`#< | `#`#> `#>  >`#>`#| `#`#< `#<  <`#<`#)

em que as partes 1 e 2 codificam as formas do planador e as partes 3 e 4 codificam suas contrapartes refletidas.

Observe que o Slip usa backtick `para escapar. Isso ocorre porque o Slip tem outra forma de movimento que dá nome ao idioma - o comando slip. /desliza o ponteiro da partida ortogonalmente para a esquerda, enquanto \desliza o ponteiro da partida ortogonalmente para a direita.

Por exemplo,

abc   ghi
   def

pode ser correspondido por abc\def/ghi.

Embora não seja particularmente útil por si só, o escorregamento se torna mais importante quando combinado com o (?| <regex> )grupo estacionário, que age como um lookahead correspondente. A regex interna é correspondida e, no final, a posição e a direção do ponteiro da correspondência são redefinidas para o estado antes do grupo estacionário.

Por exemplo,

abc
def
ghi

pode ser combinado com (?|abc)\(?|def)\(?|ghi).

Da mesma forma, Problema 12 - Evite que a letra Q possa ser resolvida com

%(\(?|[^qQ]{4})){4}

onde %é um comando antiderrapante para impedir a \ativação do primeiro .

O deslizamento também possui uma declaração de comprimento (?_(<group num>) <regex> ), que só corresponde à regex interna se o comprimento da correspondência for o mesmo que o do número de grupo especificado.

Por exemplo, o Problema 13 - Mineração de diamantes pode ser facilmente resolvido com

^1X(`/*)X>(?_(1)`\*)X>(?_(1)`/*)X>(?_(1)`\*)

que tenta corresponder primeiro ao lado esquerdo superior do diamante e depois afirma que os outros três lados têm o mesmo comprimento.

(Execute com vsinalizador para saída detalhada)

Match found in rectangle: (8, 0), (12, 4)
  X
 / \
X   X
 \ /
  X

Match found in rectangle: (0, 0), (6, 6)
   X
  / \
 /   \
X     X
 \   /
  \ /
   X

Match found in rectangle: (2, 2), (4, 4)
 X
X X
 X

Match found in rectangle: (10, 2), (14, 6)
  X
 / \
X   X
 \ /
  X

Match found in rectangle: (5, 3), (9, 7)
  X
 / \
X   X
 \ /
  X

Match found in rectangle: (0, 6), (2, 8)
 X
X X
 X

Uma alternativa golfista é

^1X(`/*)(X>(?_(1)`\*)X>(?_(1)`/*)){2}

que corresponde ao primeiro lado duas vezes.

Muitos dos outros problemas podem ser resolvidos usando escorregões, grupos estacionários e declarações de comprimento:

Problema 14 - Cruzamentos correspondentes:

(?|(`.+)(`#+)(`.+))(\(?|(?_(2)`.+)(?_(3)`#+)(?_(4)`.+)))*(\(?|(?_(2)`#+)(?_(3)`#+)(?_(4)`#+)))+(\(?|(?_(2)`.+)(?_(3)`#+)(?_(4)`.+)))+

Uma vez que você capturar as larguras das .s e #s na primeira linha, é só escorregar todo o caminho.

Resultado:

Match found in rectangle: (0, 1), (5, 5)
.###..
######
######
.###..
.###..

Match found in rectangle: (4, 6), (6, 8)
.#.
###
.#.

Provavelmente, este pode ser jogado com um pouco de recursão, uma vez que eu resolvo alguns bugs.

Problema 3 - Detecte um retângulo de dígitos:

(?|`d`d+)(\(?|(?_(1)`d+)))+

Combine uma linha superior de dois ou mais dígitos e verifique se todas as linhas abaixo têm o mesmo comprimento. `dé uma classe de caracteres predefinida equivalente a [0-9].

Observe que isso encontra todas as correspondências .

Problema 7 - Coincidir com portais inferiores:

(?|.X{2,22}.)\((?|(?_(1)X`.+X))\){3,22}(?_(1).X+.)

quais saídas, para o exemplo principal no encadeamento original :

Match found in rectangle: (2, 1), (5, 5)
XXXX
X..X
X..X
X..X
XXXX

Match found in rectangle: (9, 1), (14, 5)
.XXXX.
X....X
X....X
X....X
.XXXX.

Match found in rectangle: (13, 4), (17, 8)
.XXXX
X...X
X...X
X...X
.XXX.

Finalmente, alguns outros recursos do Slip incluem:

  • $0, $1, $2, ..., $7ancore a borda norte, o canto nordeste, a borda leste, etc. $+ancore qualquer borda e $*ancore qualquer canto.
  • $seguido por um caractere minúsculo define uma âncora na posição atual, que pode ser correspondida posteriormente $seguida pelo caractere maiúsculo correspondente, por exemplo, $ae $A.
  • # alterna o sinalizador sem movimento, o que impede o ponteiro da partida de avançar após a próxima partida.
  • ,corresponde a um caractere como ., mas não o adiciona à saída, permitindo correspondências não contíguas enquanto pode ser reconhecido por (?_()).

... e mais. Há realmente muitos para listar nesta página.

Outros problemas

Problema 1 - Encontrar tabuleiros de xadrez:

(?|`#?(`_`#)+`_?)(?_(1)(?|...+))(\(?_(1)(?|`#?(`_`#)+`_?$a)))+<(?|`#?(`_`#)+`_?)(?_(9)(?|...+))(\(?_(9)(?|`#?(`_`#)+`_?)))+$A

Os dois problemas do tabuleiro de xadrez certamente não são o forte de Slip. Combinamos a linha superior #e _, em seguida, garantimos que ela tenha pelo menos o comprimento 3 e alterne entre e , em seguida, deslize e combine as linhas subseqüentes. No final, a $aâncora deve estar no canto inferior direito do tabuleiro de xadrez.

Em seguida, vire à esquerda e repita para as colunas, certificando-se de que correspondemos $Ano final.

Problema 2 - Verificando tabuleiros de xadrez:

$7%(\(?|`_?(`#`_)*`#?$2))+$5<%(\(?|`_?(`#`_)*`#?$0))+$3

Como no problema anterior, verificamos se cada linha está correta, depois giramos para a esquerda e fazemos o mesmo para as colunas. As âncoras são usadas para garantir que apenas toda a placa seja correspondida.

Problema 9 - Alinhamento horizontal e vertical:

>?`#,*`#

Nós aplicamos o opcional? quantificador para o >comando rotate, para que correspondamos à direita ou para baixo. Encontramos todos os 5 no exemplo com o omodo de sobreposição, mas apenas 4 sem ele desde então #.,##e #.,#partimos da mesma posição.

Problema 10 - Pontos colineares

^+`#(?|(,*)<(,*))(((?_(2),*)<(?_(3),*),>)+#`#){2}

Faça a correspondência de #alguns caracteres horizontais e verticais, depois repita até o segundo #e repita até o terceiro #.

Problema 5 - Detectando entradas quadradas:

$7.(.*)>(?_(1).*)$3>((?|.*)\)*

Ancore o canto superior esquerdo e verifique se a borda superior tem o mesmo comprimento que a borda direita, antes de ancorar o canto inferior direito. Se a entrada passar por isso, subimos para trás para corresponder a toda a entrada.

Problema 8 - Colocação do baú do Minecraft:

`.^+(($^|(?|`.))>){3}($^|`.|C<(($^|(?|`.))>){3})

Corra com a pbandeira para obter as posições de cada partida. $^é uma âncora que corresponde se o próximo movimento colocar o ponteiro da correspondência fora dos limites.

Primeiro, combinamos com a ., depois verificamos que estamos cercados por três .s / limites e, em seguida, certificamo-nos de que o quarto quadrado circundante também seja um ./ limite ou seja um único baú (verificando seus quadrados circundantes).

Problema 11 - Verifique a sintaxe do Prelude :

$7>%(/(?|[^()]+$4)(?1)?|/(?|[^()]*`([^()]*$4)(?1)?/(?|[^()]*`)[^()]*$4)(?1)?)$1

Tomou algumas tentativas, mas acho que esta é correta. Aqui usamos recursão, que tem a mesma sintaxe que PCRE.

Essa abordagem exige que a entrada seja retangular, mas assim que eu fizer uma correspondência não retangular, essa suposição não será necessária.

Aqui está a mesma abordagem, com mais recursão:

$7>%((/(?|([^()]*)$4)|/(?|(?4)`((?3))(?1)?/(?|(?4)`)(?3)))*)$1

Problema 16 - Enrole as bordas:

%(\(?|`#{3})){3}

(Nota: o agrupamento ainda não foi enviado ao intérprete on-line)

Isso requer o sinalizador de quebra automática w. Tecnicamente, a inicial %para o derrapagem não é necessária, mas a partida será contada como começando a partir de um quadrado mais alto.

Problema EX 1 - Solucionador de labirinto:

S(^+`.)*^+E

Problema do comentário do BMac no chat . Use a rbandeira para o modo sem repetição, para que o ponteiro da partida não fique preso indo e voltando.

Problema EX 2 - Reconhecimento facial :

(?|O(,*),(?_(2),*)O)(?_(2)(\(?|,))*)\(?|,(?_(2),*)O)(?_(2)(\(?|,))*)\`\(?_(2)`_*)`_(?_(2)`_*)`/

Observe que estou apenas combinando rostos, não fazendo nenhuma limpeza. Observe que a pergunta contém símbolos de euro, que precisarão ser substituídos por alguns ASCII imprimíveis para funcionar.

Sp3000
fonte
Esse padrão de hash é um planador Conway
Heimdall
17

PMA / Caracóis (C ++)

Eu imagino a linguagem como caracóis se movendo em uma grade e executando comandos. Os caracóis deixam um rastro de lodo em cada quadrado em que se movem, o que, por padrão, faz com que o quadrado seja subsequentemente incomparável. Uma correspondência será bem-sucedida se o final da lista de comandos for alcançado.

Agora, existem operadores suficientes que precisaremos de uma lista de precedências para acompanhá-los. As operações são resolvidas na seguinte ordem:

  1. Dentro dos grupos ( ) [ ]
  2. Dividir ao longo do caractere de alternância |
  3. Avalie tudo à esquerda de `um grupo
  4. Quantificadores [m],[n]en
  5. Asserções = !
  6. Concatenação

O intérprete é escrito em C ++. O código-fonte abismal pode ser encontrado aqui .

Problema 4: Pesquisa de Palavras

O programa

z\G\O\L\F

é suficiente para obter um valor de verdade ou falsey para saber se a palavra é encontrada. z(um dos 15 comandos direcionais absolutos ou relativos) corresponde em qualquer direção octilinear. Vários comandos de direção consecutivos são ORed juntos. Por exemplo, ruldyseria quase equivalente a z, pois esses são os comandos para a direita, para cima, para a esquerda, para baixo e para qualquer direção diagonal. No entanto, as instruções seriam testadas em uma ordem diferente. O primeiro caractere correspondente é sempre aquele em que o caracol começa, independentemente da direção. \<caractere> corresponde a um único caractere literal.

A estratégia padrão é tentar o padrão em todos os quadrados na caixa delimitadora da entrada justificada à esquerda e gerar o número de correspondências. Se um valor booleano 1ou 0for necessário, o seguinte programa pode ser usado:

?
z\G\O\L\F

Se houver pelo menos uma nova linha no arquivo de origem, a primeira linha será tratada como opções para a conversão inicial da entrada em um formato retangular. A ?opção imprime 0 ou 1, dependendo se há uma correspondência em qualquer lugar.

Problema 15: Boggle

Após implementar a alternância, agora é possível resolver o Boggle. Seria melhor usar a correspondência sem distinção entre maiúsculas e minúsculas para esse, mas implementar essa não é minha maior prioridade.

\p|\P)z(\a|\A)z{\n|\N)z{\a|\A}z(\m|\M)z(\a|\A

|funciona exatamente da mesma forma que uma regex unidimensional. Existem dois pares correspondentes de delimitadores para agrupamento, a saber, ()e {}. Um colchete de fechamento fechará quaisquer grupos abertos do tipo oposto que ficarem entre ele e o mais próximo do mesmo tipo. Por exemplo, a seguir {({{), apenas o grupo mais à esquerda permanece aberto. Como você pode ver, símbolos de agrupamento incomparáveis ​​nas bordas estão implicitamente fechados. Há outro comando de agrupamento no `qual não entrarei agora.

Problema 8: Baús do Minecraft

O programa imprime o número de canais válidos no peito. Este foi o primeiro que eu realmente tive que jogar golfe e reduzi minha contagem de bytes (17) algumas vezes.

\.!(o\C)2o(!\Cw)3
  • \. corresponde a um ponto literalmente, no ponto de partida da partida.
  • !(o\C)2é equivalente a !((o\C)2)quantificação ter maior precedência que asserção. <atom> <number>significa repetir <atom>exatamente os <number>tempos. ogira o caracol em qualquer direção ortogonal. !é uma afirmação negativa. Assim, esta parte verifica a ausência de um baú duplo adjacente.
  • o gira em alguma direção ortogonal.
    • (!\Cw)3afirma que não há Cna frente do caracol e depois gira no sentido anti-horário, três vezes.

Problema 2: Verificando Tabuleiros de Xadrez

&
\#!(o^_)|\_!(o^#

A &opção define a saída do programa como 1se a correspondência tivesse êxito em todas as posições e 0caso contrário. ^ccorresponde a um caractere que não é c, equivalente a [^c]em regex. Como um todo, o programa significa: Imprima 1 se, em todas as posições do retângulo delimitador da entrada, houver um #que não seja ortogonalmente adjacente a um caractere que não seja _ou _que não seja ortogonalmente adjacente a um caractere que seja não #; caso contrário, 0.

feersum
fonte
A idéia rastro de lodo é uma boa para lidar com boggle, eu estava tendo alguns problemas com isso
BMAC
Essa é uma boa solução para o problema do Boggle. Não posso resolver isso com a minha abordagem.
Logic Knight
14

A classe Re2d, Python 2

Atualização: adicionado o problema "9. Alinhamento".

Minha abordagem é usar o módulo re Python para fazer a pesquisa e correspondência. A classe Re2d prepara o texto para processamento, executa as funções re e formata os resultados para saída.

Observe que este não é um idioma totalmente novo - é o idioma de expressão regular padrão projetado em 2 dimensões com sinalizadores adicionais para modos 2D adicionais.

A classe tem o seguinte uso:

re2dobject = Re2d(<horizontal pattern>, [<vertical pattern>], [<flags>])

Ambos os padrões são padrões RE de texto linear padrão. Se um padrão vertical não for fornecido, a classe usará o padrão horizontal para fazer a correspondência vertical também. Os sinalizadores são os sinalizadores RE padrão com algumas extensões 2D.

Testando

1. Finding chessboards
Chessboard pattern at (2, 1, 4, 3)

print '\n1. Finding chessboards'
reob1 = Re2d('#(_#)+_?|_(#_)+#?')
found = reob1.search('~______~\n~##_#_#~\n~#_#_##~\n~##_#_#~\n~______~')
print 'Chessboard pattern at', found
assert not reob1.search('#_##\n_#_#\n__#_\n#_#_\n#_#_')

O método de busca encontrou um padrão de tabuleiro de xadrez e retorna uma posição de quatro tuplas. A tupla tem a x,yposição do primeiro caractere da partida e width, heighta área correspondente. Somente um padrão é fornecido e, portanto, será usado para correspondência horizontal e vertical.

2. Verifying chessboards
Is chess? True

print '\n2. Verifying chessboards'
reob2 = Re2d('^#(_#)*_?|_(#_)*#?$')
print 'Is chess?', reob2.match('_#_#_#_#\n#_#_#_#_\n_#_#_#_#')
assert not reob2.match('_#_#_#__\n__#_#_#_\n_#_#_#__')

O tabuleiro de xadrez foi verificado com o método match, que retorna um valor booleano. Note que o ^e $iniciar e caracteres finais são obrigados a corresponder ao todo texto.

3. Rectangle of digits
Found: [(0, 1, 5, 3), (1, 1, 4, 3), (2, 1, 3, 3), (3, 1, 2, 3), (0, 2, 5, 2), (1, 2, 4, 2), (2, 2, 3, 2), (3, 2, 2, 2), (6, 3, 2, 2)]
Not found: None

print '\n3. Rectangle of digits'
reob3 = Re2d(r'\d\d+', flags=MULTIFIND)
print 'Found:', reob3.search('hbrewvgr\n18774gwe\n84502vgv\n19844f22\ncrfegc77')
print 'Not found:', reob3.search('uv88wn000\nvgr88vg0w\nv888wrvg7\nvvg88wv77')

Agora usamos o MULTIFINDsinalizador para retornar todas as correspondências possíveis para o bloco de 2 ou mais dígitos. O método encontra 9 correspondências possíveis. Observe que eles podem se sobrepor.

4. Word search (orthogonal only)
Words: [(0, 0, 4, 1), (0, 3, 4, 1), (3, 3, -4, -1), (3, 2, -4, -1), (3, 0, -4, -1)] [(0, 0, 1, 4), (3, 0, 1, 4), (3, 3, -1, -4), (0, 3, -1, -4)]
Words: ['SNUG', 'WOLF', 'FLOW', 'LORE', 'GUNS'] ['S\nT\nE\nW', 'G\nO\nL\nF', 'F\nL\nO\nG', 'W\nE\nT\nS']
No words: [] []

print '\n4. Word search (orthogonal only)'
words = 'GOLF|GUNS|WOLF|FLOW|LORE|WETS|STEW|FLOG|SNUG'
flags = HORFLIP | VERFLIP | MULTIFIND
reob4a, reob4b = Re2d(words, '.', flags), Re2d('.', words, flags)
matching = 'SNUG\nTEQO\nEROL\nWOLF'
nomatch = 'ABCD\nEFGH\nIJKL\nMNOP'
print 'Words:', reob4a.search(matching), reob4b.search(matching)
print 'Words:', reob4a.findall(matching), reob4b.findall(matching)
print 'No words:', reob4a.findall(nomatch), reob4b.findall(nomatch)

Este teste mostra o uso de inversão vertical e horizontal. Isso permite que as palavras correspondentes sejam revertidas. Palavras diagonais não são suportadas. O MULTIFINDsinalizador permite várias correspondências sobrepostas nas 4 direções. O método findall usa a pesquisa para encontrar as caixas correspondentes e extrai os blocos de texto correspondentes. Observe como a pesquisa usa largura e / ou altura negativas para correspondências na direção reversa. As palavras na direção vertical têm novos caracteres de linha - isso é consistente com o conceito de blocos de caracteres 2D.

7. Calvins portals
Portals found: [(3, 1, 5, 6)]
Portal not found None

print '\n7. Calvins portals'
reob7 = Re2d(r'X\.{2,22}X|.X{2,22}.', r'X\.{3,22}X|.X{3,22}.', MULTIFIND)
yes = '....X......\n.XXXXXX.XX.\n...X...X...\n.X.X...XXX.\n...X...X.X.\n.XXX...X.X.\nX..XXXXX.X.'
no = 'XX..XXXX\nXX..X..X\nXX..X..X\n..X.X..X\n.X..X.XX'
print 'Portals found:', reob7.search(yes)
print 'Portal not found', reob7.search(no)

Essa pesquisa precisava de padrões separados para cada dimensão, pois o tamanho mínimo é diferente para cada uma.

9. Alignment
Found: ['#.,##', '##'] ['#\n.\n,\n.\n#', '#\n,\n.\n#']
Found: [(3, 4, 5, 1), (6, 4, 2, 1)] [(7, 0, 1, 5), (3, 1, 1, 4)]
Not found: None None

print '\n9. Alignment'
reob9a = Re2d(r'#.*#', r'.', MULTIFIND)
reob9b = Re2d(r'.', r'#.*#', MULTIFIND)
matching = '.,.,.,.#.,\n,.,#,.,.,.\n.,.,.,.,.,\n,.,.,.,.,.\n.,.#.,##.,\n,.,.,.,.,.'
nomatch = '.,.#.,.,\n,.,.,.#.\n.,#,.,.,\n,.,.,.,#\n.#.,.,.,\n,.,.#.,.\n#,.,.,.,\n,.,.,#,.'
print 'Found:', reob9a.findall(matching), reob9b.findall(matching)
print 'Found:', reob9a.search(matching), reob9b.search(matching)
print 'Not found:', reob9a.search(nomatch), reob9b.search(nomatch)

Este conjunto de 2 pesquisas localiza 2 correspondências verticais e 2 horizontais, mas não consegue encontrar a #.,#sequência incorporada .

10. Collinear Points (orthogonal only)
Found: [(0, 1, 7, 1)] [(3, 1, 1, 4)]
Not found: None None

print '\n10. Collinear Points (orthogonal only)'
matching = '........\n#..#..#.\n...#....\n#.......\n...#....'
nomatch = '.#..#\n#..#.\n#....\n..#.#'
reob10h = Re2d(r'#.*#.*#', '.')
reob10v = Re2d('.', r'#.*#.*#')
flags = MULTIFIND
print 'Found:', reob10h.search(matching, flags), reob10v.search(matching, flags)
print 'Not found:', reob10h.search(nomatch, flags), reob10v.search(nomatch, flags)

Aqui usamos 2 pesquisas para encontrar correspondências nas duas direções. É capaz de encontrar várias correspondências ortogonais, mas essa abordagem não suporta correspondências diagonais.

12. Avoid qQ
Found: (2, 2, 4, 4)
Not found: None

print '\n12. Avoid qQ'
reob12 = Re2d('[^qQ]{4,4}')
print 'Found:', reob12.search('bhtklkwt\nqlwQklqw\nvtvlwktv\nkQtwkvkl\nvtwlkvQk\nvnvevwvx')
print 'Not found:', reob12.search('zxvcmn\nxcvncn\nmnQxcv\nxcvmnx\nazvmne')

Esta pesquisa encontra a primeira correspondência.

13. Diamond Mining
.X.
X.X
.X.

.X.
X.X
.X.

..X..
./.\.
X...X
.\./.
\.X..

..X..
./.\.
X...X
.\./.
..X..

.XX.\
//.\.
X...X
.\./.
..X..

...X...
../.\..
./.X.\.
X.X.X.X
.\.X.//
..\./X.
.X.X..\

Diamonds: [(2, 2, 3, 3), (0, 6, 3, 3)] [(8, 0, 5, 5), (10, 2, 5, 5), (5, 3, 5, 5)] [(0, 0, 7, 7)]
Not found: None None None

print '\n13. Diamond Mining'
reob13a = Re2d(r'.X.|X.X', flags=MULTIFIND)
reob13b = Re2d(r'..X..|./.\\.|X...X|.\\./.', flags=MULTIFIND)
reob13c = Re2d(r'...X...|../.\\..|./...\\.|X.....X|.\\.../.|..\\./..', flags=MULTIFIND)
match = '''
...X......X....
../.\..../.\...
./.X.\..X...X..
X.X.X.XX.\./.\.
.\.X.//.\.X...X
..\./X...X.\./.
.X.X..\./...X..
X.X....X.......
.X.............
'''.strip().replace(' ', '')
nomatch = '''
.X......./....
.\....X.......
...X.\.\...X..
..X.\...\.X.\.
...X.X...X.\.X
../X\...\...X.
.X...\.\..X...
..\./.X....X..
...X..../.....
'''.strip().replace(' ', '')
for diamond in reob13a.findall(match)+reob13b.findall(match)+reob13c.findall(match):
    print diamond+'\n'
print 'Diamonds:', reob13a.search(match), reob13b.search(match), reob13c.search(match)
print 'Not found:', reob13a.search(nomatch), reob13b.search(nomatch), reob13c.search(nomatch)

O problema do diamante é mais difícil. Três objetos de pesquisa são necessários para os três tamanhos. Ele pode encontrar os seis diamantes no conjunto de teste, mas não é dimensionado para diamantes de tamanho variável. Esta é apenas uma solução parcial para o problema do diamante.

Código Python 2

import sys
import re

DEBUG = re.DEBUG
IGNORECASE = re.IGNORECASE
LOCALE = re.LOCALE
UNICODE = re.UNICODE
VERBOSE = re.VERBOSE
MULTIFIND = 1<<11
ROTATED = 1<<12     # not implemented
HORFLIP = 1<<13
VERFLIP = 1<<14
WRAPAROUND = 1<<15  # not implemented

class Re2d(object):
    def __init__(self, horpattern, verpattern=None, flags=0):
        self.horpattern = horpattern
        self.verpattern = verpattern if verpattern != None else horpattern
        self.flags = flags

    def checkblock(self, block, flags):
        'Return a position if block matches H and V patterns'
        length = []
        for y in range(len(block)):
            match = re.match(self.horpattern, block[y], flags)
            if match:
                length.append(len(match.group(0)))
            else:
                break
        if not length:
            return None
        width = min(length)
        height = len(length)
        length = []
        for x in range(width):
            column = ''.join(row[x] for row in block[:height])
            match = re.match(self.verpattern, column, flags)
            if match:
                matchlen = len(match.group(0))
                length.append(matchlen)
            else:
                break
        if not length:
            return None
        height = min(length)
        width = len(length)
        # if smaller, verify with RECURSIVE checkblock call:
        if height != len(block) or width != len(block[0]):
            newblock = [row[:width] for row in block[:height]]
            newsize = self.checkblock(newblock, flags)
            return newsize
        return width, height

    def mkviews(self, text, flags):
        'Return views of text block from flip/rotate flags, inc inverse f()'
        # TODO add ROTATED to generate more views
        width = len(text[0])
        height = len(text)
        views = [(text, lambda x,y,w,h: (x,y,w,h))]
        if flags & HORFLIP and flags & VERFLIP:
            flip2text = [row[::-1] for row in text[::-1]]
            flip2func = lambda x,y,w,h: (width-1-x, height-1-y, -w, -h)
            views.append( (flip2text, flip2func) )
        elif flags & HORFLIP:
            hortext = [row[::-1] for row in text]
            horfunc = lambda x,y,w,h: (width-1-x, y, -w, h)
            views.append( (hortext, horfunc) )
        elif flags & VERFLIP:
            vertext = text[::-1]
            verfunc = lambda x,y,w,h: (x, height-1-y, w, -h)
            views.append( (vertext, verfunc) )
        return views

    def searchview(self, textview, flags=0):
        'Return matching textview positions or None'
        result = []
        for y in range(len(textview)):
            testtext = textview[y:]
            for x in range(len(testtext[0])):
                size = self.checkblock([row[x:] for row in testtext], flags)
                if size:
                    found = (x, y, size[0], size[1])
                    if flags & MULTIFIND:
                        result.append(found)
                    else:
                        return found
        return result if result else None

    def search(self, text, flags=0):
        'Return matching text positions or None'
        flags = self.flags | flags
        text = text.split('\n') if type(text) == str else text
        result = []
        for textview, invview in self.mkviews(text, flags):
            found = self.searchview(textview, flags)
            if found:
                if flags & MULTIFIND:
                    result.extend(invview(*f) for f in found)
                else:
                    return invview(*found)
        return result if result else None

    def findall(self, text, flags=0):
        'Return matching text blocks or None'
        flags = self.flags | flags
        strmode = (type(text) == str)
        text = text.split('\n') if type(text) == str else text
        result = []
        positions = self.search(text, flags)
        if not positions:
            return [] if flags & MULTIFIND else None
        if not flags & MULTIFIND:
            positions = [positions]
        for x0,y0,w,h in positions:
            if y0+h >= 0:
                lines = text[y0 : y0+h : cmp(h,0)]
            else:
                lines = text[y0 : : cmp(h,0)]
            if x0+w >= 0:
                block = [row[x0 : x0+w : cmp(w,0)] for row in lines]
            else:
                block = [row[x0 : : cmp(w,0)] for row in lines]
            result.append(block)
        if strmode:
            result = ['\n'.join(rows) for rows in result]
        if flags & MULTIFIND:
            return result
        else:
            return result[0]

    def match(self, text, flags=0):
        'Return True if whole text matches the patterns'
        flags = self.flags | flags
        text = text.split('\n') if type(text) == str else text
        for textview, invview in self.mkviews(text, flags):
            size = self.checkblock(textview, flags)
            if size:
                return True
        return False
Cavaleiro Lógico
fonte
Se o problema do diamante não estava claro, os diamantes podem ter qualquer tamanho, não apenas 0, 1 ou 2. Editar: editei a especificação para deixar isso mais claro.
PhiNotPi 6/03/2015
Entendi. Anotarei na resposta que o Re2d tem apenas uma solução parcial para esse problema. Não pode ser dimensionado para tamanhos variáveis. Tudo bem?
Logic Knight
Sim está bem.
PhiNotPi
14

Grime , Haskell

Introdução

O Grime é baseado em gramáticas booleanas . A idéia básica é construir padrões retangulares a partir de componentes menores e verificar se eles são encontrados na matriz de entrada. Até agora, o Grime suporta apenas correspondências retangulares e resolve pelo menos 11 problemas com mais ou menos elegância.

EDIT: Corrigido os cruzamentos (graças ao DLosc por detectar o bug) e adicionado mineração de diamantes.

EDIT2: Adicionadas classes de personagens, inspiradas nas de Slip. Também alterou a sintaxe dos sinalizadores de opção, melhorou o analisador de expressão e adicionou o problema não-Q.

EDIT3: Implementou restrições de tamanho e adicionou o problema dos portais Nether.

Uso

Um programa Grime é chamado de gramática , e a extensão de arquivo correta para uma gramática é .gr, embora isso não seja imposto. A gramática é avaliada como

runhaskell grime.hs [options] grammarfile matrixfile

onde matrixfileé um arquivo que contém a matriz de caracteres. Por exemplo, a gramática de dígitos seria avaliada como

runhaskell grime.hs digits.gr digit-matrix

Para uma velocidade extra, recomendo compilar o arquivo com otimizações:

ghc -O2 grime.hs
./grime digits.gr digit-matrix

Por padrão, o intérprete imprime a primeira correspondência encontrada, mas isso pode ser controlado usando os sinalizadores de opção:

  • -e: corresponde apenas a matriz inteira, imprime 1para correspondência e 0para não correspondência.
  • -n: imprime o número de correspondências ou a matriz inteira, se -etambém for fornecida.
  • -a: imprime todas as correspondências.
  • -p: imprime também as posições das correspondências, no formato (x,y,w,h).
  • -s: não imprime as correspondências.
  • -d: imprime informações de depuração.

As opções também podem ser especificadas na gramática, inserindo-as antes de qualquer linha e adicionando uma vírgula ,(veja exemplos abaixo).

Sintaxe e Semântica

Uma gramática do Grime consiste em uma ou mais definições , cada uma em uma linha separada. Cada um deles define o valor de um não - terminal e um deles deve definir o não-terminal anônimo de nível superior . A sintaxe de uma definição é N=Eou E, onde Né uma letra maiúscula e Eé uma expressão .

Expressões são construídas da seguinte maneira.

  • Qualquer caractere com escape \corresponde a qualquer 1x1retângulo que contenha esse caractere.
  • . corresponde a qualquer caractere único.
  • $corresponde a um 1x1retângulo fora da matriz de caracteres.
  • _ corresponde a qualquer retângulo com largura ou altura zero.
  • Os grupos de caracteres predefinidos são digit, uppercase, lowercase, alphabetic, alfa numérico e ssímbolo.
  • Novas classes de caracteres podem ser definidas pela sintaxe [a-prt-w,d-gu]. As letras à esquerda estão incluídas e as da direita são excluídas, portanto, isso corresponde exatamente às letras abchijklmnoprtvw. Se o lado esquerdo estiver vazio, é usado para conter todos os caracteres. A vírgula pode ser omitida se o lado direito estiver vazio. Os caracteres [],-\devem ser escapados com \.
  • Uma letra maiúscula sem escape é não-terminal e corresponde à expressão que está atribuída.
  • Se Pe Qsão expressões, então PQé apenas a concatenação horizontal e P/Qa concatenação vertical, com Pno topo.
  • P+é um ou mais Ps alinhados horizontalmente e P/+é o mesmo alinhado verticalmente.
  • As operações booleanas são indicadas P|Q, P&Qe P!.
  • P?é uma abreviação de para P|_, P*para P+|_e P/*para P/+|_.
  • P#corresponde a qualquer retângulo que contenha uma correspondência de P.
  • P{a-b,c-d}, Onde abcdsão inteiros não negativos, é uma restrição tamanho na P. Se Pfor uma classe de caracteres, a expressão corresponderá a qualquer mxnretângulo que contenha apenas esses caracteres, desde que mentre ae binclusive, e nentre ce dinclusive. Em outros casos, a expressão corresponde a qualquer retângulo que tenha o tamanho correto e que Ptambém corresponda. Se aou csão omitidos, eles são considerados 0e se bou dsão omitidos, são infinitos. Se o hífen entre ae bfor omitido, usamos o mesmo número para as duas extremidades do intervalo. Se todo oc-dparte é omitida, ambos os eixos são restritos. Para esclarecer, {-b}é equivalente a {0-b,0-b}e {a-,c}é equivalente a {a-infinity,c-c}.

Notas

O Grime permite definições paradoxais, como A=A!no comportamento indefinido. No entanto, eles não causarão falhas ou loops infinitos.

O Grime suporta entradas não retangulares; as linhas são simplesmente alinhadas à esquerda e as lacunas podem ser correspondidas usando $.

No futuro, gostaria de implementar o seguinte:

  • Correspondência mais rápida. Atualmente, o intérprete não leva em conta o fato de que, por exemplo, .só pode corresponder a 1x1retângulos. Até encontrar uma correspondência, ele tenta todos os retângulos de todos os tamanhos em ordem, falhando instantaneamente para cada um deles.
  • Operações de rotação e reflexão, para os desafios de busca por palavra e planador.

  • Correspondências não retangulares usando contextos , o que seria útil no desafio do quadro Boggle. Por exemplo, Pv(Q>R)significa Pcom contexto inferior ( Qcom contexto correto R). Combinaria com os padrões em forma de L

    PPP
PPP
QQQRRRR
QQQRRRR
QQQRRRR

As tarefas

Dado aproximadamente em ordem de complexidade.

Retângulo de dígitos

d{2-}

Isso é simples: pelo menos um retângulo de dígitos de tamanho 2x2.

Não q ou Q

[,qQ]{4}

Isso é quase tão simples quanto o primeiro; agora temos um tamanho mais restrito e uma classe de caracteres personalizada.

Alinhamento horizontal e vertical

\#.*\#|\#/./*/\#

Agora temos alguns caracteres escapados. Basicamente, isso corresponde a um #, a qualquer número de caracteres e #, na horizontal ou na vertical.

Detectar entradas quadradas

S=.|S./+/.+
e,S

Essa gramática é muito simples, ela basicamente define que um quadrado é um 1x1retângulo ou um quadrado menor com uma coluna alinhada na borda direita e uma linha alinhada na parte inferior. Observe também a eopção antes do nível não-terminal de nível superior, que alterna a verificação de entrada inteira.

Localizando uma palavra em uma pesquisa por palavra

G=\G
O=\O
L=\L
F=\F
GOLF|FLOG|G/O/L/F|F/L/O/G|G.../.O../..L./...F|...G/..O./.L../F...|F.../.L../..O./...G|...F/..L./.O../G...

Essa é horrível, já que Grime não tem operações de rotação ou reflexão. Também é extremamente lento, uma vez que Grime não sabe que os jogos só pode ser de tamanho 4x1, 1x4ou 4x4.

O problema do planador poderia ser resolvido da mesma forma, mas tenho preguiça de anotá-lo.

Portais inferiores

.\X+./\X/+\.{2-22,3-22}\X/+/.\X+.

Com o operador de restrição de tamanho, este não é tão difícil. A parte do meio\.{2-22,3-22} corresponde a qualquer retângulo dos .tamanhos corretos e, em seguida, apenas adicionamos colunas de Xs em ambos os lados e alinhavamos linhas de Xs com extremidades ignoradas na parte superior e inferior do mesmo.

Cruzamentos correspondentes

E=\.+/+
F=\#+/+
EFE/F/EFE&(E/F/E)F(E/F/E)

O que temos aqui é uma conjunção (AND lógico) de duas expressões. O não terminal Ecorresponde a um retângulo não vazio de .s e Fum retângulo não vazio de# s. O lado esquerdo da conjunção corresponde a retângulos do tipo

...####..
...####..
...####..
#########
#########
.....##..
.....##..

onde nós temos EFE no topo, então Fe EFEnovamente. O lado direito corresponde às transposições dessas, então obtemos exatamente as cruzes.

Mineração de diamantes

C=./+
T=\X|CTC/\/.+\\
B=\X|\\.+\//CBC
CTC/\X.+\X/CBC

O não C- terminal é uma abreviação para qualquer 1xncoluna. A metade superior de um diamante corresponde a T: é um único Xou outro Tcercado por uma coluna de ambos os lados e uma linha/[something]\ abaixo . Bcoincide com o fundo de um diamante da mesma maneira, e o não-terminal de nível superior é apenas uma linha do formulário X[something]Xentre a metade superior e a metade inferior.

Encontrar tabuleiros de xadrez

(\#\#|\#/\#|\_\_|\_/\_)#!&[#_]{3-}

O lado direito [#_]{3-}corresponde a um 3x3ou mais retângulos de #s e _s, enquanto o lado esquerdo garante que ele não contém dois# s ou s_ .

Verificando tabuleiros de xadrez

e,(\#\#|\#/\#|\_\_|\_/\_)#!&[#_]+/+

É basicamente o mesmo que acima, exceto que podemos corresponder a qualquer retângulo não vazio, mas precisamos usar o esinalizador para verificação de entrada inteira.

Verificar sintaxe do prelúdio

A=[,()]/*
P=A*|P(A/\(/A)P(A/\)/A)P
e,P

Esta é provavelmente a gramática mais interessante até agora. O não terminal Acorresponde a qualquer coluna que não contenha (ou )e Pcorresponde a algum número de As ou dois parênteses correspondentes, entre e fora dos quais existem mais Ps.

Zgarb
fonte
@DLosc Fixed, obrigado por encontrar o bug!
Zgarb 30/03
Funcionaria \#(.*|./*)\#?
seequ
@ Sieg Para o alinhamento? Infelizmente não, porque isso seria analisado como "um #à esquerda, depois uma linha ou coluna de qualquer coisa, depois um #à direita". Eu preciso especificar que os #s são verticalmente concatenados para a coluna usando as barras /.
Zgarb 31/03
10

TMARL

Idioma de correspondência e reconhecimento de modelos

Descrição

Meu intérprete ocupa caracteres de 24K ( trechos de código ocupam caracteres? ), Portanto, a descrição completa pode ser encontrada aqui .

A melhor parte: o intérprete está em Javascript, o que significa que você pode experimentá-lo aqui!

Mostrar snippet de código

E para os problemas:

# 1 - Encontrar tabuleiros de xadrez

$#_#
a
$_#_
bvacvbS5&(avcS5)G0G2P

&anexa pesquisas. O G2 no final obtém o terceiro elemento em um elemento de correspondência, a correspondência real. Os 2 primeiros elementos são coordenadas xey (com base em 1, e não em 0).

# 3 - Detectar um retângulo de dígitos

$DD
$DD
S1G2P

Eu acho que esse é bem direto.

# 4 - Encontrando uma palavra em uma pesquisa por palavra

$GO\LF
a
$G
$*O
$**\L
$***F
S6&(aS6)G0G2P

o S argumento é uniforme para que ele procure todas as rotações. É maior que 4 porque pode ser anexado à próxima pesquisa (correspondências individuais não podem ser anexadas).

# 5 - Detectar entradas quadradas

IL-(IG0L)!P

Não tenho certeza se isso é completamente legal, pois ele determina apenas a quadratura corretamente se a entrada for um retângulo. Ele compara o comprimento da entrada ILcom o comprimento da primeira linhaIG0L e a inverte.

# 6 - Encontre planadores em um jogo da vida

$## 
$# #
$# 
a
$ ##
$## 
$  #
bS6&(bMS6)&(aS6)&(aMS6)G0G2P

Finalmente, um uso para espelho!

# 12 - Evite a letra Q

$[^Qq]
~4*4S1G2P

S1 porque apenas 1 correspondência é necessária.

Farei alguns dos mais difíceis mais tarde.

Stretch Maniac
fonte