21
\$\begingroup\$

Introduction

In the field of mathematics known as topology, there are things called separation axioms. Intuitively, you have a set X and a collection of subsets of X, which we can think of as properties. The system is well separated, if one can distinguish between all items of X based on their properties. The separation axioms formalize this idea. In this challenge, your task is to check three separation axioms, given X and the list of properties.

Input

Your inputs are an integer n ≥ 2, and a list of lists T of integers. The integers in T are drawn from X = [0, 1, ..., n-1]. The lists in T may be empty and unsorted, but they will not contain duplicates.

Output

Your output is one of four strings, determined by three separation axioms, each stronger than the last. There are other axioms, but we stick with these for simplicity.

  • Suppose that for all distinct x and y in X, there exists a list in T containing exactly one of them. Then X and T satisfy axiom T0.
  • Suppose that for all distinct x and y in X, there exist two lists in T, one of which contains x but not y, and the other contains y but not x. Then X and T satisfy axiom T1.
  • Suppose that the two lists above also contain no common elements. Then X and T satisfy axiom T2.

Your output is one of T2, T1, T0 or TS, depending on which of the above conditions holds (TS means none of them do). Note that T2 is stronger than T1, which is stronger than T0, and you should always output the strongest possible axiom.

Rules and scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

Test cases

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
\$\endgroup\$
  • \$\begingroup\$ Is the input n superfluous? In the rest of the challenge, I'm not seeing it used beyond defining what elements can be in T, so is it just a provided shortcut for T.Maximum()? \$\endgroup\$ – AdmBorkBork Jan 7 '16 at 14:20
  • \$\begingroup\$ @TimmyD, no. See the first test case. 0 [] should give T2. \$\endgroup\$ – Peter Taylor Jan 7 '16 at 14:56
  • \$\begingroup\$ @PeterTaylor Aaaahhhhhhhh. Thanks, that helps tremendously. \$\endgroup\$ – AdmBorkBork Jan 7 '16 at 15:01
  • \$\begingroup\$ Great explanation of what separability means! \$\endgroup\$ – Luis Mendo Jan 7 '16 at 21:15
  • \$\begingroup\$ @LuisMendo Weird terminology alert: These are separation axioms, and a topological spaces that satisfies T2 is sometimes called separated, but separability is something else entirely. \$\endgroup\$ – Dennis Jan 8 '16 at 13:36
9
+100
\$\begingroup\$

Haskell, 317 209 174 168 bytes

The function f does the job.

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

output:

TS
T0
T2
TS
T0
T0
T1
TS
T0
T1
T2
\$\endgroup\$
  • \$\begingroup\$ Giving t a function as input is a clever trick! \$\endgroup\$ – Zgarb Jan 7 '16 at 19:44
  • \$\begingroup\$ In absence of competition, this bounty goes to your answer. Congratulations! \$\endgroup\$ – Zgarb Jan 19 '16 at 18:52
  • \$\begingroup\$ some free bytes - replace f by an operator name, and replace p(x%y)(x%y) by p(x%y)$x%y. and by the way, nice work! \$\endgroup\$ – proud haskeller Oct 12 '16 at 21:29

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.