Guest User

Untitled

a guest
Apr 24th, 2019
70
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