Séparez mes entiers

21

introduction

Dans le domaine des mathématiques connu sous le nom de topologie , il existe des choses appelées axiomes de séparation . Intuitivement, vous avez un ensemble Xet une collection de sous-ensembles de X, que nous pouvons considérer comme des propriétés. Le système est bien séparé, si l'on peut distinguer tous les éléments de Xsur la base de leurs propriétés. Les axiomes de séparation officialisent cette idée. Dans ce défi, votre tâche consiste à vérifier trois axiomes de séparation, donnés Xet la liste des propriétés.

Contribution

Vos entrées sont un entier n ≥ 2et une liste de listes Td'entiers. Les entiers Tsont tirés de X = [0, 1, ..., n-1]. Les listes dans Tpeuvent être vides et non triées, mais elles ne contiendront pas de doublons.

Production

Votre sortie est l'une des quatre chaînes, déterminées par trois axiomes de séparation, chacun plus fort que le précédent. Il existe d'autres axiomes, mais nous les conservons pour plus de simplicité.

  • Supposons que pour tous distincts xet ydans X, il existe une liste Tcontenant exactement un d'entre eux. Alors Xet Tsatisfont l' axiome T0 .
  • Supposons que pour tout distinct xet yin X, il existe deux listes in T, dont l'une contient xmais pas y, et l'autre contient ymais pas x. Alors Xet Tsatisfait à l' axiome T1 .
  • Supposons que les deux listes ci-dessus ne contiennent également aucun élément commun. Alors Xet Tsatisfont l' axiome T2 .

Votre sortie est l' un T2, T1, T0ou TS, selon lequel des conditions ci - dessus tient ( des TSmoyens qu'aucun d'entre eux ne). Notez que T2 est plus fort que T1, qui est plus fort que T0, et vous devez toujours produire l'axiome le plus fort possible.

Règles et notation

Vous pouvez écrire un programme complet ou une fonction. Le nombre d'octets le plus bas l'emporte et les failles standard sont interdites.

Cas de test

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
la source
L'entrée est-elle nsuperflue? Dans le reste du défi, je ne le vois pas utilisé au-delà de la définition des éléments qui peuvent être T, est-ce juste un raccourci fourni pour T.Maximum()?
AdmBorkBork
@TimmyD, non. Voir le premier cas de test. 0 []devrait donner T2.
Peter Taylor
@PeterTaylor Aaaahhhhhhhh. Merci, cela aide énormément.
AdmBorkBork
Grande explication de ce que signifie la séparabilité!
Luis Mendo
@LuisMendo Alerte terminologique bizarre: ce sont des axiomes de séparation, et un espace topologique qui satisfait T2 est parfois appelé séparé, mais la séparabilité est tout autre chose.
Dennis

Réponses:

9

Haskell, 317 209 174 168 octets

La fonction f fait le travail.

(#)=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]

tests:

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]]

production:

TS
T0
T2
TS
T0
T0
T1
TS
T0
T1
T2
Damien
la source
Donner tune fonction en entrée est une astuce astucieuse!
Zgarb
En l'absence de concurrence, cette prime va à votre réponse. Toutes nos félicitations!
Zgarb
certains octets libres - remplacer fpar un nom d'opérateur et remplacer p(x%y)(x%y)par p(x%y)$x%y. et au fait, beau travail!
fier haskeller du