Czynnością, którą czasami robię, gdy się nudzę, jest pisanie kilku znaków w pasujących parach. Następnie rysuję linie (ponad szczytami nigdy poniżej), aby połączyć te postacie. Na przykład mógłbym napisać $abcbac$ a następnie narysować linie jako:

Albo mógłbym napisać $abbcac$

Po narysowaniu tych linii próbuję narysować zamknięte pętle wokół kawałków, aby moja pętla nie przecięła żadnej z linii, które właśnie narysowałem. Na przykład w pierwszej jedyną pętlą, którą możemy narysować, jest wokół całej rzeczy, ale w drugiej możemy narysować pętlę wokół tylko $b$ s (lub wszystkiego innego)

Jeśli zastanowimy się nad tym przez chwilę, okaże się, że niektóre ciągi znaków można narysować tylko po to, aby zamknięte pętle zawierały wszystkie litery lub żadną z nich (jak w naszym pierwszym przykładzie). Nazwiemy takie ciągi dobrze połączonymi ciągami.

Pamiętaj, że niektóre ciągi znaków można narysować na wiele sposobów. Na przykład $bbbb$ można narysować na dwa następujące sposoby (i nie uwzględniono trzeciego):

lub

Jeśli jeden z tych sposobów można narysować w taki sposób, że można utworzyć zamkniętą pętlę zawierającą niektóre znaki bez przecinania którejkolwiek linii, łańcuch nie jest dobrze połączony. (więc $bbbb$ nie jest dobrze powiązane)

Zadanie

Twoim zadaniem jest napisanie programu identyfikującego dobrze powiązane ciągi. Twoje dane wejściowe będą składać się z łańcucha, w którym każdy znak pojawia się parzystą liczbę razy, a twój wynik powinien być jedną z dwóch różnych spójnych wartości, jedną, jeśli łańcuchy są dobrze połączone, a drugą w przeciwnym razie.

Ponadto program musi być dobrze połączony ciąg sens

• Każda postać pojawia się w twoim programie parzystą liczbę razy.

• Powinien generować prawdziwą wartość po przekazaniu.

Twój program powinien być w stanie wygenerować prawidłowe dane wyjściowe dla dowolnego łańcucha składającego się ze znaków z drukowalnego ASCII lub własnego programu. Każda postać pojawia się parzystą liczbę razy.

Odpowiedzi będą oceniane jako ich długości w bajtach, przy czym mniej bajtów jest lepszym wynikiem.

Wskazówka

Ciąg nie jest dobrze połączony, jeśli istnieje ciągły niepusty pusty podciąg, tak że każdy znak pojawia się w tym podciągu parzystą liczbę razy.

Przypadki testowe

abcbac -> True
abbcac -> False
bbbb -> False
abacbc -> True
abcbabcb -> True
abcbca -> False

Regex (ECMAScript 2018 lub .NET), 140 126 118 100 98 82 bajtów

^(?!(^.*)(.+)(.*$)(?<!^\2|^\1(?=(|(<?(|(?!\8).)*(\8|\3$){1}){2})*$).*(.)+\3$)!?=*)

Jest to znacznie wolniejsze niż wersja 98-bajtowa, ponieważ ^\1lewa strona z wyprzedzeniem, a zatem jest oceniana po niej. Poniżej znajduje się prosty przełącznik, który odzyskuje prędkość. Ale z tego powodu dwa poniższe TIO są ograniczone do ukończenia mniejszego zestawu przypadków testowych niż wcześniej, a jeden .NET jest zbyt wolny, aby sprawdzić swój regex.

Wypróbuj online! (ECMAScript 2018)
Wypróbuj online! (.NETTO)

Aby upuścić 18 bajtów (118 → 100), bezwstydnie ukradłem naprawdę fajną optymalizację z wyrażenia regularnego Neila, który pozwala uniknąć konieczności umieszczania spojrzenia w środku negatywnego spojrzenia (uzyskując 80 bajtów nieograniczonego wyrażenia regularnego). Dziękuję Neil!

Stało się to przestarzałe, kiedy zrzuciło niewiarygodne 16 dodatkowych bajtów (98 → 82) dzięki pomysłom jaytea , które doprowadziły do ​​69-bajtowego nieograniczonego wyrażenia regularnego! Jest znacznie wolniejszy, ale to golf!

Zauważ, że (|(brak operacji poprawienia powiązania wyrażenia regularnego powoduje, że ocenia on bardzo powoli w .NET. Nie mają tego efektu w ECMAScript, ponieważ opcjonalne dopasowania o zerowej szerokości są traktowane jako niepasujące .

ECMAScript zabrania kwantyfikatorów w odniesieniu do asercji, co utrudnia grę w golfa w ograniczonych źródłach . Jednak w tym momencie gra jest tak dobrze golfa, że ​​nie sądzę, aby zniesienie tego konkretnego ograniczenia otworzyło dalsze możliwości gry w golfa.

Bez dodatkowych znaków potrzebnych do przejścia przez ograniczenia ( 101 69 bajtów):

^(?!(.*)(.+)(.*$)(?<!^\2|^\1(?=((((?!\8).)*(\8|\3$)){2})*$).*(.)+\3))

Jest powolny, ale ta prosta edycja (tylko 2 dodatkowe bajty) odzyskuje utraconą prędkość i więcej:

^(?!(.*)(.+)(.*$)(?<!^\2|(?=\1((((?!\8).)*(\8|\3$)){2})*$)^\1.*(.)+\3))

^
(?!
    (.*)               # cycle through all starting points of substrings;
                       # \1 = part to exclude from the start
    (.+)               # cycle through all ending points of non-empty substrings;
                       # \2 = the substring
    (.*$)              # \3 = part to exclude from the end
    (?<!               # Assert that every character in the substring appears a total
                       # even number of times.
        ^\2            # Assert that our substring is not the whole string. We don't
                       # need a $ anchor because we were already at the end before
                       # entering this lookbehind.
    |                  # Note that the following steps are evaluated right to left,
                       # so please read them from bottom to top.
        ^\1            # Do not look further left than the start of our substring.
        (?=
            # Assert that the number of times the character \8 appears in our
            # substring is odd.
            (
                (
                    ((?!\8).)*
                    (\8|\3$) # This is the best part. Until the very last iteration
                             # of the loop outside the {2} loop, this alternation
                             # can only match \8, and once it reaches the end of the
                             # substring, it can match \3$ only once. This guarantees
                             # that it will match \8 an odd number of times, in matched
                             # pairs until finding one more at the end of the substring,
                             # which is paired with the \3$ instead of another \8.
                ){2}
            )*$
        )
        .*(.)+         # \8 = cycle through all characters in this substring
        # Assert (within this context) that at least one character appears an odd
        # number of times within our substring. (Outside this negative lookbehind,
        # that is equivalent to asserting that no character appears an odd number
        # of times in our substring.)
        \3             # Skip to our substring (do not look further right than its end)
    )
)

Napisałem go za pomocą molekularnego lookahead ( 103 69 bajtów) przed przekształceniem go w look-look o zmiennej długości:

^(?!.*(?*(.+)(.*$))(?!^\1$|(?*(.)+.*\2$)((((?!\3).)*(\3|\2$)){2})*$))

^
(?!
    .*(?*(.+)(.*$))       # cycle through all non-empty substrings;
                          # \1 = the current substring;
                          # \2 = the part to exclude from the end
    (?!                   # Assert that no character in the substring appears a
                          # total even number of times.
        ^\1$              # Assert that our substring is not the whole string
                          # (i.e. it's a strict substring)
    |
        (?*(.)+.*\2$)    # \3 = Cycle through all characters that appear in this
                          # substring.
        # Assert (within this context) that this character appears an odd number
        # of times within our substring.
        (
            (
                ((?!\3).)*
                (\3|\2$)
            ){2}
        )*$
    )
)

Aby pomóc w poprawnym powiązaniu mojego wyrażenia regularnego, użyłem odmiany powyższego wyrażenia regularnego:

(?*(.+)(.*$))(?!^\1$|(?*(.)+.*\2$)((((?!\3).)*(\3|\2$)){2})*$)\1

W połączeniu z regex -xml,rs -otym identyfikuje ścisły podciąg wejściowy, który zawiera parzystą liczbę każdego znaku (jeśli taki istnieje). Jasne, mógłbym napisać program, który nie robi wyrażeń regularnych, aby to dla mnie zrobić, ale gdzie byłaby w tym zabawa?

Galaretka, 20 bajtów

ĠẈḂẸẆṖÇ€Ạ
ĠẈḂẸ
ẆṖÇ€Ạ

Wypróbuj online!

Pierwszy wiersz jest ignorowany. Ma tylko spełnić warunek, że każda postać pojawia się parzysta liczba razy.

Następny wiersz najpierw Ġroups indeksy według ich wartości. Jeśli następnie weźmiemy długość każdej podlisty na wynikowej liście ( Ẉ), otrzymamy liczbę wyświetleń każdego znaku. Aby sprawdzić, czy którykolwiek z nich nie jest parzysty, otrzymujemy ostatni Ḃwynik z każdej liczby i pytamy, czy istnieje ẸXist prawdziwa (niezerowa) wartość.

Dlatego to łącze pomocnicze zwraca informację, czy podciąg nie może zostać zakreślony.

W głównym łączu bierzemy wszystkie podłańcuchy input ( Ẇ), Ṗop wyłączamy ostatni (abyśmy nie sprawdzali, czy cały ciąg może zostać zakreślony) i uruchamiamy link pomocniczy ( Ç) na €dowolnym podciągu. Rezultatem jest wtedy, czy Ạpodciągów 11 nie można zakreślić.

J , 34 bajty

2:@':.,|~*'>1(#.,)*/@(1>2|#/.~)\.\

Wypróbuj online!

-8 bajtów dzięki FrownyFrog

oryginał

J , 42 bajty

(*#'.,012&|@~#')=1#.[:,([:*/0=2&|@#/.~)\.\

Wypróbuj online!

wyjaśnienie

(*#'.,012&|@~#') = 1 #. [: , ([: */ 0 = 2&|@#/.~)\.\

(*#'.,012&|@~#')                                       NB. this evaluates to 1
                                                       NB. while supplying extra
                                                       NB. chars we need.  hence...
                 =                                     NB. does 1 equal...
                   1 #.                                NB. the sum of...
                        [: ,                           NB. the flatten of...
                             (                  )\.\   NB. the verb in parens applied
                                                       NB. to every suffix of every
                                                       NB. prefix, ie, all contiguous 
                                                       NB. substrings
                             ([: */ 0 = 2&|@#/.~)      NB. def of verb in paren:
                                             /.~       NB. when we group by each
                                                       NB. distinct char...
                              [: */                    NB. is it the case that
                                                       NB. every group...
                                           @#          NB. has a length...
                                    0 = 2&|            NB. divisible by 2...

Python 3.8 (wersja wstępna) , 66 bajtów

lambda l,b={id}:len({str(b:=b^{c})for(c)in l})<len(l)#,<^fmnost{}#

Wypróbuj online!

Era wyrażeń przydziału jest już nad nami. Z PEP 572 zawartym w Pythonie 3.8 gra w golfa nigdy nie będzie taka sama. Można zainstalować wcześniejszą developer preview 3.8.0a1 tutaj .

Wyrażenia przypisania pozwalają :=na przypisanie do zmiennej wbudowanej podczas obliczania tej wartości. Na przykład (a:=2, a+1)daje (2, 3). Można to oczywiście wykorzystać do przechowywania zmiennych do ponownego użycia, ale tutaj idziemy o krok dalej i używamy go jako akumulatora w zrozumieniu.

Na przykład ten kod oblicza sumy skumulowane [1, 3, 6]

t=0
l=[1,2,3]
print([t:=t+x for x in l])

Zwróć uwagę, że przy każdym przejściu przez zrozumienie listy skumulowana suma tjest zwiększana o, xa nowa wartość jest zapisywana na liście utworzonej przez zrozumienie.

Podobnie b:=b^{c}aktualizuje zestaw znaków, baby przełączać, czy zawiera on znak c, i ocenia nową wartość b. Więc, kod [b:=b^{c}for c in l]iteruje znaków cw li gromadzi zbiór znaków widoczny nieparzystą liczbę razy w każdym niepustym przedrostkiem.

Ta lista jest sprawdzana pod kątem duplikatów, czyniąc ją zrozumieniem zestawu i sprawdzając, czy jej długość jest mniejsza niż s, co oznacza, że ​​niektóre powtórzenia zostały zwinięte. Jeśli tak, powtórzenie oznacza, że ​​w części swidzianej pomiędzy tymi czasami każdy znak napotkał parzystą liczbę liczb, co powoduje, że łańcuch nie jest dobrze powiązany. Python nie zezwala na to, aby zestawy zestawów były niehashowalne, więc zestawy wewnętrzne są konwertowane na ciągi.

Zestaw bjest inicjowany jako opcjonalne argumenty i pomyślnie modyfikowany w zakresie funkcji. Martwiłem się, że to uniemożliwi ponowne użycie funkcji, ale wydaje się, że resetuje się między kolejnymi uruchomieniami.

W celu ograniczenia źródła nieparzyste znaki są umieszczane w komentarzu na końcu. Pisanie for(c)in lzamiast for c in lanulować dodatkowe pareny za darmo. Wstawiamy iddo początkowego zestawu b, który jest nieszkodliwy, ponieważ można go uruchomić jako dowolny zestaw, ale pustego zestawu nie można zapisać, {}ponieważ Python utworzy pusty słownik. Ponieważ litery ii dnależą do tych, które wymagają parowania, możemy umieścić idtam funkcję .

Zauważ, że kod wypisuje zanegowane wartości logiczne, więc poprawnie się da False.

Python 2 , 74 bajty

bmn0=f=lambda s,P={0},d=[]:s<" "if(P in d)else+f(s[f<s:],P^{s[0^0]},[P]+d)

Wypróbuj online!

Iteruje przez ciąg znaków, śledząc Pzestaw znaków widzianych do tej pory nieparzystą liczbę razy. Lista dprzechowuje wszystkie poprzednie wartości P, a jeśli widzisz Pjuż obecny d, oznacza to, że w postaciach widzianych od tego czasu, każda postać pojawiła się parzystą liczbę razy. Jeśli tak, sprawdź, czy przeszliśmy przez cały sygnał wejściowy: jeśli tak, zaakceptuj, ponieważ cały ciąg jest sparowany zgodnie z oczekiwaniami, a w przeciwnym razie odrzuć.

Teraz o ograniczeniach źródłowych. Postacie wymagające parowania są umieszczane w różnych nieszkodliwych miejscach, co podkreślono poniżej:

bmn0=f=lambda s,P={0},d=[]:s<" "if(P in d)else+f(s[f<s:],P^{s[0^0]},[P]+d)
_____              _              _      _    _    ___        ___    

W f<sZwraca 0podczas parowania akcję f, korzystając z nazwa funkcji jest też ftak, że to określone (przez czas funkcja jest wywoływana.) Do 0^0wchłania się ^symbol.

0W P={0}to niefortunne: w Pythonie {}Wynikiem jest pusty dict zamiast pustego zestawu jak chcemy, a tutaj możemy umieścić w dowolnym elemencie bez znaków i będzie to nieszkodliwe. Nie widzę jednak nic do dodania, włożyłem 0i zduplikowałem bmn0, co kosztuje 2 bajty. Zauważ, że początkowe argumenty są oceniane, gdy funkcja jest zdefiniowana, więc zmiennych, które sami definiujemy, nie można wstawić tutaj.

Perl 6 , 76 bajtów

*.comb[^*X+(^*).map(^*)].grep({$_&[&]($_)}).none.Bag{*}.none%2#*^+XBob2rec%#

Wypróbuj online!

Cokolwiek lambda, które zwraca None Junction of None Junction, które można podwyższyć do wartości true / falsey. ?Zalecałbym jednak nie usuwać tego, który zwiększa wynik zwracania, w przeciwnym razie dane wyjściowe stają się dość duże .

Rozwiązanie to jest trochę bardziej skomplikowane niż to konieczne, ze względu na kilka zaangażowane funkcje są odłączone, np .., all, >>, %%itd. Bez ograniczeń źródłowego, może to być 43 bajtów:

*.comb[^*X.. ^*].grep(?*).one.Bag{*}.all%%2

Wypróbuj online!

Wyjaśnienie:

*.comb                     # Split the string to a list of characters
      [^*X+(^*).map(^*)]   # Get all substrings, alongside some garbage
                        .grep({$_&[&]($_)})        # Filter out the garbage (empty lists, lists with Nil values)
                                           .none                 # Are none of
                                                .Bag{*}          # The count of characters in each substring
                                                       .none%2   # All not divisible by 2

                                               #*^+XBob2rec%#    And garbage to even out character counts

Perl 5 -p, 94, 86, 78 bajtów

m-.+(?{$Q|=@q&grp,$\|=$&eq$_^!grep+/^/&(@m=$g=~/\Q$_/g),($g=$&)=~/./g})(?!)-}{

ouput 0, jeśli dobrze połączone 1 w innym przypadku.

78 bajtów

86 bajtów

94 bajty

Jak to działa

• -pz }{zakończoną lewą do wyjścia $\na końcu
• m-.+(?{.. })(?!)-, aby wykonać kod na wszystkich niepustych podciągach ( .+najpierw dopasowuje cały ciąg, a po wykonaniu kodu między (?{.. })cofnięciami z powodu nieudanego wymuszenia(?!)
• $Q|=@q&grp, śmieci ze względu na ograniczenie źródła
• $\|=liczba całkowita bitowa lub przypisanie, jeśli jest prawie jedna 1, $\będzie wynosić 1 (prawda), domyślnie jest pusta (fałsz)
• $&eq$_przypadek, w którym sbustrowanie jest całym łańcuchem, jest bitowo xoredowany ^z „brakiem dziwnego znaku”
• ($g=$&)=~/./gdo skopiowania dopasowanego podłańcucha do $g(ponieważ zostanie przytłoczony po następnym dopasowaniu wyrażenia regularnego) i zwróci tablicę znaków podłańcucha.
• /^/ śmieci, których wynikiem jest 1
• grep1 &(@m=$g=~/\Q$_/g),dla każdego znaku w podciągu uzyskuje tablicę znaków w $gdopasowaniu do siebie, tablica w skalarnie ocenia się na jej rozmiar, a grepfiltrowanie znaków o nieparzystym wystąpieniu 1&xjest równoważne zx%2==1

Siatkówka , 150 96 bajtów

^(?!(.*)(.+)(.*)$(?<!^\2|^\1(?:(^?(?:(?!\6).)*\6){2})*(|(?!\6).)*(?!.+\6.*\3$)(.){1,}\3)(?!,<)?)

Wypróbuj online! Link zawiera przypadki testowe, w tym siebie. Edycja: Grałem trochę w golfa w oryginalnym wyrażeniu regularnym z pomocą @Deadcode, a następnie nieco mniej ekstrawagancko cofałem się, aby zachować układ źródłowy. Wyjaśnienie:

^(?!(.*)(.+)(.*)$

Upewnij się, że nie ma podciągów \3, które pasują do następujących ograniczeń.

(?<!^\2|

Upewnij się, że podciąg nie jest całym oryginalnym łańcuchem.

^\1(?:(^?(?:(?!\6).)*\6){2})*(|(?!\6).)*(?!.+\6.*\3$)(.){1,}\3)(?!,<)?)

Zapewnij, że nie ma \6takiego znaku , który:

• nie pojawia się między samym znakiem (wyłącznym) a końcem podłańcucha
• pojawia się parzysta liczba razy między początkiem podłańcucha a sobą (wyłącznie)

Aby zdać ograniczenie układu źródło, wymieniłem ((((z (?:(^?(?:(i ((z (|(. Nadal miałem jedno ograniczenie źródłowe, ))a pozostałe postacie !()1<{}, więc zmieniłem +na {1,}i wstawiłem bezużyteczne, (?!,<)?aby pochłonąć resztę.

C # (interaktywny kompilator Visual C #) , 208 206 200 198 bajtów

x=>!x.GroupBy(c=>c).Any(g=>g.Count()%2>0)&!Enumerable.Repeat(x.Count,x.Count*x.Count).Where(
(l,i)=>i%l>0&!x.Skip(i/l).Take(i%l).GroupBy(c=>c).Any(g=>g.Count()%2>0)
).Any()/*>!oyAnC0EmeablR*WhiS/T*/

Wypróbuj online!

-2 bajty dzięki @KevinCruijssen!

W końcu mam poniżej 200, więc na razie mogę grać w golfa :) Skończyłem tworzenie drugiego TIO, aby przetestować wszystko na podstawie poprzedniej odpowiedzi.

Wypróbuj online!

Rzeczy, które utrudniały to zadanie:

• Operator równości ==nie był dozwolony
• Operator inkrementacji / przypisania ++był niedozwolony
• All()Funkcja Linq była niedozwolona

Skomentowany kod poniżej:

// anonymous function that takes an IList as input
x=>
  // the first condition makes sure the string even
  // counts of each character
  !x.GroupBy(c=>c).Any(g=>g.Count()%2>0)&
  // the second condition generates all proper substrings of x
  // and tests for any that contain even character counts
  // the string length `l` is repeated `l*l` times
  !Enumerable.Repeat(x.Count,x.Count*x.Count)
    .Where((l,i)=>
      // check that the substring length is greater than 0
      i%l>0&
      // use skip/take to generate a substring
      // and check for a character count thats odd
      // negate the result meaning we have found
      // a substring that invalidates the input
      !x.Skip(i/l).Take(i%l)
        .GroupBy(c=>c).Any(g=>g.Count()%2>0)
    )
    // if any invalid substrings are found
    // then the result in invalid
    // the comment string at the end is needed
    // to make the program well-linked
    .Any()/*>!oyAnC0EmeablR*WhiS/T*/

Python 2 , 108 bajtów

lambda d,e=enumerate:min(max(d[l:l+b].count(k)%2for(k)in d)for b,c in e(d[2:],2)for l,f in e(d) )#b =:x+.%2#

Wypróbuj online!

-2 dzięki Ørjan Johansen .

Brachylog , 16 bajtów

sᶠb∋p~j&sᶠb∋p~j&

Wypróbuj online!

Odbitki false.dla autentycznych przypadków i true.dla fałszywych przypadków. Wersja TIO jest zbyt wolna, aby poradzić sobie sama, ale jest wyraźnie powiązana, ponieważ jest ciągiem znaków z unikatowymi powtórzeniami dwukrotnie.

Wyjaśnienie

    Input is a string: "abcacbaa"
sᶠ  Find all substrings: ["abcacbaa","abcacba","abcacb",..,"a"]
b   Behead (now the proper substrings remain): ["abcacba","abcacb",..,"a"]
∋   Take one of them: "abcacb"
p   Permute it: "abcabc"
~j  It is some string repeated twice: "abc"
&   Get the input again: "abcacbaa"
    Then repeat the above.
    If the constraints can be satisfied, the result is true, otherwise false.

05AB1E , 22 20 bajtów

Œε¢Pà}KŒIKεSIS¢ÈP}àÈ

Wyprowadzane, 1jeśli ciąg jest dobrze połączony i 0jeśli ciąg nie jest dobrze połączony.

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

Program podstawowy to ŒsKεsS¢ÈP}à( 11 bajtów ), który wyprowadza, 0jeśli jest dobrze połączony i 1jeśli nie jest dobrze połączony. Kropka È(is_even) jest pół-op, który nie odwraca wyjście, więc 1na dobrze połączonych ciągów i 0za nie dobrze połączonych ciągów. Pozostałe części nie są zgodne z regułami wyzwań.

Œε¢Pà}K         # No-ops: substrings, map, count, product, maximum, close map, remove
                # Due to the last remove, we're back at the (implicit) input again
Π              # Take the substrings of the input
 IK             # Remove the input itself from that list of substrings
   ε            # Map each substring to:
    S           #  No-op: transform the substring into a list of characters
     IS         #  Get the input-string as a list of characters
       ¢        #  Count the occurrence of each character in the current substring
        È       #  Check which counts are even (1 if truthy; 0 if falsey)
         P      #  Take the product of that
          }à    # After the map: check if any are truthy by taking the maximum
            È   # Semi no-op: check if this maximum is even (0 becomes 1; 1 becomes 0)
                # (and output the result implicitly)