Окруженные страны

54

Странам принадлежит ряд территорий в одномерном мире. Каждая страна уникально идентифицируется номером. Право собственности на территории может быть представлено в виде списка:

1 1 2 2 1 3 3 2 4

Мы определяем самые крайние территории страны как две территории, самые близкие к любому краю. Если приведенный выше список был проиндексирован с нуля, 1крайние территории страны находятся в позиции 0и 4.

Страна окружает другую, если подсписок между ее двумя крайними территориями содержит все территории другой страны. В приведенном выше примере подсписок между 2крайними территориями страны:

2 2 1 3 3 2

И мы видим, что все территории страны 3находятся между крайними территориями страны 2, поэтому страна 2окружает страну 3.

Страна с одним элементом никогда не будет окружать другой.

Вызов

Возьмите список целых чисел в качестве входных данных (в любом формате) и выведите истинное значение, если какая-либо страна окружена другой, и ложное значение в противном случае.

Вы можете предположить, что входной список не пуст, содержит только положительные целые числа и не пропускает никакие числа: например, 1 2 1 5будет неправильный ввод.

Тестовые случаи

+----------------------+--------+
|        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  |
+----------------------+--------+
Сизиф
источник
21
Добро пожаловать в PPCG! Поздравляю с первым вопросом. этот выглядит действительно хорошо!
Mego
6
И сколько армий я получу в следующий ход, чтобы окружить страну?
ThisSuitIsBlackNot

Ответы:

33

Pyth, 7 байт

n{Q_{_Q

Запустите код в тестовых случаях.

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)

Единственный способ избежать окружения - сортировка крайних левых территорий в том же порядке, что и крайние правые территории. Если две страны поменялись местами в этом порядке, одна из них имеет территорию как влево, так и дальше вправо, чем в другой, и поэтому окружает ее.

Чтобы получить уникальные страны в порядке крайней левой территории, мы просто дедуплицируем, что сохраняет этот порядок. То же самое делается для самой правой территории путем реверсирования, дедупликации, а затем реверса снова. Если они дают разные результаты, тогда страна окружена.

XNOR
источник
12

Сетчатка , 61 60 байт

Намного дольше, чем хотелось бы ...

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

Печать числа стран, которые окружают хотя бы одну другую страну.

Попробуйте онлайн.

Это очень простая реализация спецификации: мы ищем такой шаблон A...B...A, который не Bпоявляется ни до, ни после матча.

Мартин Эндер
источник
11

Python, 64 байта

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

Единственный способ избежать окружения - сортировка крайних левых территорий в том же порядке, что и крайние правые территории. Если две страны поменялись местами в этом порядке, одна из них имеет территорию как влево, так и дальше вправо, чем в другой, и поэтому окружает ее.

Функция проверяет, что сортировка территорий по левому и правому краям дает одинаковые результаты. К сожалению, списки Python не имеют rindexаналога rfind, поэтому мы переворачиваем список, а затем переворачиваем отсортированный вывод.

Та же длина (64) со вспомогательной функцией:

g=lambda l:sorted(l,key=l.index)
lambda l:g(l)[::-1]!=g(l[::-1])
XNOR
источник
6

C #, 113 байт

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);
}

Используя краткий LINQподход.

Джейсон Эванс
источник
1
Добро пожаловать в PPCG. Это очень хорошее решение для безвкусицы ; Мне часто приходится информировать новых пользователей о том, что людям часто нравится видеть неопрятные (читаемые, комментируемые) версии своего кода. Тем не менее, вы забыли включить версию для гольфа! Есть несколько приемов, которые вы можете использовать, в том числе имена переменных 1char, удаление пробелов и «переменные, которые, как предполагается, должны быть, intесли вы не говорите иначе». +1 за алгоритм и реализацию.
wizzwizz4
2
Аааа, я вижу. Да, я новичок в этом. Урежу немного жира и попробую еще раз. Спасибо за совет.
Джейсон Эванс
Вы можете сохранить два байта, используя односимвольные имена переменных - на самом деле, вы можете сохранить больше, вообще не используя переменные и просто сделав их одним выражением.
Дверная ручка
Я подозреваю, что вы могли бы пропустить .ToArray().
Влад
1
Я знаю, что прошло почти 2,5 года, но вы можете увеличить его до 82 байт : using System.Linq;+ n=>!n.Distinct().SequenceEqual(n.Reverse().Distinct().Reverse())(импорт Linq, к сожалению, обязателен). Попробуйте онлайн. Хороший ответ, +1 от меня!
Кевин Круйссен
4

Japt, 12 байт

Uâ ¬¦Uw â ¬w

Попробуйте онлайн!

Спасибо @xnor за выяснение алгоритма. Входной массив автоматически сохраняется U, âявляется уникальным, wобратным и ¦имеет значение !=. ¬объединяется с пустой строкой ( [1,2,3] => "123"); это необходимо, потому что при сравнении JavaScript два массива считаются не равными, если они не являются одним и тем же объектом. Например (код JS, а не Japt):

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

Если бы это было не так, мы могли бы удалить два байта, просто не объединяя каждый массив:

Uâ ¦Uw â w
ETHproductions
источник
Похоже, что Japt может захотеть реализовать ценностное равенство.
Исаак
4

ES6, 76 75 65 64 байта

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

Прямой порт ответов @ xnor.

Редактировать: 1 байт сохранен путем замены a.lastIndexOf(x)==iна a.indexOf(x,i+1)<0.

Редактировать: 10 байтов сохранено благодаря @ user81655.

Редактировать: 1 байт сохранен путем замены r||iна r|i.

Нил
источник
2
65 байт с использованием функции:a=>(f=r=>a.filter((x,i)=>a.indexOf(x,r&&i+1)==(r||i))+a)()!=f(-1)
user81655
используйте ~ вместо <0.
Mama Fun Roll
@ ՊՓԼՃՐՊՃՈԲՍԼ Нет, я хочу, чтобы это было -1. ~так же, как >=0.
Нил
Ой, не бери в голову: P
Mama Fun Roll
@ user81655 Извините, я почему-то не заметил ваш комментарий. Хитрый, но мне это нравится!
Нил
1

Java, 281 символов

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;}}
минимальная
источник
1

Python 3, 90 байт

Эта функция принимает входные данные в виде списка Python. К сожалению, списки Python напрямую не поддерживают поиск с конца, как это делают строки rindex(), ну да ладно.

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)
Тим Педерик
источник