Apakah ini kode awalan?

33

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.

DJMcMayhem
sumber
Apakah Anda menginginkan nilai kebenaran yang konsisten atau dapat berupa misalnya "bilangan bulat positif" (yang mungkin berbeda di antara input yang berbeda).
Martin Ender
@DrGreenEggsandHamDJ Saya tidak berpikir bahwa jawaban dimaksudkan untuk mengatasi konsistensi output sama sekali, maka pertanyaannya. ;)
Martin Ender
Karena penasaran: Tantangannya mengatakan: "Keuntungan terbesar dari ini, adalah bahwa teks yang dikodekan dapat ditulis tanpa pemisah di antara mereka, dan itu masih akan dapat diuraikan secara unik.". Bagaimana sesuatu seperti 001bisa diuraikan secara unik? Bisa jadi 00, 1atau 0, 11.
Joba
2
@Joba Tergantung pada kunci Anda. Jika Anda memiliki 0, 00, 1, 11semua 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 Anda 0, 10, 11adalah kode awalan dan dapat diuraikan secara unik. 001bukan pesan yang valid, tetapi 0011atau 0010dapat diuraikan secara unik.
DJMcMayhem

Jawaban:

11

Pyth, 8 byte

.AxM.PQ2

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).

isaacg
sumber
12

Haskell, 37 byte

f l=[x|x<-l,y<-l,zip x x==zip x y]==l

Setiap elemen xdari ldiulang 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 dengan x, yang memotong elemen di luar panjang x.

Tidak
sumber
Ini adalah solusi yang elegan (+1)
Michael Klein
9

Java, 128 127 126 125 124 121 byte

(Terima kasih @Kenny Lau, @Maltysen, @ Patrickrick, @Joba)

Object a(String[]a){for(int i=0,j,l=a.length;i<l;i++)for(j=0;j<l;)if(i!=j&a[j++].startsWith(a[i]))return 1<0;return 1>0;}

Tidak disatukan

Object a(String[] a) {
    for (int i = 0, j, l = a.length; i < l; i++) 
        for (j = 0; j < l;) 
            if (i != j & a[j++].startsWith(a[i])) return 1<0;
    return 1>0;
}

Keluaran

[Hello, World]
true

[Code, Golf, Is, Cool]
true

[1, 2, 3, 4, 5]
true

[This, test, case, is, true]
true

[111, 010, 000, 1101, 1010, 1000, 0111, 0010, 1011, 0110, 11001, 00110, 10011, 11000, 00111, 10010]
true

[4, 42]
false

[1, 2, 3, 34]
false

[This, test, case, is, false, t]
false

[He, said, Hello]
false

[0, 00, 00001]
false

[Duplicate, Duplicate, Keys, Keys]
false
Marv
sumber
1
idk tentang java, tetapi apakah akan &berhasil &&?
Maltysen
1
Benar, menyimpan byte lain. Di Jawa, menggunakan operator bitwise dengan operan boolean berperilaku seperti operator logis normal, kecuali mereka tidak mengalami hubungan pendek yang tidak diperlukan dalam kasus ini.
Marv
Tidak bisakah Anda hanya mengubah jenis fungsi kembali ke intdan kembali 0dan 1? Itu akan menghemat beberapa byte. Juga saya lupa apakah ini berlaku di Jawa, tetapi jika Anda menyatakan i, jdan ldi dalam luar forloop yang akan menyelamatkan satu byte dari satu titik koma kurang.
Patrick Roberts
@ PatrickRoberts Maltysen menyarankan ini sebelumnya, tetapi ini tidak valid sesuai dengan definisi yang paling tinggi tentang truthy / falsey . Namun, menempatkan deklarasi dalam loop sangat valid dan cukup jelas sekarang setelah saya pikirkan. Itulah yang Anda dapatkan untuk bermain golf pada jam 4 pagi: ^)
Marv
3
@Joba Cukup yakin itu tidak valid karena indexOf mengembalikan -1 ketika string tidak ditemukan; perlu indexOf(a[i])==0dalam hal ini tidak ada tabungan.
Pokechu22
6

Python 2, 48 51 byte

lambda l:all(1/map(a.find,l).count(0)for a in l)

Untuk setiap elemen adari l, fungsi a.findmenemukan indeks dari kejadian pertama adalam string input, memberikan-1 untuk absen. Jadi, 0tunjukkan awalan. Dalam daftar bebas awalan, pemetaan fungsi ini hanya mengembalikan satu 0untuk adirinya sendiri. Fungsi memeriksa bahwa ini adalah kasus untuk setiap a.


51 byte:

lambda l:[a for a in l for b in l if b<=a<b+'~']==l

Ganti ~dengan karakter dengan kode ASCII 128 atau lebih tinggi.

Untuk setiap elemen adalam l, salinan disertakan untuk setiap elemen yang merupakan awalan darinya. Untuk daftar bebas awalan, satu-satunya elemen tersebut adalah adirinya sendiri, jadi ini memberikan daftar asli.

Tidak
sumber
4

CJam, 14 byte

q~$W%2ew::#0&!

Suite uji.

Penjelasan

q~   e# Read and evaluate input.
$    e# Sort strings. If a prefix exists it will end up directly in front 
     e# of a string which contains it.
W%   e# Reverse list.
2ew  e# Get all consecutive pairs of strings.
::#  e# For each pair, find the first occurrence of the second string in the first.
     e# If a prefix exists that will result in a 0, otherwise in something non-zero.
0&   e# Set intersection with 0, yielding [0] for falsy cases and [] for truthy ones.
!    e# Logical NOT.
Martin Ender
sumber
4

JavaScript ES6, 65 43 40 byte

a=>!/(.*)\1/.test(''+a.sort().join``)
      ^            ^               ^ embedded NUL characters

Solusi saya sebelumnya, yang menangani array string semua karakter UTF-8:

a=>!/[^\\]("([^"]*\\")*[^\\])",\1/.test(JSON.stringify(a.sort()))

Saya dapat menghindarinya JSON.stringifykarena tantangannya hanya menentukan karakter ASCII yang dapat dicetak.

Uji

f=a=>!/(\0.*)\1/.test('\0'+a.sort().join`\0`) // since stackexchange removes embedded NUL characters

O.textContent += 'OK: '+
[["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"]
].map(a=>f(a)) 

O.textContent += '\nKO: '+
[["4", "42"]                             
,["1", "2", "3", "34"]                   
,["This", "test", "case", "is", "false", "t"]
,["He", "said", "Hello"]
,["0", "00", "00001"]
,["Duplicate", "Duplicate", "Keys", "Keys"]
].map(a=>f(a))
<pre id=O></pre>

Patrick Roberts
sumber
3

Haskell, 49 byte

g x=[1|z<-map((and.).zipWith(==))x<*>x,z]==(1<$x)

Ini memiliki beberapa bagian:

-- Are two lists (or strings) equal for their first min(length_of_1,length_of_2) elements, i.e. is one the prefix of the other?
(and.).zipWith(==)

-- Check whether one element is the prefix of the other, for all pairs of elements (including equal pairs)
map((and.).zipWith(==))x<*>x

-- This is a list of 1's of length (number of elements that are the prefix of the other)
[1|z<-map((and.).zipWith(==))x<*>x,z]

-- This is the input list, with all the elements replaced with 1's
(1<$x)

Jika kedua daftar sama, maka sebuah elemen hanyalah awalan dari dirinya sendiri, dan itu valid.

Michael Klein
sumber
3

Retina , 19 byte

Hitungan byte mengasumsikan penyandian ISO 8859-1.

O`.+
Mm1`^(.+)¶\1
0

Input harus dipisahkan dengan linefeed. Keluaran adalah 0untuk kepalsuan dan 1untuk kebenaran.

Cobalah online! (Sebaliknya, sedikit dimodifikasi untuk mendukung beberapa test case yang dipisahkan oleh ruang.)

Penjelasan

O`.+

Urutkan garis di input. Jika ada awalan itu akan berakhir langsung di depan string yang berisi itu.

Mm1`^(.+)¶\1

Cobalah untuk mencocokkan ( M) baris lengkap yang juga ditemukan di awal baris berikutnya. The mmengaktifkan modus multiline sehingga ^pertandingan garis awal dan 1memastikan bahwa kami hanya menghitung paling banyak satu pertandingan sehingga output adalah 0atau 1.

0

Untuk bertukar 0dan 1dalam hasilnya, kami menghitung jumlah 0s.

Martin Ender
sumber
3

Java, 97 byte

Object a(String[]a){for(String t:a)for(String e:a)if(t!=e&t.startsWith(e))return 1<0;return 1>0;}

Gunakan sebagian besar trik yang ditemukan dalam jawaban @ Marv , tetapi juga memanfaatkan persamaan foreach loop dan referensi string.

Tidak dijinakkan:

Object a(String[]a){
    for (String t : a)
        for (String e : a)
            if (t != e & t.startsWith(e))
                return 1<0;
    return 1>0;
}

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:

System.out.println(a(new String[] {new String("Hello"), new String("World")}));
System.out.println(a(new String[] {new String("Code"), new String("Golf"), new String("Is"), new String("Cool")}));
System.out.println(a(new String[] {new String("1"), new String("2"), new String("3"), new String("4"), new String("5")}));
System.out.println(a(new String[] {new String("This"), new String("test"), new String("case"), new String("is"), new String("true")}));
System.out.println(a(new String[] {new String("111"), new String("010"), new String("000"), new String("1101"), new String("1010"), new String("1000"), new String("0111"), new String("0010"), new String("1011"), new String("0110"), new String("11001"), new String("00110"), new String("10011"), new String("11000"), new String("00111"), new String("10010")}));
System.out.println(a(new String[] {new String("4"), new String("42")}));
System.out.println(a(new String[] {new String("1"), new String("2"), new String("3"), new String("34")}));
System.out.println(a(new String[] {new String("This"), new String("test"), new String("case"), new String("is"), new String("false"), new String("t")}));
System.out.println(a(new String[] {new String("He"), new String("said"), new String("Hello")}));
System.out.println(a(new String[] {new String("0"), new String("00"), new String("00001")}));
System.out.println(a(new String[] {new String("Duplicate"), new String("Duplicate"), new String("Keys"), new String("Keys")}));
Pokechu22
sumber
@ Jo King Lihat bagian kedua dari jawaban saya; ini agak rumit dan tergantung pada bagaimana input ditentukan. Tapi saya tidak ingat benar-benar menulis ini
Pokechu22
3

PostgreSQL, 186 , 173 byte

WITH y AS(SELECT * FROM t,LATERAL unnest(c)WITH ORDINALITY s(z,r))
SELECT y.c,EVERY(u.z IS NULL)
FROM y LEFT JOIN y u ON y.i=u.i AND y.r<>u.r AND y.z LIKE u.z||'%' GROUP BY y.c

Keluaran:

masukkan deskripsi gambar di sini

Tidak ada demo langsung kali ini. http://sqlfiddle.com hanya mendukung 9.3 dan untuk menjalankan demo ini diperlukan 9.4.

Bagaimana itu bekerja:

  1. Split array string dengan angka dan beri nama y
  2. Dapatkan semua y
  3. LEFT OUTER JOINke tabel turunan yang sama berdasarkan pada i(id) yang sama, tetapi dengan perbedaan oridinalyang dimulai dengan awalany.z LIKE u.z||'%'
  4. Hasil grup berdasarkan c(array awal) dan menggunakan EVERYfungsi pengelompokan. Jika setiap baris dari tabel keduaIS NULL itu berarti tidak ada awalan.

Masukan jika seseorang tertarik:

CREATE TABLE t(i SERIAL,c text[]);

INSERT INTO t(c)
SELECT '{"Hello", "World"}'::text[]
UNION ALL SELECT  '{"Code", "Golf", "Is", "Cool"}'
UNION ALL SELECT  '{"1", "2", "3", "4", "5"}'
UNION ALL SELECT  '{"This", "test", "case", "is", "true"}'         
UNION ALL SELECT  '{"111", "010", "000", "1101", "1010", "1000", "0111", "0010", "1011","0110", "11001", "00110", "10011", "11000", "00111", "10010"}'
UNION ALL SELECT  '{"4", "42"}'
UNION ALL SELECT  '{"1", "2", "3", "34"}'                   
UNION ALL SELECT  '{"This", "test", "case", "is", "false", "t"}'
UNION ALL SELECT  '{"He", "said", "Hello"}'
UNION ALL SELECT  '{"0", "00", "00001"}'
UNION ALL SELECT  '{"Duplicate", "Duplicate", "Keys", "Keys"}';

EDIT:

SQL Server 2016+ pelaksanaan:

WITH y AS (SELECT *,z=value,r=ROW_NUMBER()OVER(ORDER BY 1/0) FROM #t CROSS APPLY STRING_SPLIT(c,','))
SELECT y.c, IIF(COUNT(u.z)>0,'F','T')
FROM y LEFT JOIN y u ON y.i=u.i AND y.r<>u.r AND y.z LIKE u.z+'%' 
GROUP BY y.c;

LiveDemo

Catatan: Ini adalah daftar yang dipisahkan koma, bukan array nyata. Tapi ide utamanya sama dengan diPostgreSQL .


EDIT 2:

Sebenarnya WITH ORDINALITYbisa diganti:

WITH y AS(SELECT *,ROW_NUMBER()OVER()r FROM t,LATERAL unnest(c)z)
SELECT y.c,EVERY(u.z IS NULL)
FROM y LEFT JOIN y u ON y.i=u.i AND y.r<>u.r AND y.z LIKE u.z||'%' GROUP BY y.c

SqlFiddleDemo

Lad2025
sumber
3

Brachylog , 8 byte

¬(⊇pa₀ᵈ)

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).

¬(     )    It cannot be shown that
   p        a permutation of
  ⊇         a sublist of the input
      ᵈ     is a pair of values [A,B] such that
    a₀      A is a prefix of B.

Kurang sepele 9-byte varian dari ¬(⊇Ċpa₀ᵈ)yang dijalankan dalam waktu yang wajar adalah ¬(⊇o₁a₀ᵈ), ¬(⊇o↔a₀ᵈ), dan ¬(⊇oa₀ᵈ¹).

String yang tidak terkait
sumber
Jika tantangan ini menggunakan "dua nilai yang berbeda dan konsisten" alih-alih "benar / salah", ini hanya akan memakan waktu 5 byte.
String yang tidak terkait
2

Perl 6 , 24 byte

{.all.starts-with(.one)}

Cobalah online!

Wow, mengejutkan pendek saat menggunakan built-in yang lama.

Penjelasan

{                      }  # Anonymous code block taking a list
 .all                     # Do all of the strings
     .starts-with(    )   # Start with
                  .one    # Only one other string (i.e. itself)
Jo King
sumber
Saya menulis jawaban 50 byte tetapi Anda hanya meniup milik saya keluar dari air.
bb94
1
@ bb94 Ya, saya mulai dengan jawaban yang sama tetapi mengalami masalah yang sama seperti milik Anda dengan set dengan kunci duplikat yang mengembalikan kebenaran. Menulis jawaban ini sangat memuaskan
Jo King
1

Racket, 70 byte

(λ(l)(andmap(λ(e)(not(ormap(curryr string-prefix? e)(remv e l))))l))
Winny
sumber
1

Python, 58 55 byte

lambda l:sum(0==a.find(b)for a in l for b in l)==len(l)
DJMcMayhem
sumber
a.index(b)==0sedikit lebih pendek. Atau, Anda bisa melakukannya 0**sum(a.index(b)for a in l for b in l).
Mego
@Mego Itu tidak bekerja karena indexmelempar pengecualian ketika btidak ditemukan. Dan karena itu seharusnya ==, bukan >=. Namun, findberhasil. (Dan ini juga lebih pendek!)
DJMcMayhem
Aduh, aku bermaksud mengetik find. Otak yang mengantuk itu mengantuk. Versi kedua juga bisa digunakan find.
Mego
@Mego Saya tidak yakin apakah saya mendapatkan versi kedua. Bukankah itu selalu mengembalikan 0?
DJMcMayhem
@Mego Itu hanya berfungsi jika setiap string sama. Alasan kami membandingkannya len(l)adalah karena kami melakukan iterasi pada semua bs pada masing-masing a, akan selalu ada setidaknya satu pertandingan per a. Jadi kami memeriksa apakah jumlah kecocokan sama dengan jumlah elemen.
DJMcMayhem
1

JavaScript (ES6), 52 54

Edit 2 byte yang disimpan thx @Neil

a=>!a.some((w,i)=>a.some((v,j)=>i-j&&!w.indexOf(v)))

Uji

f=a=>!a.some((w,i)=>a.some((v,j)=>i-j&&!w.indexOf(v)))

O.textContent += 'OK: '+
[["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"]
].map(a=>f(a)) 

O.textContent += '\nKO: '+
[["4", "42"]                             
,["1", "2", "3", "34"]                   
,["This", "test", "case", "is", "false", "t"]
,["He", "said", "Hello"]
,["0", "00", "00001"]
,["Duplicate", "Duplicate", "Keys", "Keys"]
].map(a=>f(a))
<pre id=O></pre>

edc65
sumber
!w.indexOf(v)?
Neil
@Neil benar, terima kasih
edc65
1

Mathematica 75 69 68 byte

Loquacious seperti biasa. Tetapi Martin B mampu mengurangi kode sebanyak 7 byte.

Metode 1: Menyimpan output dalam Array

(68 byte)

f@a_:=!Or@@(Join@@Array[a~Drop~{#}~StringStartsQ~a[[#]]&,Length@a])

f@{"111", "010", "000", "1101", "1010", "1000", "0111", "0010", "1011", "0110", "11001", "00110", "10011", "11000", "00111", "10010"}

Benar


f@{"He", "said", "Hello"}

Salah


Metode 2: Menyimpan output dalam a List

(69 byte)

f@a_:=!Or@@Flatten[a~Drop~{#}~StringStartsQ~a[[#]]&/@Range@Length@a]
DavidC
sumber
Aturan yang diutamakan harus membuat a~Drop~{#}~StringStartsQ~a[[#]]pekerjaan. Juga Arrayharus menyimpan beberapa byte Length, terutama karena itu akan memungkinkan Anda untuk menggunakan Join@@bukan Flatten@(asalkan, Anda Flattenhanya menggunakan untuk satu level).
Martin Ender
Terima kasih untuk sarannya. Saya akan melihat Arraynanti.
DavidC
1

Mathematica, 41 byte

!Or@@StringStartsQ@@@Reverse@Sort@#~Subsets~{2}&
A Simmons
sumber
1

APL (Dyalog Unicode) , 13 byte SBCS

-2 byte:

≢=∘≢∘⍸∘.(⊃⍷)⍨

Cobalah online!

Penjelasan:

≢=∘≢∘⍸∘.(⊃⍷)⍨   Monadic function train
               "Find": Convert the right argument into a boolean vector,
                where ones correspond to instances of the left argument
              Take the first item of the above vector (i.e., only prefixes)
     ∘.(  )⍨   Commutative outer product: take the above function and apply
               it for each possible pair of elements in the input
               If the input is a prefix code, the above should have a number of ones
               equal to the length of the input (i.e., each item is a prefix of only itself)
               To test this...
              Find the location of all ones in the above
   ≢∘          Take the length of the above
≢=∘            Compare to the length of the input
voidhawk
sumber
~2∊+\⊃¨∘.⍷⍨⎕­
ngn
1

J , 17 byte

#=1#.1#.{.@E.&>/~

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

0=1#.2{.@E.&>/\/:~

Mencoba pendekatan yang berbeda. Solusi ini memilah dan melihat pasangan yang berdekatan.

Cobalah online!

Jonah
sumber
1

R , 48 byte

function(s)sum(outer(s,s,startsWith))==length(s)

Cobalah online!

Penjelasan: outer(s,s,startsWith)mengeluarkan matriks logika memeriksa apakah s[i]merupakan awalan s[j]. Jika skode awalan, maka ada length(s)elemen yang BENAR dalam hasilnya, yang sesuai dengan elemen diagonal ( s[i]adalah awalan dari dirinya sendiri).

Robin Ryder
sumber
1
Saya telah menemukan banyak alternatif 48 byte lainnya, seperti function(s)all(colSums(outer(s,s,startsWith))<2)tapi tetap saja itu startsWithadalah fungsi yang saya tidak tahu! Temuan yang bagus.
Giuseppe
1
@ Giuseppe Saya mencoba beberapa cara untuk memeriksa apakah matriks tersebut adalah matriks identitas, tetapi juga tidak bisa mendapatkannya di bawah 48 byte. Saya pikir cara ini adalah yang paling mudah dipahami, tapi saya yakin seseorang akan melakukannya!
Robin Ryder
47 byte dengan membalikkan TRUEdan FALSE...
Giuseppe
@ Giuseppe Apakah itu diizinkan? Aturan secara eksplisit meminta kebenaran ketika input adalah kode awalan yang valid. (Juga tautan Anda ke versi 48 byte, tetapi saya menduga saran Anda adalah untuk mengganti== dengan >:-).)
Robin Ryder
0

Ruby, 48 byte

Menggunakan argumen sebagai input dan stdout sebagai output.

p !$*.map{a,*b=$*.rotate!
a.start_with? *b}.any?
ezrast
sumber
0

Scala, 71 byte

(s:Seq[String])=>(for{x<-s;y<-s}yield x!=y&&x.startsWith(y)).forall(!_)
Yakub
sumber
0

Racket 130 byte

(define g #t)(for((n(length l)))(for((i(length l))#:unless(= i n))(when(string-prefix?(list-ref l i)(list-ref l n))(set! g #f))))g

Tidak Disatukan:

(define(f l)
  (define g #t)
  (for ((n (length l)))
    (for ((i (length l)) #:unless (= i n))
      (when (string-prefix? (list-ref l i) (list-ref l n))
        (set! g #f))))g)

Pengujian:

(f [list "Hello" "World"])             
(f [list "Code" "Golf" "Is" "Cool"])
(f [list "1" "2" "3" "4" "5"])
(f [list "This" "test" "case" "is" "true"])          
(f [list "111" "010" "000" "1101" "1010" "1000" "0111" "0010" "1011" 
         "0110" "11001" "00110" "10011" "11000" "00111" "10010"])

(f [list "4" "42"])                             
(f [list "1" "2" "3" "34"])                   
(f [list "This" "test" "case" "is" "false" "t"])
(f [list "He" "said" "Hello"])
(f [list "0" "00" "00001"])
(f [list "Duplicate" "Duplicate" "Keys" "Keys"])

Keluaran:

#t
#t
#t
#t
#t
#f
#f
#f
#f
#f
#f
juga
sumber
0

C (gcc) , 93 byte

p(r,e,f,i,x)char**r;{for(f=i=0;i<e;++i)for(x=0;x<e;++x)f|=x!=i&&strstr(r[i],r[x])==r[i];r=f;}

Cobalah online!

Ganda sederhana untuk loop digunakan strstr(a,b)==auntuk memeriksa preferensi. Terutama ditambahkan karena sepertinya belum ada jawaban C.

LambdaBeta
sumber
88 byte
ceilingcat
0

05AB1E , 13 byte

2.ÆDí«ε`Å?}O_

Terlalu lama .. Awalnya saya punya solusi 9-byte, tetapi gagal untuk kasus uji kunci duplikat.

Cobalah secara online atau verifikasi semua kasus uji .

Penjelasan:

2.Æ             # Get all combinations of two elements from the (implicit) input-list
   Dí           # Duplicate and reverse each pair
     «          # Merge the lists of pairs together
      ε         # Map each pair to:
       `        #  Push both strings to the stack
        Å?      #  And check if the first starts with the second
          }O    # After the map: sum to count all truthy values
            _   # And convert it to truthy if it's 0 or falsey if it's any other integer
                # (which is output implicitly as result)
Kevin Cruijssen
sumber
0

Japt , 8 byte

á2 ËrbÃe

Cobalah

á2 ËrbÃe     :Implicit input of array
á2           :Permutations of length 2
   Ë         :Map each pair
    r        :  Reduce by
     b       :  Get the index of the second in the first - 0 (falsey) if it's a prefix
      Ã      :End map
       e     :All truthy (-1 or >0)
Shaggy
sumber
0

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.

rekursif
sumber