Países rodeados

54

Los países poseen una serie de territorios en un mundo 1D. Cada país se identifica de manera única por un número. La propiedad de los territorios puede representarse mediante una lista de la siguiente manera:

1 1 2 2 1 3 3 2 4

Definimos los territorios más extremos de un país como los dos territorios más cercanos a cualquier borde. Si la lista anterior no estaba indexada, 1los territorios más extremos del país se encuentran en la posición 0y 4.

Un país rodea a otro si la sublista entre sus dos territorios más extremos contiene todos los territorios de otro país. En el ejemplo anterior, la sublista entre 2los territorios más extremos del país es:

2 2 1 3 3 2

Y vemos que todos los territorios del país 3están entre los territorios más extremos del país 2, por lo que el país 2rodea al país 3.

Un país con un solo elemento nunca rodeará a otro.

Desafío

Tome una lista de enteros como entrada (en cualquier formato) y genere un valor verdadero si algún país está rodeado por otro, y un valor falso de lo contrario.

Puede suponer que la lista de entrada no está vacía, solo contiene enteros positivos y no 'saltea' ningún número: por ejemplo, 1 2 1 5sería una entrada no válida.

Casos de prueba

+----------------------+--------+
|        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  |
+----------------------+--------+
Sísifo
fuente
21
Bienvenido a PPCG! Felicidades por tu primera pregunta; este se ve muy bien!
Mego
66
¿ Y cuántos ejércitos tengo en mi próximo turno por rodear un país?
ThisSuitIsBlackNot

Respuestas:

33

Pyth, 7 bytes

n{Q_{_Q

Ejecute el código en casos de prueba.

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)

La única forma de evitar los alrededores es ordenar los territorios más a la izquierda de los países en el mismo orden que sus territorios más a la derecha. Si se intercambian dos países en este orden, uno tiene un territorio más a la izquierda y más a la derecha que el otro, y así lo rodea.

Para obtener los países únicos en orden de territorio más a la izquierda, simplemente deduplicamos, lo que preserva este orden. Lo mismo se hace para el territorio más a la derecha invirtiendo, deduplicando y luego invirtiendo nuevamente. Si estos dan resultados diferentes, entonces un país está rodeado.

xnor
fuente
12

Retina , 61 60 bytes

Mucho más de lo que me gustaría ...

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

Imprime el número de países que rodean al menos a otro país.

Pruébalo en línea.

Es una implementación muy sencilla de la especificación: buscamos el patrón A...B...Atal que Bno aparezca ni antes ni después del partido.

Martin Ender
fuente
11

Python, 64 bytes

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

La única forma de evitar los alrededores es ordenar los territorios más a la izquierda de los países en el mismo orden que sus territorios más a la derecha. Si se intercambian dos países en este orden, uno tiene un territorio más a la izquierda y más a la derecha que el otro, y así lo rodea.

La función verifica que al ordenar los territorios por la apariencia más a la izquierda y la más a la derecha se obtienen los mismos resultados. Desafortunadamente, las listas de Python no tienen un rindexanálogo rfind, por lo que revertimos la lista y luego revertimos la salida ordenada.

Misma longitud (64) con una función auxiliar:

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

C #, 113 bytes

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

Sin golf:

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

    return !uniqueLeftmost.SequenceEqual(uniqueRightmost);
}

Usando un LINQenfoque conciso .

Jason Evans
fuente
1
Bienvenido a PPCG. Esta es una muy buena solución sin golf ; A menudo tengo que informar a los nuevos usuarios que a la gente le gusta ver versiones no codificadas (legibles, comentadas) de su código. ¡Sin embargo, se ha olvidado de incluir una versión de golf! Hay varios trucos que podría usar, incluidos los nombres de variables 1char, la eliminación de espacios en blanco y el intcapricho de "variables que se supone que son a menos que usted diga lo contrario". +1 para el algoritmo y la implementación.
wizzwizz4
2
Ahhhh, ya veo. Sí, soy nuevo en esto. Recortará un poco de grasa e intentará nuevamente. Gracias por el consejo.
Jason Evans el
Puede guardar dos bytes mediante el uso de nombres de variables de un carácter; en realidad, puede ahorrar más al no utilizar variables y simplemente convertirlo en una sola expresión.
Pomo de la puerta
Sospecho que podrías omitir .ToArray().
Vlad
1
Sé que han pasado casi 2,5 años, pero puedes reducirlo a 82 bytes : using System.Linq;+ n=>!n.Distinct().SequenceEqual(n.Reverse().Distinct().Reverse())(desafortunadamente, la importación de Linq es obligatoria). Pruébalo en línea. Buena respuesta, +1 de mi parte!
Kevin Cruijssen
4

Japt, 12 bytes

Uâ ¬¦Uw â ¬w

Pruébalo en línea!

Gracias a @xnor por descifrar el algoritmo. La matriz de entrada se almacena automáticamente U, âes unificable, wes inversa y ¦es !=. ¬se une con la cadena vacía ( [1,2,3] => "123"); Esto es necesario porque la comparación de JavaScript cuenta dos matrices como no iguales a menos que sean el mismo objeto. Por ejemplo (código JS, no Japt):

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

Si este no fuera el caso, podríamos eliminar dos bytes simplemente no uniendo cada matriz:

Uâ ¦Uw â w
ETHproducciones
fuente
Parece que Japt podría querer implementar la igualdad de valores.
isaacg
4

ES6, 76 75 65 64 bytes

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

Puerto directo de las respuestas de @ xnor.

Editar: guardado 1 byte reemplazando a.lastIndexOf(x)==icon a.indexOf(x,i+1)<0.

Editar: Guardado 10 bytes gracias a @ user81655.

Editar: guardado 1 byte reemplazando r||icon r|i.

Neil
fuente
2
65 bytes usando una función:a=>(f=r=>a.filter((x,i)=>a.indexOf(x,r&&i+1)==(r||i))+a)()!=f(-1)
user81655
use ~ en lugar de <0.
Mama Fun Roll
@ ՊՓԼՃՐՊՃՈԲՍԼ No, quiero que sea -1. ~es el mismo que >=0.
Neil
Oh, espera, no importa: P
Mama Fun Roll
@ user81655 Lo siento, no he notado tu comentario antes por alguna razón. Truco, pero me gusta!
Neil
1

Java, 281 caracteres

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;}}
Mínimo
fuente
1

Python 3, 90 bytes

Esta función que toma la entrada como una lista de Python. Lamentablemente, las listas de Python no admiten directamente la búsqueda desde el final como lo hacen las cadenas rindex(), pero bueno.

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)
Tim Pederick
fuente