[Kotlin] Korean Coding Test - Programmers - Path cycle of light

Question

Link

Each column has a grid with S, L, or R written on it. You want to shoot light from this grid. Each column of this grid has the following unusual properties.

• If light reaches the space where "S" is written, go straight.
• If the light reaches the space where "L" is written, turn left.
• If the light reaches the space where "R" is written, turn right.
• When light crosses the end of the grid, it returns to the opposite end. For example, if the light travels from row 1 to row decreasing, it returns to the opposite end of the same column.

You want to know how many path cycles are there for light to travel in this lattice, and how long is each cycle. A path cycle means a circulating path through which light travels.

For example, the following illustration shows that if a grid ["SL", "LR"] emits light from row 1 to row 2 in the direction of row 1, this grid has one cycle of length 16 and no other cycle exists.

A one-dimensional string array grid representing the information in the grid is given as a parameter. Complete the solution function so that all the lengths of the light path cycles created through the given lattice are arranged in an array and returned in ascending order.

Restrictions

1 ≤ length of grid ≤ 500

• 1 ≤ length of each string of grid ≤ 500
• All strings in grid have the same length.
• All strings in grid consist of 'L', 'R', and 'S'.

Input/Output Example

Input/Output Example #1

• Input: ["SL","LR"]
• Output: [16]

Input/Output Example #2

• Input: ["S"]
• Output: [1,1,1,1]

Input/Output Example #3

• Input: ["R","R"]
• Output: [4,4]

Solve

Problems that require understanding and array utilization of problems rather than algorithms

1. To understand how a cycle occurs when light is shot from any position (four directions, up, down, left and right)

• Light travels according to a given grid element SRL and returns to its original position.
• One cycle ends when the light returns to its original position.
• Do not use the path through which the other cycle has passed. (From the moment of duplication, it becomes the same as the previous cycle.)
• To avoid infinite movement, you should know whether each lattice element has been stopped in four directions.
• Set 3D array variables with [x][y][direction] (visible)

2. Each grid element must shoot light in all four directions, so determine the direction of rotation.

• Set x and y movement coordinate variables by setting rotation direction (*_axis_direction)
• x, If you draw the y-axis and check the movement coordinate variable, 'Next index = (the index that comes out when rotating from the current index + index 0) % variable length'

3. Find rules that change coordinates when rotated

• When light travels out of the grid, it returns to the opposite end.
• Next Axis Position = (Current Axis Position + Rotation Direction + Axis Length) % Axis length

Code

class Solution {
    private val xAxisDir = arrayOf(0, -1, 0, 1)
    private val yAxisDir = arrayOf(-1, 0, 1, 0)

    private val directionCount = 4
    private var rowCount: Int = 0
    private var colCount: Int = 0
    
    private lateinit var visible: Array<Array<BooleanArray>>
    
    fun solution(grid: Array<String>): IntArray {
        rowCount = grid.size
        colCount = grid[0].length

        visible = Array(rowCount) { Array(colCount) { BooleanArray(directionCount) { false } } }

        val answer = ArrayList<Int>()

        for (y in 0 until rowCount) {
            for (x in 0 until colCount) {
                for (d in 0 until directionCount) {
                    if (visible[y][x][d]) continue
                    answer.add(lightCycle(grid, y, x, d))
                }
            }
        }

        return answer.sorted().toIntArray()
    }

    private fun lightCycle(grid: Array<String>, row: Int, col: Int, direction: Int): Int {
        var lightLength = 0
        var (y, x, d) = Triple(row, col, direction)
        while (!visible[y][x][d]) {
            lightLength++
            visible[y][x][d] = true

            d = rotation(grid[r][c], d)
            y = (y + yAxisDir[d] + rowCount) % rowCount
            x = (x + xAxisDir[d] + colCount) % colCount
        }
        return lightLength
    }

    private fun rotation(direction: Char, entryDirection: Int): Int {
        return when (direction) {
            'L' -> (entryDirection + 3) % 4
            'R' -> (entryDirection + 1) % 4
            else -> entryDirection
        }
    }
}

TEST 1 〉	Pass (25.04ms, 63.3MB)
TEST 2 〉	Pass (21.85ms, 64.1MB)
TEST 3 〉	Pass (16.41ms, 64.8MB)
TEST 4 〉	Pass (31.90ms, 63.3MB)
TEST 5 〉	Pass (31.95ms, 66.2MB)
TEST 6 〉	Pass (35.99ms, 64.5MB)
TEST 7 〉	Pass (109.65ms, 77.7MB)
TEST 8 〉	Pass (82.17ms, 71.7MB)
TEST 9 〉	Pass (79.79ms, 100MB)
TEST 10 〉	Pass (87.28ms, 101MB)
TEST 11 〉	Pass (88.31ms, 102MB)