Wprowadzenie

W ścianie są 3 gwoździe. Masz kawałek sznurka, który jest przymocowany do ramy obrazu na obu końcach. Aby powiesić obraz, zaplątałeś sznurek w gwoździe. Ale zanim puścisz zdjęcie: czy możesz przewidzieć, czy obraz spadnie, po prostu patrząc na to, jak sznurek jest owinięty wokół paznokci?

W pierwszym przykładzie obraz nie spadnie. W drugim przykładzie obraz spadnie.

Wyzwanie

Biorąc pod uwagę ścieżkę sznurka wokół Ngwoździ, określ, czy zdjęcie spadnie, czy nie. Zwróć wartość zgodną z prawdą, jeśli obraz ma spaść, w przeciwnym razie wartość fałsz.

Detale

• Możesz założyć, że paznokcie i zdjęcie są ułożone w regularny N+1sposób, z obrazem na dole.
• Można założyć, że w linie nie ma węzłów, tzn. Linę można bez przerwy łączyć z jednego z dwóch końców.
• Każdy gwóźdź jest wyliczany zgodnie z ruchem wskazówek zegara za pomocą litery alfabetu. Możesz założyć, że jest maksymalnie 26 gwoździ (AZ).
• Owinięcie w prawo wokół gwoździa jest oznaczone małą literą, owinięcie w lewo jest oznaczone wielką literą.

Pierwszy przykład z góry zostanie zakodowany jako BcA, drugi przykład jest zakodowany jako CAbBac.

Dla skłonnego czytelnika: ten problem jest równoważny z ustaleniem, czy elementem wolnej grupy - wygenerowanym przez zestaw gwoździ - jest tożsamość, czy nie. Oznacza to, że wystarczy kilkakrotnie anulować podciągi, takie jak aAlub, Aaaż do osiągnięcia określonego punktu. Jeśli stałym punktem jest pusty ciąg, jest to element neutralny, w przeciwnym razie nie jest.

Przykłady

Picture will fall:
Aa
CAbBac
aBbA
DAacAaCdCaAcBCBbcaAb
ARrQqRrUuVHhvTtYyDdYyEKRrkeUWwua
AKkQqEeVvBESWwseYQqyXBbxVvPpWwTtKkVHLlWwNBbAanYYyyhWwEJZUuNnzjYyBLQqQqlEGgebeEPLlTtZzpUuevZzSsbXSGgsUuLlHhUQquPpHUuFfhTZzIitGgFAaBRrBbbYXxOoDZTDdtzVvXxUudHhOVvoUuXKkxyBEeLlbFfKkHhfVAaQqHAaJjODdoVvhSsZzMZzmPpXNBbnxBbUuSSsUuDRrdNnUusJDIiUuIidCEGgeMmcLlDPOopdTEeQqCAETtNnYyeGUuPEFfSsWwHheAaBbpgCcOHUuhAaCcoEFBbfeaFHhfcCFFffNncGFfgtjMVUuKAakvKkXxLlTMmtmOFfoUuXSsYZzLXxlyxUuRPZzTtprSsWwRrPLlpGgMmKRrDHhdRCcUurYNnKCckykXJjxWwUSsJjKkLlKkuBbBbOoWwWwIiUuPDdBbCcWHBbCFfcDdYBbLlyVvSsWGgEewCchDdYywAaJjEepPpPpQXxZzFfLGXxglNnZzYDdyqCcKWXxwXxQqXTtxkFfBSSAasTFftZzsXGgxSsLlLlbZzAaCCccXVvYyxTIiOoBbFftCVQqDdBbGgAavQqKkDPpKTCctRrkdcvAaQWOowLOolqVMmvZAaHCBbcPphIiRKkrLlzFMOomDIiXJjIixMmdNnMHhmfNTtIiKkSDdTtsVvHhnAaNSVvTUutNnXxsGIiXxPpPHhUupgNnAaAAOoaaIiHJjhVvLlnYyXxQqSsTtKJjkBbNnVvEYCcFfMHGghBbmNnEeJTtjJjWYywyeNWwDIiZYyzOodnMQqmVvCcQqxVvGNnEeNBbngVvUGgYyBbDdVvIiAAaauPpQKDdEekNnVLlvHhGSDIidPZzpsPCcpgQqKkQqNOonLlIiLlJjqPAaPXxTtppYyCPpHhCIicARBbracXxWwXEVUuUuGgZHhzBSsbvGgFfeVvxLlNKknWwBLlIibWOowNnRSsrSEeKAakOosLZzZRrHhzTtTFfUuNnOKkotXxTtla


Picture will not fall:
A
BcA
ABCD
aBaA
bAaBcbBCBcAaCdCaAcaCAD
ARrQqRrUatuVHhvTYyDdYyEKRrkeUAua
AEEeQqNneHhLlAIiGgaECXxcJjZzeJFfVWwDdKkvYWwyTJjtCXxANIinaXWwxcTWwtUuWwMmTBbVWIiFLlWwZzfwPLlEepvWZzwKkEYEeWXxwySXTtEexRIiNBbnWAaTtQqNnBMSsWwOombwWwPVPpGPpgYyvDdpBbrQqHhUusKRrDAVvadLlWwOZzokGJCXSSssXxxJPpGIigZzjJjLlOoNRrnPpcMZzmjgJjNDEeQqWKkNTtnSswIidCcnYBGgbyJSsjPpIiMmMmMmSNnWVvwZzIQqLXHhxTPptlisOoeTtTtYMmVvPpyKNnMFfmkXxSVvsCGJjXxgXYJPpjWwQIiXxqyDdxFfDdAaRNnJjrctHBbZzhEQqMmeCcRBbrGgAaAaJNnRrYyWwSDdVvsJOojQGgWWwIBbiwRrqJjjWwOoFPMmDdRrQOoqNnRrDPJjpMmdPpGFfVvWUuwgpWCcNnPpwfUXCcZzJjUSsuXxxUuuRGgHhrSQqJjOosMMTtmHhmKkXxDdLlWwjSUuAaMmKYyksZzVvPZzVEeVvvHhZZOozBbzMmZCczYyGgISsiQqpXxMmXxEMmeRrAGgaGgMOGgomZFfDdzSSssBGPpgbTtBbOoRWWwGgLJjlEeGgLDdRrUulNnZzJjJjUKkuXxFfwATtaZzLVvlWwSsMmrBAaELleGBLFflbgHhbIFfiBbPpTWZzwKkKLASsaTJYyjtBbBbWwIiZCcWwzIiZLlUTtuBbYyBbIizTJjtLTtDOOoBbodBbllSsUGgLlAKkauYykUuUNnPpuDFfAaLNVvnVvlHhdMmBAaBbIiVRrGWOoPpwgWXwKkvJjOoTtYCUucVGgYyLlVvFfvRrMmySsDdbtICZzcNnINSOosDQAaXoxRGgKkrqdZznDdXxZzMGgmiJjNnACcMQqmaNnWZzUOuwTVvAJjSsaRrGgSsTtOMmRroVvRrtAVGgvMmaINniDGCcOogRrWwMVvYFfyTtmTtVvOoOIiodRrGgAxaSsGgiJja

Retina , 21 bajtów

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

^$

Wypróbuj online!

Podobnie jak rozwiązanie flawr, to po prostu wielokrotnie usuwa sąsiednie pary wielkich / małych liter, a następnie sprawdza, czy wynik jest pusty, czy nie.

Jeśli chodzi o to, jak dopasować parę wielkich / małych liter:

(.)     # 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.

MATLAB, 76 bajtów Octave, 82 79 77 bajtów

To może być pierwszy raz, kiedy MATLAB jest rzeczywiście krótszy niż Octave (o cały bajt)!

Nowa odpowiedź w MATLAB:

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

Odpowiedź w oktawie:

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

Zapisane trzy pięć bajtów dzięki flawr. ~nnz(c)jest krótszy niż isempty(c)i 'Aa'jest o dwa bajty krótszy niż [0,32].

Wypróbuj wersję Octave online!

Wyjaśnienie:

c=input('')pyta użytkownika o dane wejściowe. Definiujemy k='Aa'jako tablicę znaków.

while k++<1e5: Pętla gdzie oba elementy ksą zwiększane każdej iteracji Aa, Bb, Cci tak dalej. Pętla będzie kontynuowana, aż pojawi się największy element 1e5, który powinien być wystarczająco wysoki dla większości łańcuchów. Można go zwiększyć do 9e9bez zwiększania liczby bajtów.

Podejmiemy tę strrepfunkcję krokami, zaczynając od środka.

Korzystając z niego mod(k,64), otrzymamy następujące informacje, gdy dotrzemy do końca alfabetu (jeśli przekonwertujemy z kpowrotem na znaki):

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

Jak widać, pomiędzy nimi będą znajdować się pewne symbole, ale potem zawiną się i zaczną ponownie od alfabetu, ale teraz najpierw od małych liter. Jest to bardzo krótki sposób sprawdzenia zarówno Aai aA.

['',65+mod(k,64)]konkatenuje wartości liczbowe z mod-call, z pustym łańcuchem, konwertując liczby na znaki.

strrepsłuży do usuwania elementów z łańcucha ci zwracania go. Wyszuka wszystkie wystąpienia kciągu i zastąpi go pustym ciągiem.

Po 1e5iteracjach albo będziemy mieli pusty ciąg, albo niepusty ciąg. Sprawdzamy, czy w cużyciu są jakieś elementy nnz(c). Wracamy not(nnz(c)), więc 1jeśli jest pusta i 0jeśli pozostały w niej postaciec

Minkolang 0,15 , 30 bajtów

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

Wypróbuj tutaj!

Wyjaśnienie

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

Wykorzystano tu toroidalną naturę Minkolanga, aby wyeliminować potrzebę zewnętrznej pętli. Ogólna idea polega na tym, aby sprawdzić, czy dwa górne elementy stosu są od siebie oddzielone o 32 jednostki (co oznacza, że ​​są parą wielkich / małych liter), a jeśli tak, usuń oba z nich. Ponieważ odbywa się to „w czasie rzeczywistym”, że tak powiem, zagnieżdżanie par jest obsługiwane poprawnie.

Haskell, 62 bajty

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

Wypróbuj online

Kredyt dla flawr zaabs i Laikoni na fromEnummapie .

Funkcja pomocnicza %pobiera już uproszczony ciąg li wstawia symbol aprzed uproszczeniem wyniku. Jeśli lzaczyna się od znaku odwrotnego do a, anuluje się. W przeciwnym razie ajest po prostu poprzedzony. Należy pamiętać, że na tym etapie nie są potrzebne dalsze uproszczenia.

Główna funkcja fpoprzedza i upraszcza każdą postać kolejno za pomocą foldr. Następnie sprawdza, czy wynik jest pusty.

Aby sprawdzić, czy dwa znaki są przeciwnymi literami i dlatego powinny zostać anulowane, sprawdź, czy ich wartości ASCII różnią się o 32. Każdy element jest przetwarzany fromEnumprzed przekazaniem do %.

05AB1E , 17 bajtów

DvADu‚øDíìvyK}}õQ

Wypróbuj online!

Wyjaśnienie

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

Haskell , 98 97 85 81 bajtów

Jest to po prostu naiwna implementacja, która wielokrotnie próbuje anulować sąsiednie litery, dopóki nie będzie więcej zmian, a następnie ustali z nich wynik.

Dzięki @nimi za -12 bajtów i @xnor za kolejne -4 bajty!

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

Wypróbuj online! lub Zweryfikuj wszystkie przykłady!

Mathematica, 102 bajty

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

Nienazwana funkcja przyjmująca ciąg alfabetyczny jako dane wejściowe i zwracająca Truelub False.

Sercem implementacji jest utworzenie funkcji, która usuwa dowolną parę anulującą, taką jak "Pp"lub "gG"z łańcucha. Wyrażenie {Join[a=Alphabet[],A=ToUpperCase@a],A~Join~a}tworzy uporządkowaną parę list znaków, z których pierwsza to {"a","b",...,"Z"}druga, a druga to {"A","B",...,"z"}. Następnie #<>#2&~MapThread~tworzy listę, w której odpowiadające elementy tych dwóch list zostały połączone, to znaczy {"aA","bB",...,"Zz"}. Zabawne wyrażenie ""|##&@@(dzięki magii sekwencji argumentów ##) tworzy listę alternatyw "" | "aA" | "bB" | ... | "Zz"; wreszcie StringDelete[...]jest funkcją, która usuwa dowolne wystąpienie dowolnej z tych alternatyw z ciągu.

Wystarczy teraz wielokrotnie stosować tę funkcję do ciągu wejściowego, aż wynik się nie zmieni, co jest osiągane przez ~FixedPoint~#, a następnie sprawdzić, czy wynikiem jest pusty ciąg znaków ""==.

JavaScript (ES6), 73 bajty

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

W przeciwieństwie do .NET, JavaScript nie ma możliwości wyłączenia rozróżniania wielkości liter w środku dopasowania, więc zamiast tego musimy znaleźć wszystkie podciągi powtarzających się liter bez rozróżniania wielkości liter, a następnie usunąć wszelkie niedopasowane pary sąsiednich znaków, które do tego momentu muszą być para wielka / mała.

Perl, 28 bajtów

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

Wyjaśnienie:

Perl pozwala na dołączenie dynamicznie generowanego wyrażenia regularnego do standardowego wyrażenia regularnego.

.Pasuje wszystko.

Jest (??{to początek wygenerowanego wyrażenia regularnego.

$&Zmienna będzie zawierać cały dopasowany ciąg tej pory, która w tym przypadku jest po prostu cokolwiek .dopasowane.

^Operator ma albo xor lub ciąg liczbowy XOR, w zależności od wartości operandów. W tym przypadku będzie to ciąg xor.

Jest ' 'to po prostu łańcuch zawierający spację, która dogodnie ma wartość ascii (lub Unicode!) Wynoszącą 32. Kiedy spacja jest zapisana za pomocą znaku z zakresu az lub AZ, zmieni się z wielkich na małe litery lub imadło versa.

})Jest koniec wygenerowanego regex.

1 while s/whatever// wielokrotnie wyszukuje wzór i zastępuje go pustym ciągiem.

$_jest zmienną domyślną. Ta zmienna jest tym, co Perl robi zabawne i ekscytujące rzeczy, gdy nie podajesz innej zmiennej. Tutaj używam go do zwrócenia wartości prawda lub fałsz, ponieważ ciąg o zerowej długości jest fałszywy, a ciąg o niezerowej długości, który nie "0"jest równy, jest prawdziwy. Zakładam również, że łańcuch wejściowy został pierwotnie w nim umieszczony.

Wypróbuj tutaj

Prolog (SWI) , 151 bajtów

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

Dużo czasu zajmuje uruchomienie dłuższych fałszywych przypadków z powodu cofania się.

Wypróbuj online!

Nie golfił

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.

MATL , 20 bajtów

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

Wypróbuj online! Lub zweryfikuj wszystkie przypadki testowe (zajmuje to chwilę).

Wyjaśnienie

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

Mathematica, 65 bajtów

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

JavaScript (Node.js) , 47 bajtów

x=>![...x].reduce(x=>x.replace(/(.)\1/gi,''),x)

Wypróbuj online!

Python 3 , 71 bajtów

s=input()
for i in s*len(s):s=s.replace(i+i.swapcase(),'')
print(not s)

Wypróbuj online!