Dalam teori informasi, "kode awalan" adalah kamus di mana tidak ada kunci yang merupakan awalan dari yang lain. Dengan kata lain, ini berarti bahwa tidak ada string yang dimulai dengan yang lain.
Misalnya, {"9", "55"}
adalah kode awalan, tetapi {"5", "9", "55"}
tidak.
Keuntungan terbesar dari ini, adalah bahwa teks yang dikodekan dapat ditulis tanpa pemisah di antara mereka, dan itu masih akan dapat diuraikan secara unik. Ini muncul dalam algoritma kompresi seperti pengkodean Huffman , yang selalu menghasilkan kode awalan yang optimal.
Tugas Anda sederhana: Diberikan daftar string, tentukan apakah itu kode awalan yang valid atau tidak.
Masukan Anda:
Akan ada daftar string dalam format apa pun yang masuk akal .
Hanya akan berisi string ASCII yang dapat dicetak.
Tidak akan mengandung string kosong.
Output Anda akan menjadi nilai truey / falsey : Sejujurnya jika itu kode awalan yang valid, dan falsey jika bukan.
Berikut ini beberapa kasus uji yang benar:
["Hello", "World"]
["Code", "Golf", "Is", "Cool"]
["1", "2", "3", "4", "5"]
["This", "test", "case", "is", "true"]
["111", "010", "000", "1101", "1010", "1000", "0111", "0010", "1011",
"0110", "11001", "00110", "10011", "11000", "00111", "10010"]
Berikut adalah beberapa kasus pengujian yang salah:
["4", "42"]
["1", "2", "3", "34"]
["This", "test", "case", "is", "false", "t"]
["He", "said", "Hello"]
["0", "00", "00001"]
["Duplicate", "Duplicate", "Keys", "Keys"]
Ini adalah kode-golf, sehingga celah standar berlaku, dan jawaban tersingkat dalam byte menang.
sumber
001
bisa diuraikan secara unik? Bisa jadi00, 1
atau0, 11
.0, 00, 1, 11
semua sebagai kunci, ini bukan kode awalan karena 0 adalah awalan 00, dan 1 adalah awalan 11. Kode awalan adalah di mana tidak ada kunci yang dimulai dengan kunci lain. Jadi misalnya, jika kunci Anda0, 10, 11
adalah kode awalan dan dapat diuraikan secara unik.001
bukan pesan yang valid, tetapi0011
atau0010
dapat diuraikan secara unik.Jawaban:
Pyth, 8 byte
Suite uji
Ambil semua 2 elemen permutasi dari input, petakan masing-masing ke indeks dari satu string di string lainnya (0 untuk awalan) dan kembalikan apakah semua hasilnya benar (bukan nol).
sumber
Haskell, 37 byte
Setiap elemen
x
daril
diulang sekali untuk setiap elemen bahwa itu adalah awalan, yang persis sekali untuk daftar prefix bebas, memberikan daftar asli. Properti awalan diperiksa dengan zip kedua daftar denganx
, yang memotong elemen di luar panjangx
.sumber
Java,
128127126125124121 byte(Terima kasih @Kenny Lau, @Maltysen, @ Patrickrick, @Joba)
Tidak disatukan
Keluaran
sumber
&
berhasil&&
?int
dan kembali0
dan1
? Itu akan menghemat beberapa byte. Juga saya lupa apakah ini berlaku di Jawa, tetapi jika Anda menyatakani
,j
danl
di dalam luarfor
loop yang akan menyelamatkan satu byte dari satu titik koma kurang.indexOf(a[i])==0
dalam hal ini tidak ada tabungan.Python 2, 48
51byteUntuk setiap elemen
a
daril
, fungsia.find
menemukan indeks dari kejadian pertamaa
dalam string input, memberikan-1
untuk absen. Jadi,0
tunjukkan awalan. Dalam daftar bebas awalan, pemetaan fungsi ini hanya mengembalikan satu0
untuka
dirinya sendiri. Fungsi memeriksa bahwa ini adalah kasus untuk setiapa
.51 byte:
Ganti
~
dengan karakter dengan kode ASCII 128 atau lebih tinggi.Untuk setiap elemen
a
dalaml
, salinan disertakan untuk setiap elemen yang merupakan awalan darinya. Untuk daftar bebas awalan, satu-satunya elemen tersebut adalaha
dirinya sendiri, jadi ini memberikan daftar asli.sumber
CJam, 14 byte
Suite uji.
Penjelasan
sumber
JavaScript ES6,
654340 byteSolusi saya sebelumnya, yang menangani array string semua karakter UTF-8:
Saya dapat menghindarinya
JSON.stringify
karena tantangannya hanya menentukan karakter ASCII yang dapat dicetak.Uji
sumber
Haskell, 49 byte
Ini memiliki beberapa bagian:
Jika kedua daftar sama, maka sebuah elemen hanyalah awalan dari dirinya sendiri, dan itu valid.
sumber
Retina , 19 byte
Hitungan byte mengasumsikan penyandian ISO 8859-1.
Input harus dipisahkan dengan linefeed. Keluaran adalah
0
untuk kepalsuan dan1
untuk kebenaran.Cobalah online! (Sebaliknya, sedikit dimodifikasi untuk mendukung beberapa test case yang dipisahkan oleh ruang.)
Penjelasan
Urutkan garis di input. Jika ada awalan itu akan berakhir langsung di depan string yang berisi itu.
Cobalah untuk mencocokkan (
M
) baris lengkap yang juga ditemukan di awal baris berikutnya. Them
mengaktifkan modus multiline sehingga^
pertandingan garis awal dan1
memastikan bahwa kami hanya menghitung paling banyak satu pertandingan sehingga output adalah0
atau1
.Untuk bertukar
0
dan1
dalam hasilnya, kami menghitung jumlah0
s.sumber
Java, 97 byte
Gunakan sebagian besar trik yang ditemukan dalam jawaban @ Marv , tetapi juga memanfaatkan persamaan foreach loop dan referensi string.
Tidak dijinakkan:
Perhatikan bahwa, seperti yang saya katakan, ini menggunakan persamaan referensi string. Itu berarti bahwa kode dapat berperilaku aneh karena interning String . Kode tidak berfungsi saat menggunakan argumen yang dikirimkan dari baris perintah, dan juga saat menggunakan sesuatu yang dibaca dari baris perintah. Namun, jika Anda ingin meng-hardcode nilai yang akan diuji, Anda harus memanggil konstruktor String secara manual untuk memaksa interning agar tidak terjadi:
sumber
PostgreSQL,
186, 173 byteKeluaran:
Tidak ada demo langsung kali ini. http://sqlfiddle.com hanya mendukung 9.3 dan untuk menjalankan demo ini diperlukan 9.4.
Bagaimana itu bekerja:
y
LEFT OUTER JOIN
ke tabel turunan yang sama berdasarkan padai
(id) yang sama, tetapi dengan perbedaanoridinal
yang dimulai dengan awalany.z LIKE u.z||'%'
c
(array awal) dan menggunakanEVERY
fungsi pengelompokan. Jika setiap baris dari tabel keduaIS NULL
itu berarti tidak ada awalan.Masukan jika seseorang tertarik:
EDIT:
SQL Server 2016+
pelaksanaan:LiveDemo
Catatan: Ini adalah daftar yang dipisahkan koma, bukan array nyata. Tapi ide utamanya sama dengan di
PostgreSQL
.EDIT 2:
Sebenarnya
WITH ORDINALITY
bisa diganti:SqlFiddleDemo
sumber
Brachylog , 8 byte
Cobalah online!
Keluaran melalui keberhasilan / kegagalan predikat. Memakan waktu lebih dari 60 detik pada kasus uji kebenaran terakhir
["111","010","000","1101","1010","1000","0111","0010","1011","0110","11001","00110","10011","11000","00111","10010"]
tetapi melewatinya dengan cepat dengan byte tambahan yang menghilangkan sejumlah besar kemungkinan lebih awal daripada yang dilakukan program sebaliknya (Ċ
sebelum memeriksa permutasi daripadaᵈ
setelah memeriksa permutasi, untuk membatasi panjang sublist ke dua).Kurang sepele 9-byte varian dari
¬(⊇Ċpa₀ᵈ)
yang dijalankan dalam waktu yang wajar adalah¬(⊇o₁a₀ᵈ)
,¬(⊇o↔a₀ᵈ)
, dan¬(⊇oa₀ᵈ¹)
.sumber
Perl 6 , 24 byte
Cobalah online!
Wow, mengejutkan pendek saat menggunakan built-in yang lama.
Penjelasan
sumber
Racket, 70 byte
sumber
Python,
5855 bytesumber
a.index(b)==0
sedikit lebih pendek. Atau, Anda bisa melakukannya0**sum(a.index(b)for a in l for b in l)
.index
melempar pengecualian ketikab
tidak ditemukan. Dan karena itu seharusnya==
, bukan>=
. Namun,find
berhasil. (Dan ini juga lebih pendek!)find
. Otak yang mengantuk itu mengantuk. Versi kedua juga bisa digunakanfind
.len(l)
adalah karena kami melakukan iterasi pada semuab
s pada masing-masinga
, akan selalu ada setidaknya satu pertandingan pera
. Jadi kami memeriksa apakah jumlah kecocokan sama dengan jumlah elemen.JavaScript (ES6), 52
54Edit 2 byte yang disimpan thx @Neil
Uji
sumber
!w.indexOf(v)
?Mathematica
75 6968 byteLoquacious seperti biasa. Tetapi Martin B mampu mengurangi kode sebanyak 7 byte.
Metode 1: Menyimpan output dalam
Array
(68 byte)
Metode 2: Menyimpan output dalam a
List
(69 byte)
sumber
a~Drop~{#}~StringStartsQ~a[[#]]
pekerjaan. JugaArray
harus menyimpan beberapa byteLength
, terutama karena itu akan memungkinkan Anda untuk menggunakanJoin@@
bukanFlatten@
(asalkan, AndaFlatten
hanya menggunakan untuk satu level).Array
nanti.Mathematica, 41 byte
sumber
APL (Dyalog Unicode) , 13 byte SBCS
-2 byte:
Cobalah online!
Penjelasan:
sumber
~2∊+\⊃¨∘.⍷⍨⎕
J , 17 byte
Cobalah online!
Catatan: Saya benar-benar menulis ini sebelum melihat jawaban APL, untuk mendekatinya tanpa bias. Ternyata pendekatannya hampir identik, yang menarik. Saya kira ini adalah solusi "array thinknig" alami
Ambil input kemas karena string memiliki panjang yang tidak sama.
Buat tabel fungsi-sendiri
/~
dari setiap elemen yang dipasangkan dengan setiap elemen dan lihat apakah ada kecocokan di awal{.@E.
. Ini akan menghasilkan matriks hasil 1-0.Jumlahkan dua kali
1#.1#.
untuk mendapatkan angka tunggal yang mewakili "semua yang ada dalam matriks", dan lihat apakah angka itu sama dengan panjang input#=
. Jika ya, satu-satunya pencocokan awalan adalah pencocokan sendiri, yaitu, kami memiliki kode awalan.solusi penyortiran, 18 byte
Mencoba pendekatan yang berbeda. Solusi ini memilah dan melihat pasangan yang berdekatan.
Cobalah online!
sumber
R , 48 byte
Cobalah online!
Penjelasan:
outer(s,s,startsWith)
mengeluarkan matriks logika memeriksa apakahs[i]
merupakan awalans[j]
. Jikas
kode awalan, maka adalength(s)
elemen yang BENAR dalam hasilnya, yang sesuai dengan elemen diagonal (s[i]
adalah awalan dari dirinya sendiri).sumber
function(s)all(colSums(outer(s,s,startsWith))<2)
tapi tetap saja itustartsWith
adalah fungsi yang saya tidak tahu! Temuan yang bagus.TRUE
danFALSE
...==
dengan>
:-).)Pyth -
1312 byteCobalah online di sini .
sumber
Ruby, 48 byte
Menggunakan argumen sebagai input dan stdout sebagai output.
sumber
Scala, 71 byte
sumber
Racket 130 byte
Tidak Disatukan:
Pengujian:
Keluaran:
sumber
C (gcc) , 93 byte
Cobalah online!
Ganda sederhana untuk loop digunakan
strstr(a,b)==a
untuk memeriksa preferensi. Terutama ditambahkan karena sepertinya belum ada jawaban C.sumber
05AB1E , 13 byte
Terlalu lama .. Awalnya saya punya solusi 9-byte, tetapi gagal untuk kasus uji kunci duplikat.
Cobalah secara online atau verifikasi semua kasus uji .
Penjelasan:
sumber
Japt , 8 byte
Cobalah
sumber
C # (Visual C # Interactive Compiler) , 70 byte
Cobalah online!
sumber
Stax , 6 byte
Jalankan dan debug itu
Ini menghasilkan nol untuk kebenaran.
Gagasan umum adalah mempertimbangkan setiap pasangan string dalam input. Jika indeks substring satu di yang lain selalu nol, maka itu bukan kode awalan yang valid. Di stax, indeks dari hasil substrat tidak ada
-1
. Dengan cara ini, semua indeks substring pasangan-bijaksana dapat dikalikan bersama.Ini adalah algoritma yang sama dengan solusi pyth isaacg, tetapi saya mengembangkannya secara independen.
sumber