En esta tarea, consideramos matrices de enteros positivos como este:

3 18 321 17 4 4 51 1 293 17

La entrada comprende un par de tales matrices de longitud positiva arbitraria, posiblemente distinta. Determinar si un orden total ≤ _X ⊂ N × N , donde N es el conjunto de números enteros positivos, existe tal que ambas matrices de entrada están en orden con respecto a ≤ _X . Tenga en cuenta que (A ≤ _X B ∧ B ≤ _X A) ↔ A = B debe cumplir, es decir, dos números se consideran iguales bajo ≤ _X si y solo si son el mismo número.

Por ejemplo, si la entrada era el par de matrices

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

entonces se supone que debes averiguar si existe un orden total ≤ _X tal que

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

y

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

Su envío puede ser una subrutina o programa que recibe dos matrices (como se especificó anteriormente) de una manera definida por la implementación, calcula si existe un pedido total ≤ _{X que} satisface las demandas mencionadas anteriormente y devuelve un valor que representa "sí" o un valor diferente valor que representa "no". La elección de estos valores es arbitraria, documentarlos.

Puede suponer que las matrices de entrada contienen no más de 2 ¹⁵ - 1 elementos cada una y que cada uno de sus elementos está en el rango de 1 a 2 ¹⁵ - 1 inclusive. Puede requerir que cada matriz sea terminada por un centinela constante fuera del rango antes mencionado, como 0. Especifique qué centinela se necesita. Puede requerir las longitudes de las matrices como entrada adicional si la longitud no puede deducirse de las matrices mismas (por ejemplo, en lenguajes como C). Además de la prohibición de las lagunas estándar, no está permitido usar rutinas de clasificación topológica.

Este desafío es el código de golf. La presentación con la menor cantidad de caracteres gana.

Pyth, 28 22

L.AmqdSdmfhTmxhkbek^b2

Crea una función yque puede llamar con una tupla que contiene las dos matrices. Devuelve "Verdadero" si existe un pedido total, "Falso" si no.

Un programa auxiliar que define y llama a la función anterior con stdin:

L.AmqdSdmfhTmxhkbek^b2y,rw7rw7 

Pruébalo aquí

Primero leemos ambas matrices. Luego crearemos todas las combinaciones de ambas matrices. Luego, para cada combinación, asumiremos que la primera matriz es autorizada y verificaremos si es consistente con la segunda matriz.

GolfScript, 25 bytes

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

Prueba este código en línea.

Toma una matriz de dos (¡o más!) Matrices en la pila; devuelve 1 (verdadero) si cada par de matrices de entrada tiene un orden total compatible, o 0 (falso) de lo contrario.

Funciona haciendo un bucle sobre cada posible par de matrices de entrada (incluida cada matriz emparejada consigo misma), ordenando los elementos en la primera matriz de acuerdo con la posición en la que ocurren por primera vez en la segunda (ignorando los que no se encuentran), y verificando que el orden resultante coincide con el original.

Si bien este código puede tomar un número arbitrario de matrices de entrada, vale la pena señalar que solo verifica la coherencia por pares . Por ejemplo, devuelve verdadero para la entrada [[1 2] [2 3] [3 1]], ya que dos de las tres matrices tienen un orden total consistente. Sin embargo, eso es suficiente para el caso de dos entradas, que es todo lo que requiere el desafío.

Aquí hay una versión de golf con comentarios:

: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

PD. Sería posible guardar trivialmente uno o dos bytes al requerir que la entrada se dé directamente en la variable nombrada A, y / o al cambiar el formato de salida a una matriz vacía para "sí" y una matriz no vacía para "no" . Sin embargo, eso me parecería bastante cursi.

J, 36 30 26 bytes

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

Llamemos a las dos listas de entrada ay b. La función verifica (con (e.~(-:/:~)@#i.)) si

• aLos elementos ordenados (con respecto a a) enb
• aLos elementos ordenados (con respecto a a) ena
• bLos elementos ordenados (con respecto a b) ena
• bLos elementos ordenados (con respecto a b) enb

La entrada es una lista de dos vectores enteros.

El resultado es 1si existe un pedido de 0otra manera. (El tiempo de ejecución es O (n * n)).

Uso:

   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

Pruébelo en línea aquí.

Rubí, 79

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

Espera que la entrada sea un archivo de dos líneas de números separados por espacios. Devuelve truecuando existe un pedido, nilsi no es así.

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

Devoluciones Trueo False. Ejemplo de uso: [7,2,1,1,4,12,3] # [9,8,7,2,5,1]-> True.

Cómo funciona: eliminar duplicados consecutivos de las listas de entrada (por ejemplo:. [1,2,2,3,2] -> [1,2,3,2]Existe un orden si ambas listas resultantes no contienen duplicados y la intersección de list1 y list2 es igual a la intersección de list2 y list1.