Start learning free

LESSON 564 OF 573 · OBJECT-ORIENTED PROGRAMMING - CHALLENGES

Shapes Perimeter in Scala: Polymorphism

Practice O(n) Read the full explanation

A drawing app keeps rectangles, squares and triangles in one list. 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 is polymorphism: one call, shape.perimeter(), and each kind of shape runs its own version.

Every shape class inherits from the class Shape, the common type. Shape has two methods:

  • name() returns the kind of shape as text: "Shape" for a plain Shape.
  • perimeter() returns the length around the shape: 0 for a plain Shape.

Each shape class overrides both:

  • Rectangle(width, height): its name is "Rectangle", its perimeter 2 × (width + height).
  • Square(side): its name is "Square", its perimeter 4 × side.
  • Triangle(a, b, c): its name is "Triangle", its perimeter a + b + c.

In Scala each shape class extends Shape and writes its versions of the methods with override def. Each shape class gets its sizes as val parameters of its constructor.

Then write two methods of the class Solution, as in the course's other lessons. Both get the shapes as Array[Shape]:

  • totalPerimeter(shapes) returns the sum of the perimeters of all the shapes.
  • largestShape(shapes) returns the name of the shape with the largest perimeter. If several shapes share the largest perimeter, the one that comes first wins.

Both functions must work through the common type's methods only: never check which kind a shape is. Then a new kind of shape, added later, works with them unchanged.

The starter code already has every class header, constructor included, and every method header: write the method bodies. For each test, the harness reads the shapes, builds them in the order given, calls totalPerimeter and largestShape, and prints the two results on one line, separated by a space.

 

Example 1:

Input:
    Rectangle(3, 4)
    Square(5)
    Triangle(3, 4, 5)
Output: 46 Square
Explanation: The perimeters are 2 × (3 + 4) = 14, 4 × 5 = 20 and 3 + 4 + 5 = 12. Their total is 46, and the square's 20 is the largest.

Example 2:

Input:
    Rectangle(2, 4)
    Square(3)
    Triangle(4, 4, 4)
Output: 36 Rectangle
Explanation: All three perimeters are 12: 2 × (2 + 4), 4 × 3 and 4 + 4 + 4. On a tie the shape that comes first in the list wins, so the answer is the rectangle.

Example 3:

Input:
    Square(1)
    Rectangle(1, 1)
    Triangle(2, 2, 3)
Output: 15 Triangle
Explanation: The perimeters are 4, 4 and 7, so the last shape, the triangle, is the largest. A 1 by 1 rectangle has the same sides as a square, but it is still a Rectangle: each object answers name() for its own class.

 

Constraints:

  • Every test has between 1 and 100 shapes: the list is never empty.
  • Every size (width, height, side, and each side of a triangle) is an integer from 1 to 104.
  • A triangle's three sides always make a real triangle: each side is shorter than the other two together.

Note:

Each function looks at every shape once: O(n) time for n shapes, and no extra space.

STEP 1 OF 16
    Ctrl + Enter to check

    SCALA · OBJECT-ORIENTED PROGRAMMING - CHALLENGES

    Shapes Perimeter in Scala, explained

    Problem overview

    A drawing app keeps rectangles, squares and triangles in one list. The code that works with that list should be able to ask any shape for its name() and its perimeter() without knowing which kind of shape it holds. That is polymorphism: one call, and each kind of shape runs its own version.

    Every shape class extends the common class Shape, which answers "Shape" and 0. Each kind overrides both methods:

    • Rectangle(width, height): name "Rectangle", perimeter 2 * (width + height).
    • Square(side): name "Square", perimeter 4 * side.
    • Triangle(a, b, c): name "Triangle", perimeter a + b + c.

    Then Solution has two methods that take an Array[Shape]. totalPerimeter adds up all the perimeters, and largestShape returns the name of the shape with the largest perimeter, the first one on a tie.

    For a 3 by 4 rectangle, 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 shape is the Square.

    Approach

    The two Solution methods work through the methods of Shape only. They never ask whether a shape is a Square. That keeps them short, and a new kind of shape, such as a circle with its own perimeter, would work with them unchanged.

    • Total: start a running sum at 0 and add each shape's perimeter().
    • Largest: start with the first shape as the best so far, and replace it only when a shape has a strictly larger perimeter. The strict comparison keeps the earlier shape on a tie.

    Step by step

    1. In Shape, return "Shape" from name and 0 from perimeter. These defaults give the common type its two methods.
    2. In each shape class, override name and perimeter. The constructor parameters are declared with val, so the methods can read width, side, a and so on.
    3. In totalPerimeter, declare total with var, loop over shapes, add shape.perimeter() and return total.
    4. In largestShape, declare largest as shapes(0), loop over the shapes, and set largest = shape when shape.perimeter() > largest.perimeter().
    5. Return largest.name().

    The solution in Scala

    class Shape {
    def name(): String = {
        return "Shape"
    }

    def perimeter(): Int = {
        return 0
    }
}

class Rectangle(val width: Int, val height: Int) extends Shape {
    override def name(): String = {
        return "Rectangle"
    }

    override def perimeter(): Int = {
        return 2 * (width + height)
    }
}

class Square(val side: Int) extends Shape {
    override def name(): String = {
        return "Square"
    }

    override def perimeter(): Int = {
        return 4 * side
    }
}

class Triangle(val a: Int, val b: Int, val c: Int) extends Shape {
    override def name(): String = {
        return "Triangle"
    }

    override def perimeter(): Int = {
        return a + b + c
    }
}

class Solution {
    def totalPerimeter(shapes: Array[Shape]): Int = {
        var total = 0
        for (shape <- shapes) {
            total += shape.perimeter()
        }
        return total
    }

    def largestShape(shapes: Array[Shape]): String = {
        var largest = shapes(0)
        for (shape <- shapes) {
            if (shape.perimeter() > largest.perimeter()) {
                largest = shape
            }
        }
        return largest.name()
    }
}

    Details worth knowing:

    • Constructor parameters. In class Square(val side: Int) extends Shape, the val makes side a property that the methods can use.
    • Array access. Scala reads an array element with parentheses: shapes(0), not shapes[0].
    • var. total and largest change inside the loop, so they are var. Scala works out their types, Int and Shape, from the starting values.
    • Time and space. Each method visits every shape once, so the time is O(n) for n shapes, and no extra space is used.

    Trying it

    val solution = new Solution()
val shapes: Array[Shape] = Array(new Rectangle(3, 4), new Square(5), new Triangle(3, 4, 5))
println(solution.totalPerimeter(shapes) + " " + solution.largestShape(shapes))

    This prints 46 Square. More inputs, with the results of the same two calls:

    • Rectangle(2, 4), Square(3), Triangle(4, 4, 4) gives 36 Rectangle. All three perimeters are 12, so the first shape wins the tie.
    • Square(1), Rectangle(1, 1), Triangle(2, 2, 3) gives 15 Triangle. The perimeters are 4, 4 and 7.
    • A single Square(10000) gives 40000 Square.

    Walking through the largest shape

    Take the shapes Square(1), Rectangle(1, 1) and Triangle(2, 2, 3). largest starts as the square, with perimeter 4. The loop then visits all three shapes, including the first. Comparing the square with itself changes nothing, because 4 is not greater than 4. The rectangle also has perimeter 4, which is not strictly greater, so the square stays. The triangle has perimeter 7, which is greater, so it becomes the new largest. After the loop the method returns largest.name(), which is Triangle.

    Starting the loop at the first shape is a simplification. It does one pointless comparison, but it avoids a special case for the start of the array and costs nothing noticeable.

    Why the base class has defaults

    Shape returns "Shape" and 0, and none of the three kinds uses those values. They exist so that the common type has both methods, which is what lets the code in Solution call them on an Array[Shape]. A plain new Shape() is a valid object that answers Shape and 0.

    Edge cases

    The list is never empty, which is why largestShape can safely read shapes(0). On an empty array that call would throw an exception. Sizes go up to 10000, so the total stays well inside an Int: one hundred squares of side 10000 give 4,000,000. Ties are the other case to keep in mind: the strict > keeps the shape that came first.

    Adding a new kind later needs no change here. A class Circle that extends Shape and overrides the two methods works with both Solution methods as they are.

    Common mistakes

    • Checking the kind of shape. An if on the class defeats the purpose. Call perimeter() and let each object answer.
    • Using >= in largestShape. It would replace the earlier shape on a tie. With three shapes of perimeter 12 it would answer Triangle instead of Rectangle.
    • Forgetting the factor 2. A rectangle has two sides of each size: 2 * (width + height).
    • Assuming a 1 by 1 rectangle is a square. It has the same sides, but it is still a Rectangle, and its name() says so.
    • Forgetting override. Scala requires it on the methods that replace the ones in Shape.
    Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free