Separa mis enteros

21

Introducción

En el campo de las matemáticas conocido como topología , hay cosas llamadas axiomas de separación . Intuitivamente, tiene un conjunto Xy una colección de subconjuntos de X, que podemos considerar como propiedades. El sistema está bien separado, si se puede distinguir entre todos los elementos en Xfunción de sus propiedades. Los axiomas de separación formalizan esta idea. En este desafío, su tarea es verificar tres axiomas de separación, dados Xy la lista de propiedades.

Entrada

Sus entradas son un número entero n ≥ 2y una lista de listas Tde enteros. Los enteros Tse extraen de X = [0, 1, ..., n-1]. Las listas Tpueden estar vacías y sin clasificar, pero no contendrán duplicados.

Salida

Su salida es una de cuatro cadenas, determinada por tres axiomas de separación, cada uno más fuerte que el anterior. Hay otros axiomas, pero nos quedamos con estos por simplicidad.

  • Suponga que para todos los distintos xy yen X, existe una lista que Tcontiene exactamente uno de ellos. Entonces Xy Tsatisfacer axioma T0 .
  • Supongamos que para todos los distintos xy yen X, existen dos listas en T, una de las cuales contiene xpero no y, y la otra contiene ypero no x. Entonces Xy Tsatisfacer axioma T1 .
  • Suponga que las dos listas anteriores tampoco contienen elementos comunes. Entonces Xy Tsatisfacer axioma T2 .

Su salida es uno de T2, T1, T0o TS, dependiendo de cuál de las anteriores condiciones bodegas ( TSsignifica que ninguno de ellos lo hacen). Tenga en cuenta que T2 es más fuerte que T1, que es más fuerte que T0, y siempre debe generar el axioma más fuerte posible.

Reglas y puntaje

Puede escribir un programa completo o una función. El conteo de bytes más bajo gana, y las lagunas estándar no se permiten.

Casos de prueba

2 [] -> TS
2 [[],[1]] -> T0
2 [[0],[1]] -> T2
3 [[0],[0,1,2],[1,2]] -> TS
3 [[],[0],[0,1],[2]] -> T0
3 [[0],[0,1],[2,1],[0,1,2]] -> T0
3 [[0],[0,1],[2,1],[2,0]] -> T1
6 [[0,2,4],[0,3,5],[1,2],[3,4,5]] -> TS
6 [[0,2,4],[0,3,5],[1,2],[2,5],[3,4,5]] -> T0
6 [[0,2,4],[0,3,5],[1,2],[2,5],[3,1],[3,4,5]] -> T1
6 [[0,1],[0,2,3],[1,4],[2,4],[2,3,5],[1,3],[4,5]] -> T2
Zgarb
fuente
¿La entrada es nsuperflua? En el resto del desafío, no veo que se use más allá de definir qué elementos pueden estar T, entonces, ¿es solo un atajo proporcionado T.Maximum()?
AdmBorkBork
@TimmyD, no. Ver el primer caso de prueba. 0 []debería dar T2.
Peter Taylor
@PeterTaylor Aaaahhhhhhhh. Gracias, eso ayuda enormemente.
AdmBorkBork
¡Gran explicación de lo que significa la separabilidad!
Luis Mendo
@LuisMendo Alerta de terminología extraña: estos son axiomas de separación, y los espacios topológicos que satisfacen T2 a veces se llaman separados, pero separabilidad es algo completamente diferente.
Dennis

Respuestas:

9

Haskell, 317 209 174 168 bytes

La función f hace el trabajo.

(#)=elem
x?y=[1|a<-x,b<-y,not$any(#a)b]
f n l|t(++)="TS"|t zip="T0"|t(?)="T1"|1>0="T2"where
    t p=any null[p(x%y)(y%x)|x<-[0..n-1],y<-[0..x-1]]
    x%y=[z|z<-l,x#z,not$y#z]

pruebas:

main=do
    putStrLn $ f 2 []
    putStrLn $ f 2 [[],[1]]
    putStrLn $ f 2 [[0],[1]]
    putStrLn $ f 3 [[0],[0,1,2],[1,2]]
    putStrLn $ f 3 [[],[0],[0,1],[2]]
    putStrLn $ f 3 [[0],[0,1],[2,1],[0,1,2]]
    putStrLn $ f 3 [[0],[0,1],[2,1],[2,0]]
    putStrLn $ f 6 [[0,2,4],[0,3,5],[1,2],[3,4,5]]
    putStrLn $ f 6 [[0,2,4],[0,3,5],[1,2],[2,5],[3,4,5]]
    putStrLn $ f 6 [[0,2,4],[0,3,5],[1,2],[2,5],[3,1],[3,4,5]]
    putStrLn $ f 6 [[0,1],[0,2,3],[1,4],[2,4],[2,3,5],[1,3],[4,5]]

salida:

TS
T0
T2
TS
T0
T0
T1
TS
T0
T1
T2
Damien
fuente
¡Dar tuna función como entrada es un truco inteligente!
Zgarb
En ausencia de competencia, esta recompensa va a su respuesta. ¡Felicidades!
Zgarb
algunos bytes libres: reemplácelos fpor un nombre de operador y sustitúyalos p(x%y)(x%y)por p(x%y)$x%y. y por cierto, buen trabajo!
orgulloso Haskeller