Dwa słowa są izomorfami, jeśli mają ten sam wzór powtarzania liter. Na przykład, zarówno ESTATE
i DUELED
mają wzórabcdca
ESTATE
DUELED
abcdca
ponieważ litery 1 i 6 są takie same, litery 3 i 5 są takie same i nic więcej. Oznacza to również, że słowa są powiązane szyfrem podstawienia, tutaj z dopasowaniem E <-> D, S <-> U, T <-> E, A <-> L
.
Napisz kod, który wymaga dwóch słów i sprawdza, czy są to izomorfy. Wygrywa najmniej bajtów.
Dane wejściowe: dwa niepuste ciągi wielkich liter A..Z
. Jeśli chcesz, możesz wziąć je jako zbiór dwóch ciągów lub jako pojedynczy ciąg z separatorem.
Dane wyjściowe: spójna wartość prawdy dla par, które są izomorfami , i spójna wartość Falsey, jeśli nie są. Ciągi o różnych długościach są poprawnymi danymi wejściowymi, które nigdy nie są izomorfami.
Przypadki testowe:
Prawdziwe:
ESTATE DUELED
DUELED ESTATE
XXX YYY
CBAABC DEFFED
RAMBUNCTIOUSLY THERMODYNAMICS
DISCRIMINATIVE SIMPLIFICATION
Fałszywe:
SEE SAW
ANTS PANTS
BANANA SERENE
BANANA SENSES
AB CC
XXY XYY
ABCBACCBA ABCBACCAB
ABAB CD
Dodaj więcej przypadków testowych, które okażą się przydatne.
Tabela liderów
Oto fragment kodu, który pozwala wygenerować zarówno zwykłą tabelę wyników, jak i przegląd zwycięzców według języka.
Aby upewnić się, że twoja odpowiedź się pojawi, zacznij od nagłówka, korzystając z następującego szablonu Markdown:
# Language Name, N bytes
gdzie N
jest rozmiar twojego zgłoszenia. Jeśli poprawić swój wynik, to może zachować stare porachunki w nagłówku, uderzając je przez. Na przykład:
# Ruby, <s>104</s> <s>101</s> 96 bytes
ABAB CD
(dla podejść typu zip)Odpowiedzi:
J, 4 bajty
Stosowanie
Wyjaśnienie
=
z 1 argumentem tworzy tabelę równości porównującą elementy wejścia i jego wierzchołka.-:
z 2 argumentami sprawdza ich równość (jak==
zwykle robi). Działa to również dla matryc o różnych rozmiarach (lub nawet różnych typach).f&g
stosuje g do obu danych wejściowych oddzielnie, a następnie stosuje f do obu wyników razem takx f&g y == f(g(x), g(y))
.W naszym przypadku porównujemy dwie tabele równości.
Wypróbuj online tutaj.
źródło
&
, najbliższą rzeczą, którą możesz zrobić w K, byłaby prawdopodobnie~/{x=/:x}'
dłuższa.=
będzie miała inne zastosowanie niż do zliczania wystąpień.K, 5 bajtów
To zachwycająco eleganckie rozwiązanie w K!
Operator „grupowy” (monadyczny
=
) tworzy dokładnie taki podpis, jaki chcemy w przypadku izomorfizmu słów; zbieranie wektorów indeksów każdego elementu wektora, z grupami uporządkowanymi według wyglądu:Biorąc parę ciągów za wektor, musimy po prostu zastosować grupę do każdego elementu (
=:'
), a następnie zmniejszyć za pomocą „match” (~
), operatora głębokiej równości:źródło
Python 2, 41 bajtów
źródło
CJam, 9 bajtów
Drukuje,
1
jeśli słowa są izomorfami, a0
jeśli nie są.Wypróbuj online w interpretatorze CJam .
Jak to działa
źródło
JavaScript, ES7,
62 55 54 5251 bajtówLogika jest prosta. Po prostu przekształcam oba dane wejściowe na odpowiadające im wartości indeksu znaków, przekształcam tablicę w ciąg znaków i porównuję.
Wypróbuj powyższy kod, korzystając z fragmentu poniżej.
Pokaż fragment kodu
2 bajty zapisane dzięki @ edc65
źródło
+0
zamiast+""
?Bash + coreutils, 38
Zauważ, że używamy tutaj zwykłej idei powłoki - prawda / fałsz - zero oznacza SUKCES lub PRAWDA, a niezerowa oznacza błąd lub FAŁSZ:
źródło
Haskell,
3329EDYTOWAĆ:
jest o wiele za późno, ale zauważyłem tę poprawę za pomocą aplikacji, które zostały dodane w celu preludium dopiero w marcu 2015 roku.
Stara wersja:
funkcja sprawdzania to
(%)
działa to poprzez generowanie dla każdego łańcucha „rekordu równości”: dla każdego z dwóch wskaźników ij rejestruje, czy mają one równe znaki. rekord jest uporządkowany w taki sposób, że rekord dla dwóch indeksów i, j jest zawsze w tym samym miejscu *, a zatem sprawdzenie równości rekordów zwróci, czy łańcuchy będą miały ten sam wzorzec.
na przykład zapis równości „ABC” wynosi
[1,0,0,0,1,0,0,0,1]
(1 dla prawdy, 0 dla fałszu) - tamTrue
gdzie jakikolwiek indeks jest porównywany z samym sobą. gdziekolwiek indziej jest fałszem. (pomijanie tych kontroli może być bardziej wydajne, ale trudniejsze pod względem golfowym)* jeśli struny są tej samej długości. w przeciwnym razie zwraca false tylko dlatego, że rekordy mają różną długość
źródło
Haskell,
4541 bajtówZwraca
True
lubFalse
np."ESTATE" ! "DUELED"
->True
.Używa metody map-char-to-first-index, jak widać w wielu innych odpowiedziach. Przydają się listy skojarzeń, ponieważ wcześniejsze wpisy są atutem.
"aba"
staje się[(a,1),(b,2),(a,3)]
tam, gdzielookup
zawsze pobieraa
->1
.Edycja: @ Mauris znalazł 4 bajty do zapisania.
źródło
(flip lookup$zip l[1..])
przez(`lookup`zip l[1..])
.Brainfuck,
169168162144140131130Kompatybilny z bff Alexa Pankratova (interpreter pieprzenia mózgu używany na SPOJ i ideone) oraz BFI Thomasa Corta (używany na Anarchy Golf).
Oczekiwanym wejściem są dwa ciągi znaków oddzielone tabulatorem, bez nowego wiersza po drugim ciągu. Dane wyjściowe dotyczą
1
izomorfów i0
nieizomorfów, co jest wygodne do wizualnego sprawdzania wyników, chociaż nie jest to najkrótsza opcja. ( Aktualizacja: krótsza wersja z wyjściem\x01
i\x00
jako wyjście oraz\x00
jako separator u dołu odpowiedzi).Demonstracja na ideonie.
Ten problem okazuje się bardzo miły dla pieprzenia mózgu.
Podstawową ideą indeksowania jest cofanie się od końca bieżącego prefiksu łańcucha. Jeśli znak nie występował wcześniej, możemy wziąć długość prefiksu łańcucha. Na przykład:
Indeksowanie w kodzie jest nieco inne, ale wykorzystuje tę samą zasadę.
Układ pamięci jest w blokach po 5:
c
oznacza znak,i
indeks ip
poprzedni (indeks). Podczas przetwarzania pierwszego ciągu wszystkiep
szczeliny mają wartość zero. Komórka po lewej stroniec
służy do przechowywania kopii bieżącego znaku, dla którego próbujemy znaleźć indeks. Komórka po lewej stronie prądui
służy do-1
łatwej nawigacji wskaźnikiem.Istnieje wiele warunków, które należy dokładnie rozważyć. Na koniec sprawdzamy izomorfy, porównując
(i,p)
pary, i docieramy do klastra zerowych komórek na lewo od lewej skrajnej(i,p)
pary tylko wtedy, gdy ciągi są izomorfami. Oto skomentowana wersja kodu, aby ułatwić śledzenie:Aktualizacja:
Oto wersja, która drukuje
\x01
dla izomorfów i\x00
dla nie-izomorfów. Jest to prawdopodobnie dokładniejsza interpretacja Truthy i Falsey dla pieprzenia mózgu, ze względu na sposób[
i]
pracę. Jedyna różnica jest na samym końcu.Dodatkowe: Teraz używa
\x00
jako separatora, aby zapisać 10 bajtów.źródło
JavaScript (ES6), 62
Korzystanie z funkcji Aux,
h
która mapuje każde słowo na tablicę zawierającą pozycję każdej litery w słowie, na przykład: PASS -> [1,2,3,3]. Zwraca wartość true, jeślih
zastosowana funkcja dwóch słów daje ten sam wynik.źródło
R, 78
Gra w golfa:
źródło
all( (g=...)(x)==g(y))
jest krótszy niżidentical
...Rubinowy, 83 bajty
Jest to funkcja,
f
która pobiera dwa argumenty i zwracatrue
lubfalse
.Wyjaśnienie:
źródło
t=->x{z=?`;x.chars.to_a.uniq.map{|c|x.gsub!(c,z.succ!)};x};f=->a,b{t[a]==t[b]}
i możesz sprowadzić go do 68, jeśli użyjesz skrótu do uzyskania zamiany:t=->x{h={};i=9;x.gsub!(/./){|c|h[c]||h[c]=i+=1}};f=->a,b{t[a]==t[b]}
Java, 107
Mapuje każdą postać
s
it
jej lokalizację oraz sprawdza równość.Rozszerzony:
źródło
Python 3, 85 bajtów
źródło
g
jest główną funkcją,f
jest pomocnikiem. Jest to mylące wybór zmiennejg
wewnątrzf
, ale jest to niezwiązane zmienna związana .. Theg=
jest obowiązkowe zgodnie z orzeczeniem umożliwiający funkcje Anon, co oszczędza dwa znaki.Pyth, 9 bajtów
Pobiera dane w następującej formie:
Jeśli nie jest to możliwe, następujący kod ma 10 bajtów:
i używa tego formularza wejściowego:
Używa indeksu char w reprezentacji ciągu.
źródło
F
działa składanie. Co jest<binary>F
?<binary>F<seq>
jest<binary>
złożony<seq>
. Jest to równoważne rozproszeniu<binary>
między każdą parą elementów<seq>
. Zatem<binary>F
w sekwencji 2-elementowej po prostu stosuje funkcję do sekwencji, równoważną.*
w Pyth lub*
Python.Q
był ukryty w Pyth?Matlab, 50 bajtów
Funkcja jest zdefiniowana jako anonimowa w celu zaoszczędzenia miejsca.
Przykład:
źródło
Oktawa, 26 bajtów
źródło
==
jest równością elementów macierzy, a ponieważs
is'
są różnych rozmiarów, „nadawanie” oktawy automatycznie próbuje uzyskać matryce o tym samym rozmiarze do działania - co w tym przypadku oznacza powtarzanie wierszas
i kolumnys'
05AB1E , 6 bajtów
Wypróbuj online!
Pobiera dane wejściowe jako listę:
['ESTATE', 'DUELED']
Objaśnienia:
źródło
APL (Dyalog) ,
54 bajtów-1 dzięki podpowiedzi ngn.
Anonimowa funkcja ukrytego przedrostka, która przyjmuje jako argument listę dwóch ciągów.
Wypróbuj online!
To jest produkt wewnętrzny, ale zamiast zwykłego
+
i×
używa≡
identyczność.
i⍳
ɩ ndex (pierwsze wystąpienie każdego elementu)⍨
z całą dwuelementową listą słów użytych jako oba argumentyJeśli wywołamy te słowa
A
iB
, możemy wyprowadzić poprzednie rozwiązanie w następujący sposób:≡.⍳⍨ A B
A B ≡.⍳ A B
(A⍳A) ≡ (B⍳B)
(⍳⍨A) ≡ (⍳⍨B)
≡/ ⍳⍨¨ A B
Poprzednie rozwiązanie
Anonimowa funkcja ukrytego przedrostka, która przyjmuje jako argument listę dwóch ciągów.
Wypróbuj online!
≡
identyczność/
przez⍳
ɩ ndex (pierwsze wystąpienie każdego elementu ...)⍨
selfie (… samo w sobie)¨
każdegoźródło
Mathematica, 46 bajtów
źródło
Rubinowy, 50 bajtów
30 bajtów krótszego kodu ruby. Napisane przed przyjrzeniem się rozwiązaniom, sprawdzają dla każdego znaku obu ciągów, czy indeks pierwszego wystąpienia tego znaku pasuje; to znaczy. przekształca ciąg znaków w znormalizowaną formę
01121
itp. i porównuje je.Testowanie przypadków na ideone Jako dodatkowy bonus łamie to wyróżnianie kodu ideone.
źródło
Łuska , 5 bajtów
Wypróbuj online!
Wyjaśnienie
źródło
PCRE, 84 bajty
Temat powinien składać się z dwóch słów oddzielonych spacją, tak jak w OP. Oto pobieżne wyjaśnienie:
źródło
Ruby, 31 bajtów
Proc, który pobiera tablicę ciągów znaków i sprawdza, czy są one względem siebie izomorficzne.
tr s,'a-z'
z tymi argumentami normalizuje ciągs
, zastępując każdą literę n-tą literą w alfabecie, gdzien
jest największym indeksem, z którym ta litera pojawia się w ciągu. Na przykładestate
staje sięfbedef
, podobnie jakdueled
.źródło
Kobra, 72 bajty
źródło
AB CC
przypadek fałszywy?JavaScript (ES5),
14298Całkiem spory, ale jeszcze nie widziałem wersji 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)
Po prostu zastępuje każde wystąpienie pierwszej litery jego odwrotną wartością indeksu. Powtarza to dla każdej postaci.
Robi to samo dla obu wejść i porównuje wygenerowany wzór.
Porównanie jest dość brzydkie, ale nie chcę używać tablicy do przechowywania i porównywania.
źródło
;l=c
dofor(l=j=2;j--;
zapisanego bajtu?Perl, 38 bajtów
Uruchom jako
perl -E '($_,$a)=@ARGV;eval"y/$_/$a/";say$_~~$a' RAMBUNCTIOUSLY THERMODYNAMICS
Drukuje 1 jeśli prawda, nic jeśli fałsz.
źródło
Common Lisp, 76 bajtów
Wypróbuj online!
źródło
C ++,
213196162 bajtów-51 bajtów dzięki Zacharýmu
Aby wywołać lambda, musisz przekazać 2 argumenty
std::string
typu danychKod do przetestowania:
dla kodu testującego, w tym
iostream
istring
pliku nagłówkowego jest wymaganyźródło
e
jako argumentfind
, tak, to działaJavaScript (ES6),
525150 bajtówTa wersja nie korzysta ze zrozumienia tablic i pobiera dane wejściowe przy użyciu składni curry.
Pokaż fragment kodu
źródło