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

View post

Ah, regexes and string splitting. The One True Way to parse text is with parser combinators.

import org.jparsec.Parser
import org.jparsec.Parsers.*
import org.jparsec.Scanners.*

data class Origin(val left: Int, val top: Int)
data class Size(val width: Int, val height: Int)
data class Claim(val id: origin: Origin, size: Size)

val integer: Parser<Int> = INTEGER.map(String::toInt)

fun <T> integerPair(sep: Char, c: (Int, Int) -> T): Parser<T> =  
    sequence(integer.followedBy(isChar(sep)), integer, c)

val claimId: Parser<Int> = isChar('#').next(integer)

val origin: Parser<Origin> = WHITESPACES.followedBy(isChar('@')).followedBy(WHITESPACES).next(integerPair(',', ::Origin))

val size: Parser<Size> = isChar(':').followedBy(WHITESPACES).next(integerPair('x', ::Size))

val claim: Parser<Claim> = sequence(claimId, origin, size, ::Claim)

val input: List<Claim> = File("input.txt").readLines().map(claim::parse)

Part 1

I really wanted to do Part 1 geometrically by splitting and merging claims into non-overlapping regions. It would be O(N²) however, and I was short of actual time to build it so went for the big map of positions like many others:

fun part1(claims: List<Claim>): Int {
    val material = mutableMapOf<Pos, Int>()
    claims.forEach { claim ->
        claim.positions().forEach { pos ->
            material[pos] = (material[pos] ?: 0) + 1
        }
    }
    return material.filterValues { it >= 2 }.size
}

That uses a modified Claim class as follows:

data class Claim(val id: Int, val x: IntRange, val y: IntRange) {
    constructor(id: Int, origin: Origin, size: Size):
        this(id, (origin.left .. origin.left + size.width - 1), (origin.top .. origin.top + size.height - 1))

    fun positions(): Sequence<Pos> = x.asSequence().flatMap { x ->
        y.asSequence().map { y -> Pos(x, y) }
    }
}

Part 2

Fairly simple extension. The tricky bit was remembering to remove both overlapping claims from the candidate result set:

fun part2(claims: List<Claim>): Set<Int> {
    val material = mutableMapOf<Pos, Int>()
    val nonOverlapping: MutableSet<Int> = claims.map { c -> c.id }.toMutableSet()

    claims.forEach { claim ->
        claim.positions().forEach { pos ->
            val claimed = material[pos]
            if (claimed == null) {
                // unclaimed position, now claimed
                material[pos] = claim.id
            } else {
                // overlapping position, remove both claims from result set
                nonOverlapping -= setOf(claimed, claim.id)
            }
        }
    }
    return nonOverlapping
}