Verfeinerte Partitionen

19

Betrachten Sie ein Array von Ganzzahlen:

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

Es gibt viele Möglichkeiten, diese Liste in aufeinanderfolgende Unterlisten zu unterteilen. Hier sind drei:

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

Wir werden eine Partition Y aufrufen und eine andere Partition X verfeinern, wenn X von Y erhalten werden kann, indem einige seiner Unterlisten wieder zusammengefügt werden.

Dies Bist eine Verfeinerung von A: Wenn wir die ersten beiden und die letzten beiden Unterlisten wieder zusammenfügen, erhalten wir A. Aber es Cist keine Verfeinerung von A: Wir müssten das 9und das aufteilen, um uns davon 1zu erholen A. Außerdem ist jede Partition eine triviale Verfeinerung ihrer selbst.

Beachten Sie, dass wir zu keinem Zeitpunkt Unterlisten oder Elemente neu anordnen dürfen.

Die Herausforderung

Bei zwei gegebenen Partitionen (Listen von Listen von ganzen Zahlen) Xund Ybestimmen Sie, ob Yeine Verfeinerung von X.

Sie können davon ausgehen, dass die Partitionen nur ganze Zahlen von 0bis 9einschließlich enthalten. Sie dürfen das nicht annehmen Xund Ysind Partitionen derselben Liste (wenn dies nicht der Fall ist, sind sie auch keine Verfeinerungen voneinander). Xund / oder Yleer sein, aber niemals leere Unterlisten enthalten.

Sie können ein Programm oder eine Funktion schreiben, indem Sie eine Eingabe über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen und das Ergebnis über STDOUT (oder die nächstgelegene Alternative), einen Funktionsrückgabewert oder einen Funktionsparameter (out) ausgeben.

Die Eingabe kann in einem beliebigen geeigneten Zeichenfolge- oder Listenformat erfolgen. Da es sich bei den Elementen nur um einstellige Ganzzahlen handelt, können Sie ein Trennzeichen in den Unterlisten weglassen, aber sicherstellen, dass führende 0s möglich sind. Sie können wählen, Xund Yin umgekehrter Reihenfolge zu nehmen .

Die Ausgabe sollte wahr sein, wenn Yes sich um eine Verfeinerung handelt, Xund ansonsten falsch .

Ihr Code muss in der Lage sein, jeden der folgenden Testfälle in 1 Sekunde auf einem vernünftigen Desktop-Computer zu lösen. (Dies ist lediglich eine Überprüfung der geistigen Gesundheit, um einfache Brute-Force-Lösungen zu vermeiden.)

Dies ist Codegolf, daher gewinnt die kürzeste Antwort (in Bytes).

Testfälle

Jeder Testfall steht in einer eigenen Zeile, geschrieben als X Y. Ich verwende die Array-Notation im GolfScript / CJam-Stil, um etwas horizontalen Platz zu sparen:

Wahrheit:

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

Falsch:

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

Bestenlisten

Hier ist ein Stack-Snippet, um sowohl eine reguläre Rangliste als auch eine Übersicht der Gewinner nach Sprache zu generieren.

Um sicherzustellen, dass Ihre Antwort angezeigt wird, beginnen Sie Ihre Antwort mit einer Überschrift. Verwenden Sie dazu die folgende Markdown-Vorlage:

# Language Name, N bytes

Wo Nist die Größe Ihres Beitrags? Wenn Sie Ihre Punktzahl verbessern, können Sie alte Punkte in der Überschrift behalten, indem Sie sie durchstreichen. Zum Beispiel:

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

Verwandte Herausforderungen

Martin Ender
quelle
Wäre [[[1 0 9] [1 3 8]] [[1] [0 9] [1 3] [8]]]oder [["109" "138"] ["1" "09" "13" "8"]]wäre ein akzeptables Eingabeformat?
Dennis
@Dennis Es scheint seltsam, den gesamten Eingang in ein Array zu packen. Mir ist das nicht bewusst, aber es könnte eine Meta-Frage wert sein. Ohne diese äußeren Klammern ist es definitiv in Ordnung.
Martin Ender,
Ich werde versuchen, eine Meta-Frage zu schreiben.
Dennis

Antworten:

6

CJam, 13 10 9 Bytes

lr.-F-U-!

Probieren Sie es online im CJam-Interpreter aus .

Vielen Dank an @ MartinBüttner, der das geniale Eingabeformat von @ edc65 vorgeschlagen hat .

Vielen Dank an @ jimmy23013 für die Verbesserung des Eingabeformats und das Ausschalten von 3 zusätzlichen Bytes.

I / O

Eingang

Unterlisten werden durch ;und von einander getrennt durch ,:

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

Ausgabe

1

Wie es funktioniert

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.

Bei Zeichenfolgen unterschiedlicher Länge .-verbleiben Zeichen im Array, die nicht den ganzen Zahlen 0 oder 15 entsprechen können.

Dennis
quelle
Wenn Sie verwenden können , ;als Trennzeichen ... ll.m27m0-!.
Jimmy23013
@ jimmy23013: Ich verstehe nicht warum nicht. ,und ;sind beide gemeinsame Array-Syntax (und keine von ihnen wird von CJam verwendet). Vielen Dank!
Dennis
9

Pyth, 19 Bytes

&gF_m{.u+NYdYQqFsMQ

Probieren Sie es online aus: Vorführ- oder Testgeschirr

Ich benutze Pyths Tupel / Listen-Format als Eingabe. Ersetzen Sie einfach die Leerzeichen der Testfälle durch Kommas.

Erläuterung:

                     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

Da der Pseudocode immer noch etwas verwirrend ist, werde ich den Algorithmus anhand einer Beispieleingabe demonstrieren.

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

Der .u+NYdYTeil berechnet alle fortlaufenden Unterlisten, die das erste Element enthalten.

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

Bist eine Verfeinerung der A, wenn jede fortlaufende Unterliste von Aauch eine fortlaufende Unterliste von ist B(es gibt nur eine Ausnahme).

Also überprüfe ich einfach, ob die Menge der fortlaufenden Unterlisten von Aeine Teilmenge der Menge der fortlaufenden Unterlisten von B( gF_m.u+NYdYQ) ist.

Die einzige Ausnahme ist, wenn die erste Eingabeliste weniger Elemente enthält als die zweite Eingabeliste. Zum Beispiel <Fm.u+YdYQwürde Truefür die Eingabe zurückkehren [[1]],[[1],[2]].

Deshalb überprüfe ich auch, ob die verbundenen Listen auch gleich sind &...qFsMQ.

Jakube
quelle
7

JavaScript ( ES6 ), 67, 70

Bearbeite 3 Bytes, die dank @apsillers gespeichert wurden

Führen Sie das folgende Snippet in Firefox aus, um es zu testen

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
quelle
Eines Tages muss ich Firefox herunterladen, um Ihre großartigen Lösungen in Aktion zu sehen. :)
Alex A.
@AlexA. wie kannst du ohne leben?
Edc65
Verwenden Sie repl.it, ich denke, dass ES6 unterstützt: D
Mark K Cowan
Mir gefällt, wie Sie die Variablen OKund benannt haben KO.
rr
7

C, 69 75

Eine Funktion mit 2 Zeichenfolgenparametern, die 0 oder 1 zurückgibt.

Parameterformat: durch Leerzeichen ('') getrennte Unterliste, durch Komma getrennte Listenelemente.

Beispiel: "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);}

Weniger golfen

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 (veraltet)

edc65
quelle
1
Clevere Wahl des Eingabeformats. Ich habe es für eine andere Haskell-Antwort ausgeliehen.
Nimi
Ich habe Ihre Idee zur Eingabe für meine JS-Antwort abgerissen und es stellte sich heraus, dass sie ein Byte länger war als Ihre C-Version, bis ich sie auf ES6 aufrüstete ... Wer hätte das gedacht ...
Mark K Cowan
6

Haskell, 76 Bytes

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

Rückgabe Trueoder False. Anwendungsbeispiel: [[1,0,9],[1,3,8]] # [[1,0],[9]]-> False.

Einfacher rekursiver Ansatz: Wenn die ersten Elemente übereinstimmen, fahren Sie mit den Endpunkten fort. Beginnen Sie ansonsten von vorne, aber verketten Sie die beiden Elemente am Anfang der zweiten Liste. Basisfälle sind: beide Listen leer -> True; beide Listen mit einem Element -> vergleichen; nur eine Liste leer -> False.

nimi
quelle
6

CJam, 19 Bytes

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

Probieren Sie es online aus.

I / O

Eingang

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

Ausgabe

1

Idee

Jede Partition kann eindeutig identifiziert werden, indem die folgenden zwei Eigenschaften beachtet werden:

  • Die Liste, die durch Verketten aller Unterlisten erstellt wurde.

  • Die "Schnittpunkte", einschließlich der Extreme der Liste.

Wir können beide Kriterien zu einem kombinieren, indem wir jeden Schnittpunkt durch die Unterliste der Elemente vom Schnittpunkt bis zum Ende der Liste ersetzen.

Um zu überprüfen, ob eine bestimmte Partition feiner ist als eine andere, müssen wir nur überprüfen, ob die wie oben dargestellte gröbere Partition eine Teilmenge der feineren ist und ob die größten Listen beider Partitionen übereinstimmen.

Code

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.

Für die Eingabe aus dem E / A-Beispiel gilt der Stapel

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

vor der Ausführung -!.

Beachten Sie, dass das erste Element jedes Arrays ein Leerzeichen am Ende enthält. Dadurch wird sichergestellt, dass die vollständige Liste der ersten Eingabe mit der vollständigen Liste der zweiten Eingabe verglichen wird.

Dennis
quelle
5

CJam, 24 Bytes

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

Algorithmus

Hier verwenden wir einfach einen gierigen Algorithmus, um zu sehen, ob erste NUnterlisten der zweiten Liste zusammengeführt werden können, um die erste Unterliste der ersten Liste zu bilden. Sobald dies Ngefunden ist, entfernen wir die ersten NUnterlisten aus der zweiten Liste und die erste Unterliste aus der ersten Liste und wiederholen den Vorgang.

Wenn die zweite Liste eine Verfeinerung der ersten war, sollten im Idealfall 2 leere Listen auf dem Stapel verbleiben. Wir prüfen das nur und drucken, 1ob das der Fall ist. In jeder anderen Kombination erhalten wir, nachdem wir die Unterlisten der zweiten Liste vollständig durchlaufen haben, keine zwei leeren Listen. Daher 0wird für solche Fälle ein gedruckt.

Code-Erweiterung

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

Probieren Sie es hier online aus oder führen Sie die komplette Testsuite hier aus

Optimierer
quelle
3

C, 120 114 Bytes

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

Ich habe in letzter Zeit nicht viel Golf gespielt, also dachte ich, ich würde es ausprobieren.

Wir definieren eine Funktion, R(char* s, char* t)die zurückgibt, 1wenn tes sich um eine verfeinerte Partition von handelt s, und 0ansonsten. sund twerden in dem Format erwartet, in dem [DDDD...][DDDD...]...jedes DElement ein anderes einstelliges Element ist.

Testcode:

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

Oben wird Folgendes gedruckt:

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

Zumindest scheint es zu funktionieren.

BrainSteel
quelle
3

Haskell, 52 50 53 Bytes

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

Ganz anders als meine andere Lösung . Verwendet dasselbe clevere Eingabeformat wie die Antwort von @ edc65 , dh Elemente werden mit ,und Listen mit getrennt .

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

Der zweite Parameter ist eine Verfeinerung des ersten, wenn sie an jeder Position gleiche Elemente haben oder der erste ist ,. Ich muss an ..beide Parameter ein eindeutiges End-Token (-> ) anhängen , da zipWithder längere Parameter abgeschnitten wird und beispielsweise "1,2,3" # "1,2"auch wäre True.

nimi
quelle
1
(\a b->a==b||a>b)ist einfach (>=).
Alephalpha
würde ich nicht auch nur "."anstatt zu ".."arbeiten hinzufügen ?
stolzer haskeller
dies schlägt fehl, "2"#"1"weil die funktionen nur
prüfen
@alephalpha: oh je, wie dumm von mir, das zu übersehen. Aber es ist trotzdem falsch. Siehe andere Kommentare.
Nimi
@ proudhaskeller: verdammt noch mal in letzter Minute bearbeitet. Ja, das ist ein Fehler. Behoben. Danke, dass Sie es herausgefunden haben. BTW, ein einzelner Punkt "."wird nicht funktionieren, denn es wäre ein falsch positiv geben für "2,1" # "2"welche zuerst erweitern würde "2,1." # "2."und dann durch abgeschnitten zipWithzu "2," # "2.". Ein Komma in der ersten Zeichenfolge stimmt mit allem überein.
Nimi
2

Mathematica, 65 Bytes

f@__=1<0;{}~f~{}=1>0;{a_,b___}~f~{c__,d___}/;a==Join@c:={b}~f~{d}
Alephalpha
quelle
1
Gute Lösung. Zu Ihrer Information, ich habe eine 59-Byte-Lösung, die keine Rekursion (oder mehrere Definitionen) verwendet.
Martin Ender
2

Mathematik mit regulären Ausdrücken macht Spaß!

ES6 Javascript, 53 Zeichen

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

Vintage Javascript, 70 Zeichen

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

Verwendet dasselbe Eingabeformat wie die Antwort von edc65 .

Vollständige Demo mit allen Testfällen hier.

Mark K. Cowan
quelle
Klug! Ich habe nie über reguläre Ausdrücke für diese Aufgabe nachgedacht.
Edc65
Ich habe ein Perl-Programm geschrieben, das Ganzzahlen mithilfe einer rekursiven Funktion faktorisiert, die Primfaktoren mithilfe eines regulären Backtracking-Ausdrucks ermittelt hat.
Mark K Cowan
Ich habe auch einen Parser-Generator geschrieben, der eine Sprachspezifikation in einen regulären Ausdruck umwandelt. Mit diesem regulären Ausdruck können dann Ausdrücke in der angegebenen Sprache analysiert werden. Grundsätzlich wird eine für Menschen lesbare Sprachspezifikation zu einem "ausführbaren" regulären Ausdruck "kompiliert". github.com/battlesnake/d-slap Der generierte reguläre Ausdruck zum Parsen von AngularJS-Verständnisausdrücken ist ungefähr 400-500 Zeichen lang ...
Mark K Cowan
2

Mathematica, 55 Bytes

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

Dies definiert eine unbenannte Funktion, die die beiden Partitionen in einer einzigen Liste in umgekehrter Reihenfolge (dh Yerste, Xzweite) aufnimmt.

Erläuterung

Equal@@Join@@@#

Dadurch wird überprüft, ob beide Partitionen tatsächlich Partitionen derselben Liste sind.

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

Dies ist eine gelungene Form meines Ansatzes in dieser Frage über Mathematica.SE , die diese Herausforderung inspiriert hat. Grundsätzlich wird eine Partition als eine Anzahl von Indizes definiert, in die Teilungen eingefügt werden, und dies überprüft, ob alle Teilungspositionen Xauch in erscheinen, Yindem die Längen der Unterlisten akkumuliert werden.

Martin Ender
quelle
2

Python 2, 68 51 Bytes

Vielen Dank an xnor für die erheblichen Byteeinsparungen!

Anonyme Funktion, die zwei Zeichenfolgen der Form annimmt"1,0,9 1,3,8" (aus der C-Antwort von edc65 entnommen ) und Trueoder zurückgibt False. Neue Version mit map(None)funktioniert nicht mehr in Python 3.

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

Testsuite:

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

Vorherige 92-Byte-Lösung, bei der die Eingabe folgendermaßen erfolgt "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
quelle
Ich denke, Sie können eine explizite Längenprüfung vermeiden, indem Sie None zuordnen . Der Fall, dass eine Liste länger als eine andere ist, wird abgelehnt, wenn eine Liste Noneeine Nummer hat , der andere Index jedoch eine Nummer hat, da er i==j or"0">i>jnicht enthalten kann.
16.
Wenn mir nichts fehlt, kann der zweite Test einfach sein i==','. Auf diese Weise können Sie die Tests so kombinieren, wie es der Fall sein könnte i in[',',j](was wir nicht können i in ','+j) . jNone
16.
@xnor Wow, danke. Nr. 1 ist mir nicht in den Sinn gekommen, weil ich es ziemlich gewohnt bin, jetzt in Python 3 zu denken. Nr. 2 ist mir nicht eingefallen, weil "Was ist, wenn ban dieser Stelle eine Nummer ist?" ... zu vergessen, dass dies mit diesem Eingabeformat nicht möglich ist.
DLosc