Kotlin

My solution can’t be very good because it took over a minute to run part 2. I used a ray casting algorithm to determine if a point was in the main polygon. I did that for the 2 corners of each rectangle that weren’t given as input. If both of those corners were in the polygon, then I checked each point of each edge of that rectangle.

My first stab at this didn’t consider the edge points of the rectangle, and after looking at some visualizations of the polygon, I could see where I was going wrong. I wouldn’t have considered a rectangle with all 4 corners in the polygon could have an edge that goes outside the polygon without looking at a visualization.

Part 2 code:

fun main() {
    val input = getInput(9)
    val polygon = parseInput1(input)
    val rectangles: MutableList<Rectangle> = mutableListOf()
    for (i in polygon.indices) {
        for (j in i + 1..<polygon.size) {
            rectangles.add(Rectangle(polygon[i], polygon[j]))
        }
    }
    rectangles.sortByDescending { it.area }
    var answer: Rectangle? = null
    for (rectangle in rectangles) {
        if (isInsidePolygon(rectangle.corner3, polygon)
            && isInsidePolygon(rectangle.corner4, polygon)
        ) {
            val edgePoints: MutableList<Pair<Long, Long>> = mutableListOf()
            edgePoints.addAll(getAllPointsBetween(rectangle.corner1, rectangle.corner3))
            edgePoints.addAll(getAllPointsBetween(rectangle.corner1, rectangle.corner4))
            edgePoints.addAll(getAllPointsBetween(rectangle.corner2, rectangle.corner3))
            edgePoints.addAll(getAllPointsBetween(rectangle.corner2, rectangle.corner4))
            var isInside = true
            for (edgePoint in edgePoints) {
                if (!isInsidePolygon(edgePoint, polygon)) {
                    isInside = false
                    break
                }
            }
            if (isInside) {
                answer = rectangle
                break
            }
        }
    }
    println(answer?.area ?: "Whoops")
}

fun parseInput1(input: String): List<Pair<Long, Long>> = input.lines()
    .filter { it.isNotBlank() }
    .map {
        val split = it.split(",")
        split[0].toLong() to split[1].toLong()
    }

data class Rectangle(val corner1: Pair<Long, Long>, val corner2: Pair<Long, Long>) {
    val corner3: Pair<Long, Long> = corner1.first to corner2.second
    val corner4: Pair<Long, Long> = corner2.first to corner1.second
    val area: Long = (1 + abs(corner1.first - corner2.first)) * (1 + abs(corner1.second - corner2.second))
}

fun isInsidePolygon(point: Pair<Long, Long>, polygon: List<Pair<Long, Long>>): Boolean {
    val x = point.first
    val y = point.second
    var intersectionCount = 0L
    for (i in polygon.indices) {
        val p1 = polygon[i]
        val p2 = polygon[(i + 1) % polygon.size]
        if (point == p1 || point == p2 || isOnEdge(point, p1, p2)) {
            return true
        }
        val y1 = p1.second
        val y2 = p2.second
        val crossesRay = (y in y1..<y2) || (y in y2..<y1)
        if (crossesRay) {
            val x1 = p1.first
            val x2 = p2.first
            val xIntersect = (x2 - x1) * (y - y1).toDouble() / (y2 - y1) + x1
            if (x < xIntersect) {
                intersectionCount++
            }
        }
    }
    return intersectionCount % 2L != 0L
}

fun isOnEdge(p: Pair<Long, Long>, p1: Pair<Long, Long>, p2: Pair<Long, Long>): Boolean {
    val crossProduct = (p.second - p1.second) * (p2.first - p1.first) -
            (p.first - p1.first) * (p2.second - p1.second)
    if (crossProduct != 0L) {
        return false
    }
    val isBetweenX = p.first in minOf(p1.first, p2.first)..maxOf(p1.first, p2.first)
    val isBetweenY = p.second in minOf(p1.second, p2.second)..maxOf(p1.second, p2.second)
    return isBetweenX && isBetweenY
}

fun getAllPointsBetween(left: Pair<Long, Long>, right: Pair<Long, Long>): List<Pair<Long, Long>> {
    if (right.first == left.first) {
        val max = maxOf(left.second, right.second)
        val min = minOf(left.second, right.second)
        return (min + 1..<max).toList().map { right.first to it }
    } else if (right.second == left.second) {
        val max = maxOf(left.first, right.first)
        val min = minOf(left.first, right.first)
        return (min + 1..<max).toList().map { it to right.second }
    } else {
        throw Exception("Whoops")
    }
}