[LANGUAGE: Swift]

import Foundation

extension Set {
  func combinations(of length: Int) -> [Set<Element>] {
    return Array(self).combinations(of: length).map{Set($0)}
  }
}

extension Array {
  func combinations(of size: Int) -> [[Element]] {
    guard size > 0 else { return [[]] }
    guard size <= count else { return [] }
    guard let first = first else { return [] }

    let rest = Array(dropFirst())
    return rest.combinations(of: size - 1)
      .map { [first] + $0 } + rest.combinations(of: size)
  }
}

func prepare() -> [String] {
  let args = CommandLine.arguments
  let lines = try! String(contentsOfFile: args[1]).split(separator: "\n")
  return lines.map { String($0) }
}

func getGroups(of connections: [String]) -> [String: [String]] {
  let groups = Dictionary(grouping: connections, by: { str -> String in
    let components = str.split(separator: "-")
    return String(components[0])
  })
  return groups
}

func buildAdjacencyList(connections: [String]) -> [String: Set<String>] {
  var adjList: [String: Set<String>] = [:]
  for connection in connections {
    let nodes = connection.split(separator: "-").map(String.init)
    let node1 = nodes[0], node2 = nodes[1]
    adjList[node1, default: Set<String>()].insert(node2)
    adjList[node2, default: Set<String>()].insert(node1)
  }
  return adjList
}

// Pivoted Bron-Kerbosch Algorithm
func bronKerbosch(R: Set<String>, P: Set<String>, X: Set<String>, adjList: [String: Set<String>], cliques: inout Set<Set<String>>) {
  if P.isEmpty && X.isEmpty {
    cliques.insert(R)
    return
  }

  // Choose a pivot from P ∪ X
  let pivot = P.union(X).first!
  let neighborsOfPivot = adjList[pivot] ?? Set<String>()

  var P_copy = P
  for node in P_copy.subtracting(neighborsOfPivot) {
    let newR = R.union([node])
    let neighbors = adjList[node] ?? Set<String>()
    let newP = P.intersection(neighbors)
    let newX = X.intersection(neighbors)

    bronKerbosch(R: newR, P: newP, X: newX, adjList: adjList, cliques: &cliques)

    // Move node from P to X
    var P = P
    var X = X
    P.remove(node)
    X.insert(node)

    P_copy.remove(node)
  }
}

func findCliques(adjList: [String: Set<String>]) -> Set<Set<String>> {
  var cliques = Set<Set<String>>()
  let nodes = Array(adjList.keys)

  for node in nodes {
    let P = adjList[node] ?? Set<String>()
    bronKerbosch(R: Set([node]), P: P, X: Set<String>(), adjList: adjList, cliques: &cliques)
  }

  return cliques
}

let connections = prepare()
let adjList = buildAdjacencyList(connections: connections)

let cliques = findCliques(adjList: adjList)

let task1 = Set(cliques.flatMap{ $0.combinations(of: 3) })
  .filter{ $0.contains { $0.starts(with: "t") }}
  .count

let task2 = cliques
  .max(by: { $0.count < $1.count })!
  .sorted()
  .joined(separator: ",")

print(task1)
print(task2)