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

Kotlin

Language :

Question

Link

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).

RisingStarGraphStar.jpg

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 ..

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

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.

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

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
RisingStarExpression.png

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

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]) }
    }
}
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

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
    }
    // ...
}
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

백엔드 개발자입니다.