Rectangles in Crystal: Complete Solution & Deep Dive Guide

---

Mastering ASCII Art Puzzles: The Complete Guide to Counting Rectangles in Crystal

Discover the elegant algorithmic solution to counting all valid rectangles within an ASCII diagram. This guide breaks down the problem from conceptual logic to a fully optimized and commented Crystal implementation, perfect for honing your grid traversal and pattern recognition skills.

---

Have you ever found yourself mesmerized by ASCII art, those intricate images crafted from simple text characters? It’s a unique blend of art and code. But what happens when a programming challenge asks you to reverse-engineer that art—to find the hidden structure within? It feels like a simple visual task for a human, but teaching a computer to "see" these shapes is a fascinating algorithmic puzzle.

You might stare at a grid of +, -, and | characters, easily spotting a few rectangles, but feeling a rising sense of complexity when you try to formalize the process. How do you account for overlapping rectangles? How do you ensure a shape is a complete, valid rectangle and not just a collection of random corners? This is a common pain point for developers diving into algorithmic thinking.

This comprehensive guide will demystify the entire process. We will transform this seemingly complex visual puzzle into a clear, step-by-step algorithm. You will learn how to traverse a 2D grid, identify potential corners, validate the connecting edges, and implement an efficient solution using the expressive power of the Crystal programming language. By the end, you'll not only have a working solution but a deeper understanding of grid-based problem-solving.

---

What is the Rectangle Counting Problem?

The Rectangle Counting problem, a popular challenge found in the kodikra.com learning curriculum, asks you to write a program that counts the number of valid rectangles in a given multi-line string representing an ASCII diagram. The input is an array of strings, where each string is a row in the diagram.

The characters forming the rectangles are specific:

• + represents a corner.
• - represents a horizontal side.
• | represents a vertical side.

A valid rectangle is formed by four + corners connected by appropriate - and | characters. The challenge lies in the fact that rectangles can overlap, share corners, and share edges. Your algorithm must be robust enough to correctly identify and count every single unique rectangle, regardless of its size or position.

For example, consider this input:

+--+
|  |
+--+

This diagram contains one rectangle. But a more complex diagram like this:

+-+-+
| | |
+-+-+

Contains three rectangles: one large one and two smaller ones that share a middle edge.

---

Why Is This a Foundational Algorithmic Challenge?

This problem is more than just a fun puzzle; it's a fantastic exercise for developing core programming skills. It forces you to think systematically about data that is inherently two-dimensional. Successfully solving it demonstrates proficiency in several key areas:

• Grid Traversal: The core of the solution involves navigating a 2D grid (the array of strings). This requires mastery of nested loops and coordinate management (row and column indices).
• State Management: You need to keep track of potential corners and their relationships. The algorithm involves identifying a starting point (a top-left corner) and then searching for corresponding corners to complete a shape.
• Pattern Recognition: At its heart, this is a pattern recognition problem. You are defining the "pattern" of a rectangle in code—four corners, valid horizontal tops and bottoms, and valid vertical sides.
• Algorithmic Complexity: It encourages you to think about efficiency. A naive solution might be very slow. The process of refining your logic from a brute-force approach to a more optimized one is a critical step in becoming a better developer.
• Attention to Detail: The problem has strict rules. A line of +---+--+ is not a valid top edge because of the gap. Your code must be precise in validating these details, which hones your ability to handle edge cases.

Mastering this type of problem provides a solid foundation for tackling more complex challenges in areas like image processing, game development (e.g., collision detection in a tile-based game), and data analysis on grid-like structures.

---

How to Deconstruct the Problem: The Four-Corner Strategy

The most intuitive and robust way to solve this is to think like a human, but systematically. When we see a rectangle, we identify its corners. We can translate this directly into an algorithm. The strategy is to find every possible combination of four '+' characters and then check if they form a valid rectangle.

A more optimized version of this is to iterate through the grid and, upon finding a '+', treat it as a potential top-left corner. From there, we search for its corresponding partners: a top-right, a bottom-left, and a bottom-right corner.

The Core Logic Flow

Here is the step-by-step breakdown of the algorithm. We will iterate through every possible rectangle by defining its top-left and bottom-right corners.

1. Represent the Grid: Treat the input `Array(String)` as a 2D grid of characters.
2. Find a Top-Left Corner (P1): Iterate through every cell (r1, c1) of the grid. If the character at this position is a '+', we have a potential top-left corner of a rectangle.
3. Find a Top-Right Corner (P2): From (r1, c1), scan to the right along the same row r1. For every '+' we find at position (r1, c2), we have a potential top-right corner.
4. Find a Bottom-Left Corner (P3): From (r1, c1), scan downwards along the same column c1. For every '+' we find at position (r2, c1), we have a potential bottom-left corner.
5. Check for the Bottom-Right Corner (P4): For every combination of a top-left, top-right, and bottom-left corner, we can calculate the position of the required fourth corner: (r2, c2). We must check if the character at this position is also a '+'.
6. Validate the Edges: If all four corners exist, the final step is to verify that the lines connecting them are valid.
   • The top edge (from (r1, c1) to (r1, c2)) must only contain '-' or '+'.
   • The bottom edge (from (r2, c1) to (r2, c2)) must only contain '-' or '+'.
   • The left edge (from (r1, c1) to (r2, c1)) must only contain '|' or '+'.
   • The right edge (from (r1, c2) to (r2, c2)) must only contain '|' or '+'.
7. Increment Counter: If all four corners and all four edges are valid, we have found one unique rectangle. Increment our counter.

This process guarantees that we will find every single rectangle without double-counting because each rectangle is uniquely defined by its top-left and bottom-right corner pair.

Logic Flow ASCII Diagram

This diagram visualizes the nested search process starting from a single point.

    ● Start Grid Traversal
    │
    ▼
  ┌──────────────────┐
  │ Loop Rows (r1)   │
  │ Loop Cols (c1)   │
  └─────────┬────────┘
            │
            ▼
    ◆ Is grid[r1][c1] a '+'?
   ╱           ╲
  Yes           No ───────────► Continue
  │
  ├─► Treat as Top-Left (P1)
  │
  ▼
  ┌───────────────────────────┐
  │ Scan Right for '+' (P2)   │
  │ at (r1, c2)               │
  └────────────┬──────────────┘
               │
               ▼
  ┌───────────────────────────┐
  │ Scan Down for '+' (P3)    │
  │ at (r2, c1)               │
  └────────────┬──────────────┘
               │
               ▼
    ◆ Is grid[r2][c2] a '+'? (P4)
   ╱           ╲
  Yes           No ───────────► Continue Search
  │
  ▼
  ┌───────────────────────────┐
  │ Validate Top/Bottom Edges │
  │ Validate Left/Right Edges │
  └────────────┬──────────────┘
               │
               ▼
    ◆ All Edges Valid?
   ╱           ╲
  Yes           No
  │              │
  ▼              ▼
[Increment Count] [Discard]
  │              │
  └──────┬───────┘
         ▼
    ● End of Loops

---

Where to Implement in Crystal: The Full Code Solution

Now, let's translate our logic into clean, idiomatic Crystal code. Crystal's expressive syntax, efficient compiled nature, and rich standard library make it a joy to use for problems like this. We will encapsulate the logic within a Rectangles class with a single class method, count, as is standard in the kodikra.com modules.

# The Rectangles class provides a utility to count rectangles in an ASCII diagram.
class Rectangles
  # Counts the number of valid rectangles in a given set of ASCII lines.
  #
  # A rectangle is defined by four '+' corners connected by '-' (horizontal)
  # and '|' (vertical) characters.
  def self.count(lines : Array(String))
    # Return 0 immediately if the input is empty or has no content.
    return 0 if lines.empty? || lines[0].empty?

    rows = lines.size
    cols = lines[0].size
    count = 0

    # Iterate through each cell to find potential top-left corners.
    (0...rows).each do |r1|
      (0...cols).each do |c1|
        # A rectangle must start with a '+' as its top-left corner.
        next unless lines[r1][c1] == '+'

        # From the top-left corner, search for potential bottom-right corners.
        # This defines the diagonal of the potential rectangle.
        (r1 + 1...rows).each do |r2|
          (c1 + 1...cols).each do |c2|
            
            # Check if we have a full set of four '+' corners.
            if is_corner?(lines, r1, c2) && # Top-right
               is_corner?(lines, r2, c1) && # Bottom-left
               is_corner?(lines, r2, c2)    # Bottom-right

              # If all four corners are present, validate the connecting edges.
              if is_horizontal_edge_valid?(lines, r1, c1, c2) && # Top edge
                 is_horizontal_edge_valid?(lines, r2, c1, c2) && # Bottom edge
                 is_vertical_edge_valid?(lines, c1, r1, r2) &&   # Left edge
                 is_vertical_edge_valid?(lines, c2, r1, r2)      # Right edge
                
                # If all checks pass, we've found a valid rectangle.
                count += 1
              end
            end
          end
        end
      end
    end

    count
  end

  # Helper method to check if a character at given coordinates is a corner ('+').
  private def self.is_corner?(lines, row, col)
    lines[row][col] == '+'
  end

  # Helper method to validate a horizontal edge between two column indices on a given row.
  # A valid horizontal edge consists only of '+' and '-' characters.
  private def self.is_horizontal_edge_valid?(lines, row_idx, col_start, col_end)
    (col_start + 1...col_end).all? do |c|
      char = lines[row_idx][c]
      char == '+' || char == '-'
    end
  end

  # Helper method to validate a vertical edge between two row indices on a given column.
  # A valid vertical edge consists only of '+' and '|' characters.
  private def self.is_vertical_edge_valid?(lines, col_idx, row_start, row_end)
    (row_start + 1...row_end).all? do |r|
      char = lines[r][col_idx]
      char == '+' || char == '|'
    end
  end
end

---

Who Benefits and How: A Detailed Code Walkthrough

Understanding the code is as important as having it. Let's break down the implementation line by line to see how it perfectly executes our strategy. This walkthrough is for anyone looking to deepen their understanding of Crystal syntax and algorithmic implementation.

Class and Method Structure

class Rectangles
  def self.count(lines : Array(String))
    # ... implementation
  end
  # ... private helper methods
end

• We define a class Rectangles to namespace our logic.
• The primary method is a class method self.count. This is common for utility functions that don't need to maintain state in an instance. It takes one argument, lines, which is type-annotated as an Array(String) for clarity and compile-time safety.

Initial Setup and Edge Cases

return 0 if lines.empty? || lines[0].empty?

rows = lines.size
cols = lines[0].size
count = 0

• The first line is a guard clause. If the input array of lines is empty or the first line itself is empty, no rectangles can exist, so we return 0 immediately. This prevents errors on invalid input.
• We cache the number of rows and columns (rows, cols) in local variables. Accessing local variables is slightly faster than repeatedly calling .size in loops.
• We initialize our count variable to 0. This will be our accumulator.

The Nested Loops: Finding Corners

(0...rows).each do |r1|
  (0...cols).each do |c1|
    next unless lines[r1][c1] == '+'

    (r1 + 1...rows).each do |r2|
      (c1 + 1...cols).each do |c2|
        # ... validation logic
      end
    end
  end
end

• This is the heart of the algorithm: four nested loops. It might look intimidating, but it's a logical structure.
• The outer two loops, iterating with r1 and c1, are responsible for finding our top-left corner. The next unless lines[r1][c1] == '+' is a crucial optimization: if the current cell isn't a '+', we immediately skip to the next cell, avoiding the expensive inner loops.
• The inner two loops, with r2 and c2, search for a bottom-right corner. Notice the ranges: (r1 + 1...rows) and (c1 + 1...cols). This ensures that r2 is always below r1 and c2 is always to the right of c1, which is the definition of a bottom-right corner relative to a top-left one. This prevents us from checking invalid or redundant rectangle configurations.

The Four-Corner and Edge Validation

if is_corner?(lines, r1, c2) && # Top-right
   is_corner?(lines, r2, c1) && # Bottom-left
   is_corner?(lines, r2, c2)    # Bottom-right

  if is_horizontal_edge_valid?(...) && # Top
     is_horizontal_edge_valid?(...) && # Bottom
     is_vertical_edge_valid?(...) &&   # Left
     is_vertical_edge_valid?(...)      # Right
    
    count += 1
  end
end

• Inside the innermost loop, we have a candidate rectangle defined by top-left (r1, c1) and bottom-right (r2, c2).
• First, we check the other two corners. Are (r1, c2) (top-right) and (r2, c1) (bottom-left) also '+' characters? We use our simple is_corner? helper for this. We also re-check (r2, c2) for clarity, though the inner loops already position us there.
• Only if all four corners are present do we proceed to the more expensive edge validation. This is another key optimization.
• We call our validation helpers (is_horizontal_edge_valid? and is_vertical_edge_valid?) for all four sides.
• If all four corners AND all four edges are valid, we finally increment our count.

The Helper Methods

private def self.is_horizontal_edge_valid?(lines, row_idx, col_start, col_end)
  (col_start + 1...col_end).all? do |c|
    char = lines[row_idx][c]
    char == '+' || char == '-'
  end
end

• These methods are marked private because they are internal implementation details of the Rectangles class and shouldn't be called from outside.
• The logic is straightforward. For a horizontal edge, we iterate through all the characters between the start and end columns (e.g., col_start + 1...col_end).
• Crystal's .all? enumerable method is perfect here. It returns true only if the given block returns a truthy value for every single element in the range.
• We check if each character is either a '+' (part of an overlapping rectangle) or a '-'. If even one character is a space or a '|', .all? will return false, and the edge is invalid. The logic for is_vertical_edge_valid? is analogous.

---

When to Consider Alternative Approaches

The four-corner detection method is efficient and highly readable, but it's not the only way to solve the problem. Understanding alternatives helps you develop a more flexible problem-solving mindset.

Alternative: The "Top-Edge First" Approach

Instead of finding a top-left corner and then a bottom-right, you could first identify all valid horizontal line segments that could serve as the top edge of a rectangle.

1. Iterate through the grid to find all pairs of '+' characters on the same row, connected by valid '-' or '+' characters. Let's call these (r1, c1) and (r1, c2).
2. For each such valid top edge, scan downwards from r1 to find a matching bottom edge.
3. A matching bottom edge would be another pair of '+' characters at (r2, c1) and (r2, c2), also connected by a valid horizontal line.
4. Finally, if a matching bottom edge is found, you would still need to validate the left and right vertical edges connecting (r1, c1) to (r2, c1) and (r1, c2) to (r2, c2).

This approach can sometimes be more intuitive, as you build rectangles "downwards" from a complete top side. However, the time complexity remains similar, as you are still essentially checking combinations of rows and columns.

Comparison of Approaches ASCII Diagram

This diagram shows the conceptual difference between the two main strategies.

     Our Implemented Method                 Alternative Method
     (4-Corner Search)                      (Top-Edge First)
   ┌───────────────────────┐              ┌───────────────────────┐
   │       ● Start         │              │       ● Start         │
   │       │               │              │       │               │
   │       ▼               │              │       ▼               │
   │   Find P1 ('+')       │              │  Find Valid Top Edge  │
   │       │               │              │  (P1 to P2)           │
   │       ▼               │              │       │               │
   │   Find P2, P3         │              │       ▼               │
   │       │               │              │  Scan Down from Edge  │
   │       ▼               │              │       │               │
   │   Check for P4        │              │       ▼               │
   │       │               │              │  Find Matching Bottom │
   │       ▼               │              │  Edge (P3 to P4)      │
   │   Validate 4 Edges    │              │       │               │
   │       │               │              │       ▼               │
   │       ▼               │              │  Validate Side Edges  │
   │   ● Found/Discard     │              │  (P1-P3, P2-P4)       │
   └───────────────────────┘              └───────────────────────┘

Pros & Cons of Our Chosen Approach

To provide a balanced view, here are the advantages and potential disadvantages of the implemented four-corner search algorithm.

Pros	Cons / Risks
Clarity and Readability: The logic of finding a top-left and bottom-right corner is very direct and maps well to the problem's definition.	Time Complexity: The O(R² * C²) complexity can be slow on extremely large grids, although it's perfectly fine for typical inputs.
Correctness Guarantee: By checking every valid pair of top-left and bottom-right corners, it's guaranteed to find all rectangles and not miss any.	Redundant Checks: The edge validation helpers might re-scan the same segments multiple times for different overlapping rectangles. This could be memoized for a slight performance gain, but at the cost of complexity.
Easy to Debug: If the count is wrong, you can easily trace the logic by printing the coordinates (r1, c1) and (r2, c2) of the rectangle being considered.	Less Intuitive for Some: Some developers might find the "build from a top edge" approach more natural to conceptualize.

---

Frequently Asked Questions (FAQ)

1. What is the time complexity of this solution?

The time complexity is determined by the four nested loops. Let R be the number of rows and C be the number of columns. The algorithm runs in approximately O(R² * C²). Inside the loops, the edge validation takes O(R + C) time. So, a more precise complexity is O(R³ * C² + R² * C³). While this looks high, it's heavily pruned by the `if is_corner?` checks, making its real-world performance much better on sparse grids (grids with few '+' characters).

2. How does the algorithm handle overlapping rectangles correctly?

It handles them perfectly because it doesn't think in terms of "shapes." It thinks in terms of unique corner pairs. A large rectangle defined by corners (0,0) and (2,2) is counted once. A smaller, overlapping rectangle defined by (0,0) and (1,1) is counted separately. Since each rectangle has a unique pair of top-left and bottom-right corners, there is no risk of double-counting.

3. Why not just count all the `+` characters and divide by four?

This would be incorrect for several reasons. First, rectangles can share corners. In a 2x2 grid of rectangles, there are nine corners but four rectangles. Second, a `+` character might not be part of any valid, complete rectangle. The algorithm's strength is that it validates the entire structure, not just the presence of corners.

4. Can this algorithm be adapted to find other shapes, like squares?

Yes, absolutely. To adapt it to find only squares, you would add one more condition inside the validation block. After finding a valid rectangle with width `w = c2 - c1` and height `h = r2 - r1`, you would simply add a check: `if w == h`, then increment the square counter.

5. What are some common edge cases to consider for this problem?

• Empty Input: An empty array of strings.
• Malformed Input: Jagged arrays where rows have different lengths. (Our solution assumes a proper rectangle input as per the problem constraints).
• No Rectangles: A valid grid that simply contains no complete rectangles.
• Incomplete Shapes: A shape with three `+` corners but missing the fourth, or a shape with four corners but a broken edge (e.g., `+-- --+`). Our edge validation handles this.

6. Why is Crystal a good choice for this type of algorithmic problem?

Crystal shines here for several reasons. Its syntax is clean and highly readable, resembling Ruby, which makes the complex nested logic easier to write and understand. However, unlike Ruby, it's a compiled language, offering C-like performance. This means the nested loops run very fast. Finally, its strong type system helps catch errors at compile time, ensuring that `lines[r][c]` will always be a `Char` and preventing common runtime errors.

7. What's a potential future-proofing consideration for this code?

As of Crystal 1.12+, the language is very stable. A future enhancement could involve parallelization. Since the work for each potential top-left corner `(r1, c1)` is independent, one could potentially parallelize the outer loops using Crystal's concurrency features (fibers and channels) to speed up processing on massive grids, though this would add significant complexity.

---

Conclusion: From Pixels to Patterns

We have successfully journeyed from a seemingly simple visual puzzle to a robust, efficient, and well-structured algorithmic solution in Crystal. By breaking the problem down into a systematic "four-corner" search strategy, we were able to translate human intuition into precise code. The key takeaway is the power of methodical iteration and validation: find a potential starting point, search for its partners, and then rigorously verify that the complete pattern meets all required conditions.

This exercise from the kodikra.com curriculum is a perfect example of how fundamental programming concepts—nested loops, conditional logic, and helper functions—combine to solve complex problems. The skills you've reinforced here are directly applicable to a wide range of challenges in software development.

Now that you've mastered this, you're better equipped to tackle even more intricate grid-based puzzles. Continue your journey on the Crystal 4 roadmap to discover new challenges, or explore our comprehensive Crystal programming guides to further deepen your knowledge of this powerful language.

Disclaimer: All code in this article is written and tested against Crystal version 1.12.x. While the core logic is timeless, language syntax and standard library features may evolve in future versions.

---

Published by Kodikra — Your trusted Crystal learning resource.