Kotlin Coding Test, Let’s try DDR

In this post, we will discuss a problem related to the ‘DDR’ game, which is frequently presented as one of the algorithm problems for job interviews. This problem involves basic array manipulation and requires algorithmic thinking, making it very helpful for coding test preparation. We will examine the problem definition and the process of solving it in detail.

Problem Definition

You are a fan of the ‘DDR (Dance Dance Revolution)’ game. In this game, arrows appear in various directions (up, down, left, right) on a rectangular step pad. The step pad is composed of a N * N grid. Arrows can appear at various positions on the grid, and according to certain rules, the grid is filled, and the arrows must be compressed upwards.

You need to solve the problem of returning the compressed state based on the given initial state of the DDR step pad. The following rules apply:

  • The game pad is of size N * N, and each position is represented by 0 (empty) or 1 (arrow).
  • You must return the arrows that appear by compressing downwards in all columns. In other words, you need to push down by column.

Input and Output Format

Input:

  1. The first line contains the size of the step pad N (1 ≤ N ≤ 100).
  2. The next N lines contain the state of the step pad. Each consists of N space-separated numbers made up of 0 and 1.

Output:

Print the compressed state of the step pad over N lines. Each line consists of 0 and 1, separated by spaces.

Example

Input

    5
    0 0 0 0 0
    1 0 1 0 0
    1 1 0 1 0
    0 0 0 1 1
    0 0 0 0 0

Output

    0 0 0 0 0
    0 0 1 1 1
    1 1 1 0 0
    1 0 0 0 0
    1 0 0 0 0

Problem Solving Process

Now, let’s plan the algorithm to solve the given problem. This problem requires us to implement the process of compressing downwards by column from the given grid. Let’s approach it step by step.

Step 1: Choosing the Data Structure

We will use a 2D array to store each input in a workspace. I will create a list for each column to count the number of 1s by checking each scene.

Step 2: Implementing the Compression Logic

We will check each column individually to count the number of 1s and perform the compression in a way that aligns the structure downwards. To do this, we will place 1s from the bottom in a newly structured array and fill the rest with 0s.

Step 3: Writing Kotlin Code

Now, let’s implement the above process in Kotlin. Here is the implemented code:

    fun compressDDRPads(n: Int, pads: Array): Array {
        // Initialize a 2D array to store the result
        val result = Array(n) { IntArray(n) }

        // Iterate through each column to compress downwards
        for (j in 0 until n) {
            var count = 0

            // Loop through the column to count the number of 1s
            for (i in 0 until n) {
                if (pads[i][j] == 1) {
                    count++
                }
            }

            // Fill the compressed result from the bottom
            for (i in n - 1 downTo n - count) {
                result[i][j] = 1
            }
        }

        return result
    }

    // Example input
    fun main() {
        val n = 5
        val pads = arrayOf(
            intArrayOf(0, 0, 0, 0, 0),
            intArrayOf(1, 0, 1, 0, 0),
            intArrayOf(1, 1, 0, 1, 0),
            intArrayOf(0, 0, 0, 1, 1),
            intArrayOf(0, 0, 0, 0, 0)
        )

        val compressedPads = compressDDRPads(n, pads)

        // Print the result
        for (row in compressedPads) {
            println(row.joinToString(" "))
        }
    }

Conclusion

In this post, we explored the process of solving the DDR problem using Kotlin. We found that understanding algorithmic thinking and data structures is crucial in the problem-solving process. By repeatedly practicing such problems in actual coding tests, you will find it easier to solve them. I hope to deepen my coding skills through various algorithm problems in the future.

References