Problem overview
A drawing app keeps rectangles, squares and triangles in one list. You write the shape types so that code holding that list can ask any shape for its name and its perimeter, the length all the way around it, without knowing which kind of shape it is. That idea is called polymorphism: one call, shape.perimeter(), and each kind of shape runs its own version.
There are two parts:
- the classes: a parent
Shape(name"Shape", perimeter 0) and three children that override both methods,Rectangle(width, height),Square(side)andTriangle(a, b, c); - two methods of
Solution:totalPerimeter(shapes)returns the sum of all perimeters, andlargestShape(shapes)returns the name of the shape with the largest perimeter, the earliest one on a tie.
For a rectangle 3 by 4, a square of side 5 and a triangle with sides 3, 4 and 5, the perimeters are 14, 20 and 12. The total is 46 and the largest is the square.
Approach
Both methods take an Array<Shape>. Every element has the parent type, so the only calls the code can make are the ones Shape offers: name() and perimeter(). That is also exactly what the task demands. Never check which class a shape is; ask it. Then a new kind of shape, say a circle added next year, works with both methods unchanged, as long as it extends Shape and overrides the two methods.
Each method needs one pass over the array. totalPerimeter adds as it goes. largestShape remembers the best shape so far and replaces it only when it meets a strictly larger perimeter, which keeps the earliest shape on a tie.
Step by step
- Write
Shapewith its twoopenmethods:name()returns"Shape"andperimeter()returns0. A plain shape has no sides, and these defaults are what makes the common type have both methods. - In
Rectangle,name()returns"Rectangle"andperimeter()returns2 * (width + height). The class header already keepswidthandheightasvalproperties. - In
Square, the name is"Square"and the perimeter is4 * side. - In
Triangle, the name is"Triangle"and the perimeter isa + b + c. - In
totalPerimeter, startvar total = 0, loop over the shapes and addshape.perimeter(). Returntotalafter the loop. - In
largestShape, start withvar largest = shapes[0]. The array is never empty, so the first element exists. Loop over all shapes and, whenshape.perimeter() > largest.perimeter(), setlargest = shape. - Return
largest.name(). The object that won knows its own name.
The solution in Kotlin
open class Shape {
open fun name(): String {
return "Shape"
}
open fun perimeter(): Int {
return 0
}
}
class Rectangle(val width: Int, val height: Int) : Shape() {
override fun name(): String {
return "Rectangle"
}
override fun perimeter(): Int {
return 2 * (width + height)
}
}
class Square(val side: Int) : Shape() {
override fun name(): String {
return "Square"
}
override fun perimeter(): Int {
return 4 * side
}
}
class Triangle(val a: Int, val b: Int, val c: Int) : Shape() {
override fun name(): String {
return "Triangle"
}
override fun perimeter(): Int {
return a + b + c
}
}
class Solution {
fun totalPerimeter(shapes: Array<Shape>): Int {
var total = 0
for (shape in shapes) {
total += shape.perimeter()
}
return total
}
fun largestShape(shapes: Array<Shape>): String {
var largest = shapes[0]
for (shape in shapes) {
if (shape.perimeter() > largest.perimeter()) {
largest = shape
}
}
return largest.name()
}
}
Kotlin details worth knowing:
- Writing
valinside a class header, as inSquare(val side: Int), declares the constructor parameter and a read-only property in one go. - Each child writes
: Shape()to call the parent's constructor, and every method it replaces needsoverride. The parent's methods needopen, because Kotlin classes and methods are final by default. - In
for (shape in shapes), the variable has typeShape. The callshape.perimeter()runs the version of the object's real class.
A run
Called on three arrays of type Array<Shape>, the two methods give:
| Shapes | totalPerimeter | largestShape |
|---|---|---|
| Rectangle(3, 4), Square(5), Triangle(3, 4, 5) | 46 | Square |
| Rectangle(2, 4), Square(3), Triangle(4, 4, 4) | 36 | Rectangle |
| Square(1), Rectangle(1, 1), Triangle(2, 2, 3) | 15 | Triangle |
In the second row every perimeter is 12, so the first shape, the rectangle, wins the tie. In the third row a 1 by 1 rectangle has the same sides as a square, but it still answers Rectangle, because each object reports its own class. A variable of the parent type works the same way:
val s: Shape = Square(5)
println("${s.name()} ${s.perimeter()}")
println("${Shape().name()} ${Shape().perimeter()}")
Square 20
Shape 0Adding a new kind of shape
To see why the two methods never check classes, add a shape of your own in a file of your own:
class Hexagon(val side: Int) : Shape() {
override fun name(): String {
return "Hexagon"
}
override fun perimeter(): Int {
return 6 * side
}
}
With the array Square(5), Hexagon(4), Triangle(3, 4, 5), totalPerimeter returns 56 and largestShape returns Hexagon, and neither method was edited. Only the new class had to be written, which is the benefit of calling methods through the common type.
Complexity
Each method looks at every shape once and calls methods that take constant time, so both run in O(n) time for n shapes, with O(1) extra space: a couple of variables.
Edge cases and common mistakes
- Using
>=instead of>. It lets a later shape replace an equal earlier one, which breaks the tie rule. - Checking the class. Code like "if it is a Square, then 4 * side" defeats the point and fails for any new kind of shape.
- Forgetting
openoroverride. Without them the compiler rejects the child classes. - Starting
largestat 0. It must hold a shape, not a number, because the answer is a name. Starting fromshapes[0]is safe because the list is never empty. - A single shape. The loop compares the first shape with itself, changes nothing, and returns its name. That is correct.
