Problem overview
A drawing app keeps rectangles, squares and triangles in one list. The code that holds the list wants to ask every shape for its name() and its perimeter() without knowing which kind it is. You write a parent class Shape, three subclasses that override both methods, and two methods of Solution: totalPerimeter(_:) and largestShape(_:).
Shape: name"Shape", perimeter 0.Rectangle(width, height): perimeter2 * (width + height).Square(side): perimeter4 * side.Triangle(a, b, c): perimetera + b + c.
For a 3 by 4 rectangle, a square of side 5 and a 3-4-5 triangle, the perimeters are 14, 20 and 12. The total is 46 and the largest shape is the square.
Approach
Both Solution methods get a [Shape] and call only perimeter() and name(), the two methods the common type has. They never ask which class a shape is. Each object runs its own version, so a new kind of shape added later works with both methods unchanged.
Each method visits every shape once, so the time is O(n) for n shapes and the extra space is O(1). largestShape keeps the best shape found so far and replaces it only when a perimeter is strictly greater, so on a tie the shape that came first stays.
Step by step
Shape'sname()returns"Shape"and itsperimeter()returns 0. The subclasses override both, so these are only the common defaults.- Each subclass declares its sizes as
varproperties of typeInt:widthandheight;side;a,bandc. - Its
initstores each parameter in the property of the same name, withself.in front. - Its
name()returns the class's name and itsperimeter()returns the formula above. totalPerimeterstartstotalat 0, loops over the shapes and addsshape.perimeter().largestShapestartslargestasshapes[0], loops over all shapes, replaceslargestwhenshape.perimeter() > largest.perimeter(), and returnslargest.name().
The solution in Swift
class Shape {
func name() -> String {
return "Shape"
}
func perimeter() -> Int {
return 0
}
}
class Rectangle: Shape {
var width: Int
var height: Int
init(_ width: Int, _ height: Int) {
self.width = width
self.height = height
}
override func name() -> String {
return "Rectangle"
}
override func perimeter() -> Int {
return 2 * (width + height)
}
}
class Square: Shape {
var side: Int
init(_ side: Int) {
self.side = side
}
override func name() -> String {
return "Square"
}
override func perimeter() -> Int {
return 4 * side
}
}
class Triangle: Shape {
var a: Int
var b: Int
var c: Int
init(_ a: Int, _ b: Int, _ c: Int) {
self.a = a
self.b = b
self.c = c
}
override func name() -> String {
return "Triangle"
}
override func perimeter() -> Int {
return a + b + c
}
}
class Solution {
func totalPerimeter(_ shapes: [Shape]) -> Int {
var total = 0
for shape in shapes {
total += shape.perimeter()
}
return total
}
func largestShape(_ shapes: [Shape]) -> String {
var largest = shapes[0]
for shape in shapes {
if shape.perimeter() > largest.perimeter() {
largest = shape
}
}
return largest.name()
}
}
Here are the three examples of the lesson:
let s = Solution()
let a: [Shape] = [Rectangle(3,4), Square(5), Triangle(3,4,5)]
print(s.totalPerimeter(a), s.largestShape(a))
let b: [Shape] = [Rectangle(2,4), Square(3), Triangle(4,4,4)]
print(s.totalPerimeter(b), s.largestShape(b))
let c: [Shape] = [Square(1), Rectangle(1,1), Triangle(2,2,3)]
print(s.totalPerimeter(c), s.largestShape(c))
46 Square
36 Rectangle
15 Triangle
In the second list all three perimeters are 12, and the rectangle wins because it comes first.
Swift details worth knowing
- The subclass
initsets only its own properties. Once every property has a value, Swift runsShape's owninitby itself, so no call tosuper.init()is written here. - The type of
largestisShape. Because it starts asshapes[0], which is aShape, it can later hold a rectangle, a square or a triangle. - Each object answers for its own class. A
Rectangle(1, 1)has the sides of a square but itsname()is still"Rectangle". In[Square(1), Rectangle(1,1)]both perimeters are 4, solargestShapegivesSquare.
Edge cases and common mistakes
- Using
>=in the comparison. It would move the answer to the last shape on a tie. - Checking the kind of shape. An
ifon the class inside the loop works today and breaks the idea: every new shape would need a new branch. - Forgetting
override. Swift refuses to compile a method that replaces the parent's without it. - A plain
Shape.Shape().name()is"Shape"andShape().perimeter()is 0.
Tracing the tie example
In the second example the list is a 2 by 4 rectangle, a square of side 3 and a triangle with sides 4, 4 and 4. Their perimeters are 2 * (2 + 4), 4 * 3 and 4 + 4 + 4: all three are 12. totalPerimeter adds them to 36. largestShape starts with the rectangle as largest. The square's 12 is not greater than 12, so it stays; the triangle's 12 is not greater either. The answer is Rectangle, and the program prints 36 Rectangle.
If the same shapes came in another order, the winner would change with it. That is why the comparison is strict and why the first shape is the starting value rather than 0 or an empty name: with a start value of the first shape there is no special case for an empty "best so far".
Adding a new shape
The two Solution methods were written against Shape only, so a shape that doesn't exist yet needs no change in them. Here is a regular hexagon, defined next to the others:
class Hexagon: Shape {{
var side: Int
init(_ side: Int) {{
self.side = side
}}
override func name() -> String {{
return "Hexagon"
}}
override func perimeter() -> Int {{
return 6 * side
}}
}}
let s = Solution()
let shapes: [Shape] = [Square(5), Hexagon(4), Triangle(3, 4, 5)]
print(s.totalPerimeter(shapes), s.largestShape(shapes))
56 Hexagon
The perimeters are 20, 24 and 12. Neither totalPerimeter nor largestShape was touched, and both handle the hexagon.
Properties are variables
The sizes are declared with var, so a shape can be changed after it is built. After let r = Rectangle(3, 4) and r.width = 10, the call r.perimeter() gives 28, because the method reads the current values. A class instance can be changed through a let constant, since the constant holds a reference to the object.
Key takeaways
- Code written against the parent type works for every subclass, including ones added later.
- Ties are decided by comparing strictly, so the first shape stays.
