54
\$\begingroup\$

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  |
+----------------------+--------+
\$\endgroup\$

10 Answers 10

33
\$\begingroup\$

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.

\$\endgroup\$
12
\$\begingroup\$

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.

\$\endgroup\$
11
\$\begingroup\$

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])
\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – wizzwizz4 Jan 11 '16 at 19:07
  • 2
    \$\begingroup\$ Ahhhh, I see. Yup, I'm new to this. Will trim a bit of fat and try again. Thanks for the advice. \$\endgroup\$ – Jason Evans Jan 11 '16 at 19:09
  • \$\begingroup\$ 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. \$\endgroup\$ – Doorknob Jan 11 '16 at 21:49
  • \$\begingroup\$ I suspect you could omit .ToArray(). \$\endgroup\$ – Vlad Jan 13 '16 at 8:58
  • 1
    \$\begingroup\$ I know it's been almost 2.5 years, but you can golf it down to 82 bytes: using System.Linq; + n=>!n.Distinct().SequenceEqual(n.Reverse().Distinct().Reverse()) (the Linq import is unfortunately mandatory). Try it online. Nice answer, +1 from me! \$\endgroup\$ – Kevin Cruijssen May 7 '18 at 12:14
5
\$\begingroup\$

CJam (14 13 bytes)

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

Online demo

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

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Sounds like Japt might want to implement value equality. \$\endgroup\$ – isaacg Jan 13 '16 at 10:22
4
\$\begingroup\$

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.

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

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
\$\endgroup\$
1
\$\begingroup\$

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;}}
\$\endgroup\$
1
\$\begingroup\$

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)
\$\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.