Wyzwaniem jest podnieść na duchu naszego moda Alexa A. , który zwykle się myli .
Załóżmy, że masz przyjaciela o imieniu Alex, który potrzebuje pomocy w zakresie podstawowej logiki i matematyki, w szczególności równoważności matematycznej .
Daje ci listę równań formy, w [variable] = [variable]
których a [variable]
jest zawsze pojedynczą wielką literą od A do Z (nie małą literą, nie liczbą ani niczym innym). Na liście jest jedno równanie na linię z wyjątkiem jednej linii, która mówi tylko therefore
.
Wszystkie równania powyżej therefore
są przesłankami , faktami, które uważa się za prawdziwe. Wszystkie równania poniżej therefore
są niezweryfikowanymi twierdzeniami, faktami, które Alex próbuje wywnioskować z przesłanek, i mogą być lub nie być prawdziwe.
Na przykład na tej liście równań A = C
zdarza się, że jedna twierdzenie podsumowujące jest prawdziwe:
A = B
B = C
therefore
A = C
Twoim zadaniem jest powiedzieć Alexowi, czy wszystkie jego propozycje logicznie wynikają z danych przesłanek. Oznacza to, że musisz powiedzieć Alexowi, czy on się myli lub nie ma racji we wnioskach.
Napisz program / funkcję, która pobiera ciąg listy równań zgodnie z opisem i wypisuje / zwraca
Alex is right
jeśli wszystkie wnioski wynikają logicznie z przesłanek i w inny sposób wynikają
Alex is wrong
jeśli jakikolwiek wniosek nie wynika logicznie z przesłanek.
Najkrótszy kod w bajtach wygrywa.
Uważaj na te przypadki:
Zmienna zawsze jest równa sobie. na przykład
B = A therefore A = A X = X
powoduje w
Alex is right
.Nie można zakładać, że zmienne o nieznanych relacjach są równe. na przykład
P = Q therefore E = R
powoduje w
Alex is wrong
.Gdy po tym
therefore
czasie nie ma równań, wnioski są bezsprzecznie prawdziwe . na przykładD = C therefore
i
therefore
oba skutkują
Alex is right
.Jeśli przedtem nie ma równań,
therefore
można wywnioskować tylko samowyrównanie. na przykładtherefore R = R
powoduje
Alex is right
, aletherefore R = W
powoduje w
Alex is wrong
.
Więcej przykładów
Alex ma złe przypadki: (oddzielone pustymi liniami)
A = B
C = D
therefore
A = C
A = L
E = X
A = I
S = W
R = O
N = G
therefore
G = N
L = I
R = O
S = A
X = X
X = E
D = K
D = Q
L = P
O = L
M = O
therefore
K = L
A = B
therefore
B = C
Z = A
S = S
therefore
A = Z
A = A
S = A
A = S
Z = A
Z = A
K = L
K = X
therefore
X = P
L = X
L = P
therefore
A = B
B = C
A = C
therefore
A = A
B = B
C = C
D = D
E = E
F = F
G = G
H = H
I = I
J = J
K = K
T = I
L = L
M = M
N = N
O = O
P = P
Q = Q
R = R
S = S
T = T
U = U
V = V
W = W
X = X
Y = Y
Z = Z
A = B
B = C
C = D
D = E
E = F
F = G
G = H
H = I
I = J
J = K
K = L
L = M
M = N
N = O
O = P
P = O
Q = R
R = S
S = T
T = U
U = V
V = W
W = X
X = Y
Y = Z
therefore
A = Z
therefore
C = D
T = Y
A = Z
P = Q
therefore
E = R
therefore
R = W
Alex ma rację:
H = J
therefore
J = H
K = L
K = X
therefore
L = X
C = B
B = A
therefore
A = B
K = L
K = X
K = P
therefore
L = X
L = P
X = P
A = Y
Y = Q
Q = O
therefore
O = Y
O = A
C = C
therefore
C = C
A = B
B = A
therefore
A = B
B = A
A = B
B = C
C = D
therefore
A = A
A = B
A = C
A = D
B = A
B = B
B = C
B = D
C = A
C = B
C = C
C = D
D = A
D = B
D = C
D = D
therefore
A = A
B = B
C = C
D = D
E = E
F = F
G = G
H = H
I = I
J = J
K = K
L = L
M = M
N = N
O = O
P = P
Q = Q
R = R
S = S
T = T
U = U
V = V
W = W
X = X
Y = Y
Z = Z
D = I
F = H
J = M
therefore
M = J
D = I
H = F
A = B
B = C
C = D
D = E
E = F
F = G
G = H
H = I
I = J
J = K
K = L
L = M
M = N
N = O
O = P
P = Q
Q = R
R = S
S = T
T = U
U = V
V = W
W = X
X = Y
Y = Z
therefore
Z = A
F = R
G = I
W = L
A = B
B = C
therefore
A = C
B = A
therefore
A = A
X = X
P = P
C = G
M = C
therefore
D = C
therefore
therefore
therefore
R = R
Alex is wrong
Weryfikuje wszystkie przypadki testowe.therefore\nTABS < SPACES
->Alex is right
Odpowiedzi:
CJam, 49
Inspirowany roztworem Ruby histocrata. Wypróbuj online
3 bajty zniszczone dzięki jimmy23013 :)
Wyjaśnienie:
Dla każdej przesłanki program zastępuje pierwszą zmienną drugą zmienną w pozostałej części tekstu. Następnie sprawdza, czy jest jakiś wniosek z różnymi zmiennymi.
Stara wersja, 85
Wykorzystuje algorytm znajdowania związku. Wypróbuj online
źródło
"Alex is "qN%S{f{)er}(_el-}h;{)#},"wrong""right"?
.Alex is * wrong * right * ?
Rubin,
8076 + 2 = 78Z flagami wiersza poleceń
p0
uruchomWyjaśnienie:
Wykorzystuje to czystą manipulację ciągiem.
p0
wczytuje pełne dane wejściowe jako pojedynczy ciąg do zmiennej$_
. Następnie wielokrotnie dopasowujemy ten ciąg do wyrażenia regularnego/(.) = (?!\1)(.)/
, które znajduje wszystkie ciągi w postaci „X = Y”, gdzie X i Y nie są tą samą literą, i przypisuje X do 1 $, a Y do 2 $. Po znalezieniu takiego dopasowaniagsub$1,$2
zamienia wszystkie wystąpienia X na Y w ciągu. Sprawdzamy również, czy to dopasowanie wystąpiło przed czy po „zatem” zJeśli miało to miejsce później, jest to nieuzasadnione roszczenie, a Alex się myli. Śledzimy, czy takie zdarzenia wystąpiły przy użyciu
p=
. Zastosowaniep
jako zmiennej śledzącej zapobiega pękaniu rzeczy, jeśli pętla nigdy nie trafi ani razu, ponieważp
zwróci zero, jeśli nigdy nie została przypisana.Od tego postu rozwiązanie CJam jest dłuższe. Dumny, bez wątpienia ulotny moment.
Edycja: Tak, szybko zdetronizowany. Ponadto, aby zakończyć objaśnienie, z
p
flagą końcowa wartość$_
jest wyprowadzana na końcu wykonywania, więc ostatni wiersz jest wyjściem.źródło
String#format
połączenia zarówno połączenia gsub, jak i przypisania do jednego wyrażenia to całkiem fajny pomysł, +1!CJam,
8375686764 bajtówDzięki Dennisowi za zaoszczędzenie 1 bajtu.
Zestaw testowy. Przypadki testowe są zbyt długie, aby można było je połączyć bezpośrednio, więc po prostu skopiuj je z pytania. Zauważ, że jest to dość powolne - zajmuje on minutę lub dwie w tłumaczu online. Możesz zrobić to znacznie szybciej, zmieniając
5*
na,2*
w którym przypadku zakończy się prawie natychmiast i rozwiąże wszystkie przypadki testowe oprócz jednego.Wyjaśnienie
(Nieco przestarzałe.)
Chodzi o to, aby zrobić coś w rodzaju „wypełnienia zalewowego” możliwych równości, a następnie usunąć wszystkie równości, które uzyskaliśmy z listy wniosków. Można wykazać, że potrzebujemy nie więcej niż 5 kroków wypełnienia powodziowego, ponieważ obejmowałyby one odległość (na początkowym wykresie nierówności), ale maksymalną odległość wynosi 25.
25 = 32
źródło
R
183192 bajtyZmodyfikowałem swoją odpowiedź, aby rozwiązać problem wskazany przez użytkownika2357112. Wciąż istnieje bardzo małe prawdopodobieństwo, że zadzwoni do Alexa, gdy ma on rację (co nie zdarza się często, jeśli rozumiem kontekst wyzwania :-). Mam nadzieję, że nie będzie miał nic przeciwko.
Muszę to trochę de-golfować:
Na przykład, jeśli dane wejściowe to
najpierw oceni
setup
:a później
premises
będą uruchamiane 1000 razy w losowej kolejności. Ma to zapewnić („prawie pewność”), że wszystkie równości są propagowane. Na koniec oceni
propositions
:źródło
A = B, B = C, C = A
, wartości po prostu zmieniają się na zawsze. 26 rund oceny to za mało.Haskell, 208 bajtów
Przenoszę pracę do
Data.Equivalence.Persistent
modułu, który udostępnia funkcje do manipulowania klasami równoważności. Pozostaje tylko przeanalizować dane wejściowe i wywoływać funkcje, które czasem mają zbyt długie nazwy dla prawidłowego grania w golfa.Przykład użycia:
źródło
Mathematica, 182
Działa na ciąg znaków, jak na wyzwanie.
źródło
f
jako czystej funkcji, zastępującSimplify[#2,#1]
z#2~Simplify~#
, i zastępowanieStringSplit[s,"\n"]
z#~StringSplit~"<actual newline>"
.q=StringSplit;
a następnie s / StringSplit / q / dla kolejnych 6 bajtów lub tak zapisanych. Ale w końcu obawiam się, że nie jest to dobre wyzwanie dla Mathematiki, mimo że logiczna postać wydawała się idealnie dopasowana.a___
ib___
prawdopodobnie można go zmienić naa__
ib__
, is=Symbol;
.a__
ib__
nie będzie działać, jeśli przesłanki, propozycje lub oba będą pusteSiatkówka, 90 bajtów
Aby uruchomić, umieść następujące 12 wierszy kodu w 12 osobnych plikach (+11 bajtów zliczonych dla każdego pliku poza pierwszym).
<empty>
oznacza pusty plik;\n
oznacza dosłowną nową linię. Alternatywnie, zachowaj\n
s takimi, jakie są, umieść wszystkie linie w jednym pliku i użyj-s
opcji. Upewnij się, że wszystkie pliki używają dosłownych znaków nowej linii, a nie Windows\r\n
, i zwróć uwagę na miejsce na końcu ostatniego wiersza.Jak to działa
Pierwsza zamiana pasuje do pierwszej przesłanki w danych wejściowych, ilekroć lhs przesłanki występuje później w pliku. Zastępuje to późniejsze wystąpienie rhs przesłanki.
+
Modyfikator zapewnia, że wymiana jest powtarzany, aż nie pasuje do żadnego więcej. Tak więc, jeśli pierwszą przesłanką jestA = B
, wszystkie kolejneA
s w pliku są przekształcane wB
s.Druga zamiana usuwa pierwszą przesłankę z danych wejściowych, ponieważ skończyliśmy już teraz. Następnie
)
modyfikator zapętla się z powrotem do pierwszej zamiany i powtarza, dopóki nie nastąpi żadna zmiana w całym przejściu przez pętlę. Dzieje się tak, gdy wszystkie przesłanki zostały zastąpione i usunięte, a dane wejściowe zaczynają się odtherefore
.Trzecie zastąpienie dopasowuje pierwszy wiersz danych wejściowych (który jest
therefore
) lub cokolwiek z formularzaA = A
i usuwa je. Jeśli wszystkie propozycje są obsługiwane przez przesłanki, wszystkie będą pasować do tego formularza, więc to, co pozostanie, powinno składać się wyłącznie z nowych linii. Czwarta zamiana zmienia to naright
. W przeciwnym razie piąta zamiana zmienia wszystko, co pozostało (które nie zawiera,r
ponieważtherefore
zostało usunięte) nawrong
. Wreszcie ostatnia wymiana dodajeAlex is
na początku.źródło
Python 2, 264 bajty
Istnieje już niezwykła odpowiedź na Python 3 autorstwa mbomb007 . Ta odpowiedź rażąco kradnie od tej (w szczególności sztuczka „Alex jest wrriognhgt”).
Ta odpowiedź jest również znacznie dłuższa niż ta ...
W każdym razie, w tej odpowiedzi chodzi o utrzymanie słownika par klucz-wartość, gdzie klucze to 26 wielkich liter, a odpowiadająca im wartość każdego klucza to zestaw liter, które są równoważne kluczowi. (Gdyby wszystkie 26 liter były równoważne, to każdy klucz miałby zestaw 26 liter odpowiadających im wartości.)
(Aby zaoszczędzić bajty, ta odpowiedź miesza spacje i tabulatory , co jest dozwolone w Pythonie 2).
Ten kod jest naprawdę bardzo wydajny, ponieważ słownik jest ograniczony do maksymalnego możliwego rozmiaru (26 na 26, jak opisano powyżej), który nie zależy od liczby wierszy wejściowych.
Teraz, gdy grałem w golfa w tym rozwiązaniu, zdałem sobie sprawę, że mogę zapisać cztery bajty , używając ciągów zamiast zestawów wartości słownika, zastępując je
z
Oczywiście musisz także zastąpić (UWAGA: NIE RÓB TO) trzema instancjami operacji ustawiania unii
|
z konkatenacją łańcuchów+
, ale to nie zmienia długości kodu. Rezultat jest taki, że wszystko powinno nadal działać tak samo, z wyjątkiem tego, że nie eliminuje duplikatów, tak jak robisz to z setami (po prostu będzie dodawać na końcu łańcucha). Brzmi OK - pewnie trochę mniej wydajnie, ale 260 bajtów zamiast 264.Okazuje się, że 260-bajtowa wersja jest tak nieefektywna , że spowodowała to,
MemoryError
gdy ją testowałemTo było dla mnie zaskakujące. Przeanalizujmy 260-bajtową wersję „konkatenacji łańcuchów”!
Oczywiście zaczynałoby się od par klucz-wartość
A:A
iB:B
(plus 24 innych, które nie mają znaczenia). Napiszemy,d[A]
aby oznaczać wartość słownika odpowiadającą kluczowiA
, więc na początku mielibyśmyd[A] = A
. Teraz, biorąc pod uwagę założenieA = B
, zacząłoby się od połączenia wartościd[A]=A
id[B]=B
zdobyciay = AB
. Następnie dwukrotnie zapętliłby ten ciąg:for v in AB: for w in AB:
...Więc po raz pierwszy w pętli mamy
v=A
iw=A
. Zastosowanied[v] += d[w]
id[w] += d[v]
wyniki w następującej sekwencji słowników:Następnie za pomocą
v=A
iw=B
:Następnie
v=B, w=A
:I
v=B, w=B
:Powyższa sekwencja kroków zaimplementowałaby jedną przesłankę
A = B
, z wnioskiem, któryA
jest równy każdej literze w ciąguAAAABBAAAABAAAAB
, aB
równy jest każdej literze wBAAAABAAAABBAAAABAAAABBAAAABAAAABBAAAABAAAAB
.Załóżmy teraz, że kolejna przesłanka jest
A = B
znowu . Najpierw obliczyszy = d[A] + d[B] = AAAABBAAAABAAAABBAAAABAAAABBAAAABAAAABBAAAABAAAABBAAAABAAAAB
.Następnie dwukrotnie zapętlamy ten ciąg:
for v in y: for w in y:
...Tak. Może nie byłoby to bardzo skuteczne wdrożenie.
źródło
ES6, 128 bajtów
Luźno oparty na wersji Ruby.
Szuka jakiejkolwiek nierównouprawnienia przed „zatem” i za każdym razem zastępuje zmienną w całym ciągu (zapisuje to bajty w pętli while).
źródło
C, 240 bajtów
Działa to poprzez łączenie wartości w zestaw drzew, więc wszelkie równoważne wartości prowadzą do tego samego katalogu głównego. Niegolfowane, z jawnymi typami niejawnymi.
180 bajtów
Ta krótsza wersja działa dla wszystkich przypadków z OP, ale w przypadku niektórych innych danych wejściowych niepoprawnie twierdzi, że Alex się myli. Wykorzystuje podobne podejście, ale dla każdej przesłanki po prostu ustawia drugi wpis na bieżącą wartość pierwszego wpisu. Porównując, szuka tylko dokładnych wartości zamiast wyszukiwania drzewa.
Przykładowe dane wejściowe, dla których to się nie udaje:
źródło
05AB1E , 32 bajty
Zainspirowany odpowiedzią CJam @aditsu .
Wypróbuj online lub sprawdź wszystkie przypadki testowe .
Wyjaśnienie:
Zobacz moją wskazówkę 05AB1E (sekcja Jak korzystać ze słownika? ), Aby zrozumieć, dlaczego
…±º€ˆ
jest"alex is "
i„–у©
jest"wrong right"
.źródło
bash + awk + SWI-Prolog , 167 bajtów
Wypróbuj online!
Początkowo była to po prostu odpowiedź Prologa, ale narzędzia, które mogłem znaleźć, aby faktycznie przekształcić format wejściowy w coś użytecznego, były na tyle ograniczone, że zdecydowałem się wykonać tę część w bashu, chociaż nie miałem prawie żadnego doświadczenia robienie czegokolwiek w uderzeniu i nigdy nawet nie dotknęło awk. Skończyło się na tym, że spędziłem wystarczająco dużo godzin, aby opublikować go nawet po tym, jak wyrósł na ten 167-bajtowy, ledwo golfowy potwór.
Zasadniczo program awk pobiera dane wejściowe ze standardowego wejścia, usuwa linię z
therefore
, zastępujeA = B
po nim?=(A,B)
i dołączawrite(\"Alex is right\");write(\"Alex is wrong\"). halt.
. Następniepaste -sd ,
zastępuje każdy nowy wiersz, ale ostatni przecinkiem, przekształcając go w prawidłowe dwa zapytania do powłoki SWI-Prolog, które są następnie uruchamiane, a wydrukowany wynik jest obcinany do jednej liniihead -n1
, co wymaga<(...)
zamiast potoku z przyczyn niezależnych moje zrozumienie. Wszystko po to, aby użyć wbudowanego !źródło