Skip to main content
2 of 3
Clarified indexing.
Zgarb
  • 42.8k
  • 4
  • 79
  • 259

Almost Lexicographical List Comparison

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.

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]
Zgarb
  • 42.8k
  • 4
  • 79
  • 259