8
\$\begingroup\$

In this task, we consider arrays of positive integers such as this:

3 18 321 17 4 4 51 1 293 17

The input comprises a pair of such arrays both of arbitrary, possibly distinct, positive length. Determine if a total ordering ≤XN × N, where N is the set of positive integers, exists such that both input arrays are in order with respect to ≤X. Notice that (A ≤X B ∧ B ≤X A) ↔ A = B must hold, that is, two numbers are considered equal under ≤X if and only if they are the same number.

For example, if the input was the pair of arrays

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

then you are supposed to figure out if a total ordering ≤X exists such that

7 ≤X 2 ≤X 1 ≤X 1 ≤X 4 ≤X 12 ≤X 3

and

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

Your submission may be a subroutine or program that receives two arrays (as specified above) of input in an implementation-defined way, computes whether a total ordering ≤X satisfying the demands mentioned above exists and returns one value representing “yes” or a different value representing “no.” The choice of these values is arbitrary, please document them.

You may assume that the input arrays contain no more than 215 - 1 elements each and that each of their elements is in the range from 1 to 215 - 1 inclusive. You may require each arrays to be terminated by a constant sentinel outside of the aforementioned range such as 0. Please specify what sentinel is needed. You may require the lengths of the arrays as additional input if the length cannot be inferred from the arrays themselves (e. g. in languages like C). In addition to the prohibition of standard loopholes, you are not allowed to use topological sorting routines.

This challenge is code golf. The submission with the least amount of characters wins.

\$\endgroup\$
  • 2
    \$\begingroup\$ For the ease of everyone, could you make some example inputs/outputs to test with? \$\endgroup\$ – orlp Apr 5 '15 at 15:26
  • 1
    \$\begingroup\$ Can one list be paradoxical and has loops itself? \$\endgroup\$ – jimmy23013 Apr 5 '15 at 15:29
  • \$\begingroup\$ @user23013 yes. \$\endgroup\$ – FUZxxl Apr 5 '15 at 15:33
  • \$\begingroup\$ @orlp Sure. Give me some time please. \$\endgroup\$ – FUZxxl Apr 5 '15 at 15:35
  • 1
    \$\begingroup\$ @orlp Equality shouldn't be touched by the different ordering, but let me add a paragraph. \$\endgroup\$ – FUZxxl Apr 5 '15 at 15:39
4
\$\begingroup\$

Pyth, 28 22

L.AmqdSdmfhTmxhkbek^b2

Creates a function y that you can call with a tuple containing the two arrays. Returns "True" if a total ordering exists, "False" if not.

A helper program that defines and calls the above function with stdin:

L.AmqdSdmfhTmxhkbek^b2y,rw7rw7 

Try it here.

We first read both arrays. Then we will create all combinations of both arrays. Then for each combination we will assume the first array is authoritative, and check if it's consistent with the second array.

\$\endgroup\$
  • \$\begingroup\$ Is the positive integer the same for every true output? It is the intent of the specification that there is one integer representing “yes” and one integer representing no. \$\endgroup\$ – FUZxxl Apr 5 '15 at 15:52
  • \$\begingroup\$ @FUZxxl Now it does. \$\endgroup\$ – orlp Apr 5 '15 at 15:59
  • \$\begingroup\$ I think you're allowed to take input however you want, which would save a lot of characters. Receives two arrays ... in an implementation-defined way. You can save at least 7 characters. \$\endgroup\$ – isaacg Apr 6 '15 at 3:28
  • \$\begingroup\$ @isaacg Thanks, I can only save 6 though, because I'll have to use a lambda - I have to give either a subroutine or a program. \$\endgroup\$ – orlp Apr 6 '15 at 7:33
2
\$\begingroup\$

GolfScript, 25 bytes

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

Try this code online.

Takes an array of two (or more!) arrays on the stack; returns 1 (true) if every pair of input arrays has a compatible total order, or 0 (false) otherwise.

It works by looping over every possible pair of input arrays (including each array paired with itself), sorting the elements in the first array according to the position where they first occur in the second one (ignoring those that are not found), and checking that the resulting order matches the original.

While this code can take an arbitrary number of input arrays, it's worth noting that it only checks for pairwise consistency. For example, it returns true for the input [[1 2] [2 3] [3 1]], since any two of the three arrays do have a consistent total order. That's enough for the two-input case, though, which is all that the challenge requires.

Here's a de-golfed version with comments:

: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

Ps. It would be possible to trivially save one or two bytes by requiring the input to be given directly in the named variable A, and/or by changing the output format to an empty array for "yes" and a non-empty array for "no". However, that would seem rather cheesy to me.

\$\endgroup\$
  • \$\begingroup\$ This is a neat idea. Maybe I'm doing a J port of this solution. \$\endgroup\$ – FUZxxl Apr 5 '15 at 20:01
2
\$\begingroup\$

J, 36 30 26 bytes

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

Let's call the two input lists a and b. The function checks (with (e.~(-:/:~)@#i.)) whether

  • a's elements sorted (in regard to a) in b
  • a's elements sorted (in regard to a) in a
  • b's elements sorted (in regard to b) in a
  • b's elements sorted (in regard to b) in b

Input is a list of two integer vectors.

Result is 1 if an ordering exists 0 otherwise. (Runtime is O(n*n).)

Usage:

   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

Try it online here.

\$\endgroup\$
  • \$\begingroup\$ How can b not be sorted in regard to b? \$\endgroup\$ – FUZxxl Apr 5 '15 at 18:17
  • \$\begingroup\$ @FUZxxl e.g. b=1 2 1 or in my second example b=7 2 1 1 4 12 3 1 \$\endgroup\$ – randomra Apr 5 '15 at 18:22
  • \$\begingroup\$ Ok... Kind of makes sense. \$\endgroup\$ – FUZxxl Apr 5 '15 at 18:42
1
\$\begingroup\$

Ruby, 79

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

Expects input to be a two-line file of space-separated numbers. Returns true when an ordering exists, nil if it doesn't.

\$\endgroup\$
  • \$\begingroup\$ Please obey the output format: Return one value specifying existence of an ordering or another value specifying nonexistence. These values must be independent of input. \$\endgroup\$ – FUZxxl Apr 6 '15 at 18:19
  • \$\begingroup\$ Done. Could technically comply with the spec with one fewer character, but returning nil or false just feels too wrong. \$\endgroup\$ – histocrat Apr 6 '15 at 18:25
  • \$\begingroup\$ Returning nil or false is absolutely ok. \$\endgroup\$ – FUZxxl Apr 6 '15 at 18:47
1
\$\begingroup\$

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

Returns True or False. Example usage: [7,2,1,1,4,12,3] # [9,8,7,2,5,1] -> True.

How it works: remove consecutive duplicates from the input lists (e.g: [1,2,2,3,2] -> [1,2,3,2]. An order exists if both resulting lists do not contain duplicates and the intersection of list1 and list2 equals the intersection of list2 and list1.

\$\endgroup\$
  • \$\begingroup\$ This is a neat idea. \$\endgroup\$ – FUZxxl Apr 6 '15 at 18:58

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.