Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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  |
+----------------------+--------+
share|improve this question
17  
Welcome to PPCG! Congratulations on your first question; this one looks really good! – Mego Jan 11 at 7:11
5  
And how many armies do I get on my next turn for surrounding a country? – ThisSuitIsBlackNot Jan 11 at 17:14

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.

share|improve this answer

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])
share|improve this answer

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.

share|improve this answer

CJam (14 13 bytes)

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

Online demo

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

share|improve this answer

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.

share|improve this answer
1  
Welcome to PPCG. This is a very good ungolfed solution; I often have to inform new users that people often like to see ungolfed (readable, commented) versions of their code. However, you have forgotten to include a golfed version! There are several tricks you could use, including 1char variable names, removing whitespace and the "variables assumed to be int unless you say otherwise" quirk. +1 for the algorithm and implementation. – wizzwizz4 Jan 11 at 19:07
2  
Ahhhh, I see. Yup, I'm new to this. Will trim a bit of fat and try again. Thanks for the advice. – Jason Evans Jan 11 at 19:09
    
You can save two bytes by using one-character variable names—actually, you can save more by not using variables at all and simply making it a single expression. – Doorknob Jan 11 at 21:49
    
I suspect you could omit .ToArray(). – Vlad Jan 13 at 8:58

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.

share|improve this answer
2  
65 bytes using a function: a=>(f=r=>a.filter((x,i)=>a.indexOf(x,r&&i+1)==(r||i))+a)()!=f(-1) – user81655 Jan 11 at 14:09
    
use ~ instead of <0. – Mama Fun Roll Jan 11 at 14:40
    
@ՊՓԼՃՐՊՃՈԲՍԼ No, I want it to be -1. ~ is the same as >=0. – Neil Jan 11 at 16:30
    
Oh wait nevermind :P – Mama Fun Roll Jan 11 at 23:48
    
@user81655 Sorry I didn't notice your comment before for some reason. Tricksy, but I like it! – Neil Jan 12 at 10:37

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
share|improve this answer
    
Sounds like Japt might want to implement value equality. – isaacg Jan 13 at 10:22

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;}}
share|improve this answer

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)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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