Comparación de listas casi lexicográficas

9

Entrada

Dos listas Ay Bde enteros no negativos.

Salida

Ya sea 1, 0o -1, dependiendo de si Aes mayor, igual o menor que Bcon respecto al ordenamiento lexicográfico retorcido como se define a continuación. Si lo desea, puede reemplazarlo 1, 0y -1con otros tres valores constantes.

El ordenamiento lexicográfico retorcido es como el ordenamiento lexicográfico ordinario, en el que compara las listas elemento por elemento, y decide su orden en el primer índice diferente. Sin embargo, en la versión retorcida usamos un orden diferente para enteros no negativos en cada índice. Es decir, en cada índice i(la indexación comienza desde 1), el orden de los primeros ienteros no negativos (de 0a i-1) se invierte y se mueven por encima de todos los demás números. Además, el "elemento faltante" que significa que una lista es más corta que la otra se mueve directamente debajo i-1. Visualmente, el orden en el índice ies

i < i+1 < i+2 < i+3 < ... < [missing element] < i-1 < i-2 < i-3 < ... < 2 < 1 < 0

Tenga en cuenta que el primero ...denota infinitos números. Esto significa que las siguientes listas están en orden ascendente con respecto al ordenamiento lexicográfico retorcido:

[3,2,3,4]
[3,2,3,5]
[3,2,3,10]
[3,2,3,1341]
[3,2,3]
[3,2,3,3]
[3,2,3,2]
[3,2,3,1]
[3,2,3,0]

Reglas

Puedes dar un programa completo o una función. El conteo de bytes más bajo gana, y las lagunas estándar no se permiten.

Casos de prueba

Output 1:
[0] []
[] [1]
[] [1,2,1,2]
[2,1] [1,1]
[0,1,2] [0,2,1]
[3,0] [3,1]
[3,1] [3]
[2] [2,2]
[2] [2,23]
[2,24] [2,23]
[2,1] [2,23]

Output 0:
[] []
[0] [0]
[1,1] [1,1]
[2,1,2] [2,1,2]

Output -1:
[1,2,1,1,2] [1,2,1,1,1]
[1,2,1,1,5] [1,2,1,1,4]
[1,2,1,1,5] [1,2,1,1]
[1,2,1] [1,2,1,1]
[1,2,1,1,5] [1,2,1,1,6]
[1,2,1,1,6] [1,2,1,1,7]
Zgarb
fuente
¿Las listas de entrada están indexadas de 0, de 1 o de lo que sea apropiado para nuestro idioma?
Peter Taylor
@PeterTaylor De 1. Lo aclararé.
Zgarb
¿Puedo usar la propia enumeración de Haskell para resultados de comparación en lugar de -1/0/1 para la salida?
John Dvorak
@ JanDvorak Lo permitiré y editaré el desafío.
Zgarb

Respuestas:

1

CJam - 57

q:S~=0{S~]:A:,~e>{A{_,I>{I=_I>0{W*2}?}1?[\]}%}fI]z~>2*(}?

Sí, todavía es muy largo ...

Pruébalo en línea

Breve explicación:
el código genera 0 si las matrices son iguales en el sentido tradicional; de lo contrario, convierte cada elemento de cada matriz en una matriz de 2 elementos: [0 a i ] si a i > i (basado en 0), [1 lo que sea] si falta un i , y [2 -a i ] si a i <= i. En el proceso, la matriz más corta también se extiende al tamaño más grande. Luego, las matrices transformadas se comparan lexicográficamente y el resultado se ajusta a -1/1.

aditsu renunció porque SE es MALO
fuente
3

Python 2, 76 bytes

c=lambda*a:cmp(*[[(max(i-x,-1),x)for i,x in enumerate(L)]+[(0,)]for L in a])

Esto reemplaza cada número entero en ambas listas con una tupla de 2 para dar cuenta del orden retorcido. La cmpconstrucción de Python 2 hace el resto.

Uso:

>>> c([1,2,1,1,6], [1,2,1,1,7])
-1
grc
fuente
1
¿Cómo esta cuenta para una lista más corta para ir entre las diferentes listas más largas ( [3,2,3,1341] < [3,2,3] < [3,2,3,0]?
nutki
@nutki agrega la tupla (0,)al final de cada lista, que es mayor que cualquiera (-1, x)y menor que (i-x, x)cuando i-x >= 0.
grc
Oh por supuesto. No estoy alfabetizado en Python.
nutki
1

Perl, 74

Sin buenas funciones de manipulación de matriz, Perl no es la herramienta óptima para el trabajo, pero funciona.

#!perl -pa
$i=0,s/\d+,?/$s=sprintf"%9d",$&;$&>$i++?$s:~$s/ge for@F;$_=$F[0]cmp$F[1]

Ponme a prueba .

nutki
fuente
1

J, 95 bytes

(No súper corto, pero lo que sea. Definitivamente golfable).

f=.4 :0
m=.>:>./x,y
t=.(|+(1+m)*0>:*)@(i.@#-~])@(],m$~>&#*-&#)
x(t~(*@-&((m+#x,y)&#.))t)y
)

Pasando todos los casos de prueba. (¡Gran conjunto de casos de prueba! ¡Gracias!)

Método:

  • Relleno de la lista más corta con maxvalue + 1 ( m=.>:>./x,y).(],m$~>&#*-&#
  • Transformar elementos de la lista para que se pueda utilizar una comparación normal. (|+(1+m)*0>:*)@(i.@#-~])
  • Cálculo de dos números baseX de las dos listas con suficiente X. ((m+#x,y)&#.)
  • Devolviendo el signo de la diferencia de dos números.*@-&
randomra
fuente
0

Mathematica, 65

f=-Order@@MapIndexed[If[#>Last@#2,#,a-b#]&,PadRight[{##}+1],{2}]&

Uso:

f[{1, 2, 1, 1, 6}, {1, 2, 1, 1, 7}]

-1

alephalpha
fuente