Un serpent extensible ressemble à ceci:
<||=|||:)~
Chaque séquence distincte de barres verticales ( |
) dans un serpent extensible, appelée partie extensible , peut être étendue individuellement jusqu'à deux fois sa largeur et est dessinée avec des barres obliques alternées ( /
, \
) une fois déployée.
Le serpent ci-dessus a deux telles portions extensibles, ce qui lui donne quatre poses possibles:
<||=|||:)~
</\/\=|||:)~
<||=/\/\/\:)~
</\/\=/\/\/\:)~
La forme générale d'un serpent extensible dans sa pose la moins étirée est définie par cette expression rationnelle :
<(\|+=)*\|+:\)~
Ce qui peut être écrit en mots comme:
<
, suivi par un nombre quelconque de séquences de|
's jointes avec des=
signes, suivi de:)~
.
Ainsi <|:)~
et <||:)~
et <|=|:)~
et <|=|=||=|||||=||:)~
sont des serpents élastiques, mais <=:)~
et <=|:)~
et <||=:)~
et <|==||:)~
ne sont pas.
Les serpents extensibles peuvent également faire face à gauche au lieu de droite, par exemple ~(:|||=||>
. Les formes sont les mêmes, juste en miroir.
Défi
Ecrivez un programme qui prend une seule ligne de deux serpents extensibles se faisant face, avec un certain nombre d'espaces entre eux. Les deux serpents seront dans leur pose la moins étirée (toutes les barres verticales, pas de barres obliques). La chaîne commence par la queue du serpent dirigé vers la droite et se termine par celle du serpent dirigé vers la gauche (vous pouvez éventuellement supposer qu'il existe également une nouvelle ligne).
Par exemple, voici une entrée possible avec cinq espaces entre les serpents:
<|=||:)~.....~(:||||>
J'utilise des points ( .
) au lieu des espaces réels pour plus de clarté.
Zéro espace entre les serpents est également une entrée valide:
<|=||:)~~(:||||>
Nous disons que les serpents s'embrassent lorsque leurs langues se touchent de la sorte.
Votre programme doit étendre une combinaison des parties extensibles des deux serpents de manière à ce qu’ils aient le moins d’espaces possibles (sans se chevaucher), c’est-à - dire que les serpents s’embrassent le plus possible .
Les deux queues des serpents sont fixes mais leurs têtes et leurs corps peuvent bouger - à droite pour le serpent à droite, à gauche pour le serpent à gauche - en fonction des portions étendues qui ont été étendues.
La sortie de votre programme est une chaîne simple ligne (plus une nouvelle ligne facultative) qui montre les serpents aussi près que possible d'embrasser, avec des barres obliques alternées au lieu de barres verticales pour les portions extensibles qui ont été étendues.
Par exemple, la sortie pour <|=||:)~.....~(:||||>
(à partir de ci-dessus) serait:
</\=||:)~~(:/\/\/\/\>
C’est la seule solution ici car avec toute autre combinaison de parties extensibles étendues, les serpents se chevaucheraient ou seraient plus éloignés des baisers.
S'il existe plusieurs solutions possibles, la sortie peut être l'une d'entre elles.
Par exemple, si l’entrée était
<|=||:)~.....~(:|||=|>
la sortie pourrait être
<|=/\/\:)~~(:/\/\/\=|>
ou
</\=||:)~~(:/\/\/\=/\>
N'oubliez pas qu'il ne sera pas toujours possible de faire s'embrasser les serpents, mais vous devez toujours les rapprocher le plus possible.
Par exemple, si l’entrée était
<||=||||:)~...~(:||>
la sortie pourrait être
</\/\=||||:)~.~(:||>
ou
<||=||||:)~.~(:/\/\>
Si les serpents s'embrassent déjà, la sortie sera la même que l'entrée. par exemple
<|=||:)~~(:||||>
En général, la sortie sera la même que l'entrée si l'extension d'une partie élastique rend les serpents superposés. par exemple
<|||=|||:)~..~(:||||=|||||=||||||>
Remarques
- Prend les entrées à partir de stdin ou de la ligne de commande, comme d'habitude, ou écrit une fonction prenant une chaîne. Imprimer ou renvoyer la sortie.
- Vous pouvez utiliser des points (
.
) dans les entrées et les sorties à la place d'espaces () si vous préférez.
- Il est seulement important que les barres obliques alternent dans la séquence de barres verticales qu'elles ont remplacées. Leur ordre dans le serpent en général ou si une barre oblique en avant ou en arrière vient en premier n'a pas d'importance.
- Les portions extensibles ne peuvent pas s’allonger partiellement, c’est exactement une extension double ou pas du tout.
Notation
C'est du code-golf . La soumission la plus courte en octets l'emporte. Tiebreaker est une réponse plus tôt.
la source
>
, ne deviendrait pas non<
plus pareil, identique pour(
et)
), mais il a également déclaré: "Il est seulement important que les barres obliques alternent dans la séquence de barres verticales qu'elles ont remplacées. serpent en général ou si une barre oblique avant ou arrière vient en premier n'a pas d'importance. "Réponses:
CJam,
87717068 octetsEssayez-le en ligne dans l' interprète CJam .
Comment ça fonctionne
la source
Retina ,
209107999792 octetsÀ des fins de comptage, chaque ligne est placée dans un fichier séparé, mais vous pouvez exécuter le code à partir d'un seul fichier avec l'
-s
indicateur.Rassembler les meilleures fonctionnalités de .NET regex et Retina: groupes d'équilibrage, recherche de longueur arbitraire et substitution répétée de regex.
Essentiellement, le long regex code une solution valide et le backtracker du moteur de regex en trouve l’un des meilleurs pour moi.
Explication
Voyons d’abord comment trouver une solution valide (ne produisant pas nécessairement le bon résultat) avec une expression rationnelle. Nous pouvons utiliser les groupes d'équilibrage .NET pour nous aider à compter les parties élastiques. Considérez le regex plus simple suivant:
Nous pouvons comprendre cela.
Cela correspond à la chaîne entière, en insérant une capture dans la
1
pile de groupes pour chaque espace de l'entrée. Nous allons utiliser cette pile pour nous assurer que les parties extensibles occupent exactement l'espace capturé dans ces groupes.Suivant est un lookbehind. Le problème, c’est que les repères sont assortis de droite à gauche dans .NET (c’est ce que vous devriez lire). Cela nous donne l’occasion de parcourir la chaîne une seconde fois, en déterminant s’il existe un sous-ensemble de partie extensible qui correspond au nombre d’espaces correspondants. En passant par le regard de droite à gauche:
Ceci est juste pour nous assurer que nous partons réellement de la fin de la chaîne (la queue du serpent).
Pour chaque partie extensible, cela correspond simplement à la partie entière sans rien faire (
\|+
), ou bien à la partie entière tout en faisant apparaître des captures de pile1
((?<-1>\|)*
). Cette alternance garantit que nous ne pouvons que prolonger entièrement une partie extensible ou la laisser inchangée, et ne pas avoir de choses comme|/\|
. Ensuite, nous passons à la prochaine partie extensible avec[^|]+
.Enfin, nous nous assurons que nous avons traversé toute la chaîne (les deux serpents) et que la pile
1
est complètement vide. C'est-à-dire que nous avons trouvé un sous-ensemble de parties extensibles qui correspond exactement au nombre d'espaces capturés précédemment.Le backtracker parcourt la chaîne en essayant toutes les combinaisons de parties non modifiées et étendues jusqu'à ce que le problème de la somme des sous-ensembles soit résolu. Si un tel sous-ensemble n'existe pas, la recherche en arrière échouera. Ainsi, le backtracker retournera à la
\S+( )+.+
pièce et essaiera de capturer un espace de moins avec( )+
(ce qui sera simplement couvert par.+
). En raison de la gourmandise de,+
nous essayons donc de remplir autant d'espaces que possible.Vous pouvez vérifier la validité de cette approche avec cette substitution légèrement modifiée:
Ce qui vous donnera une chaîne
=spaces=
avec exactement le nombre d'espaces pouvant être remplis avec les serpents donnés.J'ai dû ajouter quelques astuces pour développer les
|
s corrects . Fondamentalement, je veux remplacer tous les|
s qui ont été appariés en utilisant la(?<-1>\|)+
branche. L'idée est de faire correspondre un caractère individuel, de placer le solveur dans un lookaround et de définir un indicateur si la correspondance se trouve à l'intérieur de cette branche. Si cet indicateur n'a pas été défini, nous invaliderons la correspondance à la fin pour éviter le remplacement d'autres caractères.Pour ce faire, nous utilisons un tas de corrections imbriquées. Encore une fois, les recherches d'arrière-plan de longueur variable .NET sont appariées de droite à gauche. Par conséquent, si nous imbriquons des recherches d'antécédents, nous pouvons laisser le moteur des expressions rationnelles traverser la chaîne plusieurs fois. Pour des raisons liées au golf, le solveur est inversé dans ma solution actuelle (en partant de la fin, ramasser les espaces de droite à gauche, puis en résolvant la somme du sous-ensemble de gauche à droite), mais sinon la structure du solveur est exactement la même. . Disséquons la regex complète:
Nous faisons correspondre un seul caractère, puis capturons le reste de la chaîne et déplaçons le curseur à la fin de la chaîne. Nous utiliserons ce groupe
1
plus tard pour vérifier dans le solveur si nous en sommes à la position du match.Cela ressemble à la première partie du solveur simple ci-dessus, sauf que nous prenons les espaces de droite à gauche. Le retour en arrière du nombre d'espaces fonctionne exactement comme avant, sauf que nous utilisons
5
maintenant le groupe .C’est la même chose que précédemment, sauf que nous allons de gauche à droite, et chaque fois que nous correspondons à un
|
dans la branche en expansion, nous vérifions si c’est celui qui correspond le mieux àC'est une option optionnelle. Il essaie à
1
nouveau de faire correspondre le groupe (ce qui, ici, n’est possible que si nous sommes juste après le caractère mis en correspondance), et si nous le faisons, nous capturons une chaîne vide dans le groupe4
, ce qui indique que nous avons trouvé le caractère actuel dans un groupe. des bits développés. Si\1
ne correspond pas,4
rien ne sera capturé, et le système?
s'assurera que la recherche échouée n'aura aucune incidence sur le solveur.Enfin, après que toute la résolution soit terminée, nous vérifions simplement
\4
si cette apparence a été utilisée. Si c'est le cas, nous voulons remplacer le caractère actuel par/\
.Une difficulté demeure: supprimer la bonne quantité d'espaces. Le moyen le plus rapide que j'ai trouvé jusqu'à présent consiste à insérer un espace avec le
/\
, puis à supprimer un espace entre les langues pour chacun de ces espaces dans une étape distincte:la source
Rubis
191 187 186 170162C'est une fonction qui prend une chaîne en tant que paramètre et retourne une chaîne.
Tests en ligne: http://ideone.com/uhdfXt
Voici la version lisible:
Dans la version golfée, la fonction principale est l’équivalent de la
KISS
fonction ci-dessus et laCOMBINATIONS
fonction a été intégrée.la source
<|=||:)~~(:||||>
, spécifiée par la spécification comme entrée valide.Python, 205 octets
Avoir un seul lambda a l'air soigné et tout, mais je suis presque certain que ce n'est pas la meilleure façon de faire. Mais je poste ceci car c'est tout ce que j'ai jusqu'ici qui semble à moitié décent.
C'est un simple force brute sur tous les remplacements possibles
|
avec/\
, en filtrant les configurations non valides. Le seul peu propre , je suppose que nous ne remplaçons pas vraiment tout|
avec/\
directement - nous avons d' abord remplaçons|
avecX
et laissez tomber un à.
partir du milieu pour chaque remplacement, prenez la chaîne de longueur minimale sur toutes les chaînes valides, puis remplacer lesX
s avec/\
.J'ai essayé quelques autres approches, y compris récursives, mais elles se sont révélées assez compliquées. J'ai aussi appris
re.split
qu'actuellement, les chaînes vides ne se divisaient pas, ce qui était regrettable, car l'une de mes idées impliquait la séparation des\b
mots.la source
Mathematica, 381 octets
Fonction pure prenant la chaîne comme argument. Les attentes
.
plutôtqu'entre les serpents.
Je ne pensais pas que ce serait si grave… Voici ce que j'avais avant de le briser ensemble et de tout fixer.
Voici un exemple avec explication:
la source
a=StringReplace;b=StringSplit;c=StringLength;d=Total;
ceux qui sont nécessaires ailleurs à l'intérieur, puis en les remplaçant:a=StringReplace;b=StringSplit;c=StringLength;d=Total;a[MapAt[a[#,"|"->"/\\"]&,b[#<>"="<>#2,"="],#3]~StringRiffle~"=",")="->")~"<>If[#4>0,"."~StringRepeat~#4,""]<>"~"]&[#1,#3,Sequence@@Function[{l,s},{#,#2-d@Extract[l,#]}&[Flatten[l~Position~#~Take~#2&@@@Tally@#&@@Select[Subsets@l,d@#<=s&]~MaximalBy~d,1],s]][c/@StringCases[#1<>#3,"|"..],c@#2]]&@@#~b~"~"&
Prolog (ECLiPSe), 438 octets
Mes autres réponses résolvaient le mauvais problème (désolé pour le bruit). Voici une autre tentative dans Prolog qui respecte toutes les règles.
Des tests
(format: entrée, sortie, nouvelle ligne)
Des explications
Le prédicat principal est
s/2
, qui prend l’entrée comme premier argument et délie le résultat avec le deuxième argument (les deux chaînes). L'entrée est converti en une liste de codes de caractères,E
.Ensuite,
s(E,Z,X,Y,L)
décomposez la liste en éléments suivants:Z
nombre d'espaces entre les serpentsX
etY
, représentation abstraite des corps gauche et droitLe format d'un corps est une liste
n:N
ous:N
expressions, oùN
est une longueur positive;n
des moyensnormal
et dess
moyensstretched
.L
longueur totale de la listeCe qui est intéressant,
s/5
c’est que cela va dans les deux sens , c’est-à-dire que nous pouvons construire un serpent si d’autres arguments sont instanciés:Q
qui sépare les nouveaux serpents. La longueur totale de la chaîne calculée est limitée de sorte que la recherche se termine.la source
Python 2.7.3
427421400371 octetsCode non-golfé ici -
Test de la solution golfée -
Cela peut sûrement être mieux fait (je ne vois pas comment :)).
Faites-moi savoir si j'ai oublié quelque chose d'évident en jouant au golf (c'est mon premier code-golf, je suis peut-être en train de faire une bêtise: P)
la source
exit
poursys.exit()
(oubliéexit
existé). Et vous avez raison,__import__
peut être supprimé, cela éliminé comme 20 caractères :)> 6
utilisiez l' aliasing, vous avez besoin que les caractères valent la peine d'être aliasés si vous l'utilisez deux fois, les> 3
caractères si vous l'utilisez trois fois. Je ne suis pas sûr que lef=' '
pseudonyme en vaut la peine (je compte deux fois)05AB1E , 93 octets
Bien trop long ..>.>
Essayez-le en ligne ou vérifiez tous les tests ou vérifiez tous les résultats possibles pour tous les tests .
Explication:
la source