At the time of writing this, the P vs NP problem is still unsolved, but you might have heard of Norbert Blum's new paper claiming proof that P != NP, which is already suspected to be erroneous (but we will see).
The problem discussed in this paper is the clique problem. At least that's what I read in a newspaper article, so correct me if I'm wrong, but in any case, I'd like you to write a program that solves the following variant:
Assume we have a large school with lots of students. Each of these students has some friends at this school. A clique of students is a group consisting only of students who are friends with each other member.
Your program will receive pairs of students who are friends as its input. From this information, the program must find the size of the largest clique. Students are identified by integer IDs.
If you prefer mathematical terms, this means you're fed the edges of an undirected graph, identified by two nodes each.
Your input will be a non-empty list of positive integer pairs, e.g.
[[1,2],[2,5],[1,5]]. You can take this input in any sensible form, e.g. as an array of arrays, as lines of text containing two numbers each, etc ...
The expected output is a single number
n >= 2: the size of the largest clique. With the example input above, the result would be
3, as all students (
5) are friends with each other.
[[1,2]] => 2 [[1,2],[3,1],[3,4]] => 2 [[1,2],[2,5],[1,5]] => 3 [[2,5],[2,3],[4,17],[1,3],[7,13],[5,3],[4,3],[4,1],[1,5],[5,4]] => 4 (the largest clique is [1,3,4,5]) [[15,1073],[23,764],[23,1073],[12,47],[47,15],[1073,764]] => 3 (the largest clique is [23,764,1073]) [[1296,316],[1650,316],[1296,1650],[1296,52],[1650,711],[711,316],[1650,52], [52,711],[1296,711],[52,316],[52,1565],[1565,1296],[1565,316],[1650,1565], [1296,138],[1565,138],[1565,711],[138,1650],[711,138],[138,144],[144,1860], [1296,1860],[1860,52],[711,1639]] => 6 (the largest clique is [52,316,711,1296,1565,1650])
You can use this (stupid) reference implementation (prints extra output with
-d flag) for verifying the results of other test cases.
- Your program doesn't need a defined result on invalid input. So you can assume that:
- you will always get at least one pair of IDs
- each pair consists of two different IDs
- no pair appears twice (swapping the places of the IDs would still be the same pair)
- Your algorithm isn't allowed to set an upper bound on input size. Purely technical limitations and limitations set by your language/environment (like stack size, computation time, etc) are of course inevitable.
- Standard loopholes are forbidden.
- This is code-golf, so the shortest code, measured in bytes, wins.
- If your algorithm has polynomial time complexity, you score
-1immediately regardless of your code size, but in that case, you might want to submit your solution somewhere else. ;)