Duas palavras são isomorfos se tiverem o mesmo padrão de repetições de letras. Por exemplo, ambos ESTATE
e DUELED
têm padrãoabcdca
ESTATE
DUELED
abcdca
porque as letras 1 e 6 são iguais, as letras 3 e 5 são iguais e nada mais. Isso também significa que as palavras são relacionadas por uma cifra de substituição, aqui com a correspondência E <-> D, S <-> U, T <-> E, A <-> L
.
Escreva um código que use duas palavras e verifique se são isomorfos. Menos bytes ganha.
Entrada: duas cadeias não vazias de letras maiúsculas A..Z
. Se desejar, você pode levá-las como uma coleção de duas cadeias ou como uma única cadeia com um separador.
Saída: Um valor Truthy consistente para pares que são isomorfos e um valor Falsey consistente, se não forem. Strings de diferentes comprimentos são entradas válidas que nunca são isomorfas.
Casos de teste:
Verdadeiro:
ESTATE DUELED
DUELED ESTATE
XXX YYY
CBAABC DEFFED
RAMBUNCTIOUSLY THERMODYNAMICS
DISCRIMINATIVE SIMPLIFICATION
Falso:
SEE SAW
ANTS PANTS
BANANA SERENE
BANANA SENSES
AB CC
XXY XYY
ABCBACCBA ABCBACCAB
ABAB CD
Sinta-se à vontade para adicionar mais casos de teste que achar úteis.
Entre os melhores
Aqui está um snippet de pilha para gerar uma classificação regular e uma visão geral dos vencedores por idioma.
Para garantir que sua resposta seja exibida, inicie-a com um título, usando o seguinte modelo de remarcação:
# Language Name, N bytes
onde N
está o tamanho do seu envio. Se você melhorar sua pontuação, poderá manter as pontuações antigas no título, identificando-as. Por exemplo:
# Ruby, <s>104</s> <s>101</s> 96 bytes
ABAB CD
(para abordagens semelhantes a zip)Respostas:
J, 4 bytes
Uso
Explicação
=
com 1 argumento cria uma tabela de igualdade comparando os elementos da entrada e seu nub.-:
com 2 argumentos verifica sua igualdade (como==
geralmente faz). Isso funciona para matrizes de tamanhos diferentes (ou mesmo tipos diferentes) também.f&g
aplica g às duas entradas separadamente e, em seguida, aplica f aos dois resultados juntosx f&g y == f(g(x), g(y))
.Portanto, no nosso caso, comparamos as duas tabelas de igualdade.
Experimente online aqui.
fonte
&
, a coisa mais próxima que você poderia fazer em K provavelmente seria~/{x=/:x}'
, o que é um pouco mais longo.=
tivesse outro uso além da contagem de ocorrências.K, 5 bytes
Isso tem uma solução deliciosamente elegante no K!
O operador "group" (monádico
=
) cria precisamente a assinatura que queremos para o isomorfismo da palavra; reunindo vetores dos índices de cada elemento de um vetor, com os grupos ordenados por aparência:Tomando um par de strings como vetor, precisamos aplicar o grupo a cada elemento (
=:'
) e reduzir com "match" (~
), o operador de igualdade profunda:fonte
Python 2, 41 bytes
fonte
CJam, 9 bytes
Imprime
1
se as palavras são isomorfas e0
se não são.Experimente online no intérprete CJam .
Como funciona
fonte
JavaScript, ES7,
62 55 54 5251 bytesA lógica é simples. Simplesmente converto ambas as entradas em seus valores de índice de caracteres correspondentes, converto essa matriz em string e comparo.
Experimente o código acima usando o snippet abaixo.
Mostrar snippet de código
2 bytes salvos graças a @ edc65
fonte
+0
em vez de+""
?Bash + coreutils, 38
Observe que estamos usando a ideia usual de shell de verdade / falsidade aqui - zero significa SUCESSO ou VERDADEIRO e diferente de zero significa erro ou FALSO:
fonte
Haskell,
3329EDITAR:
é tarde demais, mas eu encontrei essa melhoria usando aplicativos, que foram adicionados ao prelúdio apenas em março de 2015.
Versão antiga:
a função de verificação é
(%)
isso funciona gerando para cada string seu "registro de igualdade": para cada dois índices ij, ele registra se eles têm caracteres iguais. o registro é ordenado para que o registro para dois índices i, j esteja sempre no mesmo local * e, portanto, a verificação da igualdade dos registros retornaria se as seqüências tinham ou não o mesmo padrão.
por exemplo, o registro de igualdade de "ABC" é
[1,0,0,0,1,0,0,0,1]
(1 para verdadeiro, 0 para falso) - é aíTrue
que qualquer índice é comparado a si mesmo. em qualquer outro lugar é falso. (pular essas verificações pode ser mais eficiente, mas é mais difícil em termos de golfe)* se as cordas tiverem o mesmo comprimento. caso contrário, ele retornará false apenas porque os registros são de comprimentos diferentes
fonte
Haskell,
4541 bytesRetorna
True
ouFalse
, por exemplo,"ESTATE" ! "DUELED"
->True
.Usa o método map-char-to-first-index, como visto em muitas outras respostas. As listas de associação são úteis, porque as entradas anteriores superam.
"aba"
torna-se[(a,1),(b,2),(a,3)]
ondelookup
sempre buscaa
->1
.Edit: @Mauris encontrou 4 bytes para salvar.
fonte
(flip lookup$zip l[1..])
por(`lookup`zip l[1..])
.Brainfuck,
169168162144140131130Compatível com Alex Pankratov bff (intérprete brainfuck usado em SPOJ e ideone) e de Thomas Cort BFI (usado em Anarchy Golf).
A entrada esperada são duas cadeias separadas por uma guia, sem nova linha após a segunda cadeia. A saída é
1
para isomorfos e0
não isomorfos, o que é conveniente para verificar os resultados visualmente, embora não seja a opção mais curta. ( Atualização: versão mais curta com\x01
e\x00
como saída e\x00
como separador na parte inferior da resposta.)Demonstração em ideone.
Esse problema acaba sendo muito bom para o cérebro.
A idéia básica com a indexação é voltar ao final do prefixo de cadeia atual. Se o caractere não ocorreu anteriormente, podemos obter o comprimento do prefixo da string. Por exemplo:
A indexação no código é realmente um pouco diferente, mas usa o mesmo princípio.
O layout da memória está em blocos de 5:
c
significa caractere,i
índice ep
anterior (índice). Quando a primeira cadeia está sendo processada, todos osp
slots são zero. A célula à esquerda dec
é usada para armazenar uma cópia do caractere atual do qual estamos tentando encontrar o índice. A célula à esquerda da correntei
é usada para reter um-1
para facilitar a navegação do ponteiro.Existem muitas condições que precisam ser consideradas com cuidado. No final, verificamos isomorfos comparando os
(i,p)
pares e alcançamos o cluster de zero células à esquerda do(i,p)
par mais à esquerda se, e somente se, as cadeias de caracteres são isomorfos. Aqui está uma versão comentada do código para facilitar o acompanhamento:Atualizar:
Aqui está uma versão que imprime
\x01
para isomorfos e\x00
não isomorfos. Esta é sem dúvida uma interpretação mais precisa de Truthy e Falsey para o cérebro, por causa da maneira[
e do]
trabalho. A única diferença está no final.Adicional: Agora, use
\x00
como um separador para salvar 10 bytes.fonte
JavaScript (ES6), 62
Usando uma função aux
h
que mapeia cada palavra para uma matriz que contém a posição de cada letra na palavra, por exemplo: PASS -> [1,2,3,3]. Retorne true se a funçãoh
aplicada as duas palavras der o mesmo resultado.fonte
R, 78
De-golfe:
fonte
all( (g=...)(x)==g(y))
é mais curto do queidentical
...Ruby, 83 bytes
É uma função
f
que recebe dois argumentos e retornatrue
oufalse
.Explicação:
fonte
t=->x{z=?`;x.chars.to_a.uniq.map{|c|x.gsub!(c,z.succ!)};x};f=->a,b{t[a]==t[b]}
e você pode obtê-lo para baixo para 68 se você usar um hash para obter a substituição:t=->x{h={};i=9;x.gsub!(/./){|c|h[c]||h[c]=i+=1}};f=->a,b{t[a]==t[b]}
Java, 107
Mapeia cada caractere de
s
et
para seu local e verifica a igualdade.Expandido:
fonte
Python 3, 85 bytes
fonte
g
é a principal função,f
é auxiliar. Há uma opção confusa de variávelg
dentrof
, mas é uma variável vinculada não relacionada. Ag=
é opcional conforme a regra que permite funções anon, o que salva dois caracteres.Pitão, 9 bytes
Recebe entrada da seguinte forma:
Se isso não for aceitável, o código a seguir é 10 bytes:
e usa este formulário de entrada:
Usa o índice de char na representação de string.
fonte
F
funciona. O que é<binary>F
?<binary>F<seq>
está<binary>
dobrado<seq>
. É equivalente a intercalar<binary>
entre cada par de elementos de<seq>
. Assim,<binary>F
em uma sequência de 2 elementos, simplesmente se aplica a função à sequência, equivalente a.*
em Pyth ou*
em Python.Q
trilha estava implícita em Pyth?Matlab, 50 bytes
A função é definida como anônima para economizar espaço.
Exemplo:
fonte
Oitava, 26 bytes
fonte
==
é a matriz igualdade elemento-wise, e desdes
es'
são de tamanhos diferentes, "broadcasting" da oitava automaticamente tenta obter matrizes de mesmo tamanho para operar - que neste caso significa repetir a linhas
e colunas'
05AB1E , 6 bytes
Experimente online!
Toma entrada como uma lista:
['ESTATE', 'DUELED']
Explicações:
fonte
APL (Dyalog) ,
54 bytes-1 graças à dica de ngn.
Função de prefixo tácito anônimo que usa uma lista de duas seqüências de caracteres como argumento.
Experimente Online!
Este é um produto interno, mas em vez do usual
+
e×
usa≡
identidade.
e⍳
o ndex (a primeira ocorrência de cada elemento)⍨
com toda a lista de dois elementos de palavras usadas como ambos os argumentosSe chamarmos as palavras
A
eB
, podemos derivar a solução anterior da seguinte maneira:≡.⍳⍨ A B
A B ≡.⍳ A B
(A⍳A) ≡ (B⍳B)
(⍳⍨A) ≡ (⍳⍨B)
≡/ ⍳⍨¨ A B
Solução anterior
Função de prefixo tácito anônimo que usa uma lista de duas seqüências de caracteres como argumento.
Experimente online!
≡
identidade/
através⍳
o índice (a primeira ocorrência de cada elemento…)⍨
selfie (… em si)¨
De cadafonte
Mathematica, 46 bytes
fonte
Ruby, 50 bytes
Código ruby 30 bytes mais curto. Escrito antes de dar uma olhada nas soluções, verifica cada caractere de ambas as seqüências se o índice da primeira ocorrência desse caractere corresponde; ie transforma uma string em sua forma normalizada
01121
etc e as compara.Casos de teste no ideone Como um bônus adicional, isso quebra o destaque do código do ideone.
fonte
Casca , 5 bytes
Experimente online!
Explicação
fonte
PCRE, 84 bytes
O assunto deve ter duas palavras separadas por espaço, como no OP. Aqui está uma explicação superficial:
fonte
Ruby, 31 bytes
Um Proc que pega uma matriz de strings e verifica se alguma é isomórfica entre si.
tr s,'a-z'
com esses argumentos normaliza uma sequências
substituindo cada letra pela enésima letra do alfabeto, onden
é o maior índice com o qual essa letra aparece na sequência. Por exemplo,estate
torna-sefbedef
, como fazdueled
.fonte
Cobra, 72 bytes
fonte
AB CC
caso de teste False?JavaScript (ES5),
14298Bastante grande, mas ainda não vi uma versão ES5.
for(l=j=2;j--;){c=prompt();for(i=c.length;i--;)c=c.replace(RegExp(c[i],"g"),i);b=l==c;l=c}alert(b)
Simplesmente substitui todas as ocorrências da primeira letra pelo seu valor de índice reverso. Repete isso para todos os caracteres.
Ele faz o mesmo para as duas entradas e compara o padrão gerado.
A comparação é bastante feia, mas não quero usar uma matriz para armazenar e compará-la.
fonte
;l=c
parafor(l=j=2;j--;
e salvar um byte?Perl, 38 bytes
Correr como
perl -E '($_,$a)=@ARGV;eval"y/$_/$a/";say$_~~$a' RAMBUNCTIOUSLY THERMODYNAMICS
Imprime 1 se verdadeiro, nada se falso.
fonte
Lisp comum, 76 bytes
Experimente online!
fonte
C ++,
213196162 bytes-51 bytes graças a Zacharý
Para chamar o lambda, você precisa passar 2 argumentos que são do
std::string
tipo dadosCódigo a testar:
para o código que testa, incluindo
iostream
estring
arquivo de cabeçalho é necessáriofonte
e
como argumento defind
, sim, ele funcionaJavaScript (ES6),
525150 bytesEsta versão não usa compreensão de array e recebe entradas usando a sintaxe de currying.
Mostrar snippet de código
fonte