Partisi Halus

19

Pertimbangkan array bilangan bulat:

[1, 0, 9, 1, 3, 8]

Ada banyak cara untuk mem-partisi daftar ini menjadi sublists berturut-turut. Inilah tiga:

A: [[1, 0, 9], [1, 3, 8]]
B: [[1], [0, 9], [1, 3], [8]]
C: [[1, 0], [9, 1], [3, 8]]

Kami akan memanggil partisi Y dan memperbaiki partisi X lainnya jika X dapat diperoleh dari Y dengan menggabungkan beberapa sublistenya kembali bersama.

Begitu Bjuga penyempurnaan A: jika kita bergabung dengan dua yang pertama dan dua yang terakhir kembali bersama, kita dapatkan A. Tapi Cini bukan penyempurnaan A: kita harus memisahkan 9dan 1untuk memulihkannya A. Juga, partisi apa pun adalah perbaikan itu sendiri.

Perhatikan bahwa kami tidak diizinkan mengatur ulang setiap daftar atau elemen apa pun.

Tantangan

Diberikan dua partisi (daftar daftar bilangan bulat) Xdan Y, tentukan apakah Ypenyempurnaan X.

Anda mungkin menganggap bahwa partisi hanya akan berisi bilangan bulat dari 0ke 9, inklusif. Anda tidak boleh menganggap itu Xdan Ymerupakan partisi dari daftar yang sama (jika tidak, mereka juga bukan penyempurnaan dari satu sama lain). Xdan / atau Ymungkin kosong tetapi tidak akan pernah berisi daftar kosong.

Anda dapat menulis suatu program atau fungsi, mengambil input melalui STDIN (atau alternatif terdekat), argumen baris perintah atau argumen fungsi dan mengeluarkan hasilnya melalui STDOUT (atau alternatif terdekat), nilai pengembalian fungsi atau parameter fungsi (keluar).

Input dapat diambil dalam format string atau daftar yang nyaman. Karena elemen-elemen tersebut hanya berupa bilangan bulat satu digit, Anda dapat memilih untuk menghilangkan pembatas di dalam sublist, tetapi pastikan bahwa 0s yang terdepan mungkin. Anda dapat memilih untuk mengambil Xdan Ydalam urutan yang berlawanan.

Output harus truthy jika Ymerupakan penyempurnaan dari Xdan falsy sebaliknya.

Kode Anda harus dapat menyelesaikan setiap kasus uji di bawah dalam 1 detik pada mesin desktop yang masuk akal. (Ini hanyalah pemeriksaan kewarasan untuk menghindari solusi brute force sederhana.)

Ini adalah kode golf, jadi jawaban tersingkat (dalam byte) menang.

Uji Kasus

Setiap test case adalah pada barisnya sendiri, ditulis sebagai X Y. Saya menggunakan notasi larik GolfScript / CJam untuk menghemat ruang horisontal:

Benar:

[] []
[[0]] [[0]]
[[1 0 9 1 3 8]] [[1 0 9] [1 3 8]]
[[1 0 9 1 3 8]] [[1 0 9 1 3] [8]]
[[1 0 9 1 3 8]] [[1] [0] [9] [1] [3] [8]]
[[1 0 9] [1 3 8]] [[1 0 9] [1 3 8]]
[[1 0 9] [1 3 8]] [[1] [0 9] [1 3] [8]]
[[9 8 8 5 8 2 7] [5] [1 4] [2 0 0 6 0 8 4 2 6 4 2 3 7 8 7 3 9 5 7 9 8 2 9 5] [3 9 8] [7 1 4 9 7 4 5 9] [3 3 3] [9 0 7 8] [3 9 4 7 2 7 8 0 3 0] [8 2 2 7 3 9 3 2] [2 9 0 8 5 4 1 8 5 5 6 2 0 9 2 7 7 9 2 7] [3 6] [1 2 7 7 4 4 2 9]] [[9 8] [8] [5 8 2] [7] [5] [1 4] [2] [0 0 6] [0] [8 4 2] [6 4] [2] [3] [7 8] [7 3] [9] [5 7 9] [8 2] [9 5] [3] [9 8] [7 1 4] [9 7] [4 5 9] [3 3] [3] [9 0] [7 8] [3] [9] [4] [7 2] [7 8] [0] [3 0] [8 2] [2] [7 3] [9 3] [2] [2] [9] [0] [8 5 4] [1 8] [5 5] [6] [2 0] [9] [2] [7 7 9] [2 7] [3 6] [1 2] [7 7] [4 4 2] [9]]

Falsy:

[[0]] []
[[0]] [[1]]
[[1 0 9]] [[1 0 9] [1 3 8]]
[[1 0 9] [1 3 8]] [[1 0 9 1 3 8]]
[[1 0 9] [1 3 8]] [[1 0 9]]
[[1 0 9] [1 3 8]] [[1 0] [9]]
[[1 0 9] [1 3 8]] [[1 0] [9 1] [3 8]]
[[1] [0 9] [1 3] [8]] [[1 0 9] [1 3 8]]
[[9 8 8 5 8 2 7] [5] [1 4] [2 0 0 6 0 8 4 2 6 4 2 3 7 8 7 3 9 5 7 9 8 2 9 5] [3 9 8] [7 1 4 9 7 4 5 9] [3 3 3] [9 0 7 8] [3 9 4 7 2 7 8 0 3 0] [8 2 2 7 3 9 3 2] [2 9 0 8 5 4 1 8 5 5 6 2 0 9 2 7 7 9 2 7] [3 6] [1 2 7 7 4 4 2 9]] [[9 8] [8] [5 8 2] [7] [5 1] [4] [2] [0 0 6] [0] [8 4 2] [6 4] [2] [3] [7 8] [7 3] [9] [5 7 9] [8 2] [9 5] [3] [9 8] [7 1 4] [9 7] [4 5 9] [3 3] [3] [9 0] [7 8] [3] [9] [4] [7 2] [7 8] [0] [3 0] [8 2] [2] [7 3] [9 3] [2] [2] [9] [0] [8 5 4] [1 8] [5 5] [6] [2 0] [9] [2] [7 7 9] [2 7] [3 6] [1 2] [7 7] [4 4 2] [9]]

Papan peringkat

Berikut ini adalah Stack Snippet untuk menghasilkan leaderboard biasa dan gambaran umum pemenang berdasarkan bahasa.

Untuk memastikan bahwa jawaban Anda muncul, silakan mulai jawaban Anda dengan tajuk utama, menggunakan templat Penurunan harga berikut:

# Language Name, N bytes

di mana Nukuran kiriman Anda. Jika Anda meningkatkan skor Anda, Anda dapat menyimpan skor lama di headline, dengan mencoretnya. Contohnya:

# Ruby, <s>104</s> <s>101</s> 96 bytes

<script>site = 'meta.codegolf'; postID = 5314; isAnswer = true; QUESTION_ID = 51719</script><script src='https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js'></script><script>jQuery(function(){var u='https://api.stackexchange.com/2.2/';if(isAnswer)u+='answers/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJeRCD';else u+='questions/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJO6t)';jQuery.get(u,function(b){function d(s){return jQuery('<textarea>').html(s).text()};function r(l){return new RegExp('<pre class="snippet-code-'+l+'\\b[^>]*><code>([\\s\\S]*?)</code></pre>')};b=b.items[0].body;var j=r('js').exec(b),c=r('css').exec(b),h=r('html').exec(b);if(c!==null)jQuery('head').append(jQuery('<style>').text(d(c[1])));if (h!==null)jQuery('body').append(d(h[1]));if(j!==null)jQuery('body').append(jQuery('<script>').text(d(j[1])))})})</script>

Tantangan Terkait

Martin Ender
sumber
Apakah [[[1 0 9] [1 3 8]] [[1] [0 9] [1 3] [8]]]atau [["109" "138"] ["1" "09" "13" "8"]]menjadi format input yang dapat diterima?
Dennis
@ Dennis Membungkus seluruh input dalam array tampak aneh. Saya tidak menyadari hal itu sebagai praktik standar tetapi mungkin layak untuk pertanyaan meta. Tanpa tanda kurung luar itu jelas tidak apa-apa.
Martin Ender
Saya akan mencoba menulis pertanyaan meta.
Dennis

Jawaban:

6

CJam, 13 10 9 byte

lr.-F-U-!

Cobalah online di juru bahasa CJam .

Terima kasih kepada @ MartinBüttner karena menyarankan format input cerdik @ edc65 .

Terima kasih kepada @ jimmy23013 untuk meningkatkan format input dan bermain golf dengan 3 byte tambahan.

I / O

Memasukkan

Sublists dipisahkan oleh ;dan dari satu sama lain oleh ,:

1;0;9,1;3;8
1,0;9,1;3,8

Keluaran

1

Bagaimana itu bekerja

lr e# Read line and a whitespace-separated token from STDIN.
.- e# Vectorized difference. Pushes the differences of corresponding code points.
F- e# Remove all occurrences of 15 (';' - ',') from the array.
U- e# Remove all occurrences of 0 from the array.
!  e# Push 1 if the resulting array is empty and 0 if not.

Untuk string dengan panjang yang berbeda, .-akan meninggalkan karakter dalam array, yang tidak dapat sama dengan bilangan bulat 0 atau 15.

Dennis
sumber
Jika Anda dapat menggunakan ;sebagai pemisah ... ll.m27m0-!.
jimmy23013
@ jimmy23013: Saya tidak mengerti kenapa tidak. ,dan ;keduanya sintaks array umum (dan tidak ada yang digunakan oleh CJam). Terima kasih!
Dennis
9

Pyth, 19 byte

&gF_m{.u+NYdYQqFsMQ

Cobalah secara online: Demonstrasi atau Uji harness

Saya menggunakan format tuple / list Pyth sebagai input. Cukup ganti spasi kotak uji dengan koma.

Penjelasan:

                     implicit: Q is the evaluated input
    m        Q       map each input list d to:
      .u   dY          reduce with intermediate states over d, initial value = []
        +NY              update initial value N with sum of N and Y (current element of d)
     {                 generate a set
   _                 invert
 gF                  check, if the first element is >= (superset) than the second
&                    and
                sMQ  check, if the joined lists of the input
              qF     are equal

Karena pseudo-code masih sedikit membingungkan, saya akan mendemonstrasikan algoritma menggunakan input contoh.

Input: [[1,0,9],[1,3,8]],[[1],[0,9],[1,3],[8]]

Bagian .u+NYdYmenghitung semua sublists berkelanjutan, yang berisi elemen pertama.

[[1,0,9],[1,3,8]]     => [[], [1,0,9], [1,0,9,1,3,8]]
[[1],[0,9],[1,3],[8]] => [[], [1], [1,0,9], [1,0,9,1,3], [1,0,9,1,3,8]]

Badalah penyempurnaan dari A, jika setiap sublist kontinu Ajuga merupakan sublist kontinu B(hanya ada satu pengecualian).

Jadi saya hanya memeriksa, jika himpunan sublist kontinu Aadalah subset himpunan sublist kontinu dari B( gF_m.u+NYdYQ).

Satu-satunya pengecualian adalah, jika daftar input pertama mengandung lebih sedikit elemen dari daftar input kedua. Misalnya <Fm.u+YdYQakan kembali Trueuntuk input [[1]],[[1],[2]].

Karena itu saya juga memeriksa apakah daftar yang bergabung juga sama &...qFsMQ.

Jakube
sumber
7

JavaScript ( ES6 ), 67 70

Edit 3 byte disimpan thx @apsillers

Jalankan cuplikan di bawah ini di Firefox untuk menguji

f=(a,b)=>a+''==b // same values in the lists ?
&![...a.join(' ')].some((c,p)=>c<','&b.join(c)[p]>c) // splits in a are present in b?

// TEST

out=x=>O.innerHTML += x+'\n';

OK=[
[[],[]],
[[[0]],[[0]]],
[[[1,0,9,1,3,8]],[[1,0,9],[1,3,8]]],
[[[1,0,9,1,3,8]],[[1,0,9,1,3],[8]]],
[[[1,0,9,1,3,8]],[[1],[0],[9],[1],[3],[8]]],
[[[1,0,9],[1,3,8]],[[1,0,9],[1,3,8]]],
[[[1,0,9],[1,3,8]],[[1],[0,9],[1,3],[8]]],
[[[9,8,8,5,8,2,7],[5],[1,4],[2,0,0,6,0,8,4,2,6,4,2,3,7,8,7,3,9,5,7,9,8,2,9,5],[3,9,8],[7,1,4,9,7,4,5,9],[3,3,3],[9,0,7,8],[3,9,4,7,2,7,8,0,3,0],[8,2,2,7,3,9,3,2],[2,9,0,8,5,4,1,8,5,5,6,2,0,9,2,7,7,9,2,7],[3,6],[1,2,7,7,4,4,2,9]],[[9,8],[8],[5,8,2],[7],[5],[1,4],[2],[0,0,6],[0],[8,4,2],[6,4],[2],[3],[7,8],[7,3],[9],[5,7,9],[8,2],[9,5],[3],[9,8],[7,1,4],[9,7],[4,5,9],[3,3],[3],[9,0],[7,8],[3],[9],[4],[7,2],[7,8],[0],[3,0],[8,2],[2],[7,3],[9,3],[2],[2],[9],[0],[8,5,4],[1,8],[5,5],[6],[2,0],[9],[2],[7,7,9],[2,7],[3,6],[1,2],[7,7],[4,4,2],[9]]]
];

KO=[
[[[0]],[]],
[[[0]],[[1]]],
[[[1,0,9]],[[1,0,9],[1,3,8]]],
[[[1,0,9],[1,3,8]],[[1,0,9,1,3,8]]],
[[[1,0,9],[1,3,8]],[[1,0,9]]],
[[[1,0,9],[1,3,8]],[[1,0],[9]]],
[[[1,0,9],[1,3,8]],[[1,0],[9,1],[3,8]]],
[[[1],[0,9],[1,3],[8]],[[1,0,9],[1,3,8]]],
[[[9,8,8,5,8,2,7],[5],[1,4],[2,0,0,6,0,8,4,2,6,4,2,3,7,8,7,3,9,5,7,9,8,2,9,5],[3,9,8],[7,1,4,9,7,4,5,9],[3,3,3],[9,0,7,8],[3,9,4,7,2,7,8,0,3,0],[8,2,2,7,3,9,3,2],[2,9,0,8,5,4,1,8,5,5,6,2,0,9,2,7,7,9,2,7],[3,6],[1,2,7,7,4,4,2,9]],[[9,8],[8],[5,8,2],[7],[5,1],[4],[2],[0,0,6],[0],[8,4,2],[6,4],[2],[3],[7,8],[7,3],[9],[5,7,9],[8,2],[9,5],[3],[9,8],[7,1,4],[9,7],[4,5,9],[3,3],[3],[9,0],[7,8],[3],[9],[4],[7,2],[7,8],[0],[3,0],[8,2],[2],[7,3],[9,3],[2],[2],[9],[0],[8,5,4],[1,8],[5,5],[6],[2,0],[9],[2],[7,7,9],[2,7],[3,6],[1,2],[7,7],[4,4,2],[9]]]
];

dump=l=>l.map(x=>'['+x+']').join(',');

out('YES');
OK.forEach(l=>out(f(l[0],l[1])+' a['+dump(l[0])+'] b['+dump(l[1])+']'));
out('NO');
KO.forEach(l=>out(f(l[0],l[1])+' a['+dump(l[0])+'] b['+dump(l[1])+']'));
<pre id=O></pre>

edc65
sumber
Suatu hari saya harus mengunduh Firefox untuk melihat solusi hebat Anda dalam aksi. :)
Alex A.
@AlexA. bagaimana kamu bisa hidup tanpanya?
edc65
Gunakan repl.it, saya pikir itu mendukung ES6: D
Mark K Cowan
Saya suka bagaimana Anda menamai variabel OKdan KO.
rr-
7

C, 69 75

Fungsi dengan 2 parameter string, menghasilkan 0 atau 1.

Format parameter: sublist dipisahkan dengan spasi (''), elemen daftar dipisahkan dengan koma.

Contoh: "1,0,9 1,3,8" "1,0 9,1,3,8"

f(char*a,char*b){for(;*a-44?*a&&*b==*a:*b<48;a++)b++;return!(*b|*a);}

Kurang golf

int f(char *a, char *b)
{
    // expected in a,b: digit,separator,digit... with separator being ' ' or ','
    for(; *a; a++,b++)
       // ' ' or digit in a must be the same in b
       // comma in a must be comma or space in b
       if (*a != ',' ? *b != *a : *b > *a) return 0;
    return !*b; // must have a null in *b too
}

Ide Tes (ketinggalan jaman)

edc65
sumber
1
Pilihan format input yang cerdas. Saya sudah meminjamnya untuk jawaban Haskell yang lain.
nimi
Saya merobek ide Anda untuk masukan untuk jawaban JS saya, dan ternyata satu byte lebih lama dari versi C Anda sampai saya memutakhirkannya ke ES6 ... Siapa yang mengira bahwa ...
Mark K Cowan
6

Haskell, 76 byte

[]#[]=1<2
[x]#[y]=x==y
x@(a:b)#(c:d:e)|a==c=b#(d:e)|1<2=x#((c++d):e)
_#_=2<1

Pengembalian Trueatau False. Contoh penggunaan: [[1,0,9],[1,3,8]] # [[1,0],[9]]-> False.

Pendekatan rekursif sederhana: jika unsur-unsur pertama cocok, lanjutkan dengan ekor, kalau tidak mulailah dari awal tetapi menyatukan dua unsur di bagian depan daftar kedua. Kasing dasar adalah: kedua daftar kosong -> True; keduanya daftar dengan satu elemen -> bandingkan; hanya satu daftar kosong -> False.

nimi
sumber
6

CJam, 19 byte

q~]{_,,\f>:sS.+}/-!

Cobalah online.

I / O

Memasukkan

[[1 0 9] [1 3 8]] [[1] [0 9] [1 3] [8]]

Keluaran

1

Ide

Setiap partisi dapat diidentifikasi secara unik dengan mengamati dua properti berikut:

  • Daftar ini dibentuk dengan menggabungkan semua daftar.

  • "Titik potong", termasuk yang paling ujung dari daftar.

Kita dapat menggabungkan kedua kriteria menjadi satu dengan mengganti setiap titik pemotongan dengan sublist elemen dari titik potong ke akhir daftar.

Untuk memverifikasi bahwa partisi yang diberikan lebih baik daripada yang lain, kita hanya perlu memverifikasi apakah partisi yang lebih kasar, yang direpresentasikan di atas, adalah subset dari partisi yang lebih halus dan bahwa daftar terbesar dari kedua partisi tersebut cocok.

Kode

q~]   e# Read from STDIN and evaluate.
{     e# For each array P from the input:
  _,, e#   Push [0 ... L], where L == length(P) - 1.
  \f> e#   Push [P[0:] ... P[L]].
  :s  e#   Stringify each P[k:] (flattens).
  S.+ e#   Vectorized concatenation. This appends a space to the first element.
}/    e#
-!    e# Push the logical NOT of the difference A-B to check if A is a subset of B.

Untuk input dari contoh I / O, stack menampung

["109138 " "138"] ["109138 " "09138" "138" "8"]

sebelum dieksekusi -!.

Perhatikan bahwa elemen pertama dari setiap larik memiliki spasi tambahan. Ini memastikan kami membandingkan daftar lengkap input pertama dengan daftar lengkap input kedua.

Dennis
sumber
5

CJam, 24 byte

l~L\{+_a2$1<={;1>L}&}/+!

Algoritma

Di sini kita cukup menggunakan algoritma serakah untuk melihat apakah Nsub-daftar pertama dari daftar kedua dapat digabung bersama untuk membentuk sub-daftar pertama dari daftar pertama. Setelah Nditemukan, kami menghapus Nsub-daftar pertama dari daftar kedua dan sub-daftar pertama dari daftar pertama dan mengulangi prosesnya.

Idealnya, jika daftar kedua adalah penyempurnaan dari yang pertama, kita harus dibiarkan dengan 2 daftar kosong di tumpukan. Kami hanya memeriksa dan mencetak 1jika itu yang terjadi. Dalam kombinasi lain, setelah sepenuhnya mengulangi sub-daftar daftar kedua, kami tidak akan berakhir dengan 2 daftar kosong. Jadi a 0akan dicetak untuk kasus-kasus seperti itu.

Perluasan kode

l~L\{+_a2$1<={;1>L}&}/+!
l~L\                       e# Read the line, evaluate the two lists and put an empty list
                           e# between them
    {               }/     e# Iterate over all sub-lists of the second list
     +                     e# Append the current sub-list to whatever is on stack. Originally
                           e# an empty array, but eventually the sum of first N sub-lists
      _a                   e# Copy this and wrap it in an array
        2$                 e# Copy the first list on top of stack
          1<               e# Get only its first element wrapped in an array. This approach
                           e# is exception safe in case the array was already 0 length
            ={    }&       e# If we have a match, remove both first sub-lists
              ;            e# Remove the first N sub-lists array
               1>          e# Remove the first element from the first array
                 L         e# Put an empty array on stack to repeat the process
                      +!   e# If we are left with two empty arrays, sum them and do logical
                           e# not to get 1. If any of the arrays is non-empty, logical not
                           e# gives 0

Cobalah online di sini atau jalankan test suite lengkap di sini

Pengoptimal
sumber
3

C, 120 114 byte

#define C(x),x+=(*x/93)*(1+!!x[1])|1
o;R(char*s,char*t){for(o=1;*s;o&=*s==t[2*(*t==93&&93>*s)]C(s)C(t));return o;}

Saya belum bermain golf baru-baru ini, jadi saya pikir saya akan mencoba yang ini.

Kami mendefinisikan fungsi R(char* s, char* t)yang mengembalikan 1jika tadalah partisi yang disempurnakan s, dan 0sebaliknya. sdant diharapkan dalam format [DDDD...][DDDD...]...Di mana masing D- masing elemen satu digit.

Kode pengujian:

#include "stdio.h"

int main(int argc, char** argv) {
    char* str1, *str2;
    str1 = "[109][138]";
    str2 = "[1][09][13][8]";
    printf("Input: %s, %s --> %d\n", str1, str2, R(str1, str2));

    str1 = "[109][138]";
    str2 = "[1][19][13][8]";
    printf("Input: %s, %s --> %d\n", str1, str2, R(str1, str2));

    str1 = "[109][138]";
    str2 = "[10][91][3][8]";
    printf("Input: %s, %s --> %d\n", str1, str2, R(str1, str2));
}

Di atas mencetak yang berikut ini:

Input: [109][138], [1][09][13][8] --> 1
Input: [109][138], [1][19][13][8] --> 0
Input: [109][138], [10][91][3][8] --> 0

Tampaknya berhasil, setidaknya.

BrainSteel
sumber
3

Haskell, 52 50 53 byte

x#y=and$zipWith(\a b->a==b||a==',')(x++"..")(y++"..")

Sangat berbeda dari solusi saya yang lain . Menggunakan format input pintar yang sama dengan jawaban @ edc65 , yaitu elemen dipisahkan dengan ,dan dicantumkan dengan .

Contoh penggunaan: "1,0,9,1,3,8" # "1,0,9 1,3,8"-> True.

Parameter kedua adalah penyempurnaan dari yang pertama, jika mereka memiliki elemen yang sama di setiap posisi atau yang pertama ,. Saya harus menambahkan token ujung unik (-> ..) untuk kedua parameter, karena zipWithmemotong parameter yang lebih panjang dan misalnya "1,2,3" # "1,2"juga akan True.

nimi
sumber
1
(\a b->a==b||a>b)hanya (>=).
alephalpha
tidak akan menambahkan hanya "."alih-alih ".."bekerja juga?
haskeller bangga
ini gagal "2"#"1"karena fungsi hanya memeriksa jika nilainya lebih besar, tidak sama
bangga haskeller
@alephalpha: oh sayang, betapa bodohnya aku mengabaikan hal itu. Tapi bagaimanapun juga itu salah. Lihat komentar lain.
nimi
@proudhaskeller: suntingan menit terakhir. Ya, ini adalah bug. Memperbaikinya. Terima kasih sudah mencari tahu. BTW, satu titik "."tidak akan bekerja, karena itu akan memberikan positif palsu "2,1" # "2"yang pertama kali akan diperluas "2,1." # "2."dan kemudian dipotong oleh zipWithke "2," # "2.". Koma di string pertama cocok dengan semuanya.
nimi
2

Mathematica, 65 byte

f@__=1<0;{}~f~{}=1>0;{a_,b___}~f~{c__,d___}/;a==Join@c:={b}~f~{d}
alephalpha
sumber
1
Solusi bagus FYI, saya punya solusi 59-byte yang tidak menggunakan rekursi (atau beberapa definisi).
Martin Ender
2

Matematika dengan ekspresi reguler itu menyenangkan!

ES6 Javascript, 53 karakter

(a,b)=>RegExp('^'+a.replace(/,/g,'[ ,]')+'$').test(b)

Javascript Vintage, 70 karakter

function f(a,b){return RegExp('^'+a.replace(/,/g,'[ ,]')+'$').test(b)

Menggunakan format input yang sama dengan jawaban edc65 .

Demo lengkap termasuk semua kasus uji di sini.

Mark K Cowan
sumber
Pintar! Tidak pernah memikirkan ekspresi reguler untuk tugas ini.
edc65
Saya menulis sebuah program perl yang memfaktorkan bilangan bulat menggunakan fungsi rekursif yang menemukan faktor prima menggunakan ekspresi reguler backtracking ... Mereka tidak cantik dan jelas tidak cepat, tetapi mereka dapat melakukan beberapa hal keren!
Mark K Cowan
Saya juga menulis generator parser, yang mengubah spesifikasi bahasa menjadi ekspresi reguler, dan ekspresi reguler kemudian dapat digunakan untuk mem-parsing ekspresi dalam bahasa yang ditentukan. Pada dasarnya, "kompilasi" spesifikasi bahasa yang bisa dibaca manusia menjadi ekspresi reguler yang "dapat dieksekusi". github.com/battlesnake/d-slap Ekspresi reguler yang dihasilkan untuk parsing ekspresi pemahaman AngularJS adalah sekitar 400-500 karakter ...
Mark K Cowan
2

Mathematica, 55 byte

Equal@@Join@@@#&&SubsetQ@@(Accumulate[Length/@#]&)/@##&

Ini mendefinisikan fungsi yang tidak disebutkan namanya, mengambil dua partisi dalam satu daftar , dalam urutan terbalik (yaitu Ypertama, Xkedua).

Penjelasan

Equal@@Join@@@#

Ini memeriksa bahwa kedua partisi sebenarnya adalah partisi dari daftar yang sama.

SubsetQ@@(Accumulate[Length/@#]&)/@##

Ini adalah bentuk golf dari pendekatan saya dalam pertanyaan ini di Mathematica.SE , yang menginspirasi tantangan ini. Pada dasarnya, partisi didefinisikan sebagai sejumlah indeks tempat pemisahan dimasukkan, dan ini memeriksa apakah semua posisi pemisahan Xjuga muncul Ydengan mengakumulasikan panjang sublists.

Martin Ender
sumber
2

Python 2, 68 51 byte

Terima kasih kepada xnor untuk penghematan byte yang cukup besar!

Fungsi anonim yang mengambil dua string formulir "1,0,9 1,3,8"(diambil dari jawaban C edc65 ) dan mengembalikan Trueatau False. Versi baru map(None)tanpa lagi berfungsi di Python 3.

lambda a,b:all(i in[j,","]for i,j in map(None,a,b))

Test suite:

>>> def runTests(f):
    assert f("1,0,9 1,3,8","1 0,9 1,3 8")
    assert not f("1,0,9 1,3,8","1,0 9,1 3,8")
    assert f("1 0,9 1,3 8","1 0,9 1,3 8")
    assert not f("1 0,9 1,3 8","1,0,9 1,3,8")
    assert not f("1 0,9 1,3 8","1 0,9 1,3")
    assert not f("1 0,9 1,3,8","1 0,9 1,3")
    print("All tests pass.")


>>> runTests(lambda a,b:all(i in[j,","]for i,j in map(None,a,b)))
All tests pass.

Solusi 92 byte sebelumnya yang mengambil input sebagai "109 138":

def R(a,b):
 r=1
 for i in b.split():r&=a.find(i)==0;a=a[len(i):].strip()
 return r and""==a
DLosc
sumber
Saya pikir Anda dapat menghindari melakukan pemeriksaan panjang eksplisit dengan memetakan Tidak Ada . Kasus ketika satu daftar lebih panjang dari yang lain ditolak di mana satu daftar memiliki Nonetetapi indeks lainnya memiliki nomor, karena i==j or"0">i>jtidak dapat menampung.
xnor
Kecuali saya melewatkan sesuatu, tes kedua bisa saja i==','. Ini memungkinkan Anda menggabungkan tes sebagai i in[',',j](kami tidak dapat melakukan i in ','+j) karena jmungkin None.
xnor
@ xnor Wow, terima kasih. # 1 tidak terpikir oleh saya karena saya cukup terbiasa berpikir dengan Python 3 sekarang; # 2 tidak terpikir olehku karena "bagaimana jika bada nomor di tempat itu?" ... lupa dengan format input ini, itu tidak mungkin.
DLosc