Discussion on: AoC Day 3: No Matter How You Slice It

[Jon Bristow]

Kotlin Solution

UGH! This one seemed like a reversal, the first part was much harder than the second part.

I started out as I always do when pretending to be a video game developer: swearing loudly because my rectangles were overlapping and I forgot that it's way easier to find out if they're not overlapping.

Then I kept trying to optimize, but that wasn't getting me anywhere. I ended up brute-forcing my way through. This is ugly... maybe 25 seconds to chunk through.

Part 1

typealias Point = Pair<Int, Int>

val Point.x get() = first
val Point.y get() = second

private fun String.parseRect(): Rectangle {
    val result = Regex("""#(\d+) @ (\d+),(\d+): (\d+)x(\d+)""").find(this)
    val groups = result!!.groups
    return Rectangle(
        groups[1]!!.value,
        groups[2]!!.value.toInt(),
        groups[3]!!.value.toInt(),
        groups[4]!!.value.toInt(),
        groups[5]!!.value.toInt()
    )
}

class Rectangle(val id: String, val tl: Point, val br: Point) {
    constructor(id: String, x: Int, y: Int, width: Int, height: Int) :
            this(id, x to y, x + width to y + height)
}

private fun Rectangle.overlaps(b: Rectangle) = when {
    this.id == b.id -> false
    b.br.x <= tl.x || b.tl.x >= br.x -> false
    b.br.y <= tl.y || b.tl.y >= br.y -> false
    else -> true
}

fun Rectangle.intersection(b: Rectangle): Set<Point> =
    (max(tl.x, b.tl.x) until min(br.x, b.br.x)).flatMap { x ->
        (max(tl.y, b.tl.y) until min(br.y, b.br.y)).map { y -> x to y }
    }.toSet()

fun answer1(input: List<String>) =
    input
        .cartesian { a, b -> a.parseRect() to b.parseRect() }
        .filter { (a, b) -> a.overlaps(b) }
        .map { (a, b) -> a.intersection(b) }
        .reduce { set, other -> set.union(other) }
        .count()

Part 2

After calming down a little (rectangles are dumb), I set in to work on the second part. This turned out much simpler. It was just another n² with an early escape function. Almost identical to yesterday. The key is making sure our find eliminates candidates as fast as possible. Enter none, which returns false as soon as we see an overlap with our current. Yes, I was lazy and just added a quick "same id == no overlap" check instead of making sure I was checking unique pairs. I'm getting sleepy, and the first one frustrated me more than I would have liked.

fun answer2(input: List<String>) =
    input.asSequence()
        .map(String::parseRect)
        .let { rects ->
            rects.find { a -> rects.none(a::overlaps) }?.id
        }

[jess unrein]

I totally agree that the second part seemed so much easier that the first. It really threw me off.

[Paula Gearon]

I initially thought that I should use my data structure from part one to solve part 2, but while figuring it out I realized that a different structure was much more effective. I like to make my functions for the first and second parts independent anyway, so it didn’t bother me to do it again. And it came out much smaller!

[Jon Bristow]

From my pain, your gain! An image of the overlapping areas plotted.

[Ryan Palo]

#rectanglesaredumb