Surrounded Countries

Question

Countries own a series of territories on a 1D world. Each country is uniquely identified by a number. Ownership of the territories can be represented by a list as follows:

1 1 2 2 1 3 3 2 4

We define a country's edgemost territories as the two territories closest to either edge. If the above list was zero indexed, country 1's edgemost territories occur at position 0 and 4.

A country surrounds another if the sublist between its two edgemost territories contains all the territories of another country. In the above example, the sublist between country 2's edgemost territories is:

2 2 1 3 3 2

And we see that all the territories of country 3 are between the edgemost territories of country 2, so country 2 surrounds country 3.

A country with only one element will never surround another.

Challenge

Take a list of integers as input (in any format) and output a truthy value if any country is surrounded by another, and a falsy value otherwise.

You can assume that the input list is nonempty, only contains positive integers, and does not 'skip' any numbers: for example, 1 2 1 5 would be invalid input.

Test Cases

+----------------------+--------+
|        Input         | Output |
+----------------------+--------+
| 1                    | False  |
| 2 1 3 2              | True   |
| 2 1 2 1 2            | True   |
| 1 2 3 1 2 3          | False  |
| 1 3 1 2 2 3 2 3      | True   |
| 1 2 2 1 3 2 3 3 4    | False  |
| 1 2 3 4 5 6 7 8 9 10 | False  |
+----------------------+--------+

Answer 1

Pyth, 7 bytes

n{Q_{_Q

Run the code on test cases.

n      Check whether the following are not equal:
 {Q     The unique elements in order of first appearance
 _{_Q   The unique elements in order of last appearance
         (done by reversing, taking unique elts, then reversing again)

The only way to avoid surrounding is for the countries' leftmost territories to be sorted in the same order as their rightmost territories. If two countries are swapped in this order, one has a territory both further left and further right than the other, and so surrounds it.

To obtain the unique countries in order of leftmost territory, we simply deduplicate, which preserves this order. The same is done for the rightmost territory by reversing, deduplicating, then reversing again. If these give different results, then a country is surrounded.

Answer 2

Retina, 61 60 bytes

Much longer than I would like...

(\b(\d+)\b.* (?!\2 )(\d+) .*\b\2\b)(?!.* \3\b)(?<!\b\3 .*\1)

Prints the number of countries that surround at least one other country.

Try it online.

It's a very straightforward implementation of the spec: we look for the pattern A...B...A such that B appears neither before or after the match.

Answer 3

Python, 64 bytes

lambda l,S=sorted:S(l,key=l.index)!=S(l,key=l[::-1].index)[::-1]

The only way to avoid surrounding is for the countries' leftmost territories to be sorted in the same order as their rightmost territories. If two countries are swapped in this order, one has a territory both further left and further right than the other, and so surrounds it.

The function checks that sorting the territories by leftmost appearance and rightmost appearance gives the same results. Unfortunately, Python lists don't have rindex analogous to rfind, so we reverse the list, then reverse the sorted output.

Same length (64) with an auxiliary function:

g=lambda l:sorted(l,key=l.index)
lambda l:g(l)[::-1]!=g(l[::-1])

Answer 4

C#, 113 bytes

public bool V(int[] n){var u1=n.Distinct();var u2=n.Reverse().Distinct().Reverse();return !u1.SequenceEqual(u2);}

Ungolfed:

public bool ContainsSurroundedCountry(int[] numbers)
{
    int[] uniqueLeftmost = numbers.Distinct().ToArray();
    int[] uniqueRightmost = numbers.Reverse().Distinct().Reverse().ToArray();

    return !uniqueLeftmost.SequenceEqual(uniqueRightmost);
}

Using a concise LINQ approach.

Answer 5

CJam (14 13 bytes)

{__&\W%_&W%#}

Online demo

Thanks to Martin Büttner for a one-char saving.

Answer 6

Japt, 12 bytes

Uâ ¬¦Uw â ¬w

Try it online!

Thanks to @xnor for figuring out the algorithm. Input array is automatically stored in U, â is uniqify, w is reverse, and ¦ is !=. ¬ joins with the empty string ([1,2,3] => "123"); this is necessary because JavaScript's comparsion counts two arrays as not equal unless they are the same object. For example (JS code, not Japt):

var a = [1], b = [1]; alert(a==b); // false
var a = [1], b = a;   alert(a==b); // true

If this was not the case, we could remove two bytes by simply not joining each array:

Uâ ¦Uw â w

Answer 7

ES6, 76 75 65 64 bytes

 a=>(f=r=>a.filter((x,i)=>a.indexOf(x,r&&i+1)==(r|i))+a)()!=f(-1)

Straightforward port of @xnor's answers.

Edit: Saved 1 byte by replacing a.lastIndexOf(x)==i with a.indexOf(x,i+1)<0.

Edit: Saved 10 bytes thanks to @user81655.

Edit: Saved 1 byte by replacing r||i with r|i.

Answer 8

05AB1E, 4 bytes

ÙIÚÊ

Try it online or verify all test cases.

Port of @xnor's Pyth answer.

Explanation:

Ù       # Uniquified
 IÚ     # Reversed uniquified on the input again
   Ê    # Check if the two lists are not equal

Answer 9

Java, 281 Characters

class K{public static void main(String[]a){System.out.println(!k(a[0]).equals(new StringBuffer(k(new StringBuffer(a[0]).reverse().toString())).reverse().toString()));}static String k(String k){for(char i=49;i<58;i++){k=k.replaceFirst(""+i,""+(i-9)).replaceAll(""+i,"");}return k;}}

Answer 10

Python 3, 90 bytes

This function that takes the input as a Python list. Sadly, Python lists don't directly support searching from the end like strings do with rindex(), but oh well.

def t(c):i,I=c.index,c[::-1].index;return any(i(n)<i(m)and I(n)<I(m)for m in c for n in c)

Answer 11

Jelly, 5 bytes

UQU⁻Q

Try it online!

Just another port of xnor's answer, so go upvote that.

How it works

UQU⁻Q - Main link. Takes a list l on the left
U     - rev(l)
 Q    - unique(rev(l))
  U   - rev(unique(rev(l)))
    Q - unique(l)
   ⁻  - rev(unique(rev(l)) ≠ unique(l)