Anexar e apagar

14

Dada uma linha que consiste apenas em letras, processe da seguinte maneira:

  • Você mantém uma string vazia no começo.
  • Se o próximo caractere de entrada estiver na sequência, remova-o da sequência.
  • Se o próximo caractere de entrada não estiver na sequência, anexe-o à sequência.

Saída o estado final da string.

Você pode assumir com segurança que a entrada consiste em pelo menos um caractere (ou seja, não vazio), mas não há garantia de que a saída não esteja vazia.

Pseudocódigo (sinta-se à vontade para jogar isso):

str = EMPTY
for each character ch in input
  if ch exists in str
    remove all ch from str
  else
    append ch to str
print str

A entrada corresponde à expressão regular ^[A-Za-z]+$.

Casos de teste de amostra:

ABCDBCCBE -> ADCBE
ABCXYZCABXAYZ -> A
aAABBbAbbB -> aAbB
GG -> (empty)

A entrada pode ser fornecida de qualquer maneira aplicável, mas deve ser tratada como uma sequência e o mesmo para saída. O programa não deve sair com um erro.

O programa mais curto em cada idioma vence!

Extra (opcional): explique como o seu programa funciona. Obrigado.

iBug
fonte
A linha pode estar vazia?
user202729
1
@ user202729 Não. Mudei um pouco (não invalida nenhuma resposta) para que a entrada nunca fique vazia.
iBug 28/11
1
Então, por que você rejeitou a sugestão de edição do ais523 (link) ?
user202729

Respostas:

10

Haskell , 44 42 bytes

foldl(#)""
s#x|z<-filter(/=x)s=z++[x|z==s]

Experimente online! Edit: -2 bytes graças ao Zgarb!

Explicação:

A segunda linha define uma função (#)que pega uma string se um caractere xe executa a remoção ou o acréscimo. Isso é obtido através da filteringestão de todas as ocorrências de xin s, resultando na string z. Se xnão ocorrer s, zserá igual a se z++[x|z==s]produzirá a sequência original com xanexado. Caso contrário, [x|z==s]gera a cadeia vazia e somente a cadeia filtrada é retornada.

foldl(#)""é uma função anônima que pega uma string e adiciona um caracter após o outro a string inicialmente vazia ""com a função (#).

Laikoni
fonte
2
42 bytes reutilizando o filtro.
Zgarb
9

Geléia , 3 bytes

œ^/

Experimente online!

Programa completo.

Erik, o Outgolfer
fonte
Por que œ^/não basta?
Jonathan Allan
@ JonathanAllan O programa não deve sair com um erro.
Erik the Outgolfer
the input is never emptyBem, agora funciona.
user202729
8

J , 21 19 bytes

#~~:&.|.(2|*)1#.=/~

Como funciona:

=/~ - cria uma tabela de igualdade dos caracteres na string:

   a =. 'ABCXYZCABXAYZ'
   ]b =: =/~ a 
1 0 0 0 0 0 0 1 0 0 1 0 0
0 1 0 0 0 0 0 0 1 0 0 0 0
0 0 1 0 0 0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 1 0 0 0
0 0 0 0 1 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 1
0 0 1 0 0 0 1 0 0 0 0 0 0
1 0 0 0 0 0 0 1 0 0 1 0 0
0 1 0 0 0 0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0 0 1 0 0 0
1 0 0 0 0 0 0 1 0 0 1 0 0
0 0 0 0 1 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 1

1#. - soma de cada linha pela conversão de base 1 (quantas vezes a letra ocorre)

   ]c =: 1#. b
3 2 2 2 2 2 2 3 2 2 3 2 2

~:&.|- inverta e aplique a peneira nub (é o caractere exclusivo) e inverta novamente. Portanto, encontro as últimas ocorrências dos caracteres na string:

   ]d =. ~:&.|. a
0 0 0 0 0 0 1 0 1 1 1 1 1

* - multiplica a contagem por 1 para a última posição do caractere no anel, por 0 caso contrário, calculado pela acima ~:&.|

   ]e =. c * d
0 0 0 0 0 0 2 0 2 2 3 2 2

2| - módulo 2 (define como 0 as posições dos caracteres que contam mesmo):

   ]f =. 2| e 
0 0 0 0 0 0 0 0 0 0 1 0 0

#~- copie o argumento da direita, à esquerda, arg. times (~ inverte os lugares dos argumentos)

]f # a A

Experimente online!

Galen Ivanov
fonte
6

Brainfuck, 95 bytes

,[<<<[[->+>>>+<<<<]>>>[-<+<->>]<<[[-]<]>[[-]>>[-]>[[-<+>]>]<<[<]<<]<<]<[->>>>[-]<<<]>>>>[->+<]>>[>]>>,]<<<[.<]

Experimente Online

Como funciona

, Gets first input
[ Starts loop
    <<< Go to start of string
    [ Loop over the string
        [->+>>>+<<<<] Duplicates the current char of the string
        >>>[-<+<->>] Duplicates and subtracts the inputted char from the duplicate of the string char
        <<[[-]<] If the char is different to the input, remove the difference
        > If the char is the same
        [
            [-]>>[-]>[[-<+>]>]<<[<]<< Remove the char from the string and sets the inputted char to 0
        ]
        << Moves to the next char of the string
    ]
    >>>[->+<] adds the inputted char to the string
    >>[>]>>, gets the next input
]
<<<[.<] prints the string
Brincadeira
fonte
4

Haskell , 47 bytes

Outro bytes a poeira, graças a Bruce Forte.

import Data.List
foldl1(\x y->union(x\\y)$y\\x)

Experimente online!

Leva uma lista de seqüências de caracteres.

A diferença simétrica é irritante ...

totalmente humano
fonte
++economiza 2 bytes unioncom este método.
Ørjan Johansen
2

R , 92 84 77 bytes

for(i in el(strsplit(scan(,y<-''),y)))y=c(y[y!=i],if(!i%in%y)i);cat(y,sep='')

Experimente online!

-15 bytes graças a djhurio

Explicação

O djhurio forneceu uma excelente resposta R, evitando um forloop - como programadores R instintivamente fazem como regra (inclusive eu). Aqui está uma resposta R que utiliza um forloop (e salva alguns bytes no processo).

  • x=scan(,''); - atribua a entrada na variável x
  • y=''; - crie uma string vazia em uma variável chamada y
  • for(i in el(strsplit(x,'')))- para cada personagem iemx
  • y=c(y[y!=i],if(!i%in%y)i)- atribuir a ycada elemento yque não seja igual a i, acrescentando ise iainda não estiver emy
  • cat(y,sep='')- imprima os elementos ysem espaço entre eles

Nota

Se você clicar no link TIO acima, encontrará no cabeçalho library(methods); isso é para lidar com o erro que o djhurio experimentou em relação à el()função - a função é fornecida pelo methodspacote, que em qualquer versão do R que eu usei, é carregado por padrão, mas por qualquer motivo não é do TIO. Se library(methods)for removido do cabeçalho e unlistsubstituído el, eu ganho quatro bytes, mas djhurio também , colocando nossa contagem de bytes em 96 88 e 99, respectivamente.

duckmayr
fonte
Agradável. Nunca pensei em loop será mais curto. Você pode torná-lo ainda mais curto, omitindo a instrução else for(i in el(strsplit(scan(,y<-''),y)))y=c(y[y!=i],if(!i%in%y)i);cat(y,sep='').
djhurio
@djhurio - Eu sei, quase nunca é o caso de que o RA for um loop ajude com qualquer coisa. Em relação à sua sugestão: ótima ideia! A sugestão agora está incorporada na resposta.
duckmayr
1
@djhurio - justo o suficiente; Eu estava muito ocupado olhando para a diferença introduzida por omitir a declaração else que não via como você mudou o começo. Editando agora. Ótimo trabalho!
duckmayr
1
@djhurio @duckmayr existe uma solução de 73 bytes que basicamente usa essa solução e usa uma abordagem ligeiramente diferente para extrair caracteres. Eu realmente não queria postá-lo como uma resposta separada. Observe também que ...[[1]]é maior que, el(...)mas menor que unlist(...), desde que ...seja uma lista de comprimento 1.
Giuseppe
1
riscar isso, eu encontrei uma resposta de 70 bye, pois 0é o nulpersonagem e é convertido para a string vazia.
Giuseppe
2

MATL , 6 bytes

vi"@X~

Não funciona no ambiente TIO, mas funciona bem na implementação do MATLAB e, graças a um novo patch, você pode experimentá-lo no MATL Online

X~igual setxorou diferença simétrica, que faz exatamente o que o desafio pede. O resto está apenas repetindo a entrada i"@e começando com uma string vazia, concatenando toda a pilha que está vazia no início (obrigado Luis Mendo).

Sanchises
fonte
2

Python 2 , 56 bytes

-2 bytes graças ao xnor. -3 bytes graças a ovs.

lambda s:reduce(lambda a,c:a.replace(c,'')+c[c in a:],s)

Experimente online!

Literalmente, apenas jogou o pseudocódigo. : P

totalmente humano
fonte
1
Salvar 2 bytes: s=(s+c).replace(c,c[c in s:]).
Xnor
@xnor Isso é um pouco de golfe básico executado de maneira muito inteligente. Obrigado!
totallyhuman
1
-1 byte :s=s.replace(c,'')+c[c in s:]
ovs 26/11
1
56 bytes usando
reduzida
1

JavaScript (ES6), 60 bytes

s=>[...s].map(c=>s=s.match(c)?s.split(c).join``:s+c,s='')&&s

Casos de teste

Arnauld
fonte
Eu portado @ resposta Retina do MartinEnder e foi apenas 45 bytes ...
Neil
1

q , 38 bytes

""{$[y in x;except;,][x;y]}/
skeevey
fonte
1

APL + WIN, 19 bytes

Lógica semelhante à solução J de Galen.

(2|+⌿⌽<\⌽c∘.=c)/c←⎕     
Graham
fonte
1

Wolfram Language (Mathematica) , 36 bytes

#//.{a___,x_,b___,x_,c___}:>{a,b,c}&

Experimente online!

Toma entrada e saída como uma lista de caracteres.

Como funciona

Usa //.(alias ReplaceRepeated) para encontrar dois caracteres repetidos e excluir os dois, até que não exista mais caracteres repetidos. Se o caractere ocorrer mais de duas vezes, o Mathematica sempre excluirá as duas primeiras ocorrências. Portanto, se um personagem ocorrer um número ímpar de vezes, sua última instância será sempre a única a sobreviver.

Misha Lavrov
fonte
1

Prolog 81 byte

a([],O,O).
a([I|J],K,O):-delete(K,I,F),(K=F->append(K,[I],M),a(J,M,O);a(J,F,O)).

Versão não ofuscada:

append_and_eraze([], Output, Output).
append_and_eraze([I | Input], Interim, Output) :-
    delete(Interim, I, Filtered),
    ( Interim = Filtered ->
      append(Interim, [I], Interim1),
      append_and_eraze(Input, Interim1, Output)
    ;
    append_and_eraze(Input, Filtered, Output)
    ).
  1. delete/3 garante que seu terceiro argumento seja unificado ao primeiro, com todas as instâncias do segundo argumento removidas.
  2. Se esses forem os mesmos, anexamos o elemento (ele não foi removido).
  3. append/3 conforme seu nome, acrescenta um elemento à lista.
  4. Recorremos aos elementos da entrada até atingirmos a [](lista vazia), momento em que o resultado intermediário será unificado com o resultado desejado.

Teste:

?- append_and_eraze(`ABCDBCCBE`, [], X), string_codes(Y, X).
X = [65, 68, 67, 66, 69],
Y = "ADCBE".

?- append_and_eraze(`ABCXYZCABXAYZ`, [], X), string_codes(Y, X).
X = [65],
Y = "A".

?- append_and_eraze(`aAABBbAbbB`, [], X), string_codes(Y, X).
X = [97, 65, 98, 66],
Y = "aAbB".

?- append_and_eraze(`GG`, [], X), string_codes(Y, X).
X = [],
Y = "".

Alguns Prologs tratam seqüências de caracteres entre aspas duplas como listas, o SWI pode ser configurado para fazer o mesmo, mas por uma questão de simplicidade, eu costumava string_codes/2formatar bem a saída.

wvxvw
fonte
1

R , 84 bytes

y=el(strsplit(scan(,""),""));cat(unique(y[colSums(outer(y,y,"=="))%%2>0],,T),sep="")

Experimente online!

Outra solução, mas há melhores R respostas aqui.

R , 88 bytes

z=table(y<-el(strsplit(scan(,""),"")));cat(setdiff(unique(y,,T),names(z[!z%%2])),sep="")

Experimente online!

Obrigado a Giuseppe por -7 bytes!

Há uma resposta mais curta de duckmayr .

  1. scan(,"") leia a entrada do stdin.
  2. y<-el(strsplit(scan(,""),"")) divida a entrada por caracteres e salve como y .
  3. z=table(y<-el(strsplit(scan(,""),""))) calcular frequências de cada caractere e salvar a tabela resultante como z ;
  4. unique(y,,T) pegue caracteres únicos do lado direito.
  5. names(z[!z%%2]) selecione apenas contagens pares e extraia nomes.
  6. setdiff(unique(y,,T),names(z[!z%%2])) remover caracteres com contagem uniforme.
  7. cat(setdiff(unique(y,,T),names(z[!z%%2])),sep="") imprima a saída.
djhurio
fonte
A razão para o seu erro é que el()vem do methodspacote, que embora normalmente seja carregado por padrão, não é do TIO (discutido na minha resposta abaixo)
duckmayr
por que voce esta usando rev(unique(rev(y)))? Não unique(y)funcionaria apenas ? ooohhh espera eu vejo, você quer os caracteres únicos da direita para a esquerda. Nesse caso unique(y,,T)(configuração fromLast=T) será 88 bytes .
Giuseppe
0

Alice , 9 bytes

/X&@
\io/

Experimente online!

Explicação

Basicamente, um porto da resposta de Erik . Além de um pouco de redirecionamento de IP, o código é realmente apenas:

i&Xo@

que faz:

i   Read all input.
&X  Fold symmetric multiset difference over the input.
o   Output the result.
@   Terminate.
Martin Ender
fonte
0

APL (Dyalog) , 16 bytes

{(,⍨~∩)/⍣(≢⍵)⊖⍵}

Experimente online!

Se erros fossem permitidos, isso teria sido 9 bytes:

(,⍨~∩)/∘⊖
Erik, o Outgolfer
fonte
O que você quer dizer com erros?
FrownyFrog
@FrownyFrog A versão de 9 bytes lançaria um DOMAIN ERRORse a string estiver vazia, pois (,⍨~∩)não possui um elemento de identidade predefinido.
Erik o Outgolfer
0

Ruby , 53 bytes

->s{s.reverse.uniq.select{|c|s.count(c)%2>0}.reverse}

Experimente online!

Entrada e saída são uma matriz de caracteres. Chamadas de código de teste .charse.join por conveniência.

Explicação

Usa o fato de que as letras na sequência resultante aparecem um número ímpar de vezes e na ordem da direita para a esquerda.

->s{                # lambda function taking char-array argument
    s.reverse           # reverse the input
    .uniq               # get unique characters
    .select{|c|         # select only those which...
        s.count(c)%2>0      # appear in the input array an odd number of times
    }.reverse           # reverse back and return
}
Justin Mariner
fonte
0

Pitão, 13 bytes

{_xD_Qf%/QT2Q

Recebe entrada como lista de caracteres. Teste!

      f     Q            (f)ilter input (Q)
        /QT              On how many times (/) each character (T) appears in the 
                           input (Q)
       %   2             Only allow odd numbers of occurences (when x % 2 = 1)
 _xD_Q                   Sort (D) descending (the first _) by the location (x) of 
                           the last (the second _) inde(x) of the target character
                           in the input (Q)
{                        Remove duplicates
Steven H.
fonte
0

Röda , 34 bytes

{a=[]a-=_ if[_1 in a]else a+=_1;a}

Experimente online!

Esta é uma tradução direta do pseudocódigo. Trata a entrada e a saída como fluxos de caracteres.

Explicação:

{                    /* Anonymous function                   */
    a=[]             /* initialize a                         */
                     /* For each character _1 in the stream: */
    a-=_ if[_1 in a] /*  Remove it from a if a contains it   */
    else a+=_1;      /*  Otherwise append it to a            */
    a                /* Push characters in a to the stream   */
}
fergusq
fonte
0

Python 3 , 73 bytes

Não é o mais curto, mas eu gosto dessa abordagem.

lambda s:''.join(c*(s.count(c)%2)*(i==s.rfind(c))for i,c in enumerate(s))

Experimente online!

Faz um loop na string, mantendo apenas os caracteres em que:

  • (s.count(c)%2) == 0 - O personagem aparece um número par de vezes.
  • (i==s.rfind(c)) - O índice atual é a última aparição do personagem em questão.
FlipTack
fonte
0

REXX , 102 bytes

a=arg(1)
s=''
do while a>''
  b=right(a,1)
  if countstr(b,a)//2 then s=b||s
  a=changestr(b,a,'')
  end
say s

Experimente online!

Como funciona: Pegue a letra mais à direita, veja se o número de ocorrências é par ou ímpar (que também funciona como um valor verdadeiro) e, se ímpar, adicione-o à string de saída. Em seguida, remova todas as ocorrências da letra da sequência de entrada. Repita até que a entrada se esgote.

idrougge
fonte
0

Java 8, 93 bytes

Um lambda de Stringpara String. Apenas uma implementação do pseudocódigo na questão.

s->{String o="";for(char c:s.toCharArray())o=o.indexOf(c)<0?o+c:o.replace(c+"","");return o;}

Experimente Online

Java 8, 182 bytes

Aqui está outro lambda do mesmo tipo que usa fluxos! Provavelmente é mais eficiente.

s->s.join("",s.chars().mapToObj(c->(char)c+"").filter(c->s.replaceAll("[^"+c+"]","").length()%2>0).distinct().sorted((c,d)->s.lastIndexOf(c)-s.lastIndexOf(d)).toArray(String[]::new))

Experimente Online

Ungolfed

s ->
    s.join(
        "",
        s.chars()
            .mapToObj(c -> (char) c + "")
            .filter(c -> s.replaceAll("[^" + c + "]", "").length() % 2 < 0)
            .distinct()
            .sorted((c, d) -> s.lastIndexOf(c) - s.lastIndexOf(d))
            .toArray(String[]::new)
    )
Jakob
fonte
0

R , 70 bytes

function(s){for(i in utf8ToInt(s))F=c(F[F!=i],i*!i%in%F);intToUtf8(F)}

Experimente online!

Fui encorajado por djhurio a postar esta solução; A resposta de djhurio pode ser encontrada aqui .

Isso usa a mesma idéia que a resposta de duckmayr , mas utiliza uma abordagem numérica convertendo a string em seus pontos de código, em vez de dividi-la em caracteres, e é uma função e não um programa completo para que ela possa retornar a nova string em vez de imprimir em stdout .

function(s) {
 for(i in utf8ToInt(s))           # convert string to codepoints and iterate over it
  F=c(F[F!=i],                    # remove duplicates and append
      i*!i%in%F)                  # 0 if in F, i otherwise
 intToUtf8(F)                     # collapse from codepoints to string
}

Uma observação importante é que ela Fé inicializada como FALSEou 0e utf8ToInt(0)=="", portanto, isso será bem-sucedido para a sequência vazia, além de recolher corretamente os pontos de código.

Giuseppe
fonte
0

PHP, 71 + 1 bytes

while(~$c=$argn[$i++])$s=strstr($s,$c)?strtr($s,[$c=>""]):$s.$c;echo$s;

Execute como pipe -nRou experimente online .

Titus
fonte
0

Python 3.6 , 69 bytes

lambda a:"".join({c:1 for c in a[::-1] if a.count(c)%2}.keys())[::-1]

Experimente online!

A ordem de inserção do dict é preservada no Python 3.6.

user285259
fonte
0

SNOBOL4 (CSNOBOL4) , 97 95 bytes

	S =INPUT
N	S LEN(1) . C REM . S :F(O)
	O C :S(R)
	O =O C :(N)
R	O C =:S(R)F(N)
O	OUTPUT =O
END

Experimente online!

	S =INPUT			;* read input
N	S LEN(1) . C REM . S :F(O)	;* take the first character of S and assign it to C,
					;* assign the remainder to S, and if S has no characters left, goto O
	O C :S(R)			;* if C matches anything in O, goto R, otherwise go to next line
	O =O C :(N)			;* append C to O and goto N
R	O C =:S(R)F(N)			;* as long as C matches O, replace it with ''
					;* (unassigned variables default to the null string)
					;* then goto N once it fails to match
O	OUTPUT =O			;* output the string
END					;* terminate the program
Giuseppe
fonte