In dieser Aufgabe betrachten wir Arrays positiver Ganzzahlen wie diese:

3 18 321 17 4 4 51 1 293 17

Die Eingabe umfasst ein Paar solcher Arrays mit beliebiger, möglicherweise unterschiedlicher positiver Länge. Bestimmen Sie, ob eine Gesamtordnung ≤ _X ⊂ N × N , wobei N die Menge positiver Ganzzahlen ist, so existiert, dass beide Eingabearrays in Bezug auf ≤ _X in Ordnung sind . Beachten Sie, dass (A ≤ _X B ∧ B ≤ _X A) ↔ A = B gelten muss, dh zwei Zahlen werden unter ≤ _X genau dann als gleich angesehen, wenn sie dieselbe Zahl sind.

Zum Beispiel, wenn die Eingabe das Array-Paar war

7 2 1 1 4 12 3
9 8 7 2 5 1

dann solltest du herausfinden, ob eine Gesamtordnung ≤ _X existiert, so dass

7 ≤ _X 2 ≤ _X 1 ≤ _X 1 ≤ _X 4 ≤ _X 12 ≤ _X 3

und

9 ≤ _X 8 ≤ _X 7 ≤ _X 2 ≤ _X 5 ≤ _X 1.

Ihre Übermittlung kann eine Unterroutine oder ein Programm sein, das / das zwei Arrays (wie oben angegeben) von Eingaben auf implementierungsdefinierte Weise empfängt, berechnet, ob eine Gesamtreihenfolge ≤ _{X vorhanden ist} , die die oben genannten Anforderungen erfüllt, und einen Wert zurückgibt, der "Ja" oder einen anderen darstellt Wert für "Nr." Die Auswahl dieser Werte ist beliebig, bitte dokumentieren Sie sie.

Sie können davon ausgehen, dass die Eingabearrays jeweils nicht mehr als 2 ¹⁵ - 1 Elemente enthalten und dass jedes ihrer Elemente im Bereich von 1 bis einschließlich 2 ¹⁵ - 1 liegt. Möglicherweise müssen alle Arrays durch einen konstanten Sentinel außerhalb des oben genannten Bereichs wie 0 abgeschlossen werden. Bitte geben Sie an, welcher Sentinel benötigt wird. Sie können die Längen der Arrays als zusätzliche Eingabe benötigen, wenn die Länge nicht aus den Arrays selbst abgeleitet werden kann (z. B. in Sprachen wie C). Zusätzlich zum Verbot von Standardschlupflöchern dürfen Sie keine topologischen Sortierroutinen verwenden.

Diese Herausforderung ist Code Golf. Die Einreichung mit der geringsten Anzahl von Zeichen gewinnt.

Pyth, 28 22

L.AmqdSdmfhTmxhkbek^b2

Erstellt eine Funktion y, die Sie mit einem Tupel aufrufen können, das die beiden Arrays enthält. Gibt "True" zurück, wenn eine Gesamtbestellung vorhanden ist, andernfalls "False".

Ein Hilfsprogramm, das die obige Funktion mit stdin definiert und aufruft:

L.AmqdSdmfhTmxhkbek^b2y,rw7rw7 

Probieren Sie es hier aus.

Wir lesen zuerst beide Arrays. Dann werden wir alle Kombinationen beider Arrays erstellen. Dann nehmen wir für jede Kombination an, dass das erste Array maßgeblich ist, und prüfen, ob es mit dem zweiten Array übereinstimmt.

GolfScript, 25 Bytes

:A{:a;A{.a--.{a?}$=!},},!

Versuchen Sie diesen Code online.

Nimmt ein Array von zwei (oder mehr!) Arrays auf dem Stapel auf; Gibt 1 (true) zurück, wenn jedes Paar von Eingabearrays eine kompatible Gesamtreihenfolge hat, oder 0 (false).

Es funktioniert, indem jedes mögliche Paar von Eingabearrays (einschließlich jedes mit sich selbst gepaarten Arrays) durchlaufen wird, die Elemente im ersten Array nach der Position sortiert werden, an der sie im zweiten Array zum ersten Mal auftreten (wobei nicht gefundene ignoriert werden) und überprüft werden dass die resultierende Reihenfolge mit dem Original übereinstimmt.

Während dieser Code eine beliebige Anzahl von Eingabearrays aufnehmen kann, ist zu beachten, dass nur die paarweise Konsistenz überprüft wird . Beispielsweise wird für die Eingabe true zurückgegeben [[1 2] [2 3] [3 1]], da zwei der drei Arrays eine konsistente Gesamtreihenfolge haben. Das reicht jedoch für den Fall mit zwei Eingängen, was alles ist, was die Herausforderung erfordert.

Hier ist eine de-golfed Version mit Kommentaren:

:A         # save input to "A", and leave it on the stack to be looped over
{          # run this outer loop for each input array:
  :a;      #   save this array to "a" (and pop it off the stack)
  A{       #   also run this inner loop for each input array:
    .a--   #     remove all elements not in "a" from this array
    .      #     make a copy of the filtered array
    {a?}$  #     sort it by the first location of each element in "a"
    =!     #     check whether the sorted copy differs from the original
  },       #   select those arrays for which there was a difference
},         # select those arrays for which at least one difference was found
!          # return 1 if no differences were found, 0 otherwise

Ps. Es wäre möglich, ein oder zwei Bytes trivial zu speichern, indem die Eingabe direkt in der benannten Variablen angegeben werden Amuss und / oder indem das Ausgabeformat in ein leeres Array für "Ja" und ein nicht leeres Array für "Nein" geändert wird. . Das scheint mir jedoch ziemlich kitschig.

J, 36 30 26 Bytes

[:*/@,(e.~(-:/:~)@#i.)&>/~

Nennen wir die beiden Eingabelisten aund b. Die Funktion prüft (mit (e.~(-:/:~)@#i.)) ob

• a's Elemente sortiert (in Bezug auf a) inb
• a's Elemente sortiert (in Bezug auf a) ina
• b's Elemente sortiert (in Bezug auf b) ina
• b's Elemente sortiert (in Bezug auf b) inb

Die Eingabe ist eine Liste von zwei ganzzahligen Vektoren.

Ergebnis ist, 1wenn eine 0andere Bestellung vorliegt . (Laufzeit ist O (n * n).)

Verwendungszweck:

   f=.[:*/@,(e.~(-:/:~)@#i.)&>/~

   a=.7 2 1 1 4 12 3 [b=.7 2 1 1 4 12 3 1 [c=.9 8 7 2 5 1
   f a;c
1
   f b;c
0

Probieren Sie es hier online aus.

Ruby, 79

!!gets(p).scan(r=/\d+/){|s|$'[/.*/].scan(r){s!=$&&~/\b#$& .*\b#{s}\b/&&return}}

Erwartet, dass die Eingabe eine zweizeilige Datei mit durch Leerzeichen getrennten Zahlen ist. Gibt truewenn eine Bestellung vorhanden ist , nilwenn es nicht der Fall ist.

Haskell, 98 Bytes

import Data.List
a%b=intersect(r a)$r b
r l=map head$group l
c l=nub l==r l
x#y=c x&&c y&&x%y==y%x

Rückgabe Trueoder False. Anwendungsbeispiel: [7,2,1,1,4,12,3] # [9,8,7,2,5,1]-> True.

So funktioniert es: Entfernen Sie aufeinanderfolgende Duplikate aus den Eingabelisten (z [1,2,2,3,2] -> [1,2,3,2]. B.: Eine Reihenfolge liegt vor, wenn beide resultierenden Listen keine Duplikate enthalten und der Schnittpunkt von Liste1 und Liste2 gleich dem Schnittpunkt von Liste2 und Liste1 ist.