day03.kt 7.65 KB
Newer Older
1 2
package net.keturn.advent2018

3
import java.lang.RuntimeException
4 5
import kotlin.math.max
import kotlin.math.min
Kevin Turner's avatar
Kevin Turner committed
6
import kotlin.system.measureTimeMillis
7

8 9 10
const val CLOTH_WIDTH = 1000
const val CLOTH_HEIGHT = 1000

Kevin Turner's avatar
Kevin Turner committed
11
private fun inputClaims(): List<Claim> {
12 13
    val infile = inputDirectory.resolve("3")
    return infile.useLines {
Kevin Turner's avatar
Kevin Turner committed
14
        it.map { line -> Claim.fromString(line) }.toList()
15 16 17
    }
}

Kevin Turner's avatar
Kevin Turner committed
18
data class Claim(val id: Int, val left: Int, val top: Int, val width: Int, val height: Int) {
19
    companion object {
Kevin Turner's avatar
Kevin Turner committed
20
        // Example: #1 @ 662,777: 18x27
21
        private val pattern = Regex(
Kevin Turner's avatar
Kevin Turner committed
22 23 24
            """#(?<id>\d+)\s*@\s*(?<left>\d+),(?<top>\d+):\s*(?<width>\d+)x(?<height>\d+)"""
        )

Kevin Turner's avatar
Kevin Turner committed
25
        fun fromString(s: String): Claim {
26 27
            val matchStrings = pattern.find(s)!!
            val (id, left, top, width, height) = matchStrings.groupValues.drop(1).map(String::toInt)
Kevin Turner's avatar
Kevin Turner committed
28
            return Claim(id, left, top, width, height)
29 30 31
        }
    }

Kevin Turner's avatar
Kevin Turner committed
32 33
    val right: Int get() = left + width - 1
    val bottom: Int get() = top + height - 1
34

Kevin Turner's avatar
Kevin Turner committed
35
    fun collision(other: Claim): Rect? {
Kevin Turner's avatar
Kevin Turner committed
36
        if (this.bottom < other.top || other.bottom < this.top)
37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
            return null
        if (this.right < other.left || other.right < this.left)
            return null

        val cLeft = max(this.left, other.left)
        val cTop = max(this.top, other.top)
        val cRight = min(this.right, other.right)
        val cBottom = min(this.bottom, other.bottom)

        return Rect(cLeft, cTop, cRight - cLeft + 1, cBottom - cTop + 1)
    }
}


data class Rect(val left: Int, val top: Int, val width: Int, val height: Int) {
Kevin Turner's avatar
Kevin Turner committed
52 53
    val right: Int get() = left + width - 1
    val bottom: Int get() = top + height - 1
54

55
    fun collided(other: Rect): Set<Rect>? {
Kevin Turner's avatar
Kevin Turner committed
56
        if (this.bottom < other.top || other.bottom < this.top)
57
            return null
58 59

        if (this.right < other.left || other.right < this.left)
60
            return null
61

Kevin Turner's avatar
Kevin Turner committed
62 63 64 65 66 67 68 69 70 71
        val inLeft: Rect
        val inRight: Rect
        if (this.left <= other.left) {
            inLeft = this
            inRight = other
        } else {
            inLeft = other
            inRight = this
        }

72 73 74 75 76 77 78 79
        // Special case for one rect being completely contained by the other.
        if (inRight.top >= inLeft.top &&
            inRight.bottom <= inLeft.bottom &&
            inRight.right <= inLeft.right  // and we already know inLeft.left <= inRight.left
        ) {
            return setOf(inLeft)
        }

Kevin Turner's avatar
Kevin Turner committed
80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
        val leftRect = Rect(inLeft.left, inLeft.top, inRight.left - inLeft.left, inLeft.height)

        val collisionRect = Rect(
            left = inRight.left,
            top = min(inLeft.top, inRight.top),
            width = min(inLeft.right, inRight.right) - inRight.left + 1,
            height = max(inLeft.bottom, inRight.bottom) - min(inLeft.top, inRight.top) + 1
        )

        val rightRectFrom = if (inLeft.right > collisionRect.right) inLeft else inRight

        val rightRect = Rect(
            left = collisionRect.right + 1,
            top = rightRectFrom.top,
            width = rightRectFrom.right - collisionRect.right,
            height = rightRectFrom.height
        )
97

Kevin Turner's avatar
Kevin Turner committed
98
        return setOf(leftRect, collisionRect, rightRect).filter { it.width > 0 }.toSet()
99 100 101 102 103 104
    }

    val area: Int get() = width * height
}


Kevin Turner's avatar
Kevin Turner committed
105 106
fun partOne(claims: List<Claim>): Int {
    val collisions = findCollisions(claims)
107 108 109 110 111
    val union = unionRects(collisions)
    return sumArea(union)
}


Kevin Turner's avatar
Kevin Turner committed
112 113
fun findCollisions(claims: List<Claim>): List<Rect> {
    val leftToRight = claims.sortedBy { claim -> claim.left }
114 115
    val collisions = mutableListOf<Rect>()

Kevin Turner's avatar
Kevin Turner committed
116 117
    val notCollidedYet = claims.toMutableSet()

Kevin Turner's avatar
Kevin Turner committed
118
    for ((currentIndex, claim) in leftToRight.withIndex()) {
Kevin Turner's avatar
Kevin Turner committed
119
        for (hazard in leftToRight.listIterator(currentIndex + 1)) {
Kevin Turner's avatar
Kevin Turner committed
120
            if (hazard.left > claim.right) {
121 122
                break
            }
Kevin Turner's avatar
Kevin Turner committed
123
            val collision = claim.collision(hazard)
124 125
            if (collision != null) {
                collisions.add(collision)
Kevin Turner's avatar
Kevin Turner committed
126 127
                notCollidedYet.remove(hazard)
                notCollidedYet.remove(claim)
128 129 130 131
            }
        }
    }

Kevin Turner's avatar
Kevin Turner committed
132 133 134
    println("These ${notCollidedYet.size} never collided!")
    notCollidedYet.forEach { println(it) }

135 136 137 138
    return collisions.toList()
}


139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165
fun rasterizeClaims(claims: List<Claim>): Array<ShortArray> {
    val canvas = Array(CLOTH_WIDTH) { ShortArray(CLOTH_HEIGHT) }

    for (claim in claims) {
        for (column in claim.left until claim.left + claim.width) {
            for (row in claim.top until claim.top + claim.height) {
                val was = canvas[column][row]
                canvas[column][row] = (was + 1).toShort()
            }
        }
    }

    return canvas
}


fun countOverClaimed(canvas: Array<ShortArray>): Int {
    val totalClaimed = canvas.fold(0) { n, column -> n + column.count { it > 1 }}
    return totalClaimed
}


fun partOneRaster(claims: List<Claim>): Int {
    val canvas = rasterizeClaims(claims)
    return countOverClaimed(canvas)
}

166

167
fun unionRects(rects: List<Rect>): Set<Rect> {
168 169 170
    var oldGeneration = rects.toSet()

    val collisionFree = mutableSetOf<Rect>()
171

172 173
    var passCount = 0
    do {
174
        val leftToRight = oldGeneration.sortedBy { rect -> rect.left }.toMutableList()
175 176
        val notCollidedYet = oldGeneration.toMutableSet()
        val newGeneration = mutableSetOf<Rect>()
177

178
        println("* Pass ${passCount}, ${notCollidedYet.size} inputs, ${collisionFree.size} cleared")
179

180 181 182 183 184 185
        while (leftToRight.isNotEmpty()) {
            val rect = leftToRight.removeAt(0)
            val forRemoval = mutableListOf<Rect>()
            val forAddition = mutableSetOf<Rect>()

            bloop@ for (hazard in leftToRight) {
186
                if (hazard.left > rect.right) {
187 188 189 190 191
                    break@bloop
                }
                val results = rect.collided(hazard)

                if (results != null) {
192 193 194 195 196 197 198 199 200 201 202 203
                    if (results.all { it == rect}) {  // special case for eclipsing the other
                        forRemoval.add(hazard)
                        notCollidedYet.remove(hazard)
                    } else {
                        notCollidedYet.remove(rect)
                        notCollidedYet.remove(hazard)

                        forRemoval.add(hazard)
                        forAddition.addAll(results)
                        newGeneration.addAll(results)
                        notCollidedYet.addAll(results)
                    }
204 205
                }
            }
206 207 208 209 210 211 212 213
            leftToRight.removeAll(forRemoval)
            for (newRect in forAddition) {
                var insertionPoint = leftToRight.binarySearchBy(newRect.left) { it.left }
                if (insertionPoint < 0) {
                    insertionPoint = -insertionPoint - 1
                }
                leftToRight.add(insertionPoint, newRect)
            }
214
        }
215 216 217 218 219

        collisionFree.addAll(notCollidedYet)

        if (passCount++ > 999_999_999) {
            throw RuntimeException("Too many iterations!")
220
        }
221 222 223
        oldGeneration = newGeneration
    } while (newGeneration.isNotEmpty())

224 225
    println("* * DONE * * ${collisionFree.size} cleared")

226
    return collisionFree
227 228 229 230 231
}


fun sumArea(rects: Collection<Rect>): Int {
    return rects.fold(0) { acc, rect -> acc + rect.area }
232 233 234 235
}


fun main(args: Array<String>) {
Kevin Turner's avatar
Kevin Turner committed
236
    val claims = inputClaims()
237

Kevin Turner's avatar
Kevin Turner committed
238
    println("${claims.size} claims")
239

240 241 242 243 244 245
    var rasterOverlapArea: Int? = null
    val rasterPartOneTime = measureTimeMillis {
        rasterOverlapArea = partOneRaster(claims)
    }
    println("Overlapping area: ${rasterOverlapArea}, ${rasterPartOneTime} ms")

Kevin Turner's avatar
Kevin Turner committed
246 247
    var overlapArea: Int? = null
    val partOneTime = measureTimeMillis {
Kevin Turner's avatar
Kevin Turner committed
248
        overlapArea = partOne(claims)
Kevin Turner's avatar
Kevin Turner committed
249 250
    }
    println("Overlapping area: ${overlapArea}, ${partOneTime} ms")
251
}