Conception de langage: Correspondance de modèle 2D

49

C'est le défi bimensuel n ° 6 . Thème: Conception de la langue

Il y a une salle de discussion pour ce défi. Venez nous rejoindre si vous voulez discuter d’idées!

Et maintenant pour quelque chose de complètement différent...

Cette quinzaine, nous voulons expérimenter un nouveau type de défi. Dans ce défi, vous allez concevoir une langue! La correspondance de modèle est un problème très courant en programmation et souvent très utile pour le golf de code. Les expressions régulières, par exemple, peuvent être utilisées pour détecter un motif dans une ligne de texte. Cependant, il n’existe aucune méthode établie pour décrire et détecter les régularités bidimensionnelles.

Le défi

Vous devez concevoir un langage de correspondance de modèle qui permette la description de modèles bidimensionnels dans des blocs de texte. Le mode de fonctionnement de votre langue sera similaire à celui des expressions régulières (bien que votre langue n'ait rien d'autre en commun avec regex sinon):

  • En entrée, vous recevrez un bloc de texte rectangulaire. Vous pouvez supposer que le texte ne comprend que des caractères ASCII imprimables (0x20 à 0x7E) ainsi que des nouvelles lignes (0x0A) pour séparer les lignes de la grille.
  • Si une correspondance, conformément à la description du modèle, peut être trouvée en tant que sous-ensemble de ce bloc de texte, cette correspondance doit être renvoyée ou imprimée. Si la correspondance peut être non rectangulaire, elle doit être complétée dans une zone rectangulaire avec un caractère réservé. S'il existe plusieurs correspondances valides, vous pouvez décider comment la correspondance renvoyée est choisie (la plus grande, la plus petite, la première, etc.).

Pour certaines applications, il peut être utile que votre implémentation puisse renvoyer la position d'une correspondance au lieu de la correspondance elle-même, mais cela n'est pas obligatoire.

À tout le moins, votre langue devrait pouvoir faire correspondre un modèle en tant que sous-région rectangulaire contiguë de son entrée.

Votre réponse devrait contenir:

  • Une description de la langue.
  • Une mise en œuvre de travail . Cela peut être un programme ou un ensemble de fonctions / classes dans la langue de votre choix.
  • Vous devriez montrer votre langage en montrant comment il peut être utilisé pour résoudre les exemples fournis ci-dessous . Votre langue ne doit pas nécessairement être capable de les faire correspondre à toutes, mais vous devez être capable d’en faire correspondre au moins 8 . Si votre langue peut faire quelque chose d'extraordinaire auquel nous n'avions pas pensé, n'hésitez pas à l'inclure également.

Si votre réponse s'appuie sur des idées existantes, c'est très bien, mais merci de bien vouloir le créditer.

Les extensions

Ce qui précède décrit le minimum qu'une soumission valide doit satisfaire. Cependant, plusieurs généralisations pourraient rendre un tel langage de correspondance de modèle encore plus utile, notamment:

  • Être capable d'ancrer le motif à un ou plusieurs bords, de sorte que l'on puisse vérifier si toute la région d'entrée a un certain motif.
  • Produire tous les matches au lieu d'un seul. Vous pouvez choisir la sémantique des correspondances qui se chevauchent.
  • Prendre un texte non rectangulaire en entrée.
  • Permettre aux modèles de spécifier des correspondances non rectangulaires. Dans un tel cas, la sortie devrait être complétée en un rectangle avec un caractère réservé.
  • Permettre aux modèles de spécifier des correspondances avec des trous.
  • Permettre des correspondances non contiguës, comme deux caractères apparaissant avec un certain décalage.
  • Spécification facile des rotations et des réflexions.
  • Traiter éventuellement l'entrée cycliquement comme un cylindre ou un tore, de sorte que les bords opposés soient considérés comme adjacents.

Notation

Le principal objectif de ce défi est de produire un langage de filtrage de motifs 2D efficace pouvant éventuellement être utilisé à l'avenir. En tant que tel, un système de notation du type "longueur combinée la plus courte pour résoudre les exemples" conduirait à coder en dur certaines fonctionnalités aux dépens de la convivialité générale. Par conséquent, nous avons décidé que ce défi serait mieux géré comme un concours de popularité. La soumission avec le plus de votes nets gagne. Bien que nous ne puissions pas forcer les gens à voter, voici quelques lignes directrices concernant ce que les électeurs devraient idéalement rechercher:

  • Expressivité. Le langage peut-il résoudre divers problèmes, même au-delà des exemples présentés dans cette question? Est-ce qu'il supporte les extensions suggérées?
  • Lisibilité. À quel point la notation est-elle intuitive (du moins pour les personnes connaissant la syntaxe de base)?
  • Golfitude. C'est toujours CodeGolf.SE. Pour les besoins de ce site, il serait bien sûr d’avoir un langage correspondant qui nécessite très peu de code pour décrire un motif.

Exemple de problèmes

Le fragment de pile ci-dessous montre 16 exemples de problèmes qu’un langage de correspondance de modèle 2D pourrait traiter. Chaque exemple contient une courte description du problème. Il est ensuite généralement suivi d'un exemple d'entrée où une correspondance peut être trouvée et d'un exemple où aucune correspondance ne peut être trouvée (le cas échéant).

Comme indiqué ci-dessus, votre langue n'a besoin que de pouvoir résoudre 8 de ces problèmes. Tout ce qui est supplémentaire est facultatif, mais il faut bien entendu augmenter le nombre de votes obtenus.

(Non, vous n'avez pas besoin de lire ce code HTML. Appuyez sur le bouton "Exécuter l'extrait de code" pour obtenir un rendu fidèle par votre navigateur, que vous pourrez ensuite afficher en plein écran.)

PhiNotPi
la source
Existe-t-il une limite de temps générale pour ces problèmes? Je suis très intéressé par la résolution de ce problème, mais je suis très occupé, cela pourrait me prendre facilement 2 semaines.
Devon Parsons
7
@DevonParsons Il n'y a pas de date limite d'inscription.
PhiNotPi
Cela semble intéressant, surtout depuis que vous avez créé une nouvelle étiquette pour cela. Je pense qu'il devrait y avoir des points bonus pour la création d'un langage 2D.
mbomb007
1
@ mbomb007 Il existe des points bonus pour la création d'un langage 2D. Je suis à peu près sûr qu'il obtiendrait un nombre décent de votes positifs. ;)
Martin Ender
@ MartinBüttner Je ne sais même pas comment créer un langage, vraiment. Serait-ce quelque chose d'aussi simple que de créer un programme Python qui utilise un fichier du code de votre nouveau langage (et de l'interpréter / l'exécuter en fonction de la syntaxe définie) et de produire une sortie?
mbomb007

Réponses:

32

SnakeEx

Résout 15/16 problèmes jusqu'à présent!

Interprète en ligne ! - Spéc. De langage complet - Source Javascript

capture d'écran de l'interprète

L'idée derrière ce langage est de définir des "serpents" qui se déplacent dans le texte en vérifiant les caractères en utilisant une syntaxe de type regex.

Un programme dans SnakeEx consiste en une liste de définitions pour les serpents utilisant différentes séquences de commandes. Les serpents peuvent engendrer d'autres serpents à l'aide de ces définitions. C’est là que SnakeEx tire le meilleur parti de sa puissance: nous pouvons faire correspondre les structures de branchement et même faire de la récursion (voir l’exemple de Paren Matching).

Chaque programme ressemblera essentiellement à un ensemble de regex, mais avec l’ajout de commandes de direction de la forme <dir>qui changent la direction du serpent et d’ appeler des commandes de la forme {label<dir>params}qui engendrent plus de serpents.

Pour un point d'entrée, l'interprète génère un serpent en utilisant la première définition, en se déplaçant vers la droite.

Ce n'est pas très concis, mais c'est très puissant et (je pense) assez lisible.

Mises à jour

  • Modifié ! Logiquement pas et ~ ne pas marquer les correspondances
  • Ajouté <!>pour résoudre colinéaire
  • Résoudre les croix correspondantes
  • Résoudre les échiquiers d'une manière moins terrible
  • Ajout de la syntaxe de fermeture liée %{min,max}
  • Exemple de récursion ajouté

Solutions

15 résolus, 1 en cours

Vous pouvez facilement essayer ces programmes en utilisant l’interprète en ligne (lien ci-dessus)!

Problème 1 - Trouver des échiquiers

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

Pour une introduction détaillée, commencez par le problème 3.

Problème 2 - Vérification des échiquiers

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

Mettre fin aux livres avec les symboles hors limites $est un moyen de faire en sorte qu'un programme ne corresponde qu'à la totalité de l'entrée.

Problème 3 - Détecter un rectangle de chiffres

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

Le mserpent se déplace vers la droite, apparaissant à au moins 2 serpents ( %{2,}une fermeture signifie "2 à l'infini") en utilisant la définition c ( c) et en se déplaçant vers la droite ( <R>), ou plutôt vers le bas dans ce cas, car toutes les directions sont relatives au serpent actuel. Le Aparamètre est un sucre qui spécifie simplement que le serpent en train de se reproduire doit se déplacer après l'appel. Le 1paramètre indique comment nous limitons les correspondances aux rectangles - les paramètres numériques placent les serpents dans des "groupes". Une correspondance ne compte pas à moins que tous les serpents du même groupe parcourent exactement la même distance.

Problème 4 - Trouver un mot dans une recherche par mot

m:<*>GOLF

La commande direction <*>spécifie que le serpent doit tourner dans n'importe quelle direction diagonale ou orthogonale. Ensuite, il cherche la regex simple.

Problème 5 - Détecter les entrées carrées

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

La clé ici est le caractère spécial $, qui ne correspond que si le serpent est hors limites. Nous engendrons un serpent horizontal et un vertical; chacun de ceux-ci engendre plus de serpents lorsqu'il court le long du bord, et tous ceux-ci appartiennent au même groupe et doivent avoir la même longueur.

Problème 6 - Trouver des planeurs dans un jeu de la vie

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

mcommence dans l’une des quatre directions orthogonales ( <+>), en effectuant la rotation. Ensuite, les trois rangées apparaissent dans l’ordre, ce qui permet de réfléchir.

(Notez que j'ai remplacé les espaces par des points uniquement parce que les zones de texte HTML utilisées dans mon interprète semblent faire des choses stupides si elles ont plusieurs espaces consécutifs)

Problème 7 - Faire correspondre les portails du Nether

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

Le mserpent se déplace à droite, engendrant un serpent pour vérifier le bord gauche, 2 à 22 serpents pour vérifier les colonnes du milieu et enfin un serpent pour vérifier le bord droit. L' ~opérateur indique que ce qui suit doit être vérifié mais ne doit pas être marqué comme faisant partie de la solution.

Les fermetures délimitées nous permettent maintenant de résoudre pleinement et correctement ce problème!

Problème 8 - Placement de la poitrine dans Minecraft

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

Ici, nous utilisons une logique not ( !), qui correspond si et seulement si le jeton suivant ne correspond à rien. La déclaration ddétecte un double coffre dans une direction particulière. !{d<+>}Assurez-vous qu'il n'y a pas de double coffre dans une direction orthogonale. sdéplace un petit diamant autour du carré actuel, en vérifiant qu'au moins 3 de ces espaces sont vides ou non. La fin \.correspond finalement au carré, en supposant que toutes les conditions précédentes soient remplies.

Problème 9 - Alignement horizontal et vertical

m:<R>?#~.*#

Le serpent mtourne éventuellement à droite ( <R>?) avant de faire correspondre la séquence. .est un caractère générique, comme dans regex.

Problème 10 - Points colinéaires

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

Avec l'ajout de la <!>direction, nous pouvons résoudre ce problème maintenant! <!>est comme <+>mais au lieu de se ramifier dans quatre directions, il se ramifie dans toutes les directions possibles.

Problème 12 - Évitez la lettre Q

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

Il crée juste 4 serpents qui recherchent chacun quatre personnages qui ne sont pas la lettre Q.

Problème 13 - Extraction de diamants

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

Celui-ci est plutôt chouette. mengendre deux serpents, l'un à l'arrière droit et l'autre à l'avant droit. Chacune de celles-ci suit les barres obliques jusqu'à un X, puis engendre un autre serpent perpendiculaire à sa direction actuelle, qui suit les barres obliques jusqu'au X inférieur.

Problème 14 - Croix correspondante

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:#+

Voici la première fois que Pj'utilise le paramètre iggyback. Normalement, les serpents sont indépendants, mais si vous appelez avec ce paramètre, le serpent appelant sera déplacé avec l'appelé. Donc, e2on peut vérifier une séquence de '.', Puis une séquence de '#', puis une autre séquence de '.', Et les faire tous être des appels séparés afin que nous puissions les regrouper avec '1,' 2 'et' 3 ' , forçant leurs longueurs à correspondre.

Problème 15 - Correspondre à un mot dans un tableau de Boggle

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

Simple, si verbeux. Iparamètre spécifie la non-sensibilité à la casse (nous pouvons spécifier des paramètres sur les définitions ainsi que dans les appels). Le serpent tourne dans n'importe quelle direction, correspond au personnage, se tourne à nouveau, etc.

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

Ceci est la version sans caractères de réutilisation. Le Eparamètre xclusive interdit au serpent de faire correspondre tout caractère déjà marqué, un peu comme les traces de slime de feersum.

Problème 16 - Enrouler les bords

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

Ce Wparamètre permet au serpent de s’enrouler quand il est hors limites. Nous avons également Het Vpour permettre uniquement l'emballage horizontal ou vertical.

Extra - Solutionneur de labyrinthe

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

Résout un labyrinthe ASCII dont le sol est piétonnier. La <P>direction signifie en avant, à gauche ou à droite (sucre pour [<F><L><R>]).

Extra - Paren Matching

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

Vous ne savez pas encore comment utiliser Prelude, mais voici un premier pas! Ici, j'utilise le rserpent de manière récursive pour faire correspondre les parenthèses correspondantes en vérifiant qu'il n'y a pas de parenthèses sans correspondance entre elles.

Topologie Extra - ASCII: Comptage de boucles

BMac
la source
Envisageriez-vous l'ajout d'une syntaxe afin que ce langage puisse effectuer un remplacement plutôt qu'une simple correspondance? Je veux utiliser une solution à ce défi pour écrire une entrée pour codegolf.stackexchange.com/questions/51231/…, mais aucune solution ici ne permet de trouver et de remplacer. (Je sais que ma réponse ne serait pas valide en raison des règles de synchronisation relatives aux langues)
Sparr le
Sparr. Ce n'est pas une mauvaise idée, ce serait certainement plus utile pour le code golf. Je ne sais pas quand j'aurai le temps de le faire moi-même, mais je le garderai à l'esprit.
BMac
3
séparément: la syntaxe des changements de direction est source de confusion. parce que le serpent progresse après avoir apparié un personnage, il me semble que je dois faire en sorte que ma direction change d'un caractère avant l'endroit où cela me semble sensé. exemple: string "ABC \ nDEF" et je veux faire correspondre le morceau de tetris en forme de L défini par ABCF, je veux écrire mon serpent comme "m: ABC <R> F" mais je dois écrire "m: AB <R> CF "à la place. Je comprends que cela corresponde à la spécification, mais je trouve cela très contre-intuitif.
Sparr
J'ai une solution partielle pour la syntaxe prélude. Le seul problème est que je ne peux pas le faire ne pas correspondre s'il ne correspond pas à la totalité de l'entrée: 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 Github , interpréteur en ligne )

Comme la soumission de Feersum, ceci est également basé sur la traversée de la grille, mais comme la soumission de CarpetPython, cela est basé sur la regex. On dirait que j’ai réussi à prendre une position intermédiaire.

Je souhaite ajouter un grand nombre de fonctionnalités non implémentées. C'est pourquoi, le cas échéant, j'ai noté ce que j'avais l'intention de faire lorsque le temps me le permettrait.


Mises à jour

(Voir la page Github pour les nouvelles détaillées)

  • 5 avril 2015 : Slip a maintenant un interprète en ligne ! Il en est encore à ses débuts, il pourrait donc y avoir quelques bugs.

  • 5 avril 2015 : Mise à jour de l'efficacité! Maintenant, les portails inférieurs ont une grande entrée beaucoup plus rapide (2s). De plus, il y a eu un certain nombre de changements de syntaxe, alors assurez-vous de vérifier le wiki. La numérotation des groupes a également été corrigée.


Le glissement a un pointeur de correspondance qui commence à une case particulière et est initialement tourné vers la droite. Lorsqu'un caractère est mis en correspondance, le pointeur avance dans la direction actuelle (bien que l'implémentation ne fasse pas les choses exactement dans cet ordre).

La direction du pointeur de la correspondance peut être réglé à une direction particulière avec ^<digit>, où ^0, ^1, ^2, ..., ^7régler le pointeur vers N, NE, E, ..., NW respectivement (en sens horaire).

Les raccourcis suivants sont également disponibles:

  • ^* vérifie les 8 directions orthogonales ou diagonales,
  • ^+ vérifie les 4 directions orthogonales.

(Plan futur: autoriser la définition de directions arbitraires, par exemple (1, 2)pour le déplacement d'un chevalier)

Par exemple ( Problème 4 - Trouver un mot dans une recherche par mot ),

^*GOLF

essaie les 8 directions orthogonales ou diagonales, en recherchant le mot "GOLF". Par défaut, Slip essaie tous les carrés de départ possibles et renvoie un résultat pour chaque filtre, en filtrant les doublons.

GOLF
O
L
FLOG

ne renvoie que les lignes du haut et du bas comme correspondances (puisque la ligne du haut et la colonne de gauche "GOLF" partent du même carré). Pour obtenir toutes les correspondances, le omode de correspondance qui se chevauche peut être utilisé.

De même ( Problème 15 - Faire correspondre un mot dans un tableau Boggle ),

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

correspond panamaen essayant une direction différente à chaque fois. Utilisez le idrapeau pour l'insensibilité à la casse. Slip réutilise les caractères par défaut, mais cela peut être basculé avec le rdrapeau no-repeat.

(Plan futur: un modificateur de mode de recherche qui vérifie automatiquement des ensembles d’orientations après chaque déplacement, évitant ainsi toute répétition ^*inutile)

La direction du pointeur de correspondance peut également être tournée de 90 degrés vers la gauche ou vers la droite avec <ou >respectivement. Par exemple,

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

cherche le motif

  #
## 
 ##

en regardant dans l'ordre suivant:

765
894
123

Cela nous permet de résoudre le problème 6 - Trouver des planeurs avec

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

où les parties 1 et 2 codent les formes du planeur et les parties 3 et 4 leurs codes réfléchis.

Notez que Slip utilise backtick `pour s'échapper. En effet, le glissement a une autre forme de mouvement qui donne son nom à la langue - la commande de glissement. /glisse le pointeur de correspondance orthogonalement à gauche, alors que \le pointeur de correspondance orthogonale à droite.

Par exemple,

abc   ghi
   def

peut être jumelé par abc\def/ghi.

Bien que n'étant pas particulièrement utile en soi, le glissement devient plus important lorsqu'il est combiné avec le (?| <regex> )groupe stationnaire, qui agit comme un effet d'apparence identique. Les expressions rationnelles à l'intérieur sont mises en correspondance, puis à la fin, la position et la direction du pointeur de correspondance sont réinitialisées à l'état situé avant le groupe stationnaire.

Par exemple,

abc
def
ghi

peut être jumelé avec (?|abc)\(?|def)\(?|ghi).

De même, Problème 12 - Éviter la lettre Q peut être résolu avec

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

%est une commande antidérapante pour empêcher le premier \de s’activer.

Slip a aussi une assertion de longueur (?_(<group num>) <regex> ), qui ne correspond à la regex à l'intérieur que si sa longueur de correspondance est la même longueur que celle du groupe donné.

Par exemple, le problème 13 - L’exploitation de diamants peut être facilement résolu avec

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

qui tente de faire correspondre le premier côté gauche du diamant en premier, puis affirme que les trois autres côtés ont la même longueur.

(Run avec vflag pour une sortie prolixe)

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

Une alternative golfier est

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

qui correspond deux fois au premier côté.

De nombreux autres problèmes peuvent être résolus en utilisant des groupes de glissement, stationnaires et des affirmations de longueur:

Problème 14 - Croix correspondante:

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

Une fois que vous avez capturé les largeurs .s et #s de la première rangée, vous ne faites que glisser vers le bas.

Sortie:

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

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

Celui-ci peut probablement être joué au golf avec un peu de récursion, une fois que j'ai corrigé quelques bugs.

Problème 3 - Détecter un rectangle de chiffres:

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

Faites correspondre une rangée supérieure de deux chiffres ou plus, puis assurez-vous que chaque ligne ci-dessous a la même longueur. `dest une classe de caractères prédéfinie équivalente à [0-9].

Notez que cela trouve toutes les correspondances .

Problème 7 - Faites correspondre les portails inférieurs:

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

qui affiche, pour le premier exemple dans le thread d'origine :

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.

Enfin, certaines autres fonctionnalités de Slip incluent:

  • $0, $1, $2, ..., $7ancrez le bord nord, le coin nord-est, le bord est, etc. $+ancrez n'importe quel bord et $*ancrez n'importe quel coin.
  • $suivi d'un caractère minuscule définit une ancre à la position actuelle, qui peut être comparée ultérieurement à $suivie du caractère majuscule correspondant, par exemple, $aet $A.
  • # bascule l'indicateur de non-déplacement, qui empêche le pointeur de correspondance d'avancer après le prochain match.
  • ,correspond à un caractère comme ., mais ne l'ajoute pas à la sortie, ce qui permet des correspondances non contiguës tout en pouvant être reconnu par (?_()).

... et plus. Il y en a vraiment trop à énumérer sur cette page.

D'autres problèmes

Problème 1 - Trouver des échiquiers:

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

Les deux problèmes d’échiquier ne sont certainement pas le point fort de Slip. Nous faisons correspondre la ligne du haut, puis nous assurons qu’elle fait au moins la longueur 3 et alterne entre #et _, puis nous glissons et faisons correspondre les lignes suivantes. À la fin, l' $aancre devrait être en bas à droite de l'échiquier.

Nous tournons ensuite à gauche et répétons pour les colonnes, en nous assurant que la correspondance est établie $Aà la fin.

Problème 2 - Vérification des échiquiers:

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

Comme pour le problème précédent, nous vérifions que chaque ligne est correcte, puis pivotons à gauche et faisons de même pour les colonnes. Les ancres sont utilisées pour s’assurer que seul le tableau entier est assorti.

Problème 9 - Alignement horizontal et vertical:

>?`#,*`#

Nous appliquons les facultatifs? quantifier à la >commande de rotation afin que nous puissions faire correspondre soit vers le bas ou vers la droite. Nous trouvons tous les 5 dans l'exemple avec le omode de chevauchement, mais seulement 4 sans #.,##et depuis et #.,#partons de la même position.

Problème 10 - Points colinéaires

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

Faites correspondre #ensuite quelques caractères horizontaux et certains caractères verticaux, puis répétez jusqu'au deuxième #et répétez jusqu'au troisième #.

Problème 5 - Détection des entrées carrées:

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

Ancrez le coin supérieur gauche et vérifiez que le bord supérieur a la même longueur que le bord droit avant d’ancrer le coin inférieur droit. Si l'entrée réussit ceci, alors nous allons en arrière pour faire correspondre l'entrée entière.

Problème 8 - Placement de la poitrine de Minecraft:

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

Courez avec le pdrapeau pour obtenir les positions de chaque match. $^est une ancre qui correspond si le prochain mouvement mettrait le pointeur de correspondance en dehors des limites.

Nous avons d' abord correspondre à un ., puis vérifier que nous sommes encerclés par trois .s / limites, puis fait en sorte que la quatrième place environnante est également une ./ limite ou est un coffre (en vérifiant ses places environnantes).

Problème 11 - Vérifier la syntaxe Prelude :

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

J'ai pris quelques essais, mais je pense que c'est correct. Ici, nous utilisons la récursion, qui a la même syntaxe que PCRE.

Cette approche nécessite que l'entrée soit rectangulaire, mais une fois que j'ai obtenu une correspondance non rectangulaire, cette hypothèse ne sera plus nécessaire.

Voici la même approche, golfée avec plus de récursivité:

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

Problème 16 - Enrouler sur les bords:

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

(Remarque: le wrapping n'a pas encore été poussé vers l'interprète en ligne)

Cela nécessite le drapeau d'emballage w. Techniquement, l'initiale %pour le non-glissement n'est pas nécessaire, mais le match compterait alors comme commençant à partir d'une case plus haute.

Problème EX 1 - Solutionneur de labyrinthe:

S(^+`.)*^+E

Problème du commentaire de BMac dans le chat . Utilisez le rdrapeau pour le mode sans répétition afin que le pointeur de correspondance ne reste pas bloqué dans les deux sens.

Problème EX 2 - Reconnaissance faciale :

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

Notez que je ne fais que faire correspondre les visages sans faire de compensation. Notez que la question contient des symboles de l’euro, qui devront être remplacés par des ASCII imprimables pour fonctionner.

Sp3000
la source
Ce motif de hachage est un planeur de Conway
Heimdall
17

PMA / Escargots (C ++)

J'envisage le langage comme des escargots se déplaçant autour d'une grille et exécutant des commandes. Les escargots laissent une traînée de boue sur chaque case sur laquelle ils se déplacent, ce qui rend par défaut la case inégalable. Une correspondance est réussie si la fin de la liste de commandes est atteinte.

Il y a suffisamment d'opérateurs maintenant que nous aurons besoin d'une liste de priorité pour les suivre. Les opérations sont résolues dans l'ordre suivant:

  1. À l'intérieur des groupes ( ) [ ]
  2. Caractère divisé le long de l'alternance |
  3. Évaluez tout à gauche d' `un groupe
  4. Quantificateurs [m],[n]etn
  5. Assertions = !
  6. Enchaînement

L'interprète est écrit en C ++. Le code source abyssal peut être trouvé ici .

Problème 4: Recherche par mot

Le programme

z\G\O\L\F

est suffisant pour obtenir une valeur de vérité ou de falsey quant à savoir si le mot est trouvé. z(une des 15 commandes directionnelles absolues ou relatives) correspond dans n'importe quelle direction octilinéaire. Plusieurs ordres de direction consécutifs sont combinés ensemble. Par exemple, ce ruldyserait presque équivalent à z, car ce sont les commandes pour droite, haut, gauche, bas et toute diagonale. Cependant, les instructions seraient testées dans un ordre différent. Le premier caractère correspondant est toujours celui sur lequel l'escargot commence, quelle que soit sa direction. \<caractère> correspond à un seul caractère littéral.

La stratégie par défaut consiste à essayer le motif à chaque carré dans la boîte englobante de l'entrée justifiée à gauche et à générer le nombre de correspondances. Si une valeur booléenne 1ou 0est requise, le programme suivant peut être utilisé:

?
z\G\O\L\F

S'il y a au moins une nouvelle ligne dans le fichier source, la première ligne est traitée comme une option pour la conversion initiale de l'entrée sous une forme rectangulaire. L' ?option imprime 0 ou 1 selon qu'il existe une correspondance n'importe où.

Problème 15: Boggle

Après la mise en œuvre de l'alternance, il est maintenant possible de résoudre Boggle. Il serait préférable d’utiliser la correspondance sans distinction de casse pour celle-ci, mais sa mise en œuvre n’est pas ma plus haute priorité.

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

|fonctionne exactement comme une regex à 1 dimension. Il existe deux paires de délimiteurs correspondants pour le regroupement, à savoir ()et {}. Un crochet de fermeture ferme tous les groupes ouverts du type opposé qui le séparent du plus proche du même type. Par exemple, {({{)seul le groupe le plus à gauche reste ouvert. Comme vous pouvez le constater, des symboles de regroupement sans correspondance sur les bords sont implicitement fermés. Il y a une autre commande de regroupement dans `laquelle je n'entrerai pas maintenant.

Problème 8: Coffres Minecraft

Le programme imprime le nombre de placements valides de la poitrine. C'était la première fois que je devais jouer au golf et j'ai réduit mon nombre d'octets (17) à quelques reprises.

\.!(o\C)2o(!\Cw)3
  • \. correspond à un point littéralement, au point de départ du match.
  • !(o\C)2équivaut à !((o\C)2)la quantification est une priorité plus élevée que l'assertion. <atom> <number>signifie répéter <atom>exactement les <number>temps. otourne l'escargot dans n'importe quelle direction orthogonale. !est une affirmation négative. Ainsi, cette partie vérifie l'absence d'un double coffre adjacent.
  • o tourne dans une direction orthogonale.
    • (!\Cw)3affirme qu'il n'y a pas Cdevant l'escargot, puis 3 fois dans le sens antihoraire.

Problème 2: Vérification des échiquiers

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

L' &option définit la sortie du programme comme 1si la correspondance réussissait à toutes les positions et 0sinon. ^ccorrespond à un caractère qui n'est pas céquivalent à [^c]regex. Dans l’ensemble, le programme signifie: Print 1 Si à chaque position dans le rectangle de délimitation de l’entrée, il existe soit un #qui n’est pas orthogonalement adjacent à un caractère qui ne l’est pas _, soit un _qui n’est pas orthogonalement adjacent à un caractère qui est non #; sinon 0.

feersum
la source
Le slime trail est une bonne idée pour faire face à l'étouffement. J'avais un problème avec ça
BMac
C'est une solution intéressante au problème Boggle. Je ne peux pas résoudre cela avec mon approche.
Logic Knight
14

La classe Re2d, Python 2

Mise à jour: ajout du problème "9. Alignement".

Mon approche consiste à utiliser le module Python re pour effectuer la recherche et la correspondance. La classe Re2d prépare le texte pour le traitement, exécute les fonctions et formate les résultats pour la sortie.

Notez qu'il ne s'agit pas d'un tout nouveau langage: il s'agit du langage d'expression régulière standard projeté en 2 dimensions avec des indicateurs supplémentaires pour les modes 2D supplémentaires.

La classe a les usages suivants:

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

Les deux modèles sont des modèles RE de texte linéaire standard. Si aucun motif vertical n'est fourni, la classe utilisera également le motif horizontal pour la correspondance verticale. Les drapeaux sont les drapeaux RE standard avec certaines extensions 2D.

Essai

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#_#_')

La méthode de recherche a trouvé un motif d’échiquier et renvoie une position de 4 tuple. Le tuple a la x,yposition du premier caractère de la correspondance et width, heightla zone correspondante. Un seul motif est donné, il sera donc utilisé pour la correspondance horizontale et verticale.

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_#_#_#__')

L'échiquier a été vérifié avec la méthode de correspondance qui renvoie un booléen. Notez que les caractères ^et les caractères de $début et de fin doivent obligatoirement correspondre au texte entier .

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

Nous utilisons maintenant le MULTIFINDdrapeau pour renvoyer toutes les correspondances possibles pour le bloc de 2 chiffres ou plus. La méthode trouve 9 correspondances possibles. Notez qu'ils peuvent se chevaucher.

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)

Ce test montre l'utilisation du retournement vertical et horizontal. Cela permet de faire correspondre les mots inversés. Les mots en diagonale ne sont pas supportés. Le MULTIFINDdrapeau permet plusieurs correspondances qui se chevauchent dans les 4 directions. La méthode findall utilise la recherche pour trouver les cases correspondantes, puis extrait les blocs de texte correspondants. Notez que la recherche utilise la largeur et / ou la hauteur négatives pour les correspondances dans le sens inverse. Les mots dans la direction verticale ont des caractères de nouvelle ligne - ceci est cohérent avec le concept de blocs de caractères 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)

Cette recherche nécessitait des modèles distincts pour chaque dimension, la taille minimale étant différente pour chacune.

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)

Cet ensemble de 2 recherches trouve 2 correspondances verticales et 2 correspondances horizontales, mais ne peut pas trouver la #.,#chaîne incorporée .

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)

Ici, nous utilisons 2 recherches pour trouver des correspondances dans les deux sens. Il est capable de trouver plusieurs correspondances orthogonales mais cette approche ne prend pas en charge les correspondances en diagonale.

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

Cette recherche trouve la première correspondance.

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)

Le problème des diamants est plus difficile. Trois objets de recherche sont nécessaires pour les trois tailles. Il peut trouver les six diamants dans le jeu d’essais, mais il n’est pas adapté aux diamants de taille variable. Ce n'est qu'une solution partielle au problème des diamants.

Code 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
Logic Knight
la source
Si le problème des diamants n'était pas clair, les diamants peuvent avoir n'importe quelle taille, pas seulement 0, 1 ou 2. Modifier: J'ai modifié la spécification pour la rendre plus claire.
PhiNotPi
Je l'ai. Je ferai une note dans la réponse que le Re2d n'a qu'une solution partielle à ce problème. Il ne peut pas évoluer vers des tailles variables. Est-ce que ça va?
Logic Knight
Oui c'est bon.
PhiNotPi
14

Grime , Haskell

introduction

Grime est basé sur les grammaires booléennes . L'idée de base est de construire des motifs rectangulaires à partir de composants plus petits et de vérifier s'ils se trouvent dans la matrice d'entrée. Jusqu'à présent, Grime ne prend en charge que les allumettes rectangulaires et résout au moins 11 problèmes avec plus ou moins d'élégance.

EDIT: Correction des croix (merci à DLosc d’avoir repéré le bogue), et ajout de l’exploitation de diamants.

EDIT2: Ajout des classes de caractères, inspirées de celles de Slip. Également modifié la syntaxe des indicateurs d'option, amélioré l'analyseur d'expression et ajouté le problème no-Q.

EDIT3: Implémentation des contraintes de taille et ajout du problème des portails Nether.

Usage

Un programme Grime est appelé une grammaire et l'extension de fichier correcte pour une grammaire est .gr, bien que cela ne soit pas appliqué. La grammaire est évaluée comme

runhaskell grime.hs [options] grammarfile matrixfile

matrixfileest un fichier contenant la matrice de caractères. Par exemple, la grammaire des chiffres serait évaluée comme suit:

runhaskell grime.hs digits.gr digit-matrix

Pour plus de rapidité, je vous recommande de compiler le fichier avec les optimisations suivantes:

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

Par défaut, l'interprète imprime la première correspondance trouvée, mais cela peut être contrôlé à l'aide de l'option flags:

  • -e: correspond uniquement à la matrice entière, impression 1pour correspondance et 0pour aucune correspondance.
  • -n: affiche le nombre de correspondances, ou la matrice entière si -eest également donné.
  • -a: imprimer toutes les correspondances.
  • -p: affiche également les positions des matchs, au format (x,y,w,h).
  • -s: ne pas imprimer les allumettes elles-mêmes.
  • -d: affiche les informations de débogage.

Des options peuvent également être spécifiées dans la grammaire, en les insérant avant toute ligne et en ajoutant une virgule ,(voir ci-dessous pour des exemples).

Syntaxe et sémantique

Une grammaire Grime consiste en une ou plusieurs définitions , chacune sur une ligne distincte. Chacun d'entre eux définit la valeur d'un terminal , et l'un d'entre eux doit définir le terminal anonyme de niveau supérieur . La syntaxe d'une définition est N=Eou E, où Nest une lettre majuscule et Eune expression .

Les expressions sont construites comme suit.

  • Tout caractère échappé avec \correspond à tout 1x1rectangle contenant ce caractère.
  • . correspond à n'importe quel caractère unique.
  • $correspond à un 1x1rectangle en dehors de la matrice de caractères.
  • _ correspond à tout rectangle de largeur ou hauteur nulle.
  • Les groupes de caractères prédéfinis sont digit, uppercase, lowercase, alphabetic, alpha numeric et symbol.
  • De nouvelles classes de caractères peuvent être définies par la syntaxe [a-prt-w,d-gu]. Les lettres de gauche sont incluses et celles de droite sont exclues. Cela correspond donc exactement aux lettres abchijklmnoprtvw. Si le côté gauche est vide, il est supposé contenir tous les caractères. La virgule peut être omise si le côté droit est vide. Les personnages [],-\doivent être échappés avec \.
  • Une lettre majuscule non échappée est une minuscule et correspond à l'expression qui lui est attribuée.
  • Si Pet Qsont des expressions, alors PQn’est que leur concaténation horizontale et P/Qleur concaténation verticale, avec Pen haut.
  • P+est un ou plusieurs Ps alignés horizontalement, et P/+est le même aligné verticalement.
  • Les opérations booléennes sont notées P|Q, P&Qet P!.
  • P?est un raccourci pour P|_, P*pour P+|_et P/*pour P/+|_.
  • P#correspond à tout rectangle contenant une correspondance P.
  • P{a-b,c-d}, Où abcdsont des entiers non négatifs, est une contrainte de taille sur P. Si Pest une classe de caractères, l'expression correspond à tout mxnrectangle contenant uniquement ces caractères, à condition qu'il msoit compris entre aet binclusif et nentre cet dinclusif. Dans d'autres cas, l'expression correspond à tout rectangle ayant la taille correcte et qui Pcorrespond également. Si aou csont omis, ils sont pris pour être 0, et si bou dsont omis, ils sont infinis. Si le trait d'union entre aet best omis, nous utilisons le même nombre pour les deux extrémités de l'intervalle. Si l'ensemblec-dune partie est omise, les deux axes sont contraints. Pour clarifier, {-b}équivaut à {0-b,0-b}et {a-,c}équivaut à {a-infinity,c-c}.

Remarques

Grime permet des définitions paradoxales comme A=A!avec un comportement indéfini. Cependant, ils ne provoqueront pas de crash ni de boucle infinie.

Grime prend en charge les entrées non rectangulaires; les lignes sont simplement alignées à gauche et les espaces peuvent être appariés à l'aide de $.

Dans le futur, j'aimerais implémenter ce qui suit:

  • Correspondance plus rapide. Actuellement, l'interprète ne prend pas en compte le fait que, par exemple, .ne peut correspondre qu'à des 1x1rectangles. Jusqu'à ce qu'il trouve une correspondance, il essaie tous les rectangles de toutes les tailles dans l'ordre, en échouant instantanément pour chacun d'eux.
  • Opérations de rotation et de réflexion, pour les défis de recherche de mots et de planeur.
  • Les correspondances non rectangulaires utilisant des contextes , ce qui serait utile dans le cas du défi Boggle. Par exemple, Pv(Q>R)signifie Pavec contexte inférieur ( Qavec contexte droit R). Il correspondrait aux motifs en forme de L

    PPP
    PPP
    QQQRRRR
    QQQRRRR
    QQQRRRR
    

Les tâches

Étant donné en gros par ordre de complexité.

Rectangle de chiffres

d{2-}

C'est simple: un rectangle de chiffres de taille au moins 2x2.

Non q ou Q

[,qQ]{4}

C'est presque aussi simple que le premier. nous avons maintenant une taille plus restreinte et une classe de caractères personnalisée.

Alignement horizontal et vertical

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

Maintenant, nous avons quelques caractères échappés. En gros, cela correspond à un #, puis à un nombre quelconque de caractères, #horizontalement ou verticalement.

Détecter les entrées carrées

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

Cette grammaire est très simple, elle définit en gros qu’un carré est soit un 1x1rectangle, soit un carré plus petit avec une colonne fixée sur son bord droit et une rangée située au bas de celle-ci. Notez également l' eoption située avant le nonterminal toplevel, qui bascule la vérification de l'entrée entière.

Trouver un mot dans une recherche par mot

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

Celui-ci est horrible, car Grime n'a pas d'opération de rotation ou de réflexion. Il est également extrêmement lent, car Grime ne sait pas que les allumettes ne peuvent être que de taille 4x1, 1x4ou 4x4.

Le problème de planeur pourrait être résolu de la même manière, mais je suis trop paresseux pour le noter.

Portails du Néant

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

Avec l'opérateur de restriction de taille, celui-ci n'est pas si difficile. La partie centrale \.{2-22,3-22}correspond à n’importe quel rectangle de .la bonne taille, puis nous ajoutons simplement des colonnes de Xs des deux côtés et nous ajoutons des rangées de Xs avec des extrémités ignorées en haut et en bas de celle-ci.

Croix correspondantes

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

Ce que nous avons ici est une conjonction (ET logique) de deux expressions. Le non-terminal Ecorrespond à un rectangle non vide de .s et à Fun rectangle non vide de #s. Le côté gauche de la conjonction correspond aux rectangles du type

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

où nous avons EFEsur le dessus, puis F, puis EFEencore. Le côté droit correspond à la transposition de ceux-ci, nous obtenons donc exactement les croix.

Extraction de diamants

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

Le non terminal Cest un raccourci pour n'importe quelle 1xncolonne. La moitié supérieure d'un diamant est assortie T: c'est un seul Xou un autre Tentouré d'une colonne des deux côtés et d'une rangée en /[something]\dessous. Bcorrespond au bas d'un diamant de la même manière, et le niveau supérieur non terminal est juste rangé de la forme X[something]Xentre une moitié supérieure et une moitié inférieure.

Trouver des échiquiers

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

Le côté droit [#_]{3-}correspond à tout 3x3rectangle ou plus de #s et _s, tandis que les garanties de gauche qu'il ne contient pas de deux adjacents #s ou _s.

Vérification des échiquiers

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

Ceci est fondamentalement le même que ci-dessus, sauf que nous pouvons faire correspondre tout rectangle non vide, mais nous devons utiliser l' eindicateur pour la vérification complète de l'entrée.

Vérifier la syntaxe de prélude

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

C'est probablement la grammaire la plus intéressante à ce jour. Le non-terminal Acorrespond à toute colonne ne contenant pas (ou ), et Pcorrespond soit à un certain nombre de As, soit à deux parenthèses correspondantes, entre et en dehors desquelles il y a plus de Ps.

Zgarb
la source
@DLosc Fixe, merci d'avoir trouvé le bogue!
Zgarb
Serait \#(.*|./*)\#travailler?
seequ
@Sieg Pour l'alignement? Malheureusement non, car cela serait analysé comme "un #à gauche, puis une ligne ou une colonne de n'importe quoi, puis un #à droite". Je dois spécifier que les #s sont concaténés verticalement à la colonne à l'aide des barres obliques /.
Zgarb
10

TMARL

Langage de reconnaissance et de correspondance des modèles

La description

Mon interprète utilise des caractères 24K (les extraits de code prennent des caractères? ). Vous trouverez la description complète ici .

La meilleure partie: l'interprète est en Javascript, ce qui signifie que vous pouvez l'essayer ici!

Et pour les problèmes:

# 1 - Trouver des échiquiers

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

&ajoute des recherches. Le G2 à la fin obtient le 3ème élément d'un élément de correspondance, la correspondance réelle. Les 2 premiers éléments sont des coordonnées x et y (1 basé, pas 0).

# 3 - Détecter un rectangle de chiffres

$DD
$DD
S1G2P

Je pense que celui-ci est assez simple.

# 4 - Trouver un mot dans une recherche par mot

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

L' Sargument est même qu'il recherche toutes les rotations. Il est supérieur à 4 car il peut ensuite être ajouté à la recherche suivante (les correspondances individuelles ne peuvent pas être ajoutées).

# 5 - Détecter les entrées carrées

IL-(IG0L)!P

Je ne sais pas si cela est complètement légal, car cela détermine uniquement la perpendicularité si l’entrée est un rectangle. Il compare la longueur de l'entrée ILà la longueur de la première ligne IG0Let l'inverse.

# 6 - Trouver des planeurs dans un jeu de la vie

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

Enfin, une utilisation pour miroir!

# 12 - Évitez la lettre Q

$[^Qq]
~4*4S1G2P

S1 car 1 seule correspondance est nécessaire.

Je ferai certaines des plus difficiles plus tard.

Stretch Maniac
la source