9
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ Are the input lists indexed from 0, from 1, or from whichever is appropriate for our language? \$\endgroup\$ – Peter Taylor Feb 26 '15 at 12:35
  • \$\begingroup\$ @PeterTaylor From 1. I'll clarify that. \$\endgroup\$ – Zgarb Feb 26 '15 at 13:38
  • \$\begingroup\$ Can i use Haskell's own enum for comparison results instead of -1/0/1 for the output? \$\endgroup\$ – John Dvorak Feb 26 '15 at 14:03
  • \$\begingroup\$ @JanDvorak I'll allow that, and edit the challenge. \$\endgroup\$ – Zgarb Feb 26 '15 at 14:07
1
\$\begingroup\$

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 ai] if ai>i (0-based), [1 whatever] if ai is missing, and [2 -ai] if ai<=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.

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ How does this account for a shorter list to go in between different longer lists ([3,2,3,1341] < [3,2,3] < [3,2,3,0]? \$\endgroup\$ – nutki Feb 26 '15 at 13:54
  • \$\begingroup\$ @nutki it adds the tuple (0,) to the end of each list, which is greater than any (-1, x) and less than (i-x, x) when i-x >= 0. \$\endgroup\$ – grc Feb 26 '15 at 14:00
  • \$\begingroup\$ Oh, of course. I am not literate in Python. \$\endgroup\$ – nutki Feb 26 '15 at 14:04
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.*@-&
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.