import Foundation

extension Union {
    func grouped() -> [Int: [Int]] {
        var res = [Int: [Int]]()
        for (k, _) in id {
            if res[root(k)!] != nil {
                res[root(k)!]?.append(k)
            } else {
                res[root(k)!] = [k]
            }

        }
        return res
    }
}

class Union {

    var id: [Int: Int] = [:]
    var sizes: [Int: Int] = [:]
    private var maxTreeSize: Int
    private var size: Int

    init(size: Int) {
        self.size = size
        for i in (1...size) {
            id[i] = i
            sizes[i] = 1
        }
        maxTreeSize = size > 0 ? 1 : 0
    }

    func root(_ i: Int) -> Int? {
        guard id.keys.contains(i) else {
            return nil
        }
        var k = i
        while k != id[k]! {
            id[k] = id[id[k]!]
            k = id[k]!
        }
        return k
    }

    func isConnected(p: Int, q: Int) -> Bool {
        return root(p) == root(q)
    }

    func union(p: Int, q: Int) {
        guard let rootP = root(p), let rootQ = root(q), let pSize = sizes[rootP],  let qSize = sizes[rootQ] else {
            return
        }

        if pSize > qSize {
            sizes[rootP] = pSize + (sizes[rootQ] ?? 0)
            id[rootQ] = rootP
            maxTreeSize = max(maxTreeSize, sizes[rootP]!)
        } else {
            sizes[rootQ] = qSize + (sizes[rootP] ?? 0)
            id[rootP] = rootQ
            maxTreeSize = max(maxTreeSize, sizes[rootQ]!)
        }
    }

    func areAllConnected() -> Bool {
        return maxTreeSize == size
    }

}


class Percolation {

    var grid: [[Int]] = []
    var openSites = 0
    var virtualTop: Int
    var virtualBottom: Int
    var dimensionSize: Int
    var un: Union

    init(n: Int) {
        dimensionSize = n
        for i in (0..<n) {
            grid.append([])
            for _ in (0..<n) {
                grid[i].append(0)
            }
        }
        virtualTop = n * n + 1
        virtualBottom = n * n + 2
        un = Union(size: n * n + 2)
        connectToVirtual()
    }

    public func open(row: Int, col: Int) {
        // open site (row, col) if it is not open already
        let currenAddress = toAddress(row: row, col: col)
        if !isOpen(row: row, col: col) {
            grid[row - 1][col - 1] = 1
            openSites += 1
            if row - 1 > 0 && !un.isConnected(p: toAddress(row: row - 1, col: col), q: currenAddress) && isOpen(row: row - 1, col: col) {
                un.union(p: toAddress(row: row - 1, col: col), q: currenAddress)
            }
            if row + 1 <= dimensionSize && isOpen(row: row + 1, col: col) && !un.isConnected(p: toAddress(row: row + 1, col: col), q: currenAddress) {
                un.union(p: toAddress(row: row + 1, col: col), q: currenAddress)
            }
            //
            if col - 1 > 0 && !un.isConnected(p: toAddress(row: row, col: col - 1), q: currenAddress) && isOpen(row: row, col: col - 1) {
                un.union(p: toAddress(row: row, col: col - 1), q: currenAddress)
            }

            if col + 1 <= dimensionSize && !un.isConnected(p: toAddress(row: row, col: col + 1), q: currenAddress) && isOpen(row: row, col: col + 1) {
                un.union(p: toAddress(row: row, col: col + 1), q: currenAddress)
            }

        }
    }

    private func connectToVirtual() {
        for i in (1...dimensionSize) {
            if !un.isConnected(p: i, q: virtualTop) {
                un.union(p: i, q: virtualTop)
            }

            if isOpen(row: dimensionSize, col: i) && !un.isConnected(p: toAddress(row: dimensionSize, col: i), q: virtualBottom) {
                un.union(p: toAddress(row: dimensionSize, col: i), q: virtualBottom)
            }
        }
    }

    private func toAddress(row: Int, col: Int) -> Int {
        return ((row - 1) * dimensionSize) + col
    }

    public func isOpen(row: Int, col: Int) -> Bool {
        // is site (row, col) open?
        return grid[row - 1][col - 1] == 1
    }

    public func isFull(row: Int, col: Int) -> Bool {
        // is site (row, col) full?
        let address = toAddress(row: row, col: col)
        return un.isConnected(p: address, q: virtualTop)
    }

    public func numberOfOpenSites() -> Int {
        // number of open sites
        return openSites
    }

    public func percolates() -> Bool {
        // does the system percolate?
        return un.isConnected(p: virtualTop, q: virtualBottom)
    }

}


class PercolationStats {
    var trialStat = [Double]()

    init(n: Int, trials: Int) {

        for _ in (1...trials) {
            let perc = Percolation(n: n)
            while !perc.percolates() {
                let i = Int.random(in: 1 ... n)
                let j = Int.random(in: 1 ... n)
                if !perc.isOpen(row: i, col: j) {
                    perc.open(row: i, col: j)
                }
            }
            trialStat.append(Double(perc.openSites) / Double(n * n))
        }
    }
    public func mean()  -> Double {
        let sum: Double = trialStat.reduce(0) { (res, item) -> Double in
            return res + item
        }
        return sum / Double(trialStat.count)
    }
    public func stddev()  -> Double {
        let top = trialStat.reduce(0) { (res, item) -> Double in
            res + pow(item + mean(), 2)
        }
        return top / Double(trialStat.count - 1)
    }
    //    public func confidenceLo() -> Double {
    //                      // low  endpoint of 95% confidence interval
    //    }
    //    public func confidenceHi() -> Double {
    //                       // high endpoint of 95% confidence interval
    //    }
}



let stats = PercolationStats(n: 200, trials: 100)
print(stats.mean())
print(stats.stddev())