SHARE
TWEET

Untitled

a guest Apr 24th, 2019 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import Foundation
  2.  
  3. extension Union {
  4.     func grouped() -> [Int: [Int]] {
  5.         var res = [Int: [Int]]()
  6.         for (k, _) in id {
  7.             if res[root(k)!] != nil {
  8.                 res[root(k)!]?.append(k)
  9.             } else {
  10.                 res[root(k)!] = [k]
  11.             }
  12.            
  13.         }
  14.         return res
  15.     }
  16. }
  17.  
  18. class Union {
  19.    
  20.     var id: [Int: Int] = [:]
  21.     var sizes: [Int: Int] = [:]
  22.     private var maxTreeSize: Int
  23.     private var size: Int
  24.    
  25.     init(size: Int) {
  26.         self.size = size
  27.         for i in (1...size) {
  28.             id[i] = i
  29.             sizes[i] = 1
  30.         }
  31.         maxTreeSize = size > 0 ? 1 : 0
  32.     }
  33.    
  34.     func root(_ i: Int) -> Int? {
  35.         guard id.keys.contains(i) else {
  36.             return nil
  37.         }
  38.         var k = i
  39.         while k != id[k]! {
  40.             id[k] = id[id[k]!]
  41.             k = id[k]!
  42.         }
  43.         return k
  44.     }
  45.    
  46.     func isConnected(p: Int, q: Int) -> Bool {
  47.         return root(p) == root(q)
  48.     }
  49.    
  50.     func union(p: Int, q: Int) {
  51.         guard let rootP = root(p), let rootQ = root(q), let pSize = sizes[rootP],  let qSize = sizes[rootQ] else {
  52.             return
  53.         }
  54.        
  55.         if pSize > qSize {
  56.             sizes[rootP] = pSize + (sizes[rootQ] ?? 0)
  57.             id[rootQ] = rootP
  58.             maxTreeSize = max(maxTreeSize, sizes[rootP]!)
  59.         } else {
  60.             sizes[rootQ] = qSize + (sizes[rootP] ?? 0)
  61.             id[rootP] = rootQ
  62.             maxTreeSize = max(maxTreeSize, sizes[rootQ]!)
  63.         }
  64.     }
  65.    
  66.     func areAllConnected() -> Bool {
  67.         return maxTreeSize == size
  68.     }
  69.    
  70. }
  71.  
  72.  
  73. class Percolation {
  74.    
  75.     var grid: [[Int]] = []
  76.     var openSites = 0
  77.     var virtualTop: Int
  78.     var virtualBottom: Int
  79.     var dimensionSize: Int
  80.     var un: Union
  81.    
  82.     init(n: Int) {
  83.         dimensionSize = n
  84.         for i in (0..<n) {
  85.             grid.append([])
  86.             for _ in (0..<n) {
  87.                 grid[i].append(0)
  88.             }
  89.         }
  90.         virtualTop = n * n + 1
  91.         virtualBottom = n * n + 2
  92.         un = Union(size: n * n + 2)
  93.         connectToVirtual()
  94.     }
  95.    
  96.     public func open(row: Int, col: Int) {
  97.         // open site (row, col) if it is not open already
  98.         let currenAddress = toAddress(row: row, col: col)
  99.         if !isOpen(row: row, col: col) {
  100.             grid[row - 1][col - 1] = 1
  101.             openSites += 1
  102.             if row - 1 > 0 && !un.isConnected(p: toAddress(row: row - 1, col: col), q: currenAddress) && isOpen(row: row - 1, col: col) {
  103.                 un.union(p: toAddress(row: row - 1, col: col), q: currenAddress)
  104.             }
  105.             if row + 1 <= dimensionSize && isOpen(row: row + 1, col: col) && !un.isConnected(p: toAddress(row: row + 1, col: col), q: currenAddress) {
  106.                 un.union(p: toAddress(row: row + 1, col: col), q: currenAddress)
  107.             }
  108.             //
  109.             if col - 1 > 0 && !un.isConnected(p: toAddress(row: row, col: col - 1), q: currenAddress) && isOpen(row: row, col: col - 1) {
  110.                 un.union(p: toAddress(row: row, col: col - 1), q: currenAddress)
  111.             }
  112.            
  113.             if col + 1 <= dimensionSize && !un.isConnected(p: toAddress(row: row, col: col + 1), q: currenAddress) && isOpen(row: row, col: col + 1) {
  114.                 un.union(p: toAddress(row: row, col: col + 1), q: currenAddress)
  115.             }
  116.            
  117.         }
  118.     }
  119.    
  120.     private func connectToVirtual() {
  121.         for i in (1...dimensionSize) {
  122.             if !un.isConnected(p: i, q: virtualTop) {
  123.                 un.union(p: i, q: virtualTop)
  124.             }
  125.            
  126.             if isOpen(row: dimensionSize, col: i) && !un.isConnected(p: toAddress(row: dimensionSize, col: i), q: virtualBottom) {
  127.                 un.union(p: toAddress(row: dimensionSize, col: i), q: virtualBottom)
  128.             }
  129.         }
  130.     }
  131.    
  132.     private func toAddress(row: Int, col: Int) -> Int {
  133.         return ((row - 1) * dimensionSize) + col
  134.     }
  135.    
  136.     public func isOpen(row: Int, col: Int) -> Bool {
  137.         // is site (row, col) open?
  138.         return grid[row - 1][col - 1] == 1
  139.     }
  140.    
  141.     public func isFull(row: Int, col: Int) -> Bool {
  142.         // is site (row, col) full?
  143.         let address = toAddress(row: row, col: col)
  144.         return un.isConnected(p: address, q: virtualTop)
  145.     }
  146.    
  147.     public func numberOfOpenSites() -> Int {
  148.         // number of open sites
  149.         return openSites
  150.     }
  151.    
  152.     public func percolates() -> Bool {
  153.         // does the system percolate?
  154.         return un.isConnected(p: virtualTop, q: virtualBottom)
  155.     }
  156.    
  157. }
  158.  
  159.  
  160. class PercolationStats {
  161.     var trialStat = [Double]()
  162.    
  163.     init(n: Int, trials: Int) {
  164.        
  165.         for _ in (1...trials) {
  166.             let perc = Percolation(n: n)
  167.             while !perc.percolates() {
  168.                 let i = Int.random(in: 1 ... n)
  169.                 let j = Int.random(in: 1 ... n)
  170.                 if !perc.isOpen(row: i, col: j) {
  171.                     perc.open(row: i, col: j)
  172.                 }
  173.             }
  174.             trialStat.append(Double(perc.openSites) / Double(n * n))
  175.         }
  176.     }
  177.     public func mean()  -> Double {
  178.         let sum: Double = trialStat.reduce(0) { (res, item) -> Double in
  179.             return res + item
  180.         }
  181.         return sum / Double(trialStat.count)
  182.     }
  183.     public func stddev()  -> Double {
  184.         let top = trialStat.reduce(0) { (res, item) -> Double in
  185.             res + pow(item + mean(), 2)
  186.         }
  187.         return top / Double(trialStat.count - 1)
  188.     }
  189.     //    public func confidenceLo() -> Double {
  190.     //                      // low  endpoint of 95% confidence interval
  191.     //    }
  192.     //    public func confidenceHi() -> Double {
  193.     //                       // high endpoint of 95% confidence interval
  194.     //    }
  195. }
  196.  
  197.  
  198.  
  199. let stats = PercolationStats(n: 200, trials: 100)
  200. print(stats.mean())
  201. print(stats.stddev())
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top