Uma atividade que às vezes faço quando estou entediada é escrever alguns caracteres em pares correspondentes. Em seguida, traço linhas (por cima, nunca abaixo) para conectar esses caracteres. Por exemplo, eu poderia escrever $abcbac$ e depois desenhar as linhas como:

Ou eu poderia escrever $abbcac$

Depois de desenhar essas linhas, tento desenhar loops fechados em torno dos pedaços, para que meu loop não cruze nenhuma das linhas que acabei de desenhar. Por exemplo, no primeiro, o único loop que podemos desenhar é em torno da coisa toda, mas no segundo, podemos desenhar um loop em torno dos $b$ s (ou de todo o resto)

Se brincarmos com isso por um tempo, descobriremos que algumas cordas só podem ser desenhadas, de modo que os loops fechados contenham todas ou nenhuma das letras (como nosso primeiro exemplo). Vamos chamar essas cadeias de caracteres bem ligadas.

Observe que algumas seqüências de caracteres podem ser desenhadas de várias maneiras. Por exemplo, $bbbb$ pode ser desenhado das duas maneiras a seguir (e uma terceira não incluída):

ou

Se uma dessas maneiras puder ser desenhada de forma que um loop fechado possa ser feito para conter alguns dos caracteres sem cruzar nenhuma das linhas, a sequência não estará bem vinculada. (então $bbbb$ não está bem vinculado)

Tarefa

Sua tarefa é escrever um programa para identificar cadeias que estão bem vinculadas. Sua entrada será composta por uma sequência em que cada caractere aparece um número par de vezes, e sua saída deve ser um dos dois valores consistentes distintos, um se as sequências estiverem bem vinculadas e a outra, caso contrário.

Além disso o programa deve ser uma cadeia bem ligado significado

• Cada personagem aparece um número par de vezes no seu programa.

• Ele deve gerar o valor de verdade quando aprovado.

Seu programa deve ser capaz de produzir a saída correta para qualquer sequência que consiste em caracteres de ASCII imprimível ou no seu próprio programa. Com cada personagem aparecendo um número par de vezes.

As respostas serão pontuadas em comprimentos em bytes, com menos bytes sendo uma pontuação melhor.

Sugestão

Uma cadeia de caracteres não está bem vinculada se existir uma substring estrita não-vazia contígua, de modo que cada caractere apareça um número par de vezes nessa substring.

Casos de teste

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

Regex (ECMAScript 2018 ou .NET), 140 126 118 100 98 82 bytes

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

Isso é muito mais lento que a versão de 98 bytes, porque ^\1resta da lookahead e, portanto, é avaliada depois dela. Veja abaixo um switcheroo simples que recupera a velocidade. Mas, devido a isso, os dois TIOs abaixo estão limitados a concluir um conjunto de casos de teste menor do que antes, e o .NET é muito lento para verificar seu próprio regex.

Experimente online! (ECMAScript 2018)
Experimente online! (.LÍQUIDO)

Para eliminar 18 bytes (118 → 100), roubei descaradamente uma otimização muito boa do regex de Neil, que evita a necessidade de colocar um lookahead dentro do lookbehind negativo (produzindo um regex irrestrito de 80 bytes). Obrigado Neil!

Isso se tornou obsoleto quando ele lançou mais 16 bytes (98 → 82) incríveis, graças às idéias de jaytea , que levaram a um regex irrestrito de 69 bytes! É muito mais lento, mas isso é golfe!

Observe que as (|(no-ops para tornar o regex bem vinculado resultam em uma avaliação muito lenta no .NET. Eles não têm esse efeito no ECMAScript porque correspondências opcionais de largura zero são tratadas como não correspondências .

O ECMAScript proíbe quantificadores em asserções, o que dificulta os requisitos de fontes restritas para o golfe . No entanto, neste ponto, é tão bem jogado que não acho que o levantamento dessa restrição em particular abriria outras possibilidades de golfe.

Sem os caracteres extras necessários para fazer passar as restrições ( 101 69 bytes):

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

É lento, mas essa edição simples (por apenas 2 bytes extras) recupera toda a velocidade perdida e muito mais:

^(?!(.*)(.+)(.*$)(?<!^\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)
    )
)

Eu escrevi usando lookahead molecular ( 103 69 bytes) antes de convertê-lo em lookbehind de comprimento variável:

^(?!.*(?*(.+)(.*$))(?!^\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}
        )*$
    )
)

E para ajudar a tornar meu regex em si bem vinculado, tenho usado uma variação do regex acima:

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

Quando usado com regex -xml,rs -o, isso identifica uma substring estrita da entrada que contém um número par de cada caractere (se houver). Claro, eu poderia ter escrito um programa não regular para fazer isso por mim, mas onde seria a diversão nisso?

Gelatina, 20 bytes

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

Experimente online!

A primeira linha é ignorada. Está lá apenas para satisfazer a condição de que cada personagem apareça um número par de vezes.

A próxima linha primeiro Ġrouba os índices pelo seu valor. Se considerarmos o comprimento de cada sub-lista na lista resultante ( Ẉ), obtemos o número de vezes que cada caractere aparece. Para verificar se algum deles é impar, obtemos o último Ḃde cada contagem e perguntamos se existe Ẹum valor verdadeiro (diferente de zero).

Portanto, esse link auxiliar retorna se uma substring não pode ser circulada.

No link principal, pegamos todas as substrings da entrada ( Ẇ), Ṗdesativamos a última (para que não verifiquemos se toda a cadeia pode ser circulada) e executamos o link auxiliar ( Ç) em uma €substring. O resultado é então se Ạll substrings não podem ser circulados.

J , 34 bytes

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

Experimente online!

-8 bytes graças ao FrownyFrog

original

J , 42 bytes

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

Experimente online!

explicação

(*#'.,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 (pré-lançamento) , 66 bytes

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

Experimente online!

A era das expressões de atribuição está sobre nós. Com o PEP 572 incluído no Python 3.8, o golfe nunca mais será o mesmo. Você pode instalar a visualização antecipada do desenvolvedor 3.8.0a1 aqui .

As expressões de atribuição permitem usar :=para atribuir a uma variável embutida enquanto avalia esse valor. Por exemplo, (a:=2, a+1)dá (2, 3). Obviamente, isso pode ser usado para armazenar variáveis ​​para reutilização, mas aqui vamos um passo adiante e as usamos como um acumulador em uma compreensão.

Por exemplo, esse código calcula as somas cumulativas [1, 3, 6]

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

Observe como a cada passagem pela compreensão da lista, a soma acumulada té aumentada xe o novo valor é armazenado na lista produzida pela compreensão.

Da mesma forma, b:=b^{c}atualiza o conjunto de caracteres bpara alternar se inclui caracteres ce é avaliado para o novo valor de b. Assim, o código [b:=b^{c}for c in l]itera sobre caracteres cem le acumula o conjunto de caracteres visto um número ímpar de vezes em cada prefixo não vazio.

Essa lista é verificada quanto a duplicatas, tornando-a uma compreensão de conjunto e ver se seu comprimento é menor que o de s, o que significa que algumas repetições foram recolhidas. Nesse caso, a repetição significa que, na parte svisualizada entre esses momentos, todos os caracteres encontraram um número par de números, tornando a sequência não bem vinculada. O Python não permite que conjuntos de conjuntos sejam laváveis, então os conjuntos internos são convertidos em strings.

O conjunto bé inicializado como um argumento opcional e é modificado com êxito no escopo da função. Eu estava preocupado que isso tornasse a função não reutilizável, mas parece ser redefinida entre as execuções.

Para a restrição de origem, caracteres não emparelhados são colocados em um comentário no final. Escrever em for(c)in lvez de for c in lcancelar os parênteses extras gratuitamente. Colocamos idno conjunto inicial b, o que é inofensivo, pois pode ser iniciado como qualquer conjunto, mas o conjunto vazio não pode ser escrito, {}porque o Python criará um dicionário vazio. Desde as letras ie destão entre aqueles que necessitam de emparelhamento, podemos colocar a função idlá.

Observe que o código gera booleanos negados, portanto ele se dará corretamente False.

Python 2 , 74 bytes

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

Experimente online!

Repete a sequência, mantendo o controle Pdo conjunto de caracteres visto um número ímpar de vezes até agora. A lista darmazena todos os valores passados Pe, se a corrente Pjá estiver dpresente, isso significa que, nos caracteres vistos desde aquela época, cada caractere apareceu várias vezes. Nesse caso, verifique se passamos por toda a entrada: se tivermos, aceite porque toda a cadeia está emparelhada como esperado e, caso contrário, rejeite.

Agora sobre a restrição de origem. Os personagens que precisam de emparelhamento são colocados em vários locais inofensivos, sublinhados abaixo:

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

Ele f<savalia como 0emparelhar um f, aproveitando o nome da função também fpara que seja definido (no momento em que a função é chamada). O elemento 0^0absorve um ^símbolo.

O 0in P={0}é lamentável: no Python é {}avaliado como um ditado vazio, e não como um conjunto vazio, como queremos, e aqui podemos inserir qualquer elemento que não seja de caractere e será inofensivo. No entanto, não vejo nada de sobra para colocar, e o coloquei 0e o duplicado bmn0, custando 2 bytes. Observe que os argumentos iniciais são avaliados quando a função é definida; portanto, as variáveis ​​que definimos a nós mesmos não podem ser colocadas aqui.

Perl 6 , 76 bytes

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

Experimente online!

R Qualquer lambda que retorne uma Junção Nenhuma de Nenhuma Junção que possa ser boolificada para um valor de verdade / falsey. Eu recomendaria não remover o ?que boolifica o resultado do retorno, caso contrário, a saída fica bastante grande .

Esta solução é um pouco mais complexo do que o necessário, devido a várias funções envolvidas sendo desassociado, por exemplo .., all, >>, %%etc. Sem restrição a fonte, este pode ser 43 bytes:

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

Experimente online!

Explicação:

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

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

saída 0 se estiver bem vinculado 1 caso contrário.

78 bytes

86 bytes

94 bytes

Como funciona

• -pcom }{truque final para saída $\no final
• m-.+(?{.. })(?!)-, para executar o código em toda a substring não vazia ( .+coincide com toda a cadeia de caracteres primeiro e depois de executar o código entre as (?{.. })backtracks devido a falha forçada(?!)
• $Q|=@q&grp, lixo por causa da restrição de origem
• $\|=número inteiro bit a bit ou atribuição, se houver quase um 1, $\será 1 (verdadeiro), por padrão está vazio (falso)
• $&eq$_o caso em que sbustring é a string inteira é armazenado bit a bit ^com "sem ocorrência de caracteres ímpares"
• ($g=$&)=~/./gpara copiar a substring correspondente $g(porque será exagerada após a próxima correspondência de regex) e retorne a matriz de caracteres da substring.
• /^/ lixo que avalia para 1
• grep1 &(@m=$g=~/\Q$_/g),para cada caractere na subsequência de caracteres, obtém a matriz de caracteres $gcorrespondente, a matriz em escalar avalia seu tamanho e grepfiltrar os caracteres com ocorrência ímpar 1&xequivale ax%2==1

Retina , 150 96 bytes

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

Experimente online! O link inclui casos de teste, incluindo ele próprio. Edit: reduziu bastante o regex original com a ajuda do @Deadcode e depois voltou um pouco menos extravagante para manter o layout de origem. Explicação:

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

Afirme que não \3existe substring que corresponda às seguintes restrições.

(?<!^\2|

Afirme que a substring não é a sequência original inteira.

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

Afirme que não existe um personagem \6que:

• ele não aparece entre o próprio caractere (exclusivo) e o final da substring
• aparece um número par de vezes entre o início da substring e ele próprio (exclusivo)

Para passar a restrição de layout de origem, substituí ((((por (?:(^?(?:(e ((por (|(. Eu ainda tinha uma restrição de origem ))e os caracteres !()1<{}restantes, então mudei um +para {1,}e inseri o inútil (?!,<)?para consumir o resto.

C # (Compilador interativo do Visual C #) , 208 206 200 198 bytes

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*/

Experimente online!

-2 bytes graças a @KevinCruijssen!

Finalmente cheguei abaixo de 200, para que eu possa jogar golfe por agora :) Acabei criando um segundo TIO para testar as coisas com base em uma resposta anterior.

Experimente online!

Coisas que complicaram essa tarefa:

• Operador de igualdade ==não foi permitido
• O operador de incremento / atribuição ++não foi permitido
• A All()função Linq não foi permitida

Código comentado abaixo:

// 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 bytes

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#

Experimente online!

-2 graças a Ørjan Johansen .

Braquilog , 16 bytes

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

Experimente online!

Imprime false.para instâncias true.verdadeiras e falsas. A versão do TIO é muito lenta para lidar com ela mesma, mas está claramente bem vinculada, pois é uma sequência com caracteres únicos repetidos duas vezes.

Explicação

    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 bytes

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

Produz 1se a sequência está bem vinculada e 0se a sequência não está bem vinculada.

Experimente online ou verifique todos os casos de teste .

Explicação:

O programa base é ŒsKεsS¢ÈP}à( 11 bytes ), que sai 0se estiver bem vinculado e 1se não estiver bem vinculado. O final È(is_even) é um semi-no-op que inverte a saída, portanto, 1para cadeias bem vinculadas e 0para cadeias não bem vinculadas. As outras partes não são operacionais para cumprir as regras de desafio.

Œε¢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)