[Kotlin] Korean Coding Test - Programmers - Making a Star at the Junction

2023-10-13

Language :

Question

Given n straight lines that can be represented by Ax + By + C = 0, we want to draw a star in the integer coordinates of the intersection points of this straight line.

For example, if you draw five straight lines on a coordinate plane

2x - y + 4 = 0
-2x - y + 4 = 0
-y + 1 = 0
5x - 8y - 12 = 0
5x + 8y + 12 = 0

The coordinates of all nodes are (4, 1), (4, -4), (-4, 1), (0, 4), (1.5, 1.0), (2.1, -0.19), (0, -1.5), (-2.1, -0.19), (-1.5), (-1.5, -0.19), and (-1.5, 1.0). Of these, the coordinates represented only by integers are (4, 1), (4, -4), (-4, -4), (-4, 1), and (0, 4).

If you draw a star at an intersection represented by an integer and represent it as a string, the part where the star is drawn is expressed as *, and the space where the grid lines intersect is expressed as ..

text

"..........."  
".....*....."  
"..........."  
"..........."  
".*.......*."  
"..........."  
"..........."  
"..........."  
"..........."  
".*.......*."  
"..........."

At this point, the grid is infinitely wide, so you only need to indicate the minimum size to include all the stars. So here's the answer.

text

"....*...."  
"........."  
"........."  
"*.......*"  
"........."  
"........."  
"........."  
"........."  
"*.......*"

An array line containing information about straight lines A, B, and C is given as a parameter. At this time, complete the solution function so that the minimum square containing all the stars is returned.

Restrictions

The longitudinal (row) length of a line is a natural number of not less than 2 and not more than 1,000.

line has a width (column) length of 3.
Each element of line is in the form [A, B, C].
A, B, and C are integers greater than or equal to -100,000 and less than or equal to 100,000.
No pair of straight lines with numerous nodes is given.
If A = 0 and B = 0, it is not given.

The correct answer is expressed within 1,000 * 1,000 sizes.

Only one or more stars are drawn.

Input/Output example

Input/Output example #1

Input: [[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]]
Output: ["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"]

Input/Output example #2

Input: [[0, 1, -1], [1, 0, -1], [1, 0, 1]]
Output: ["*.*"]

Input/Output example #3

Input: [[1, -1, 0], [2, -1, 0]]
Output: ["*"]

Input/Output example #4

Input: [[1, -1, 0], [2, -1, 0], [4, -1, 0]]
Output: ["*"]

Notes

If there is only one intersection of two straight lines, the intersection is as follows.

Ax + By + E = 0
Cx + Dy + F = 0

In addition, if AD - BC = 0, the two straight lines are parallel or coincident.

Solve

Use the formula for finding the intersection given in the notes.

According to the formula, multiplication calculations between line elements are required.
If the line element is at most 100,000 and the two elements are multiplied, the data type Long should be used as at most 10^10.

Draw a grid by finding the minimum and maximum coordinates from the found intersection.

The top left coordinates (minimum X, maximum Y) are the reference points (0, 0).

Code

kotlin

class Solution {
    fun solution(line: Array<IntArray>): Array<String> {
        return makeGrid(findCrossPoint(line))
    }

    /**
     * Find the intersection of two straight lines
     */
    private fun findCrossPoint(line: Array<IntArray>): List<Pair<Int, Int>> {
        val point = mutableListOf<Pair<Int, Int>>()
        for (i in 0 until line.size - 1) {
            for (j in i + 1 until line.size) {
                val denominator = line[i][0].toLong() * line[j][1] - line[i][1].toLong() * line[j][0]
                // Skip because if the denominator is zero, it is parallel or coincident
                if (denominator == 0L) continue

                val numeratorX = line[i][1].toLong() * line[j][2] - line[i][2].toLong() * line[j][1]
                val numeratorY = line[i][2].toLong() * line[j][0] - line[i][0].toLong() * line[j][2]
                // Skip if the intersection is not an integer
                if (numeratorX % denominator != 0L || numeratorY % denominator != 0L) continue

                val x = (numeratorX / denominator).toInt()
                val y = (numeratorY / denominator).toInt()
                point.add(Pair(x, y))
            }
        }
        return point
    }

    /**
     * Drawing a grid
     */
    private fun makeGrid(crossPoint: List<Pair<Int, Int>>): Array<String> {
        val minX = crossPoint.minOf { it.first }
        val minY = crossPoint.minOf { it.second }
        val maxX = crossPoint.maxOf { it.first }
        val maxY = crossPoint.maxOf { it.second }

        val grid = Array(maxY - minY + 1) { CharArray(maxX - minX + 1) { '.' } }
        for (i in crossPoint.indices) {
            grid[maxY - crossPoint[i].second][crossPoint[i].first - minX] = '*'
        }

        return Array(grid.size) { String(grid[it]) }
    }
}

text

TEST 1 〉	Pass (0.55ms, 59.9MB)
TEST 2 〉	Pass (7.91ms, 62MB)
TEST 3 〉	Pass (0.37ms, 60.9MB)
TEST 4 〉	Pass (17.78ms, 66MB)
TEST 5 〉	Pass (4.46ms, 61MB)
TEST 6 〉	Pass (2.01ms, 62.2MB)
TEST 7 〉	Pass (5.03ms, 63MB)
TEST 8 〉	Pass (0.32ms, 59.8MB)
TEST 9 〉	Pass (18.44ms, 61.8MB)
TEST 10 〉	Pass (18.71ms, 61.9MB)
TEST 11 〉	Pass (24.09ms, 61.2MB)
TEST 12 〉	Pass (34.77ms, 61.8MB)
TEST 13 〉	Pass (25.12ms, 62MB)
TEST 14 〉	Pass (22.76ms, 61.2MB)
TEST 15 〉	Pass (28.44ms, 59.7MB)
TEST 16 〉	Pass (19.27ms, 60.7MB)
TEST 17 〉	Pass (27.19ms, 61.7MB)
TEST 18 〉	Pass (25.87ms, 62.6MB)
TEST 19 〉	Pass (22.83ms, 60.2MB)
TEST 20 〉	Pass (16.42ms, 60.9MB)
TEST 21 〉	Pass (25.47ms, 63.5MB)
TEST 22 〉	Pass (0.35ms, 59.8MB)
TEST 23 〉	Pass (0.49ms, 60.9MB)
TEST 24 〉	Pass (0.28ms, 61.7MB)
TEST 25 〉	Pass (0.31ms, 61.7MB)
TEST 26 〉	Pass (0.29ms, 62.2MB)
TEST 27 〉	Pass (0.52ms, 61.4MB)
TEST 28 〉	Pass (0.47ms, 59.4MB)
TEST 29 〉	Pass (0.40ms, 59.4MB)

Code. Use of map in the function findCrossPoint

kotlin

class Solution {
    // ...
    private fun findCrossPoint(line: Array<IntArray>): List<Pair<Int, Int>> {
        val point = mutableListOf<Pair<Int, Int>>()
        for (i in 0 until line.size - 1) {
            for (j in i + 1 until line.size) {
                val (A, B, E) = line[i].map { it.toLong() }
                val (C, D, F) = line[j].map { it.toLong() }

                val denominator = A * D - B * C
                if (denominator == 0L) continue

                val numeratorX = B * F - E * D
                val numeratorY = E * C - A * F
                if (numeratorX % denominator != 0L || numeratorY % denominator != 0L) continue

                val x = (numeratorX / denominator).toInt()
                val y = (numeratorY / denominator).toInt()
                point.add(Pair(x, y))
            }
        }
        return point
    }
    // ...
}

text

TEST 1 〉	Pass (0.91ms, 59MB)
TEST 2 〉	Pass (9.99ms, 63.5MB)
TEST 3 〉	Pass (0.59ms, 61MB)
TEST 4 〉	Pass (13.76ms, 66MB)
TEST 5 〉	Pass (5.20ms, 60.6MB)
TEST 6 〉	Pass (2.45ms, 60.6MB)
TEST 7 〉	Pass (8.01ms, 61.5MB)
TEST 8 〉	Pass (0.47ms, 61.5MB)
TEST 9 〉	Pass (97.31ms, 95.9MB)
TEST 10 〉	Pass (87.47ms, 93.8MB)
TEST 11 〉	Pass (82.76ms, 94.6MB)
TEST 12 〉	Pass (107.77ms, 94.8MB)
TEST 13 〉	Pass (154.47ms, 95.9MB)
TEST 14 〉	Pass (122.53ms, 95.6MB)
TEST 15 〉	Pass (92.45ms, 95.3MB)
TEST 16 〉	Pass (91.58ms, 95.9MB)
TEST 17 〉	Pass (117.70ms, 95.8MB)
TEST 18 〉	Pass (98.94ms, 93.5MB)
TEST 19 〉	Pass (101.00ms, 93.3MB)
TEST 20 〉	Pass (87.15ms, 94.5MB)
TEST 21 〉	Pass (126.05ms, 95.9MB)
TEST 22 〉	Pass (0.88ms, 59.6MB)
TEST 23 〉	Pass (0.54ms, 59.5MB)
TEST 24 〉	Pass (0.40ms, 62.6MB)
TEST 25 〉	Pass (0.89ms, 61.6MB)
TEST 26 〉	Pass (1.06ms, 60.9MB)
TEST 27 〉	Pass (0.57ms, 61.1MB)
TEST 28 〉	Pass (0.54ms, 59.3MB)
TEST 29 〉	Pass (0.34ms, 62.3MB)

민갤

Back-End Developer

백엔드 개발자입니다.

Profile Articles

[Kotlin] Korean Coding Test - Programmers - Check personality types

Programmer's Coding Test Problem Personality Type Examination

[Kotlin] Korean Coding Test - Programmers - Fibonacci Number

Programmer's coding test practice Fibonacci number kotlin