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.


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.


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
  • \$\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\$ Commented Jan 7, 2016 at 14:20
  • \$\begingroup\$ @TimmyD, no. See the first test case. 0 [] should give T2. \$\endgroup\$ Commented Jan 7, 2016 at 14:56
  • \$\begingroup\$ @PeterTaylor Aaaahhhhhhhh. Thanks, that helps tremendously. \$\endgroup\$ Commented Jan 7, 2016 at 15:01
  • \$\begingroup\$ Great explanation of what separability means! \$\endgroup\$
    – Luis Mendo
    Commented Jan 7, 2016 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
    Commented Jan 8, 2016 at 13:36

1 Answer 1


Haskell, 317 209 174 168 bytes

The function f does the job.

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

tests :

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


  • \$\begingroup\$ Giving t a function as input is a clever trick! \$\endgroup\$
    – Zgarb
    Commented Jan 7, 2016 at 19:44
  • \$\begingroup\$ In absence of competition, this bounty goes to your answer. Congratulations! \$\endgroup\$
    – Zgarb
    Commented Jan 19, 2016 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\$ Commented Oct 12, 2016 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.