https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2023 day 18> :thread:
# advent-of-code
a
m
Day 10 gives you the solution of just the holes inside a given perimeter, today we needed both the holes and the perimeter itself. Which was a small tweak to that logic. Proud of this one today.
Copy code
object Day18 : Challenge() {
    val parsed = input.lines().map { line -> line.split(" ") }

    override fun part1() = parsed.map { (a, b, _) -> a[0] to b.toInt() }.solve()
    override fun part2() = parsed.map { (_, _, c) -> c.toDigLine() }.solve()

    fun List<Pair<Char, Int>>.solve() = runningFold(0 to 0) { point, (dir, amount) -> point.move(dir, amount) }
        .zipWithNext { (y1, x1), (_, x2) -> (x2 - x1) * y1.toLong() }
        .sum().absoluteValue + sumOf { it.second } / 2 + 1

    private fun Pair<Int, Int>.move(direction: Char, amount: Int) = when (direction) {
        'U' -> first - amount to second
        'R' -> first to second + amount
        'D' -> first + amount to second
        else -> first to second - amount
    }

    private fun String.toDigLine() = when (get(lastIndex - 1)) {
        '0' -> 'R'
        '1' -> 'D'
        '2' -> 'L'
        else -> 'U'
    } to substring(2..6).toInt(16)
}
j
m
Part 2
My problem in part 2 was that my Point class was Int based...
m
@Jakub Gwóźdź using an enum to map both ints and chars to the same entry is pretty smart blob think smart
j
@Michael de Kaste tbh what I like most about enums is that 
when
is exhaustive in such cases, so no ugly 
else->error("should never happen")
🙂
m
yeah exactly, rewrote some of mine with your enum logic. EAST, NORTH, SOUTH, and WEST are just points like (0, 1)
Untitled
j
yeah I actually coded the Pos+Dir functionality as well before I realized it’s just the same thing as a week ago and decided to drop it. I was just a bit scared that I might fall into yet another off-by-ones, but fortunately the only thing I forgot at first try was the “.absoluteValue” 🙂
m
I wonder if this trend continues. 👀
1. Day 10 = Interior of n-sided polygon 2. Day 17 = Area of n-sided polygon 3. Day 24 = Area of 3d polygon??? 4. ???? 5. profit
e
@Marcin Wisniowski Brilliant! I failed to see it as a geometry problem and somehow initially worried there might be self-intersections. Also, I would have never figured out that you can adjust the resulting area using half of the permitter plus one. That’s a nice trick.
plus1 1
e
same 3
probably would have ended up having to decompose it into rectangles to calculate the area
e
@Marcin Wisniowski Is there a name/proof to the (area + perimeter/2 +1) formula for the full area on such a grid?
j
@elizarov Pick’s theorem
e
iirc it's provable via induction
e
@Jakub Gwóźdź Thanks. Always keep forgetting about it.
w
First time on global leaderboard for me thanks to day 10 (at least for part 1). Had to rewrite some stuff to use longs for part 2 which held me back slightly.
m
I used the following logic and then adjusted the result based on my findings in a 2D grid (but tbf I did this for Day10)
because doing this formula on points on a grid give you the total area of the interior + half of the exterior. So for day 10 it was removing half of the exterior. For day 18 it was adding half of the exterior
m
@elizarov Shoelace Formula for the area, then Pick's theorem for integer points inside the area.
j
@Marcin Wisniowski Shoelace Formula + outer edges gives the correct value too
m
I tried that first but it didn't for me. Maybe I just made a mistake in that approach though.
j
My solution for today https://github.com/bulldog98/advent-of-code/blob/main/advent2023/src/main/kotlin/year2023/Day18.kt, part1 I first solved with building a wall and then flooding from outside, but that did not work out for the big area in part 2
e
@Marcin Wisniowski I did not know it was called “shoelace formula” for the area. That’s “triangles formula” for me ;) Btw, I was originally taught to use the trapezoid formula (x2-x1) * (y2+y1) / 2 and that is what I always tend to write in all the geometry problems to compute an area.
j
@Marcin Wisniowski right, there is a +1 involved also to compute the final result
n
Long
mafia strikes again! I saw it coming, and yet I didn't think I needed to convert so early. Like @Marcin Wisniowski I was burned by my Int-based Point class.
e
points can be 
Int
, your accumulators just need to be 
Long
(that's what I did)
n
Yeah, I kept my points. It was the shoelace cross-multiplication I thought I could get away with.
t
I'm happy that I managed to solve this on my own 🙂 Part 1 was not hard due to day 10, but ofc my solution was totally inadequate for part 2. For part2: • I googled for the area formula for a simple polygon (trapezoid formula) • but I had a hard time accounting for the edges • what I finally did was offsetting ◦ all down-oriented edges by one to the right ◦ all left-oriented edges by one to the bottom • then computing trapezoid on such modified shape did the trick 😛
n
I gotta admit I arrived at my solution by a bit of trial and error. I assumed that the shoelace formula would give me a usable area number that I could just plug in. It was obviously short for the example, so I went ahead and applied Pick's (knowing that would get me the inner area per Day 10) and added the perimeter. But I still don't know why Shoelace alone is insufficient. Maybe it has something to do with using discrete blocks with their own area rather than points? I gotta go to bed so I'll take my answer off the air.
d
@Jakub Gwóźdź what theory is behind your 
calc
function? It looks so simple 🤪
e
imagine this as input:
Copy code
R 2 (#000020)
D 2 (#000021)
L 2 (#000022)
U 2 (#000023)
the path:
Copy code
.....
.┏━┓.
.┃.┃.
.┗━┛.
.....
the desired area:
Copy code
.....
.███.
.███.
.███.
.....
the area if you calculate just by multiplying coordinate differences:
Copy code
.....
.██..
.██..
.....
.....
(or
Copy code
.....
.▗▄▖.
.▐█▌.
.▝▀▘.
.....
if you think about it as being centered in the middle of the pixels) thus you need to adjust for the half perimeter + 1, or the extra half/quarter pixels, depending on how you look at it
👍 1
m
I made this small illustration 😁
😎 1
oops small mistake
p
I need help. I implemented the shoelace formula. The values were off so I was randomly adding operators to the result to accounting for the border. Now it’s working but I have no clue why 🤯. Can someone explain why my solution produces the correct results? https://github.com/PaulWoitaschek/AdventOfCode/blob/dd130b5e81c3ea8c7219eed960030fd16af7c589/2023/src/main/kotlin/aoc/year2023/Day18.kt
e
your 
border
includes 
Point.Zero
at both the start and end, so 
ceil(border.size / 2f).toInt()
is the 
(border without duplicates).size / 2 + 1
. then see the above for why that's needed for adjustments
🙏 1
m
In part 1, before actually solving it all with code, I've just drawn the perimeter in a 
BufferedImage
, opened the resulting image in an image editor, clicked with the bucket fill tool to fill the shape, then dragged that to some "count pixels" website which told me how many black pixels are there. 😄
😆 4
❤️ 1
e
external tools are always handy, I've pulled up Wolfram Alpha for checking on quite a few days. how'd that go for part 2 though? 😛
p
Oh, using a shoelace formula is a much nicer way than my ray tracing solution, but it still runs ~80ms for part 2 😄 https://github.com/glubo/adventofcode/blob/edf14194ec1aecb1c18a96a1977c395008ff5bb0/src/main/kotlin/cz/glubo/adventofcode/day18/Day18.kt (spoiler alert)
e
https://github.com/ephemient/aoc2023/actions/runs/7244631329/job/19733260429#step:6:1124
Copy code
jvm summary:
Benchmark         Mode  Cnt       Score        Error  Units
Day18Bench.part1  avgt    5     119.370 ±      2.064  us/op
Day18Bench.part2  avgt    5     123.276 ±      2.386  us/op
p
it would be a nice easter egg if colored points would form some image or text 😉
p
Copy code
Benchmark         Mode  Cnt      Score        Error  Units
BenchDay18.part1  avgt    3     46.068 ±     15.653  us/op
BenchDay18.part2  avgt    3     36.800 ±      8.228  us/op
Having shoelace already in mind from previous day helped this one - only catch was to include ~half the perimeter.
Day18.kt
Day18.kt
p
m
I consider my best achievement for today, that I implemented generic math operations on PairT, T to not worry anymore about whether my points are Int or Long. (btw, I wonder how bad is such implementation performance against no generics implementation)
m
the colors feel like they belong in the 'inverted' spectrum
😻 1
e
@Movses Elbakian if you did
Copy code
@JvmName("plusPairInt")
operator fun Pair<Int, Int>.plus(other: Pair<Int, Int>): Pair<Int, Int> =
    this.first + other.first to this.second + other.second
@JvmName("plusPairLong")
operator fun Pair<Long, Long>.plus(other: Pair<Long, Long>): Pair<Long, Long> =
    this.first + other.first to this.second + other.second
// etc.
instead, then it'll be static dispatch
🔥 1
although if you want to support all combinations of all built-in numeric types, that's a bit of a combinatorial explosion and maybe you should codegen that, like what stdlib does for primitive array types and collection-like extensions
➕ 1
m
Didn't know about static dispatch, I will consider refactoring to that way
m
for an interval library I made myself, I could use private context receiver functions with public actual contexts that define how it can make primitive types work. It means I needed to write the code only once, but it does become an import nightmare.
f
@Jakub Gwóźdź I get the outline part - but this one puzzles me. My brain might have gone into post-aoc mode though:
Copy code
var area = 0L
    var y = 0L
    data.forEach { (d, t) ->
        when (d) {
            R -> area += y * t
            D -> y += t
            L -> area -= y * t
            U -> y -= t
        }
    }
(I used the shoelace formula myself)
j
If you go up/down you increase or decrease the 
y
and when going left/right you increase/decrease the area by 
y
at that moment . Generally it's calculating the integral of function (which is the area below/inside the shape)
e
there's a geometric interpretation and a path integral interpretation. I think I saw some gifs for the former…
d
Super interesting… so for these square circumferences you don’t need shoelace at all. But then again, shoelace works for more polygon types?
j
The best way to see it is to start drawing a rectangle L2, D3, R2, U3 and see what the values are after each step, then you add more and more features to such shape
👍 1
d
I don’t think this works when two consecutive points draw a diagonal line. Am I correct?
m
it doesn't, but thats mostly bound to the fact that it works directly on the input: D 6 = go down 6. But if your next point is D6R4, your next point is not on the same line. But tbf, with this formula you can easily also add the triangle area as well
e
it does if you use the average height 🙂
m
it just so happens that the 'triangle area' is 0 in all these cases
e
can't find the gifs I was looking for, oh well
nvm found them, thanks to @elmusfire on discord
day10.mp4day10v2.mp4
🙏 1
f
wow - thx!
d
Nice! … satisfying when it’s all the way to the right and starts filling in greens going left 🤩
One to save for next year!
c
That was nice and gentle as a result of day 10. Day 18 marks the furthest i've made it in one of these 🙂 Usually there's some 3D nonsense that makes me check out and fall behind.
😂 1
💪 5
r
Instead of dusting off 
java.awt.Polygon
again after day 10, I decided to apply the things I learned from you guys that day regarding the shoelace formula and actually got a proper solution today! So thank you for teaching me! 🤓
👍 1
o
Tried kotlin notebooks for the first time, and thanks to whoever mentioned Pick's Formula
Copy code
%use kandy
import org.jetbrains.kotlinx.dataframe.api.dataFrameOf
import java.io.File


val input = File("input1.txt").readText().trim()

public enum class Direction {
    UP, DOWN, LEFT, RIGHT
}

data class Point(val x: Long, val y: Long)

fun String.commandToDirection(): Direction {
    return when (this) {
        "U" -> Direction.UP
        "D" -> Direction.DOWN
        "L" -> Direction.LEFT
        "R" -> Direction.RIGHT
        else -> error("Unknown direction $this")
    }
}

fun executeCommand(
    currentPoint: Point,
    command: Pair<Direction, Long>
): Pair<Direction, Point> {
    fun mapit(it: Long) = when (command.first) {
        Direction.UP -> currentPoint.copy(x = currentPoint.x + it)
        Direction.DOWN -> currentPoint.copy(x = currentPoint.x - it)
        Direction.LEFT -> currentPoint.copy(y = currentPoint.y - it)
        Direction.RIGHT -> currentPoint.copy(y = currentPoint.y + it)
    }
    return command.first to mapit(command.second)
}

val lines = input.trim().split("\n")
val visitedPoints = mutableSetOf<Point>()
visitedPoints.add(Point(0, 0))
val commands = lines.map {
    val line = it.split(" ").last().drop(1).dropLast(1)
    val arr = arrayOf("R", "D", "L", "U")
    arr[line.last().digitToInt()].commandToDirection() to line.dropLast(1).drop(1).toLong(16)
//    val line = it.split(" ")
//    line[0].commandToDirection() to line[1].toLong()
}
//println(commands  )
val points = mutableListOf<Point>()
points.add(Point(0, 0))
var add = false
commands.fold(commands.first().first to points.last()) { acc, command ->
    val r = executeCommand(acc.second, command)
    points.add(r.second)
    r
}
val positiveOrientedPoints =
    points.map { it.copy(x = it.x + min) }

fun polygonArea(): Long {
    val pp = listOf(points.first()) + points.reversed()
    return abs(pp.mapIndexed { index, point ->
        if (index == 0) {
            0L
        } else {
            val prevPoint = pp[index - 1]
            ((point.y * prevPoint.x) - (prevPoint.y * point.x)).toLong()
        }
    }.sum() / 2)
}

println("Area ${commands.map { it.second }.sum() / 2 + 1 + polygonArea()}")

plot {
    layout { 
        size = (800 to 800)
     }
    path {
        y(points.map { it.x })
        x(points.map { it.y })
    }
}
image.png
22 Views
Open in Slack
PreviousNext
Powered by