Rozważ tablicę liczb całkowitych:

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

Istnieje wiele sposobów podziału tej listy na kolejne listy podrzędne. Oto trzy:

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

Nazwiemy partycję Y i udoskonalenie innej partycji X, jeśli X można uzyskać z Y , łącząc ponownie niektóre jego listy podrzędne.

Podobnie Bjest z udoskonaleniem A: jeśli połączymy dwie pierwsze i dwie ostatnie podlisty razem, otrzymamy A. Ale nieC jest to wyrafinowanie : musielibyśmy rozdzielić i , aby wyjść z tego. Ponadto każda partycja jest trywialnie udoskonaleniem samego siebie.A91A

Pamiętaj, że w żadnym momencie nie możemy zmieniać kolejności podlist lub elementów.

Wyzwanie

Biorąc pod uwagę dwie partycje (listy list liczb całkowitych) Xi Yustal, czy Yjest to udoskonalenie X.

Możesz założyć, że partycje będą zawierać tylko liczby całkowite od 0do 9włącznie. Nie należy zakładać, że Xi Ysą partycje z tej samej listy (jeśli nie są one również nie są udoskonalenia siebie). Xi / lub Ymogą być puste, ale nigdy nie będą zawierać pustych list podrzędnych.

Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i wypisując wynik przez STDOUT (lub najbliższą alternatywę), wartość zwracaną funkcji lub parametr funkcji (wyjściowej).

Dane wejściowe mogą być pobierane w dowolnym dogodnym formacie ciągu lub listy. Ponieważ elementami będą tylko jednocyfrowe liczby całkowite, możesz pominąć ogranicznik w podlistach, ale upewnij się, że wiodące 0s są możliwe. Można wybrać się Xi Yw odwrotnej kolejności.

Wynik powinien być prawdziwy, jeśli Yjest udoskonaleniem, Xa fałszem w przeciwnym razie.

Twój kod musi być w stanie rozwiązać każdy z poniższych przypadków testowych w ciągu 1 sekundy na rozsądnej maszynie stacjonarnej. (Jest to jedynie kontrola rozsądku w celu uniknięcia prostych rozwiązań z użyciem siły brutalnej).

To jest kod golfowy, więc wygrywa najkrótsza odpowiedź (w bajtach).

Przypadki testowe

Każdy przypadek testowy ma swoją własną linię, zapisaną jako X Y. Używam notacji tablicowej w stylu GolfScript / CJam, aby zaoszczędzić trochę miejsca w poziomie:

Prawda:

[] []
[[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]]

Liderów

Oto fragment kodu, który pozwala wygenerować zarówno zwykłą tabelę wyników, jak i przegląd zwycięzców według języka.

Aby upewnić się, że Twoja odpowiedź się pojawi, zacznij od nagłówka, korzystając z następującego szablonu Markdown:

# Language Name, N bytes

gdzie Njest rozmiar twojego zgłoszenia. Jeśli poprawisz swój wynik, możesz zachować stare wyniki w nagłówku, przekreślając je. Na przykład:

# 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>

Powiązane wyzwania

• Oblicz łączenie i spotykanie się z partycjami

CJam, 13 10 9 bajtów

lr.-F-U-!

Wypróbuj online w interpretatorze CJam .

Dzięki @ MartinBüttner za zasugerowanie genialnego formatu wejściowego @ edc65 .

Dzięki @ jimmy23013 za ulepszenie formatu wejściowego i odgranie 3 dodatkowych bajtów.

I / O

Wejście

Podlisty są oddzielone ;od siebie przez ,:

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

Wynik

1

Jak to działa

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.

W przypadku łańcuchów o różnej długości .-pozostawi znaki w tablicy, które nie mogą być równe liczbom całkowitym 0 lub 15.

Pyth, 19 bajtów

&gF_m{.u+NYdYQqFsMQ

Wypróbuj online: Demonstracja lub Uprząż testowa

Używam formatu krotki / listy Pytha jako danych wejściowych. Po prostu zastąp spacje skrzynek testowych przecinkami.

Wyjaśnienie:

                     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

Ponieważ pseudo-kod jest nadal nieco mylący, przedstawię algorytm na przykładowym wejściu.

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

.u+NYdYCzęść oblicza ciągłych listy zagnieżdżone, które zawierają pierwszy element.

[[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]]

Bjest udoskonaleniem A, jeśli każda ciągła podlista Ajest również ciągłą podlistą B(istnieje tylko jeden wyjątek).

Więc po prostu sprawdzam, czy zbiór ciągłych list Apodrzędnych jest podzbiorem zbioru ciągłych list podrzędnych B( gF_m.u+NYdYQ).

Jedynym wyjątkiem jest sytuacja, gdy pierwsza lista wejściowa zawiera mniej elementów niż druga lista wejściowa. Na przykład <Fm.u+YdYQwróciłby Truepo dane wejściowe [[1]],[[1],[2]].

Dlatego sprawdzam również, czy połączone listy są równe &...qFsMQ.

JavaScript ( ES6 ), 67 70

Edytuj 3 bajty zapisane thx @apsillers

Uruchom poniższy fragment w przeglądarce Firefox, aby przetestować

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>

C, 69 75

Funkcja z 2 parametrami łańcuchowymi, zwracająca 0 lub 1.

Format parametru: lista podrzędna oddzielona spacjami (''), elementy listy oddzielone przecinkami.

Przykład: "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);}

Mniej golfa

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
}

Test Ideone (nieaktualny)

Haskell, 76 bajtów

[]#[]=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

Zwraca TruelubFalse . Przykładowe użycie: [[1,0,9],[1,3,8]] # [[1,0],[9]]-> False.

Proste rekurencyjne podejście: jeśli pierwsze elementy pasują, kontynuuj ogonami, w przeciwnym razie zacznij od nowa, ale połącz dwa elementy na początku drugiej listy. Podstawowymi przypadkami są: obie listy puste -> True; obie listy z jednym elementem -> porównaj je; tylko jedna lista pusta -> False.

CJam, 19 bajtów

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

Wypróbuj online.

I / O

Wejście

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

Wynik

1

Pomysł

Każdą partycję można jednoznacznie zidentyfikować, obserwując następujące dwie właściwości:

• Lista utworzona przez połączenie wszystkich podlist.

• „Punkty odcięcia”, w tym skrajności listy.

Możemy połączyć oba kryteria w jedno, zastępując każdy punkt cięcia podlistą elementów od punktu cięcia do końca listy.

Aby zweryfikować, że dana partycja jest drobniejsza niż inna, musimy tylko sprawdzić, czy grubsza partycja, reprezentowana jak powyżej, jest podzbiorem drobniejszej i czy największe listy obu partycji pasują.

Kod

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.

Dla danych wejściowych z przykładu We / Wy stos jest przechowywany

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

przed wykonaniem -!.

Zauważ, że pierwszy element każdej tablicy ma spację końcową. Dzięki temu porównamy pełną listę pierwszego wejścia z pełną listą drugiego.

CJam, 24 bajty

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

Algorytm

Tutaj po prostu używamy chciwego algorytmu, aby sprawdzić, czy pierwsze Npodlisty drugiej listy można połączyć ze sobą, tworząc pierwszą podlistę pierwszej listy. Gdy takie Nzostanie znalezione, usuwamy pierwsze Npodlisty z drugiej listy i pierwszą podlistę z pierwszej listy i powtarzamy proces.

Idealnie byłoby, gdyby druga lista była udoskonaleniem pierwszej, powinniśmy pozostawić 2 puste listy na stosie. Sprawdzamy to i drukujemy, 1jeśli tak jest. W żadnej innej kombinacji, po pełnym przejściu przez podlisty drugiej listy, nie otrzymamy 2 pustych list. Tak więc 0dla takich przypadków zostanie wydrukowany.

Rozszerzenie kodu

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

Wypróbuj online tutaj lub uruchom pełny pakiet testowy tutaj

C, 120 114 bajtów

#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;}

Ostatnio nie grałem dużo w golfa, więc pomyślałem, że spróbuję tego.

Definiujemy funkcję, R(char* s, char* t)która zwraca, 1jeśli tjest wyrafinowaną partycją si 0inaczej. si tpowinny mieć format, w [DDDD...][DDDD...]...którym każdy Djest kolejnym jednocyfrowym elementem.

Kod testowy:

#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));
}

Powyżej drukuje następujące:

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

Przynajmniej wydaje się, że działa.

Haskell, 52 50 53 bajtów

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

Całkowicie różni się od mojego innego rozwiązania . Używa tego samego sprytnego formatu wejściowego, co odpowiedź @ edc65 , tzn. Elementy są oddzielone za pomocą, ,a lista z .

Przykład użycia: "1,0,9,1,3,8" # "1,0,9 1,3,8"->True .

Drugi parametr jest udoskonaleniem pierwszego, jeśli mają albo jednakowe elementy na każdej pozycji, albo pierwszy jest ,. Muszę dołączyć unikalny token końcowy (-> ..) do obu parametrów, ponieważ zipWithobcina dłuższy parametr i na przykład "1,2,3" # "1,2"też True.

Mathematica, 65 bajtów

f@__=1<0;{}~f~{}=1>0;{a_,b___}~f~{c__,d___}/;a==Join@c:={b}~f~{d}

Matematyka z wyrażeniami regularnymi jest fajna!

ES6 JavaScript, 53 znaki

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

Vintage Javascript, 70 znaków

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

Używa tego samego formatu wejściowego co odpowiedź edc65 .

Pełna wersja demo zawierająca wszystkie przypadki testowe tutaj.

Mathematica, 55 bajtów

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

Definiuje to nienazwaną funkcję, przyjmującą dwie partycje na jednej liście , w odwrotnej kolejności (tj. YPierwsza, Xdruga).

Wyjaśnienie

Equal@@Join@@@#

To sprawdza, czy obie partycje są w rzeczywistości partycjami tej samej listy.

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

To jest golfowa forma mojego podejścia do tego pytania na Mathematica.SE , które zainspirowało to wyzwanie. Zasadniczo partycja jest zdefiniowana jako liczba wskaźników, w których wstawiane są podziały, i to sprawdza, czy wszystkie pozycje podziału Xrównież pojawiają się Ypoprzez zsumowanie długości list podrzędnych.

Python 2, 68 51 bajtów

Dzięki xnor za znaczne oszczędności bajtów!

Anonimowa funkcja, która pobiera dwa ciągi formularza "1,0,9 1,3,8"(wzięte z odpowiedzi C edc65 ) i zwraca Truelub False. Nowa wersja map(None)nie działa już w Pythonie 3.

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

Zestaw testowy:

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

Poprzednie 92-bajtowe rozwiązanie, które przyjmuje dane wejściowe jako "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