Dopracowane partycje

19

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

Martin Ender
źródło
Lepiej [[[1 0 9] [1 3 8]] [[1] [0 9] [1 3] [8]]]lub [["109" "138"] ["1" "09" "13" "8"]]być akceptowalny formatu wejściowego?
Dennis
@Dennis Zawijanie całego wejścia w tablicy wydaje się dziwne. Nie jestem świadomy tego, że jest to standardowa praktyka, ale może być warte meta pytania. Bez tych zewnętrznych wsporników jest zdecydowanie w porządku.
Martin Ender
Spróbuję napisać meta pytanie.
Dennis

Odpowiedzi:

6

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.

Dennis
źródło
Jeśli można użyć ;jako separator ... ll.m27m0-!.
jimmy23013
@ jimmy23013: Nie rozumiem, dlaczego nie. ,i ;oba są typową składnią tablicową (i żadna z nich nie jest używana przez CJam). Dzięki!
Dennis
9

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.

Jakube
źródło
7

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>

edc65
źródło
Któregoś dnia będę musiał pobrać Firefoksa, aby zobaczyć Twoje niesamowite rozwiązania w akcji. :)
Alex A.
@AlexA. jak możesz bez niego żyć?
edc65
Użyj repl.it, myślę, że obsługuje ES6: D
Mark K Cowan
Podoba mi się, jak nazwałeś zmienne OKi KO.
rr-
7

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)

edc65
źródło
1
Sprytny wybór formatu wejściowego. Pożyczyłem to na kolejną odpowiedź Haskella.
nimi
Zerwałem twój pomysł na dane wejściowe do mojej odpowiedzi JS i okazało się, że był o jeden bajt dłuższy niż wersja C, dopóki nie zaktualizowałem go do ES6 ... Kto by się tego spodziewał ...
Mark K Cowan
6

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.

nimi
źródło
6

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.

Dennis
źródło
5

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

Optymalizator
źródło
3

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.

BrainSteel
źródło
3

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.

nimi
źródło
1
(\a b->a==b||a>b)jest po prostu (>=).
alephalpha
nie dodawalibyśmy tylko "."zamiast ".."pracy?
dumny haskeller
to się nie udaje, "2"#"1"ponieważ funkcje sprawdzają tylko, czy wartości są większe, a nie równe
dumny haskeller
@alephalpha: o kochanie, jak głupio z mojej strony przeoczyłem to. Ale i tak jest źle. Zobacz inne komentarze.
nimi
@proudhaskeller: cholerne zmiany w ostatniej chwili. Tak, to jest błąd. Naprawione. Dzięki za informację. BTW, pojedyncza kropka "."nie zadziała, ponieważ dałaby fałszywy wynik dodatni, dla "2,1" # "2"którego najpierw rozwinąłaby się, "2,1." # "2."a następnie zostałaby obcięta zipWithdo "2," # "2.". Przecinek w pierwszym ciągu pasuje do wszystkiego.
nimi
2

Mathematica, 65 bajtów

f@__=1<0;{}~f~{}=1>0;{a_,b___}~f~{c__,d___}/;a==Join@c:={b}~f~{d}
alephalpha
źródło
1
Niezłe rozwiązanie. Do Twojej dyspozycji mam 59-bajtowe rozwiązanie, które nie korzysta z rekurencji (lub wielu definicji).
Martin Ender
2

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.

Mark K Cowan
źródło
Sprytny! Nigdy nie myślałem o wyrażeniach regularnych do tego zadania.
edc65
Napisałem program w perlu, który rozkładał liczby całkowite za pomocą funkcji rekurencyjnej, która znajdował czynniki pierwsze za pomocą wyrażenia regularnego cofania ... Nie są ładne i zdecydowanie nie są szybkie, ale potrafią robić fajne rzeczy!
Mark K Cowan
Napisałem również generator parsera, który konwertuje specyfikację języka na wyrażenie regularne, a tego wyrażenia regularnego można następnie użyć do analizy wyrażeń w określonym języku. Zasadniczo „kompilowanie” specyfikacji języka czytelnego dla człowieka do „wykonywalnego” wyrażenia regularnego. github.com/battlesnake/d-slap Wygenerowane wyrażenie regularne do analizowania wyrażeń AngularJS ma długość około 400-500 znaków ...
Mark K Cowan
2

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.

Martin Ender
źródło
2

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
DLosc
źródło
Myślę, że można uniknąć wykonywania jawnej kontroli długości poprzez mapowanie None . Przypadek, w którym jedna lista jest dłuższa od drugiej, jest odrzucany, gdy jedna lista ma, Noneale drugi indeks ma numer, ponieważ i==j or"0">i>jnie może zostać zatrzymany.
xnor
Chyba że czegoś mi brakuje, drugi test może być po prostu i==','. Pozwala to łączyć testy jako i in[',',j](nie możemy tego zrobić i in ','+j), ponieważ jmogą być None.
xnor
@xnor Wow, dzięki. # 1 nie przyszło mi do głowy, ponieważ jestem teraz dość przyzwyczajony do myślenia w Pythonie 3; # 2 nie przyszło mi do głowy, ponieważ „a co, jeśli bw tym miejscu jest liczba?” ... zapominając, że przy tym formacie wejściowym nie jest to możliwe.
DLosc