FoobarTabunPublic.kt

import kotlin.math.ceil
import kotlin.math.floor
import kotlin.math.roundToInt
import kotlin.math.sqrt

const val PRECISION: Double = 0.1

fun main() {
    val case0 = Conditions(
        sizeX = 3, sizeY = 2, sizeZ = 2,
        youX = 1, youY = 1, youZ = 1,
        targetX = 2, targetY = 1, targetZ = 1,
        maxDist = 5.0
    )
    val case1 = Conditions(
        sizeX = 100, sizeY = 100, sizeZ = 100,
        youX = 20, youY = 20, youZ = 20,
        targetX = 80, targetY = 80, targetZ = 80,
        maxDist = 2500.0
    )
    println("Case 0: ${Solution().solution(case0)}")
    println("Case 1: ${Solution().solution(case1)}")
}

class Solution {
    fun solution(cnd: Conditions): Int {
        // Из-за того Map не разрешает одинаковых ключей, из точек, лежащих на одном направлении, будет выбрана
        // только самая ближняя.
        val targets = HashMap<Vector, Double>()
        val obstacles = HashMap<Vector, Double>()

        iterateRooms(cnd) { roomX, roomY, roomZ ->
            val room = getRoom(cnd, roomX, roomY, roomZ)

            // Заполним мапу целей
            val targetVec = Vector(
                x = (cnd.youX - room.targetX).toDouble(),
                y = (cnd.youY - room.targetY).toDouble(),
                z = (cnd.youZ - room.targetZ).toDouble()
            )
            val targetCurrDist = targets[targetVec.normalized]
            if (targetVec.length < cnd.maxDist && (targetCurrDist == null || targetVec.length < targetCurrDist)) {
                targets[targetVec.normalized] = targetVec.length
            }

            // Заполним мапу наших отражений
            val obstacleVec = Vector(
                x = (cnd.youX - room.youX).toDouble(),
                y = (cnd.youY - room.youY).toDouble(),
                z = (cnd.youZ - room.youZ).toDouble()
            )
            val obstacleCurrDist = obstacles[obstacleVec.normalized]
            if (obstacleVec.length > 0.5 /* Не подстрели себя! */ &&
                obstacleVec.length < cnd.maxDist && (obstacleCurrDist == null || obstacleVec.length < obstacleCurrDist)) {
                obstacles[obstacleVec.normalized] = obstacleVec.length
            }
        }

        // Удалим цели которые загораживаются нашими отражениями
        targets.entries.removeIf { entry ->
            val obstacleDist = obstacles[entry.key]
            obstacleDist != null && obstacleDist < entry.value
        }

        return targets.size;
    }

    /**
     * Итерируем по всем комнатам в пределах maxDist от you.
     * Это куб, хотя дистанция образует сферу, но это не важно.
     */
    private fun iterateRooms(cnd: Conditions, forEach: (roomX: Int, roomY: Int, roomZ: Int) -> Unit) {
        val fromRoomX = floor((-cnd.maxDist + cnd.youX) / cnd.sizeX).roundToInt()
        val fromRoomY = floor((-cnd.maxDist + cnd.youY) / cnd.sizeY).roundToInt()
        val fromRoomZ = floor((-cnd.maxDist + cnd.youZ) / cnd.sizeZ).roundToInt()
        val toRoomX = ceil((cnd.maxDist + cnd.youX) / cnd.sizeX).roundToInt()
        val toRoomY = ceil((cnd.maxDist + cnd.youY) / cnd.sizeY).roundToInt()
        val toRoomZ = ceil((cnd.maxDist + cnd.youZ) / cnd.sizeZ).roundToInt()

        for (roomX in fromRoomX..toRoomX) {
            for (roomY in fromRoomY..toRoomY) {
                for (roomZ in fromRoomZ..toRoomZ) {
                    forEach.invoke(roomX, roomY, roomZ)
                }
            }
        }
    }

    /**
     * Получить отражённую комнату по алгоритму:
     * если комната расположена на нечётной клетке по оси, то комната отражённая по оси.
     */
    private fun getRoom(cnd: Conditions, x: Int, y: Int, z: Int) = Room(
        youX = cnd.sizeX * x + if (x and 1 == 0) cnd.youX else cnd.sizeX - cnd.youX,
        youY = cnd.sizeY * y + if (y and 1 == 0) cnd.youY else cnd.sizeY - cnd.youY,
        youZ = cnd.sizeZ * z + if (z and 1 == 0) cnd.youZ else cnd.sizeZ - cnd.youZ,
        targetX = cnd.sizeX * x + if (x and 1 == 0) cnd.targetX else cnd.sizeX - cnd.targetX,
        targetY = cnd.sizeY * y + if (y and 1 == 0) cnd.targetY else cnd.sizeY - cnd.targetY,
        targetZ = cnd.sizeZ * z + if (z and 1 == 0) cnd.targetZ else cnd.sizeZ - cnd.targetZ
    )
}

data class Conditions(
    val sizeX: Int, val sizeY: Int, val sizeZ: Int,
    val youX: Int, val youY: Int, val youZ: Int,
    val targetX: Int, val targetY: Int, val targetZ: Int,
    val maxDist: Double
)

data class Room(
    val youX: Int, val youY: Int, val youZ: Int,
    val targetX: Int, val targetY: Int, val targetZ: Int
)

data class Vector(val x: Double = 0.0, val y: Double = 0.0, val z: Double = 0.0) {
    val lengthSqr: Double by lazy {
        x * x + y * y + z * z
    }

    val length: Double by lazy {
        sqrt(lengthSqr)
    }

    val normalized: Vector by lazy {
        if (length >= -Double.MIN_VALUE && length <= Double.MIN_VALUE) {
            Vector()
        } else {
            Vector(x / length, y / length, z / length)
        }
    }

    /**
     * Вектора равны если указывают в одном направлении с заданной погрешностью
     */
    override fun equals(other: Any?): Boolean {
        if (this === other) return true
        if (javaClass != other?.javaClass) return false

        other as Vector

        val norm = normalized
        val otherNorm = other.normalized
        val dot = norm.x * otherNorm.x + norm.y * otherNorm.y + norm.z * otherNorm.z
        if (dot < 1.0 - PRECISION) return false

        return true
    }

    override fun hashCode(): Int {
        var result = x.hashCode()
        result = 31 * result + y.hashCode()
        result = 31 * result + z.hashCode()
        return result
    }
}