Update README. Add unoptimized RectangleBuilderGreaterArea solution.

omalovichko · Jul 6, 2019 · a191211 · a191211
1 parent b75d93d
commit a191211
Show file tree

Hide file tree

Showing 3 changed files with 190 additions and 64 deletions.
diff --git a/CodilityLessonsTests/Lesson14_MinMaxDivision.swift b/CodilityLessonsTests/Lesson14_MinMaxDivision.swift
@@ -64,18 +64,13 @@ class Lesson14_MinMaxDivision: XCTestCase {
 
     func test() {
         var a = [Int]()
+        var k: Int
+        var m: Int
 
-//        a = [8, 5, 3, 4, 6, 8]
-//        XCTAssertEqual(solution(&a), 6)
-//
-//        a = [1, 4, -3]
-//        XCTAssertEqual(solution(&a), 1)
-//
-//        a = [-8, 4, 5, -10, 3]
-//        XCTAssertEqual(solution(&a), 3)
-//
-//        a = [0]
-//        XCTAssertEqual(solution(&a), 0)
+        a = [2, 1, 5, 1, 2, 2, 2]
+        k = 3
+        m = 5
+//        XCTAssertEqual(solution(k, m, &a), 6)
     }
 
 //    func testPerformance() {
@@ -88,7 +83,66 @@ class Lesson14_MinMaxDivision: XCTestCase {
 //        }
 //    }
 
-    public func solution(_ K : Int, _ M : Int, _ A : inout [Int]) -> Int {
-        return 0
-    }
+//    public func solution(_ K : Int, _ M : Int, _ A : inout [Int]) -> Int {
+//        var prefixSums = [0]
+//        for i in 0..<A.count {
+////            totalSum += A[i]
+//            prefixSums.append(prefixSums.last! + A[i])
+//        }
+//        
+//        let totalSum = prefixSums.last!
+//        
+//        let calc: (_ startIndex: Int) -> Int = { startIndex in
+//            for i in startIndex..<prefixSums.count {
+//                let totalLeftSum = prefixSums[i]
+//                let sum = totalLeftSum - handledLeftSum
+//                
+//                if targetSum == sum {
+//                    handledLeftSum = totalLeftSum
+//                    blocks += 1
+//                }
+//            }
+//            return 1
+//        }
+//        
+//        
+//        var targetSum = totalSum / K
+//        
+//        var handledLeftSum = 0
+//        var blocks = 0
+//        
+//        
+//        
+//        
+////        var totalSum = prefixSums.last!
+////
+////        var targetSum = totalSum / K
+////
+////        var left = 0
+////        var right = A.count - 1
+////        var handledLeftSum = 0
+////        var position = -1
+////        var currentLeftSum = -1
+////
+////        repeat {
+////            let mid = (left + right) / 2
+////            let totalLeftSum = prefixSums[mid]
+////            let leftSum = totalLeftSum - handledLeftSum
+////
+////            if leftSum == targetSum {
+////                handledLeftSum = totalLeftSum
+////                position = mid
+////                break
+////            } else if leftSum > targetSum {
+////                right = mid - 1
+////            } else {
+////                left = mid + 1
+////                position = mid
+////                currentLeftSum = leftSum
+////            }
+////        } while left <= right
+////        print(position)
+//        
+//        return targetSum
+//    }
 }
diff --git a/CodilityLessonsTests/Lesson91_RectangleBuilderGreaterArea.swift b/CodilityLessonsTests/Lesson91_RectangleBuilderGreaterArea.swift
@@ -8,95 +8,167 @@
 
 import XCTest
 
+/*
+ RectangleBuilderGreaterArea
+ Count the distinct rectangle sizes, of area greater than or equal to X, that can be built out of a given set of segments.
+
+
+ Halfling Woolly Proudhoof is an eminent sheep herder. He wants to build a pen (enclosure) for his new flock of sheep. The pen will be rectangular and built from exactly four pieces of fence (so, the pieces of fence forming the opposite sides of the pen must be of equal length). Woolly can choose these pieces out of N pieces of fence that are stored in his barn. To hold the entire flock, the area of the pen must be greater than or equal to a given threshold X.
+
+ Woolly is interested in the number of different ways in which he can build a pen. Pens are considered different if the sets of lengths of their sides are different. For example, a pen of size 1×4 is different from a pen of size 2×2 (although both have an area of 4), but pens of sizes 1×2 and 2×1 are considered the same.
+
+ Write a function:
+
+ public func solution(_ A : inout [Int], _ X : Int) -> Int
+ that, given an array A of N integers (containing the lengths of the available pieces of fence) and an integer X, returns the number of different ways of building a rectangular pen satisfying the above conditions. The function should return −1 if the result exceeds 1,000,000,000.
+
+ For example, given X = 5 and the following array A:
+
+ A[0] = 1
+ A[1] = 2
+ A[2] = 5
+ A[3] = 1
+ A[4] = 1
+ A[5] = 2
+ A[6] = 3
+ A[7] = 5
+ A[8] = 1
+
+ the function should return 2. The figure above shows available pieces of fence (on the left) and possible to build pens (on the right). The pens are of sizes 1x5 and 2x5. Pens of sizes 1×1 and 1×2 can be built, but are too small in area. It is not possible to build pens of sizes 2×3 or 3×5, as there is only one piece of fence of length 3.
+
+ Write an efficient algorithm for the following assumptions:
+
+ N is an integer within the range [0..100,000];
+ X is an integer within the range [1..1,000,000,000];
+ each element of array A is an integer within the range [1..1,000,000,000].
+*/
 class Lesson91_RectangleBuilderGreaterArea: XCTestCase {
 
     func test() {
         var a = [Int]()
 
+        a = [1, 2, 3, 5, 8, 13, 21, 34, 55, 1, 2, 3, 5, 8, 13, 21, 34, 55]
+        XCTAssertEqual(solution(&a, 100), 16)
+
+        a = [1, 2, 5, 1, 1, 2, 3, 5, 1]
+        XCTAssertEqual(solution(&a, 5), 2)
+
+        a = []
+        XCTAssertEqual(solution(&a, 1), 0)
+
         a = [1, 1, 2, 2, 3, 3, 100, 100]
         XCTAssertEqual(solution(&a, 10), 3)
-        
+
         a = [2, 3, 2, 3, 2, 3, 2, 3]
         XCTAssertEqual(solution(&a, 9), 1)
 
         a = [6, 6, 6, 6, 6, 6]
         XCTAssertEqual(solution(&a, 10), 1)
 
-        a = [1, 2, 5, 1, 1, 2, 3, 5, 1]
-        XCTAssertEqual(solution(&a, 5), 2)
-
         a = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7]
         XCTAssertEqual(solution(&a, 5), 18)
     }
 
     func testPerformance() {
         var a = [Int]()
-        for _ in 0..<100_000 {
-            a.append(Int(arc4random_uniform(1_000_000_000)))
+        for i in 1..<50_000 {
+            a.append(i)
+            a.append(i)
         }
         measure {
-            _ = self.solution(&a, 500_000_000)
+            _ = self.solution(&a, 1)//500_000_000)
         }
     }
 
     public func solution(_ A : inout [Int], _ X : Int) -> Int {
+        // key: length, value: count
+        var piecesCount = [Int: Int]()
+        for i in 0..<A.count {
+            let pieceLength = A[i]
+            if let count = piecesCount[pieceLength] {
+                piecesCount[pieceLength] = count + 1
+            } else {
+                piecesCount[pieceLength] = 1
+            }
+        }
+
+        var fencesCount = 0
+
+        let sqrtX = Int(sqrt(Double(X)).rounded(.up))
+
+        // [X, ...]
+        var longPiecesCount = 0
 
-        var livestockPens = Set<LivestockPen>()
-        var fencePieces = Dictionary<Int, Int>()
+        // [sqrtX, X)
+        var mediumPieces = [Int]()
 
-        for a in A {
+        // [1, sqrtX)
+        var shortPieces = [Int]()
+
+        for entry in piecesCount {
+            let count = entry.value
+            guard count >= 2 else {
+                continue
+            }
 
-            if let count = fencePieces[a] {
-                fencePieces[a] = count + 1
-                guard count >= 1 else {
-                    continue
+            let length = entry.key
+
+            if length >= X {
+                if count >= 4 {
+                    // It is square, so + 1
+                    fencesCount += 1
                 }
 
-                for (length, count) in fencePieces {
-                    guard count >= 2 else {
-                        continue
-                    }
-                    guard length * a >= X else {
-                        continue
-                    }
-                    if length == a {
-                        if count >= 4 {
-                            livestockPens.insert(LivestockPen(a, length))
-                        }
-                    } else {
-                        livestockPens.insert(LivestockPen(a, length))
-                    }
+                longPiecesCount += 1
+            } else if length >= sqrtX {
+                if count >= 4 {
+                    // It is square, so + 1
+                    fencesCount += 1
                 }
 
+                mediumPieces.append(length)
             } else {
-                fencePieces[a] = 1
+                shortPieces.append(length)
             }
         }
 
-        return livestockPens.count
-    }
-
-    struct LivestockPen: Hashable {
+        let ml = mediumPieces.count + longPiecesCount
+        fencesCount += ((ml - 1) * ml) / 2
+        fencesCount += shortPieces.count * longPiecesCount
+
+        if fencesCount > 1_000_000_000 {
+            return -1
+        }
 
-        var longestSide: Int
-        var shortestSide: Int
+        var shortPiecesSorted = shortPieces.sorted()
+        var mediumPiecesSorted = mediumPieces.sorted()
 
-        init(_ firstSide: Int, _ secondSide: Int) {
-            if firstSide > secondSide {
-                self.longestSide = firstSide
-                self.shortestSide = secondSide
-            } else {
-                self.longestSide = secondSide
-                self.shortestSide = firstSide
+        // Caterpillar method
+        var shortEdge = shortPiecesSorted.count
+        var mediumEdge = mediumPiecesSorted.count
+        var i = 0
+        while i < shortEdge {
+            let short = shortPiecesSorted[i]
+
+            var j = 0
+            while j < mediumEdge {
+                let medium = mediumPiecesSorted[j]
+
+                if short * medium >= X {
+                    let a = shortPiecesSorted.count - i
+                    let b = mediumEdge - j
+                    fencesCount += a * b
+                    mediumEdge = j
+                    break
+                }
+                j += 1
             }
+            if fencesCount > 1_000_000_000 {
+                return -1
+            }
+            i += 1
         }
 
-        public var hashValue: Int {
-            return "\(longestSide):\(shortestSide)".hashValue
-        }
-
-        public static func ==(lhs: LivestockPen, rhs: LivestockPen) -> Bool {
-            return lhs.longestSide == rhs.longestSide && lhs.shortestSide == rhs.shortestSide
-        }
+        return fencesCount
     }
 }
diff --git a/README.md b/README.md
@@ -72,8 +72,8 @@ __Lesson 13 - Fibonacci numbers__
 * FibFrog: Count the minimum number of jumps required for a frog to get to the other side of a river.
 
 __Lesson 14 - Binary search algorithm__
-* ~~NailingPlanks: Count the minimum number of nails that allow a series of planks to be nailed.~~
 * ~~MinMaxDivision: Divide array A into K blocks and minimize the largest sum of any block.~~
+* NailingPlanks: Count the minimum number of nails that allow a series of planks to be nailed.
 
 __Lesson 15 - Caterpillar method__
 * CountDistinctSlices: Count the number of distinct slices (containing only unique numbers).