Tantangan ini adalah untuk mengangkat semangat mod kami Alex A. , yang biasanya salah .
Misalkan Anda memiliki teman bernama Alex yang membutuhkan bantuan dengan logika dan matematika dasar, khususnya kesetaraan matematika .
Dia memberi Anda daftar persamaan bentuk di [variable] = [variable]
mana a[variable]
selalu huruf besar tunggal A sampai Z (bukan huruf kecil, bukan angka, atau apa pun). Ada satu persamaan per baris dalam daftar kecuali untuk satu baris yang hanya mengatakan therefore
.
Semua persamaan di atas therefore
adalah premis , fakta yang dianggap benar. Semua persamaan di bawah ini therefore
adalah proposisi yang tidak diverifikasi, fakta yang berusaha disimpulkan Alex dari premis-premisnya, dan itu mungkin benar atau tidak benar.
Misalnya, dalam daftar persamaan ini proposisi kesimpulan tunggal A = C
ternyata benar:
A = B
B = C
therefore
A = C
Adalah tugas Anda untuk memberi tahu Alex apakah semua proposisinya secara logis mengikuti dari tempat yang diberikan. Artinya, Anda perlu memberi tahu Alex apakah dia salah atau benar dalam kesimpulannya.
Tulis program / fungsi yang mengambil string dari daftar persamaan seperti yang dijelaskan dan dicetak / dikembalikan
Alex is right
jika semua kesimpulan mengikuti secara logis dari tempat, dan jika tidak, output
Alex is wrong
jika ada kesimpulan tidak secara logis mengikuti dari tempat.
Kode terpendek dalam byte menang.
Pastikan untuk mewaspadai kasus-kasus ini:
Variabel selalu sama dengan diri mereka sendiri. misalnya
B = A therefore A = A X = X
hasil dalam
Alex is right
.Variabel dengan hubungan yang tidak diketahui tidak dapat dianggap sama. misalnya
P = Q therefore E = R
hasil dalam
Alex is wrong
.Ketika tidak ada persamaan setelah itu
therefore
maka kesimpulannya benar . misalnyaD = C therefore
dan
therefore
keduanya menghasilkan
Alex is right
.Ketika tidak ada persamaan sebelum
therefore
maka hanya kesetaraan diri dapat disimpulkan. misalnyatherefore R = R
menghasilkan
Alex is right
, tetapitherefore R = W
hasil dalam
Alex is wrong
.
Lebih banyak contoh
Kasus Alex salah: (dipisahkan oleh garis kosong)
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 adalah kasus yang benar:
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
Memverifikasi semua kasus uji.therefore\nTABS < SPACES
->Alex is right
Jawaban:
CJam, 49
Terinspirasi dari solusi Ruby histocrat. Cobalah secara online
3 byte terhapus berkat jimmy23013 :)
Penjelasan:
Untuk setiap premis, program mengganti variabel pertama dengan variabel ke-2 di seluruh teks. Kemudian memeriksa apakah ada kesimpulan dengan variabel yang berbeda.
Versi lama, 85
Ini menggunakan algoritma union-find. Cobalah online
sumber
"Alex is "qN%S{f{)er}(_el-}h;{)#},"wrong""right"?
.Alex is * wrong * right * ?
Ruby,
8076 + 2 = 78Dengan bendera baris perintah
p0
, jalankanPenjelasan:
Ini menggunakan manipulasi string murni.
p0
membaca input penuh sebagai string tunggal ke dalam variabel$_
. Kemudian, kami berulang kali mencocokkan string itu dengan ekspresi reguler/(.) = (?!\1)(.)/
, yang menemukan semua string dari bentuk "X = Y" di mana X dan Y bukan huruf yang sama, dan menetapkan X ke $ 1 dan Y ke $ 2. Ketika kecocokan seperti itu ditemukan,gsub$1,$2
ganti semua instance X dengan Y dalam string. Kami juga memeriksa apakah kecocokan ini terjadi sebelum atau setelah "oleh karena itu" denganJika itu terjadi setelah itu, itu adalah klaim yang tidak dapat dibenarkan dan Alex salah. Kami melacak apakah kejadian seperti itu terjadi saat menggunakan
p=
. Penggunaanp
sebagai variabel pelacakan mencegah hal-hal dari kerusakan jika loop tidak pernah menyentuh sekali pun, sejak itup
akan mengembalikan nol jika tidak pernah ditugaskan.Pada posting ini, solusi CJam lebih panjang. Sebuah momen singkat yang membanggakan, jika tidak diragukan.
Sunting: Yup, cepat dicopot. Juga, untuk menyelesaikan penjelasan, dengan
p
flag nilai akhir dari$_
output di akhir eksekusi, jadi baris terakhir adalah output.sumber
String#format
untuk mendapatkan panggilan gsub dan penugasan menjadi satu ekspresi adalah ide yang cukup rapi, +1!CJam,
8375686764 byteTerima kasih kepada Dennis untuk menghemat 1 byte.
Suite uji. Kasing uji terlalu panjang untuk permalink, jadi cukup salin dari pertanyaan. Perhatikan bahwa ini cukup lambat - dibutuhkan satu atau dua menit dalam juru bahasa online. Anda dapat membuatnya lebih cepat dengan mengubah
5*
ke2*
dalam hal ini akan menyelesaikan hampir seketika dan memecahkan semua kecuali satu kasus uji.Penjelasan
(Sedikit ketinggalan jaman.)
Idenya adalah untuk melakukan semacam "mengisi banjir" dari persamaan yang mungkin dan kemudian menghapus semua persamaan yang kami dapatkan dari daftar kesimpulan. Dapat ditunjukkan bahwa kita membutuhkan tidak lebih dari 5 langkah dari pengisian banjir, karena itu akan mencakup jarak (dalam grafik awal ketidaksetaraan) tetapi jarak maksimum adalah 25.
25 = 32
sumber
R,
183192 byteSaya telah memodifikasi jawaban saya untuk mengatasi batasan yang ditunjukkan oleh user2357112. Masih ada kemungkinan yang sangat kecil untuk memanggil Alex ketika dia ternyata benar (yang sepertinya tidak terlalu sering terjadi jika saya memahami konteks tantangannya :-). Saya harap dia tidak keberatan.
Saya perlu sedikit menghilangkan golf:
Misalnya, jika inputnya adalah
pertama-tama akan mengevaluasi
setup
:lalu
premises
akan dijalankan masing-masing 1.000 kali dalam urutan acak. Ini untuk memastikan ("hampir pasti") bahwa semua persamaan disebarkan. Akhirnya, itu akan mengevaluasi
propositions
:sumber
A = B, B = C, C = A
, nilainya hanya berputar-putar selamanya. 26 putaran evaluasi tidak cukup.Haskell, 208 byte
Saya menurunkan pekerjaan ke
Data.Equivalence.Persistent
modul, yang menyediakan fungsi untuk memanipulasi kelas kesetaraan. Yang tersisa untuk dilakukan adalah mem-parsing fungsi input dan panggilan yang terkadang memiliki nama terlalu panjang untuk bermain golf yang tepat.Contoh penggunaan:
sumber
Mathematica, 182
Bekerja pada input string, sesuai tantangan.
sumber
f
sebagai fungsi murni, menggantiSimplify[#2,#1]
dengan#2~Simplify~#
, dan menggantiStringSplit[s,"\n"]
dengan#~StringSplit~"<actual newline>"
.q=StringSplit;
dan kemudian s / StringSplit / q / selama 6 byte atau lebih disimpan. Tetapi pada akhirnya, ini bukan tantangan yang bagus untuk Mathematica, saya takut, meskipun karakter logika tampak pas.a___
danb___
mungkin bisa diubah menjadia__
danb__
, dans=Symbol;
.a__
danb__
tidak akan berfungsi jika bangunan, proposisi atau keduanya kosongRetina, 90 byte
Untuk menjalankan, letakkan 12 baris kode berikut dalam 12 file terpisah (+11 byte dihitung untuk setiap file di luar yang pertama).
<empty>
menunjuk file kosong;\n
menunjuk baris baru literal. Sebagai alternatif, pertahankan\n
s apa adanya, letakkan semua baris dalam satu file, dan gunakan-s
opsi. Pastikan bahwa semua file menggunakan baris baru literal, bukan Windows\r\n
, dan perhatikan ruang di akhir baris terakhir.Bagaimana itu bekerja
Penggantian pertama cocok dengan premis pertama di input, setiap kali premis terjadi kemudian dalam file. Ini menggantikan kejadian kemudian dengan rhs dari premis. The
+
Memastikan pengubah bahwa penggantian ini diulang sampai tidak cocok lagi. Dengan demikian, jika premis pertama adalahA = B
, semuaA
s berikutnya dalam file dapat ditransmisikan menjadiB
s.Penggantian kedua menghapus premis pertama dari input, karena kita sudah selesai dengan itu sekarang. Lalu
)
pengubah loop kembali ke penggantian pertama, dan ulangi sampai tidak ada perubahan secara keseluruhan melewati loop. Ini terjadi ketika semua tempat telah diganti dan dihapus, dan input dimulai dengantherefore
.Penggantian ketiga cocok dengan baris input pertama (yaitu
therefore
) atau apa pun dari formulirA = A
, dan menghapusnya. Jika semua proposisi didukung oleh premis, semuanya akan cocok dengan formulir ini, jadi yang tersisa hanya terdiri dari baris baru. Penggantian keempat mengubah ini menjadiright
. Jika tidak, penggantian kelima mengubah semua yang tersisa (yang tidak mengandungr
sejaktherefore
dihapus) menjadiwrong
. Akhirnya, penggantian terakhir ditambahkanAlex is
di awal.sumber
Python 2, 264 byte
Sudah ada jawaban Python 3 yang luar biasa dari mbomb007 . Jawaban ini mencuri secara mencolok dari yang itu (khususnya trik "Alex is wrriognhgt").
Dan jawaban ini juga jauh lebih lama dari yang ...
Yah, bagaimanapun, ide dalam jawaban ini adalah untuk memelihara kamus pasangan nilai kunci, di mana kuncinya adalah 26 karakter huruf kapital, dan nilai masing-masing tombol yang terkait adalah himpunan huruf yang setara dengan kunci. (Jika semua 26 huruf itu setara, maka setiap tombol akan memiliki satu set 26 huruf untuk nilainya yang sesuai.)
(Untuk menyimpan byte, jawaban ini menggabungkan spasi dan tab , yang sah menurut Python 2.)
Kode ini benar-benar sangat efisien, karena kamus terbatas pada ukuran maksimum yang dimungkinkan (26 x 26 seperti dijelaskan di atas) yang tidak bergantung pada jumlah baris input.
Sekarang, ketika saya bermain golf solusi ini, saya menyadari bahwa saya bisa menyimpan empat byte dengan menggunakan string daripada set untuk nilai-nilai kamus, dengan mengganti
dengan
Tentu saja maka Anda juga harus mengganti (CATATAN: JANGAN LAKUKAN INI) tiga contoh operasi serikat yang ditetapkan
|
dengan rangkaian string+
, tetapi itu tidak mengubah panjang kode. Hasilnya adalah bahwa semuanya harus tetap berfungsi sama, kecuali itu tidak akan menghilangkan duplikat seperti yang Anda lakukan dengan set (itu hanya akan terus menambahkan ke ujung string). Kedengarannya OK - sedikit kurang efisien, pasti, tetapi 260 byte, bukan 264.Nah, ternyata versi 260-byte sangat tidak efisien yang menyebabkan
MemoryError
ketika saya mengujinyaIni mengejutkan saya. Mari kita selidiki versi "string concatenation" 260-byte!
Tentu saja akan dimulai dengan pasangan kunci-nilai
A:A
danB:B
(ditambah 24 lainnya yang tidak penting). Kami akan menulisd[A]
berarti nilai kamus sesuai dengan kunciA
, jadi pada awalnya kami akan memilikid[A] = A
. Sekarang, mengingat premisA = B
, itu akan dimulai dengan menggabungkan nilai-nilaid[A]=A
dand[B]=B
untuk mendapatkany = AB
. Maka akan mengulangi string ini dua kali:for v in AB: for w in AB:
...Jadi, pertama kali melalui loop, kita punya
v=A
danw=A
. Menerapkand[v] += d[w]
dand[w] += d[v]
menghasilkan urutan kamus berikut:Selanjutnya, dengan
v=A
danw=B
:Berikutnya,
v=B, w=A
:Dan
v=B, w=B
:Urutan langkah-langkah di atas akan menerapkan premis tunggal
A = B
, dengan kesimpulan yangA
sama dengan setiap huruf dalam stringAAAABBAAAABAAAAB
, sedangkanB
sama dengan setiap huruf dalamBAAAABAAAABBAAAABAAAABBAAAABAAAABBAAAABAAAAB
.Sekarang, anggaplah bahwa premis berikutnya adalah
A = B
lagi . Anda pertama kali menghitungy = d[A] + d[B] = AAAABBAAAABAAAABBAAAABAAAABBAAAABAAAABBAAAABAAAABBAAAABAAAAB
.Selanjutnya, Anda mengulangi string ini dua kali:
for v in y: for w in y:
...Ya. Mungkin itu bukan implementasi yang sangat efisien.
sumber
ES6, 128 byte
Secara longgar didasarkan pada versi Ruby.
Mencari non-self-equality before the "Oleh karena itu" dan secara rekursif mengganti variabel sepanjang string setiap kali (ini menghemat byte selama loop sementara).
sumber
C, 240 byte
Ini bekerja dengan menggabungkan nilai-nilai ke dalam set tree, sehingga setiap nilai yang setara mengarah ke set root yang sama. Tidak disatukan, dengan tipe implisit dibuat eksplisit.
180 byte
Versi yang lebih pendek ini berfungsi untuk semua kasus dari OP, tetapi untuk beberapa input lainnya secara tidak benar mengklaim Alex salah. Ini menggunakan pendekatan yang sama, tetapi untuk setiap premis hanya mengatur entri kedua dengan nilai saat ini dari entri pertama. Saat membandingkan, itu terlihat hanya pada nilai yang tepat daripada mencari pohon.
Contoh input yang gagal dilakukan:
sumber
05AB1E , 32 byte
Terinspirasi oleh @aditsu 's CJam jawabannya .
Cobalah secara online atau verifikasi semua kasus uji .
Penjelasan:
Lihat tip tambang 05AB1E ini (bagian Cara menggunakan kamus? ) Untuk memahami mengapa
…±º€ˆ
ini"alex is "
dan„–у©
itu"wrong right"
.sumber
bash + awk + SWI-Prolog , 167 byte
Cobalah online!
Awalnya, ini hanya akan menjadi jawaban Prolog, tetapi alat yang bisa saya temukan untuk benar-benar mengubah format input menjadi sesuatu yang dapat digunakan cukup terbatas sehingga saya memutuskan untuk melakukan bagian itu dalam bash, meskipun saya hampir tidak memiliki pengalaman melakukan sesuatu dengan bash, dan bahkan tidak pernah menyentuh awk. Saya akhirnya menghabiskan berjam-jam di atasnya untuk ingin mempostingnya bahkan setelah itu tumbuh menjadi 167-byte ini, nyaris tidak golf sama sekali monster.
Pada dasarnya, apa yang dilakukan program awk adalah mengambil input dari stdin, menghapus baris
therefore
, ganti setiapA = B
setelahnya dengan?=(A,B)
, dan menambahkanwrite(\"Alex is right\");write(\"Alex is wrong\"). halt.
. Kemudian,paste -sd ,
ganti setiap baris baru tetapi yang terakhir dengan koma, mengubahnya menjadi dua kueri yang valid ke shell SWI-Prolog, yang kemudian dijalankan dengan hasil cetak yang terpotong menjadi satu barishead -n1
, yang membutuhkan<(...)
alih-alih pipa karena alasan di luar pemahaman saya. Semua ini, hanya menggunakan builtin !sumber