Last active
February 25, 2018 00:13
-
-
Save SwiftArchitect/0860c4bba5c842a215241bc497658d56 to your computer and use it in GitHub Desktop.
Swift Xcode implementation of InterviewCake 'Rectangle Intersection' with linear intersection (not range) performing in O(1). ⚠️ Spoiler alert: this is an actual answer to the https://www.interviewcake.com/question/swift/rectangular-love? question, so no peeking!
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// | |
// RectangleLove.swift | |
// | |
// Copyright © 2018 Xavier Schott | |
// Permission is hereby granted, free of charge, to any person obtaining a copy | |
// of this software and associated documentation files (the "Software"), to deal | |
// in the Software without restriction, including without limitation the rights | |
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell | |
// copies of the Software, and to permit persons to whom the Software is | |
// furnished to do so, subject to the following conditions: | |
// | |
// The above copyright notice and this permission notice shall be included in | |
// all copies or substantial portions of the Software. | |
// | |
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE | |
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | |
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, | |
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN | |
// THE SOFTWARE. | |
// | |
import Foundation | |
struct Rectangle: CustomStringConvertible { | |
// coordinates of bottom left corner | |
let leftX: Int | |
let bottomY: Int | |
// dimensions | |
let width: Int | |
let height: Int | |
init(leftX: Int, bottomY: Int, width: Int, height: Int) { | |
self.leftX = leftX | |
self.bottomY = bottomY | |
self.width = width | |
self.height = height | |
} | |
init() { | |
self.init(leftX: 0, bottomY: 0, width: 0, height: 0) | |
} | |
var description: String { | |
return String(format: "(%d, %d, %d, %d)", leftX, bottomY, width, height) | |
} | |
} | |
extension Rectangle: Equatable { | |
public static func == (lhs: Rectangle, rhs: Rectangle) -> Bool { | |
return | |
lhs.leftX == rhs.leftX && | |
lhs.bottomY == rhs.bottomY && | |
lhs.width == rhs.width && | |
lhs.height == rhs.height | |
} | |
} | |
extension Rectangle { | |
init(leftX: Int, rightX: Int, bottomY: Int, topY: Int) { | |
if rightX <= leftX || topY <= bottomY { | |
self.init(leftX: 0, bottomY: 0, width: 0, height: 0) | |
} else { | |
self.init(leftX: leftX, bottomY: bottomY, width: rightX - leftX, height: topY - bottomY) | |
} | |
} | |
} | |
class RectangleLove | |
{ | |
func intersection(a: Rectangle, b: Rectangle) -> Rectangle { | |
let x1 = max(a.leftX, b.leftX) | |
let x2 = min(a.leftX + a.width, b.leftX + b.width) | |
let y1 = max(a.bottomY, b.bottomY) | |
let y2 = min(a.bottomY + a.height, b.bottomY + b.height) | |
return Rectangle(leftX: x1, | |
rightX: x2, | |
bottomY: y1, | |
topY: y2) | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// | |
// RectangleLoveTests.swift | |
// | |
// Copyright © 2018 Xavier Schott | |
// Permission is hereby granted, free of charge, to any person obtaining a copy | |
// of this software and associated documentation files (the "Software"), to deal | |
// in the Software without restriction, including without limitation the rights | |
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell | |
// copies of the Software, and to permit persons to whom the Software is | |
// furnished to do so, subject to the following conditions: | |
// | |
// The above copyright notice and this permission notice shall be included in | |
// all copies or substantial portions of the Software. | |
// | |
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE | |
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | |
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, | |
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN | |
// THE SOFTWARE. | |
// | |
import XCTest | |
class RectangleLoveTests: XCTestCase { | |
func testRectangleLoveQuestion() { | |
let a = Rectangle(leftX: 1, bottomY: 1, width: 6, height: 3) | |
let b = Rectangle(leftX: 5, bottomY: 2, width: 3, height: 6) | |
let expected = Rectangle(leftX: 5, bottomY: 2, width: 2, height: 2) | |
let result = RectangleLove().intersection(a: a, b: b) | |
XCTAssertEqual(expected, result) | |
} | |
func testRectangleLoveNegative() { | |
let a = Rectangle(leftX: -9, bottomY: 1, width: 6, height: 3) | |
let b = Rectangle(leftX: -5, bottomY: 2, width: 3, height: 6) | |
let expected = Rectangle(leftX: -5, bottomY: 2, width: 2, height: 2) | |
let result = RectangleLove().intersection(a: a, b: b) | |
XCTAssertEqual(expected, result) | |
} | |
func testRectangleLoveNoIntersection() { | |
let a = Rectangle(leftX: 1, bottomY: 1, width: 6, height: 3) | |
let b = Rectangle(leftX: 7, bottomY: 2, width: 3, height: 6) | |
let expected = Rectangle() | |
let result = RectangleLove().intersection(a: a, b: b) | |
XCTAssertEqual(expected, result) | |
} | |
func testRectangleLoveInside() { | |
let a = Rectangle(leftX: 1, bottomY: 1, width: 6, height: 6) | |
let b = Rectangle(leftX: 2, bottomY: 2, width: 3, height: 3) | |
let expected = Rectangle(leftX: 2, bottomY: 2, width: 3, height: 3) | |
let result = RectangleLove().intersection(a: a, b: b) | |
XCTAssertEqual(expected, result) | |
} | |
func testRectangleLoveEdge() { | |
let a = Rectangle(leftX: 1, bottomY: 1, width: 6, height: 6) | |
let b = Rectangle(leftX: 7, bottomY: 2, width: 3, height: 3) | |
let expected = Rectangle() | |
let result = RectangleLove().intersection(a: a, b: b) | |
XCTAssertEqual(expected, result) | |
} | |
func testRectangleLoveCorner() { | |
let a = Rectangle(leftX: 1, bottomY: 1, width: 6, height: 6) | |
let b = Rectangle(leftX: 7, bottomY: 7, width: 3, height: 3) | |
let expected = Rectangle() | |
let result = RectangleLove().intersection(a: a, b: b) | |
XCTAssertEqual(expected, result) | |
} | |
func testRectangleLovePerformance() { | |
var lotsOfRanctangles = [Rectangle]() | |
for _ in 0 ..< 1000000 { | |
lotsOfRanctangles.append(Rectangle(leftX: Int(arc4random_uniform(1024)), | |
bottomY: Int(arc4random_uniform(1024)), | |
width: Int(arc4random_uniform(1024)), | |
height: Int(arc4random_uniform(1024)))) | |
} | |
let r = RectangleLove() | |
self.measure { | |
var aRectangle = lotsOfRanctangles[0] | |
for i in 1 ..< lotsOfRanctangles.count { | |
let bRectangle = lotsOfRanctangles[i] | |
_ = r.intersection(a: aRectangle, b: bRectangle) | |
aRectangle = bRectangle | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Even though the
Rectangle
structure contains an origin and a size, naturally leading to range intersections on the horizontal and vertical axis, the proposed solution uses linear min and max by calculating the top-right coordinates. This makes for a very compact solution in theintersection
method.The
Rectangle
validity is left to a newinit(leftX: Int, rightX: Int, bottomY: Int, topY: Int)
method, implemented as anextension
, which guarantees the rectangle isn't negative.