LeetCode in Kotlin

3923. Minimum Generations to Target Point

Medium

You are given a 2D integer array points where points[i] = [xi, yi, zi] represents a point in 3D space, and an integer array target representing a target point.

Define generation 0 as the initial list of points. For each integer k >= 1, form generation k as follows:

• Consider every pair of two distinct points a = [x1, y1, z1] and b = [x2, y2, z2] taken from all points produced in generations 0 through k - 1.
• For each such pair, compute c = [floor((x1 + x2) / 2), floor((y1 + y2) / 2), floor((z1 + z2) / 2)] and collect every such c into a generation k.
• All points in the generation k are produced simultaneously from points in generations 0 through k - 1.
• After generation k is formed, the points in the generation k are considered available for forming later generations.

Return the smallest integer k such that the target appears in one of the generations 0 through k. If the target is already in the initial points, return 0. If it is impossible to obtain the target, return -1.

Notes:

• floor denotes rounding down to the nearest integer.
• “Two distinct points” means the two chosen points must have different (x, y, z) coordinates. A point cannot be paired with itself, and pairing two points with identical coordinates is not possible.

Example 1:

Input: points = [[0,0,0],[6,6,6]], target = [3,3,3]

Output: 1

Explanation:

• Generation 0: The initial points = \[\[0, 0, 0], [6, 6, 6]].
• The target = [3, 3, 3] does not exist in generation 0.
• Generation 1: For each pair of points in generation 0, we create new points.
  • Using [0, 0, 0] and [6, 6, 6], we generate [3, 3, 3].
• After generation 1, points = \[\[0, 0, 0], [6, 6, 6], [3, 3, 3]].
• The target = [3, 3, 3] is found in generation 1, so the smallest k is 1.

Example 2:

Input: points = [[0,0,0],[5,5,5]], target = [1,1,1]

Output: 2

Explanation:

• Generation 0: The initial points = \[\[0, 0, 0], [5, 5, 5]].
• The target = [1, 1, 1] does not exist in generation 0.
• Generation 1: For each pair of points in generation 0, we create new points.
  • Using [0, 0, 0] and [5, 5, 5], we generate [2, 2, 2].
• After generation 1, points = \[\[0, 0, 0], [5, 5, 5], [2, 2, 2]].
• Generation 2: For each pair of points available after generation 1, we create new points.
  • Using [0, 0, 0] and [5, 5, 5], we generate [2, 2, 2].
  • Using [0, 0, 0] and [2, 2, 2], we generate [1, 1, 1].
  • Using [5, 5, 5] and [2, 2, 2], we generate [3, 3, 3].
• After generation 2, points = \[\[0, 0, 0], [5, 5, 5], [2, 2, 2], [1, 1, 1], [3, 3, 3]].
• The target = [1, 1, 1] is found in generation 2, so the smallest k is 2.

Example 3:

Input: points = [[0,0,0],[2,2,2],[3,3,3]], target = [2,2,2]

Output: 0

Explanation:

• Generation 0: The initial points = \[\[0, 0, 0], [2, 2, 2], [3, 3, 3]].
• The target = [2, 2, 2] already exists in generation 0, so the smallest k is 0.

Example 4:

Input: points = [[1,2,3]], target = [5,5,5]

Output: -1

Explanation:

• Only one initial point is available, so no new points can be generated.
• Therefore, the target cannot be obtained, and the answer is -1.

Constraints:

• 1 <= points.length <= 20
• points[i] = [xi, yi, zi]
• 0 <= xi, yi, zi <= 6
• target.length == 3
• 0 <= target[i] <= 6
• The initial set of points contains no duplicates.

Solution

class Solution {
    fun minGenerations(points: Array<IntArray>, target: IntArray): Int {
        val visited = BooleanArray(TOTAL_POINTS)
        val allPoints: MutableList<Int> = ArrayList<Int>()
        var frontier: MutableList<Int> = ArrayList<Int>()
        val targetCode = encode(target[0], target[1], target[2])
        initializePoints(points, visited, allPoints, frontier)
        if (frontier.contains(targetCode)) {
            return 0
        }
        var generation = 0
        while (frontier.isNotEmpty()) {
            generation++
            val nextFrontier = generateNextFrontier(frontier, allPoints, visited)
            if (nextFrontier.contains(targetCode)) {
                return generation
            }
            addPoints(nextFrontier, visited, allPoints)
            frontier = nextFrontier
        }
        return -1
    }

    private fun initializePoints(
        points: Array<IntArray>,
        visited: BooleanArray,
        allPoints: MutableList<Int>,
        frontier: MutableList<Int>,
    ) {
        for (point in points) {
            val code = encode(point[0], point[1], point[2])
            visited[code] = true
            allPoints.add(code)
            frontier.add(code)
        }
    }

    private fun generateNextFrontier(
        frontier: MutableList<Int>,
        allPoints: MutableList<Int>,
        visited: BooleanArray,
    ): MutableList<Int> {
        val nextFrontier: MutableList<Int> = ArrayList<Int>()
        val addedThisGeneration = BooleanArray(TOTAL_POINTS)
        for (pointA in frontier) {
            addGeneratedPoints(pointA, allPoints, visited, addedThisGeneration, nextFrontier)
        }
        return nextFrontier
    }

    private fun addGeneratedPoints(
        pointA: Int,
        allPoints: MutableList<Int>,
        visited: BooleanArray,
        addedThisGeneration: BooleanArray,
        nextFrontier: MutableList<Int>,
    ) {
        val a = decode(pointA)
        for (pointB in allPoints) {
            if (pointA != pointB) {
                addGeneratedPoint(a, pointB, visited, addedThisGeneration, nextFrontier)
            }
        }
    }

    private fun addGeneratedPoint(
        a: IntArray,
        pointB: Int,
        visited: BooleanArray,
        addedThisGeneration: BooleanArray,
        nextFrontier: MutableList<Int>,
    ) {
        val b = decode(pointB)
        val x = (a[0] + b[0]) / 2
        val y = (a[1] + b[1]) / 2
        val z = (a[2] + b[2]) / 2
        val newPoint = encode(x, y, z)
        if (!visited[newPoint] && !addedThisGeneration[newPoint]) {
            addedThisGeneration[newPoint] = true
            nextFrontier.add(newPoint)
        }
    }

    private fun addPoints(points: MutableList<Int>, visited: BooleanArray, allPoints: MutableList<Int>) {
        for (point in points) {
            visited[point] = true
            allPoints.add(point)
        }
    }

    private fun encode(x: Int, y: Int, z: Int): Int = x * SIZE * SIZE + y * SIZE + z

    private fun decode(code: Int): IntArray {
        var code = code
        val x: Int = code / (SIZE * SIZE)
        code %= SIZE * SIZE
        val y: Int = code / SIZE
        val z: Int = code % SIZE
        return intArrayOf(x, y, z)
    }

    companion object {
        private const val SIZE = 7
        private const val TOTAL_POINTS: Int = SIZE * SIZE * SIZE
    }
}

This site is open source. Improve this page.