Swift Coding Test Course, 2 N Tile Filling

Hello, everyone! In this post, we will discuss one of the coding test problems using Swift called “2*N Tile Filling.” This problem is one of the very useful problems for understanding the basics of dynamic programming. Below, I will detail the problem description and the process of solving it.

Problem Description

The problem is as follows. We need to find the number of ways to fill a rectangle that is 2 units high and N units wide with tiles of size 2×1 or 1×2. In other words, we need to count the number of ways to completely fill a 2*N rectangle using 2×1 and 1×2 tiles.

Examples

Here are examples for a few small values of N.

  • N=1: 1 (filling with one 1×2 tile)
  • N=2: 2 (filling with two 2×1 tiles or two 1×2 tiles)
  • N=3: 3 (filling with a combination of 1×2 and 2×1 tiles)
  • N=4: 5

Problem Solving Approach

This problem can be solved using dynamic programming. First, we need to set up the recurrence relation to solve the problem. In this problem, we can consider the following two cases.

  1. If the last column has a 1×2 tile: In this case, the size of the remaining problem is 2*(N-1).
  2. If the last row has a 2×1 tile: In this case, the size of the remaining problem is 2*(N-2).

By combining these two cases, we obtain the following recurrence relation.

f(N) = f(N-1) + f(N-2)

The initial cases are as follows.

  • f(1) = 1
  • f(2) = 2

Swift Code Implementation

Now, let’s implement the recurrence relation in Swift. During the implementation, we will use the memoization technique for efficiency.


    func tileWays(_ n: Int) -> Int {
        // Array for memoization
        var memo = Array(repeating: 0, count: n + 1)

        // Setting initial cases
        memo[1] = 1
        if n > 1 {
            memo[2] = 2
        }

        for i in 3...n {
            memo[i] = memo[i - 1] + memo[i - 2]
        }
        
        return memo[n]
    }

    // Example test
    let n = 4
    print("The number of ways to fill a height 2 and width \(n) with tiles: \(tileWays(n))")

Code Explanation

The above code works as follows:

  1. First, it declares a memo array initialized to 0. This array stores the number of ways to fill the tiles for each N.
  2. It sets the initial cases. It sets 1 for N=1 and 2 for N=2.
  3. It iterates from 3 to N, updating the memo array. For each case, it applies the recurrence relation to store values in the memo array.
  4. Finally, it returns memo[n] to provide the answer for N.

Time Complexity

This algorithm has a time complexity of O(N), which is proportional to N. By using memoization, we avoid redundant calculations and efficiently compute each case only once using the array.

Conclusion

In this post, we covered the “2*N Tile Filling” problem using Swift. Through understanding the problem and the solving process, we learned the basics of dynamic programming. I encourage you to solve more problems through practice.

In the next post, we will deal with another interesting algorithm problem. Thank you!