Sans attaches!

42

Intro

Il y a 3 clous dans le mur. Vous avez un morceau de ficelle qui est fixé au cadre avec les deux extrémités. Pour accrocher la photo, vous avez emmêlé la ficelle avec les ongles. Mais avant de laisser tomber l'image: pouvez-vous prédire si l'image va tomber, il suffit de regarder comment la ficelle est enroulée autour des ongles?

Dans le premier exemple, l'image ne tombera pas. Dans le deuxième exemple, l'image va tomber.

Défi

En fonction du tracé de la ficelle autour des Nongles, déterminez si l'image va tomber ou non. Retourne une valeur de vérité si l'image doit tomber, et une valeur de fausseté sinon.

Détails

  • Vous pouvez supposer que les ongles et l'image sont disposés de manière régulière N+1, avec l'image en bas.
  • Vous pouvez supposer qu’il n’ya pas de nœuds dans la corde, c’est-à-dire que la corde peut être déroulée en continu à partir de l’une des extrémités.
  • Chaque clou est énuméré dans le sens des aiguilles d'une montre avec une lettre de l'alphabet. Vous pouvez supposer qu'il y a au plus 26 clous (AZ).
  • La lettre minuscule entoure un clou, tandis que la lettre majuscule est enroulée dans le sens inverse.

Le premier exemple ci-dessus sera codé comme BcA, le deuxième exemple est codé comme CAbBac.

Pour le lecteur incliné: Ce problème revient à déterminer si un élément du groupe libre - généré par l’ensemble de clous - est l’identité ou non. Cela signifie qu'il est suffisant d'annuler de manière répétée des sous-chaînes telles que aAou Aajusqu'à ce que vous ayez atteint un point fixe. Si le point fixe est une chaîne vide, il s'agit de l'élément neutre, sinon ce n'est pas le cas.

Exemples

Picture will fall:
Aa
CAbBac
aBbA
DAacAaCdCaAcBCBbcaAb
ARrQqRrUuVHhvTtYyDdYyEKRrkeUWwua
AKkQqEeVvBESWwseYQqyXBbxVvPpWwTtKkVHLlWwNBbAanYYyyhWwEJZUuNnzjYyBLQqQqlEGgebeEPLlTtZzpUuevZzSsbXSGgsUuLlHhUQquPpHUuFfhTZzIitGgFAaBRrBbbYXxOoDZTDdtzVvXxUudHhOVvoUuXKkxyBEeLlbFfKkHhfVAaQqHAaJjODdoVvhSsZzMZzmPpXNBbnxBbUuSSsUuDRrdNnUusJDIiUuIidCEGgeMmcLlDPOopdTEeQqCAETtNnYyeGUuPEFfSsWwHheAaBbpgCcOHUuhAaCcoEFBbfeaFHhfcCFFffNncGFfgtjMVUuKAakvKkXxLlTMmtmOFfoUuXSsYZzLXxlyxUuRPZzTtprSsWwRrPLlpGgMmKRrDHhdRCcUurYNnKCckykXJjxWwUSsJjKkLlKkuBbBbOoWwWwIiUuPDdBbCcWHBbCFfcDdYBbLlyVvSsWGgEewCchDdYywAaJjEepPpPpQXxZzFfLGXxglNnZzYDdyqCcKWXxwXxQqXTtxkFfBSSAasTFftZzsXGgxSsLlLlbZzAaCCccXVvYyxTIiOoBbFftCVQqDdBbGgAavQqKkDPpKTCctRrkdcvAaQWOowLOolqVMmvZAaHCBbcPphIiRKkrLlzFMOomDIiXJjIixMmdNnMHhmfNTtIiKkSDdTtsVvHhnAaNSVvTUutNnXxsGIiXxPpPHhUupgNnAaAAOoaaIiHJjhVvLlnYyXxQqSsTtKJjkBbNnVvEYCcFfMHGghBbmNnEeJTtjJjWYywyeNWwDIiZYyzOodnMQqmVvCcQqxVvGNnEeNBbngVvUGgYyBbDdVvIiAAaauPpQKDdEekNnVLlvHhGSDIidPZzpsPCcpgQqKkQqNOonLlIiLlJjqPAaPXxTtppYyCPpHhCIicARBbracXxWwXEVUuUuGgZHhzBSsbvGgFfeVvxLlNKknWwBLlIibWOowNnRSsrSEeKAakOosLZzZRrHhzTtTFfUuNnOKkotXxTtla


Picture will not fall:
A
BcA
ABCD
aBaA
bAaBcbBCBcAaCdCaAcaCAD
ARrQqRrUatuVHhvTYyDdYyEKRrkeUAua
AEEeQqNneHhLlAIiGgaECXxcJjZzeJFfVWwDdKkvYWwyTJjtCXxANIinaXWwxcTWwtUuWwMmTBbVWIiFLlWwZzfwPLlEepvWZzwKkEYEeWXxwySXTtEexRIiNBbnWAaTtQqNnBMSsWwOombwWwPVPpGPpgYyvDdpBbrQqHhUusKRrDAVvadLlWwOZzokGJCXSSssXxxJPpGIigZzjJjLlOoNRrnPpcMZzmjgJjNDEeQqWKkNTtnSswIidCcnYBGgbyJSsjPpIiMmMmMmSNnWVvwZzIQqLXHhxTPptlisOoeTtTtYMmVvPpyKNnMFfmkXxSVvsCGJjXxgXYJPpjWwQIiXxqyDdxFfDdAaRNnJjrctHBbZzhEQqMmeCcRBbrGgAaAaJNnRrYyWwSDdVvsJOojQGgWWwIBbiwRrqJjjWwOoFPMmDdRrQOoqNnRrDPJjpMmdPpGFfVvWUuwgpWCcNnPpwfUXCcZzJjUSsuXxxUuuRGgHhrSQqJjOosMMTtmHhmKkXxDdLlWwjSUuAaMmKYyksZzVvPZzVEeVvvHhZZOozBbzMmZCczYyGgISsiQqpXxMmXxEMmeRrAGgaGgMOGgomZFfDdzSSssBGPpgbTtBbOoRWWwGgLJjlEeGgLDdRrUulNnZzJjJjUKkuXxFfwATtaZzLVvlWwSsMmrBAaELleGBLFflbgHhbIFfiBbPpTWZzwKkKLASsaTJYyjtBbBbWwIiZCcWwzIiZLlUTtuBbYyBbIizTJjtLTtDOOoBbodBbllSsUGgLlAKkauYykUuUNnPpuDFfAaLNVvnVvlHhdMmBAaBbIiVRrGWOoPpwgWXwKkvJjOoTtYCUucVGgYyLlVvFfvRrMmySsDdbtICZzcNnINSOosDQAaXoxRGgKkrqdZznDdXxZzMGgmiJjNnACcMQqmaNnWZzUOuwTVvAJjSsaRrGgSsTtOMmRroVvRrtAVGgvMmaINniDGCcOogRrWwMVvYFfyTtmTtVvOoOIiodRrGgAxaSsGgiJja
code-golf string decision-problem abstract-algebra flawr
la source
3
Il semble qu'en libérant les mains pour écrire le chemin de la ficelle, l'image tomberait quand même. Alors ce défi devient vraiment facile.
owacoder
@owacoder Il faut juste être assez rapide: D
mardi
Pertinente: youtube.com/watch?v=x5h3yTxeCew
flawr

Réponses:

11

Retina , 21 octets

+`(.)(?!\1)(?i)\1

^$

Essayez-le en ligne!

Comme la solution de flawr, cette opération supprime de manière répétée les paires adjacentes majuscules / minuscules, puis vérifie si le résultat est vide ou non.

Pour ce qui est de savoir comment on fait correspondre une paire majuscule / minuscule:

(.)     # Match and capture a letter.
(?!\1)  # Ensure that the next character is not the same, to avoid matching
        # "aa" and "AA".
(?i)    # Turn on case-insensitivity.
\1      # Match the backreference. In .NET, when using case insensitivity,
        # backreferences also get case-insensitive, so this *can* still match
        # iff the cases of the two letters are different.
Martin Ender
la source
7

MATLAB, 76 octets Octave, 82 79 77 octets

C'est peut-être la première fois que je vois où MATLAB est plus court qu'Octave (d'un octet entier)!

Nouvelle réponse dans MATLAB:

c=input('');k='Aa';while k<1e5,k=k+1;c=strrep(c,65+mod(k,64),'');end;~nnz(c)

Réponse en octave:

c=input('');k='Aa';while k++<1e5,c=strrep(c,['',65+mod(k,64)],'');end;~nnz(c)

A sauvé trois cinq octets grâce à flawr. ~nnz(c)est plus court que isempty(c), et a 'Aa'deux octets plus courts que [0,32].

Essayez la version Octave en ligne!

Explication:

c=input('')demande à l'utilisateur d'entrer. Nous définissons k='Aa'comme un tableau de caractères.

while k++<1e5: Bien que la boucle où les deux éléments ksont incrémentées à chaque itération, Aa, Bb, Ccet ainsi de suite. La boucle continuera jusqu'à ce que le plus grand élément soit 1e5, ce qui devrait être suffisamment élevé pour la plupart des chaînes. Vous pouvez l'augmenter 9e9sans augmenter le nombre d'octets.

Nous allons prendre la strrepfonction par étapes, en partant du milieu.

En utilisant, mod(k,64)nous aurons ce qui suit lorsque nous atteindrons la fin de l'alphabet (si nous reconvertissons ken caractères):

ans = Yy
ans = Zz
ans = [{
ans = \|
ans = ]}
ans = ^~
ans = _
ans = `�
ans = aA
ans = bB

Comme vous pouvez le constater, il y aura quelques symboles entre les deux, mais le texte reprendra son tour et recommencera avec l'alphabet, mais maintenant avec les lettres minuscules en premier. C'est un moyen très court pour vérifier les deux Aaet aA.

['',65+mod(k,64)]concatène les valeurs numériques de l' modappel -call, avec une chaîne vide, convertissant les nombres en caractères.

strrepest utilisé pour supprimer des éléments de la chaîne cet les renvoyer. Il recherchera toutes les occurrences de kdans la chaîne et la remplacera par une chaîne vide.

Après les 1e5itérations, nous aurons soit une chaîne vide, soit une chaîne non vide. Nous vérifions s'il y a des éléments à cutiliser nnz(c). Nous revenons not(nnz(c)), donc 1s'il est vide, et 0s'il reste des caractères dansc

Stewie Griffin
la source
6

Minkolang 0,15 , 30 octets

od4&x,N.I1=$6&d3~c-$~48*=,2&xx

Essayez-le ici!

Explication

od                            Take character from input and duplicate it
  4&                          If top of stack is truthy, jump 4 spaces
    x                         Dump top of stack
     ,                        NOT top of stack
      N.                      Output as number and stop

    I1=                       1 if stack has 1 element, 0 otherwise
       $6&                    If top of stack is truthy, jump 16 spaces (to the beginning)
          d3~c                Duplicate top two items of stack, in reversed order
              -               Subtract
               $~             Absolute value
                 48*          Push 32
                    =,        0 if top two items are equal, 1 otherwise
                      2&xx    If top of stack is truthy, dump two elements from top

La nature toroïdale de Minkolang est utilisée ici pour éliminer le besoin d'une boucle externe. L'idée générale ici est de vérifier si les deux éléments supérieurs de la pile sont séparés de 32 unités (c'est-à-dire qu'ils sont une paire majuscule / minuscule) et, le cas échéant, séparez-les. Comme cela se fait "en temps réel", pour ainsi dire, l’imbrication des paires est gérée correctement.

El'endia Starman
la source
5

Haskell, 62 octets

a%l|b:t<-l,abs(a-b)==32=t|1>0=a:l
f=null.foldr((%).fromEnum)[]

Essayez-le en ligne

Crédit à flawr pour leabs et Laikoni pour la fromEnumcarte .

La fonction d'assistance %prend une chaîne déjà simplifiée let ajoute le symbole aavant de simplifier le résultat. Si lcommence par le caractère inverse de a, ils annulent. Sinon, aest simplement ajouté Notez qu'aucune simplification supplémentaire n'est nécessaire à ce stade.

La fonction principale fajoute et simplifie chaque caractère via a foldr. Ensuite, il vérifie si le résultat est vide.

Pour vérifier si deux caractères sont des cas opposés et doivent donc être annulés, voyez si leurs valeurs ASCII diffèrent de 32. Chaque élément est traité par fromEnumavant d'être passé à %.

Xnor
la source
Agréable! Et merci pour l'explication, j'apprends de nouvelles choses à chaque fois!
flawr
4

05AB1E , 17 octets

DvADu‚øDíìvyK}}õQ

Essayez-le en ligne!

Explication

Dv                 # input number of times do:
  A                # push lowercase alphabet
   Du              # push uppercase alphabet
     ‚ø            # zip the alphabets together (['aA', ..., 'zZ'])
       Díì         # prepend a copy with each element reversed ('Aa' ...)
          v        # for each pair in the resulting list
           yK      # remove it from the accumulated string (starts as input)
             }}    # end loops
               õQ  # check result for equality to empty string
Emigna
la source
4

Haskell , 98 97 85 81 octets

Il s'agit simplement d'une implémentation naïve qui tente à plusieurs reprises d'annuler des lettres adjacentes jusqu'à ce qu'il n'y ait plus de changement, puis en détermine le résultat.

Merci @nimi pour -12 octets et @xnor pour un autre -4 octets!

o=fromEnum
r(a:b:l)|abs(o a-o b)==32=l|1>0=a:r(b:l)
r x=x
f=null.until((==)=<<r)r

Essayez-le en ligne! ou vérifiez tous les exemples!

flawr
la source
f=null.until(\a->r a==a)r.map fromEnumdevrait sauver deux octets.
Laikoni
Je pense (\a->r a==a)peut être ((==)=<<r).
xnor
1
Dans la deuxième ligne, je pense que vous pouvez changer =r len l, l’idée étant qu’il suffit de ne faire qu’un remplacement par cycle.
xnor
Merci! Je comprends le deuxième indice, mais je n'ai aucune idée de ce qui se passe =<<, ça semble magique XD
flawr
1
@flawr Voir ce conseil . Le =<<est comme >>=mais avec les arguments échangés. L'expression apparaît souvent sous la forme ((==)=<<r)qui signifie "est invariant sous r".
xnor
3

Mathematica, 102 octets

""==StringDelete[""|##&@@#<>#2&~MapThread~{Join[a=Alphabet[],A=ToUpperCase@a],A~Join~a}]~FixedPoint~#&

Fonction sans nom prenant une chaîne alphabétique en entrée et renvoyant Trueou False.

Le cœur de l'implémentation est la création d'une fonction qui supprime toute paire d'annulation, comme "Pp"ou "gG", d'une chaîne. L'expression {Join[a=Alphabet[],A=ToUpperCase@a],A~Join~a}produit une paire ordonnée de listes de caractères, la première {"a","b",...,"Z"}et la seconde {"A","B",...,"z"}. #<>#2&~MapThread~Produit ensuite une liste dans laquelle les éléments correspondants de ces deux listes ont été concaténés, à savoir {"aA","bB",...,"Zz"}. L’expression amusante donne ""|##&@@ensuite (par la magie de la séquence des arguments ##) une liste d’alternatives "" | "aA" | "bB" | ... | "Zz"; enfin, StringDelete[...]est une fonction qui supprime toute occurrence d’une de ces alternatives d’une chaîne.

Il suffit maintenant d'appliquer de manière répétée cette fonction à la chaîne d'entrée jusqu'à ce que le résultat ne change pas, ce qui est accompli par ~FixedPoint~#, puis de vérifier si le résultat est la chaîne vide ""==.

Greg Martin
la source
3

JavaScript (ES6), 73 octets

f=(s,t=s.replace(/(.)\1+/gi,s=>s.replace(/(.)(?!\1)./,'')))=>s==t?!s:f(t)

Contrairement à .NET, JavaScript ne permet pas de désactiver la distinction entre majuscules et minuscules au milieu d'une correspondance. Nous devons donc rechercher toutes les sous-chaînes de lettres répétées sans tenir compte de la casse, puis supprimer toute paire de caractères adjacents qui ne correspondent pas, qui une paire majuscule / minuscule.

Neil
la source
3

Perl, 28 octets

1 while s/.(??{$&^' '})//;$_

Explication:

Perl permet d'inclure une expression régulière générée dynamiquement dans une expression régulière standard.

Les .matchs rien.

Le (??{est le début de la regex générée.

La $&variable contiendra toute la chaîne correspondante jusqu'à présent, ce qui dans ce cas correspond à ce qui .correspond.

L' ^opérateur effectue un xor numérique ou une chaîne xor, en fonction des valeurs des opérandes. Dans ce cas, ce sera la chaîne xor.

Il ' 's’agit simplement d’une chaîne contenant un espace, dont la valeur ascii (ou unicode!) Est 32. Lorsqu'un espace est xor avec un caractère compris dans la plage az ou AZ, il passe du haut au minuscule ou de l'étau. vice versa.

Le })est la fin de la regex générée.

1 while s/whatever// cherchera plusieurs fois un motif et le remplacera par la chaîne vide.

$_est la variable par défaut. Cette variable est ce sur quoi perl fait des choses amusantes et excitantes lorsque vous ne spécifiez pas une autre variable. Ici, je l'utilise pour renvoyer une valeur de vérité ou de fausseté, car une chaîne de longueur nulle est fausse et une chaîne de longueur non nulle qui n'est pas égale "0"est vraie. Je suppose également que la chaîne d'entrée a été placée à l'origine dans celle-ci.

Essayez ici

Ben Goldberg
la source
techniquement, cela retourne le contraire de ce que le défi demande (vous retournez la vérité quand il devrait être faux et vice versa). Pour résoudre ce problème, ajoutez simplement !avant la finale $_. Si vous le maintenez de cette manière, vous pouvez économiser 4 octets en le changeant en s/.(??{$&^' '})//&&redo+1 octet pour le -pdrapeau. Cela ne fonctionnera pas dans un sous-programme comme vous l'avez maintenant car ce { code }n'est pas une boucle (donc &&redone fonctionnera pas), mais le -pmet dans une whileboucle.
Gabriel Benamy
Vous pouvez également enregistrer un autre octet en remplaçant ' 'par $". Jetez un coup d'oeil à ceci pour voir à quoi ressemble le code.
Gabriel Benamy le
2

Prolog (SWI) , 151 octets

f(S):-S="";string_code(I,S,X),string_code(J,S,Y),J is I+1,32is abs(X-Y),B is J+1,sub_string(S,0,I,_,T),sub_string(S,B,_,0,U),string_concat(T,U,V),f(V).

Il faut beaucoup de temps pour traiter les faux cas plus longs en raison du retour en arrière.

Essayez-le en ligne!

Ungolfed

f(S):-                       The string S corresponds to a falling picture if:
  S="";                      S is the empty string, or...
  string_code(I,S,X),        X is the character code at some index I
  string_code(J,S,Y),        Y is the character code at some index J
  J is I+1,                  J is I+1
  32 is abs(X-Y),            X and Y differ by 32 (difference between lower/upper case)
  B is J+1,                  ...
  sub_string(S,0,I,_,T),     ...
  sub_string(S,B,_,0,U),     ...
  string_concat(T,U,V),      ...
  f(V).                      The concatenation of the substrings before and after 
                             the letters X and Y corresponds to a falling picture.
Chat d'affaires
la source
1

MATL , 20 octets

t"[]yd|32=fX<tQh(]n~

Essayez-le en ligne! Ou vérifiez tous les cas de test (cela prend un certain temps).

Explication

t       % Input string implicitly. Duplicate
"       % Do as many times as input size
  []    %   Push empty array
  y     %   Duplicate current string onto the top
  d|    %   Absolute consecutive differences
  32=   %   Convert to true if 32, false otherwise
  fX<   %   Index of first occurrence of true, or empty of all false
  tQ    %   Duplicate, add 1. This gives the next index, or empty
  h     %   Concatenate. Gives the two consecutive indices of letters
        %   to be removed, or empty
  (     %   Assign an empty array to those positions, i.e. delete them
]       % End
n~      % Number of elements, negate
Luis Mendo
la source
1

Mathematica, 65 octets

(ToCharacterCode@#//.{x___,y_,z_,w___}/;Abs[y-z]==32:>{x,w})=={}&
Alephalpha
la source