Almost Lexicographical List Comparison

Question

Input

Two lists A and B of nonnegative integers.

Output

Either 1, 0, or -1, depending on whether A is larger than, equal to, or smaller than B with respect to the twisted lexicographical ordering as defined below. If you want, you can replace 1, 0 and -1 with any other three constant values.

The twisted lexicographical ordering is like the ordinary lexicographical ordering, in that you compare the lists element by element, and decide their order at the first differing index. However, in the twisted version we use a different ordering for nonnegative integers at each index. Namely, at every index i (indexing starts from 1), the order of the first i nonnegative integers (from 0 to i-1) is reversed, and they are moved above all the other numbers. Moreover, the "missing element" that signifies one list being shorter than the other is moved directly below i-1. Visually, the order at index i is

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

Note that the first ... denotes infinitely many numbers. This means that the following lists are in ascending order with respect to the twisted lexicographical ordering:

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

Rules

You can give a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

Test Cases

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]

Answer 1

Python 2, 76 bytes

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

This replaces each integer in both lists with a 2-tuple to account for the twisted ordering. Python 2's cmp builtin does the rest.

Usage:

>>> c([1,2,1,1,6], [1,2,1,1,7])
-1

Answer 2

CJam - 57

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

Yeah it's still very long...

Try it online

Brief explanation:
The code outputs 0 if the arrays are equal in the traditional sense, otherwise it converts each item of each array to a 2-element array: [0 a_i] if a_i>i (0-based), [1 whatever] if a_i is missing, and [2 -a_i] if a_i<=i. In the process, the shorter array is also extended to the larger size. Then the transformed arrays are compared lexicographically and the result is adjusted to -1/1.

Answer 3

Perl, 74

Without good array manipulation functions perl is not the optimal tool for the job, but it works.

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

Test me.

Answer 4

J, 95 bytes

(Not super-short but whatever. Definitely golfable.)

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

Passing all the test cases. (Great test case set! Thanks!)

Method:

• Padding the shorter list with maxvalue+1 (m=.>:>./x,y). (],m$~>&#*-&#
• Transforming list elements so normal comparison could be used. (|+(1+m)*0>:*)@(i.@#-~])
• Calculating two baseX numbers from the two list with sufficient X. ((m+#x,y)&#.)
• Returning the signum of the two numbers difference.*@-&

Answer 5

Jelly, 9 bytes

J_»0;1ż)M

Try it online!

Direct port of grc's Python solution. Monadic link taking a pair of its arguments and returning [1] for 1, [1, 2] for 0, and [2] for -1.

       )     For each element of the input:
 _           Subtract each element from
J            its 1-index,
  »0         take the maximum of each of those and 0,
    ;1       append 1,
      ż      and zip those with the original elements.
        M    Return the list of maximal indices.

Answer 6

Mathematica, 65

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

Usage:

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

-1