https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2023 day 3> :thread:
# advent-of-code
a
k
I made a list of all the symbol locations at the start. It was supposed to be a set. As a result, My solution takes like 20 seconds instead of 2
a
Why did you create a set?
j
making a collection and operating on it was a trap, I almost felt in it too and started coding when suddenly this realisation: “but really, why?” and it turned out that going raster by raster was much easier to code and to execute 🙂
j
Yeah after solving it I have to agree @Jakub Gwóźdź, not using collections might have been easier
m
Part 1
🙌 1
Part 2
j
My solutions for Day 3 seem to give me a false positive on „Remove explicit type arguments“ for part2 with idea https://github.com/bulldog98/advent-of-code/blob/main/advent2023/src/main/kotlin/year2023/Day03.kt
n
I first extracted all the digits into a "parts" map, and then iterated over all the symbols. Code runs in < 100ms. One trick was to not use a 2-dimensional array of Ints for the map, but instead use a 2-dimensional array of a class containing an Int. That way, I can reset all the copies of a part number in the part map by simply setting the value in the class to 0.
j
my “raster” solution goes (cold start) 5ms (part1) and 12ms (part2) - I’m not sure why part2 takes so long, yet
n
Looking at other solutions here now, I agree that using a map for the part numbers is an overkill. Could have used a list instead (avoiding storing 0 for all non-number fields). But it's still early in AoC and thus can get away with non-sparse maps.
👍 1
n
My code is organizationally too messy to share, but one of the things I like about it is that I run a simple """\d+""" regex search and the matchresult gives me all the coordinates I need to check adjacent squares for.
same 1
e
https://github.com/ephemient/aoc2023/blob/main/kt/aoc2023-lib/src/commonMain/kotlin/com/github/ephemient/aoc2023/Day3.kt I built a collection and the runtime still seems fine (>1000 ops/s, so <1ms/op)
j
@ephemient why not use buildMap?
the 
apply
after 
mutableMapOf
is basically an implementation of 
buildMap
n
Behold this monstrosity:
j
Should the distinct not be in the inner 
flatMap
? As far as I know there were no garantees the same numbers could not be in the top and let's say the last line
d
First draft, will work on cleaning it. Doesn’t yet fit on one screen. https://github.com/dfings/advent-of-code/blob/main/src/2023/problem_3.main.kts
n
I wasn't expecting anyone to actually parse that awful "functional" code! I think you could make a case for putting a 
distinct
in both the inner and outer `flatmap`s, but at any rate, the outer one is necessary and cleans up the lack of the inner. The outer loop goes through each digit in the number, so there will be plenty of repeats, which the outer 
distinct
will catch.
n
@ephemient: code looks nice (as usual for you), but wondering why you don't have to only look at 
*
symbols for part 2?
e
@Jonathan Kolberg it is basically 
buildMap
, but I wanted to specify the types directly in order to not expose 
MutableList
beyond the initializer, and if I wasn't gonna get the benefit of builder inference then I didn't feel the need to bother
@Norbert Kiesel I forgot about it and it turned out not to matter, at least for both the example and my real input
p
p
today I tried to sacrificed readability for speed. then when my code passed the test but failed the actual result, I realized why readability is important haha
😅 4
j
@Peter Duong I feel your pain, had that happen a few times last year
🙌 1
a
in part 1, to avoid repeat-finding the neighbour numbers, I would immediately set each char to '.' after extracting the digit. in part 2, I realised that since numbers can be shared between gears, I should first get all the digits and make them distinct by the starting coord - and then if I had only two numbers, I should mark them as '.' Except I forgot to mark them as '.' but got the right answer for the actual input 🤦 saying to myself "well obviously, Anirudh, if the numbers can be shared between gears why would you want to remove them ever?!" switch code back to using a 
List<List<Char>>
instead of 
List<MutableList<Char>>
j
@Anirudh Actually there are no numbers that are shared by multiple gears, or even adjacent to any two parts (at least on my input). I believe otherwise @ephemient’s solution for part 1 would not have worked.
👍 1
d
Ah the first day where I can grab my trusty Matrix class from the utils package, it has such methods as getting all adjacent points from a certain point, making this pretty straightforward. I just scanned for part 2 until I found a *, got the adjacent numbers that were already parsed, made sure there are no duplicates and exactly 2 and multiplied
a
@Johannes Gätjen oh, that is curious. 🤔 for part 2, yeah - that does appear to be the case ✅ • and it doesn't look like numbers are shared between valid and invalid gears. so even if I made that substitution, it would be been okay. • and for gears with distinct numbers, it's only 1 or 2 but never 3 or more • and never 0 either - no floating 
*
or any symbol - all symbols have at least one neighbour • no symbols share neighbours at all (gears or otherwise0 maybe he took it easy on us for Day3. result: I wasted time re-writing the "find & replace numbers" for part 2, I could have just re-used my part 1 logic it with a 
*
check and 
result.size == 2
double 🤦
👍 1
d
OK happy enough with it now
a
my Adam (Frankenstein's monster) for extracting the numbers at each neighbour:
d
I decided to denormalize the full value into each point, using the same object (with identity semantics) to allow me to dedupe easily
e
I believe otherwise @ephemient’s solution for part 1 would not have worked.
yeah, I'd have to build the map in part 2 only if that were the case. but sometimes the inputs are nice :)
y
n
Just as I was about to go to bed, I decided how I wanted to refactor. Bad for tomorrow's busy schedule, but here it is. It works with the string directly, no grids, no regex. https://github.com/nbanman/Play2022/blob/master/src/main/kotlin/org/gristle/adventOfCode/y2023/d3/Y2023D3.kt
n
I find it harder to go in direction "pick cell (symbol or star) and find adjacent numbers" rather than "pick number and filter adjacent cells (symbol or star)". Though the first one probably better generalizes part1 and part2.
y
@Nikita Merinov agree with you. it's definetly more intuitive to "locale" all entities first and then find intersections, however that's not very perfomant
So I refactored my solution to smth like this
j
Today I went with a little messy state machine / parser which all together occupies ~100 loc. No more time to refactor today. Your solutions look interesting, as always. 👏
j
Great solutions all. My solution uses classes a bit more; I liked that I was able to implement it very much top-down, and that part 2 fit very well with the classes I created for part 1.
This is my first time to try AoC. Will the puzzles get more difficult later on or does it stay at this level?
📈 4
y
They will
🤓 1
n
@y9san9 Hm, could you please tell why do you think intiutive one is not performant? With "numbers then adjacents" approach you do one iteration over all table to find numbers, than for each number you check adjacents, in worst case 8 cells around single-digit number. If number is longer, you will have less scans per digit cells (e.g. for two-digit it is 10, for 3 -> 12, etc). With "cells then numbers" approach you also do one iteration over all table to pick each cell, then for each cell you always do 8 scans to check adjacent cells. And if there are digits you do additional scans to build a number. In the worst case you can scan the same number a lot of times, suppose table like that
Copy code
.********.
.11111111.
You will do 8 times substring to build the same number.
y
@Jaap Beetstra The first one was one-liner, while this (3rd) is already a lot harder. I solved the first one in 5 minutes, the second in 12 minutes and this in 30 minutes
I don't do algorithms usually, so my time is probably slower than other guys, but tasks will get harder every day
@Nikita Merinov Oh, looks like you're right. My first implementation was that I accumulate a list of all numbers and their regions (list of coordinates), then I searched for "stars" and compared every star coordinate with every number coordinate. Even if the star was 200 coordinates away
👍 1
j
@y9san9 I'm not timing how long it takes, it feels like they all take about the same, but I spend some time getting used to the format at first, so that could be why. I think 30 minutes is about right. I use the JetBrains template, and so far I have needed 35, 48, and 48 lines of code in the DayXX.kt files.
n
@y9san9 Yea, with that first implementation it is kind of O(n^2), which will blow up for bigger tables.
r
k
I made a version of my solution with comments explaining what my util functions are doing: https://github.com/Kroppeb/AdventOfCodeSolutions2/blob/master/solutions/src/solutions/y2023/day%203%20noted.kt
👍 1
x
Not sure if my solution is ugly or nice 😅 https://twitter.com/IsuruKusumal/status/1731272464825790926
p
https://github.com/PaulWoitaschek/AdventOfCode/blob/d919a4e89f801c130d11021e9dc9f4a45a4799f0/2023/src/main/kotlin/aoc/year2023/Day3.kt Pretty happy about my solution so far. My first iteration was a total mess but now it’s okayish. Though: Is this the hardest AOC ever? 🙈
j
Screenshot 2023-12-03 at 13.59.24.png,Screenshot 2023-12-03 at 14.00.58.png
m
t
day03.part2.kt.png,day03.part1.kt.png,day03.helpers.kt.png
c
I'm in the nasty position in part 1 that my solution works on the sample but not the main thing and I can't see why 😞
p
@Charles Flynn add one entry that ends with a digit and check if your code handles that
c
How do you mean?
Ahhh
At the end of the line
👍 1
Thankyou that'll be it 🙂
p
🤗
c
Yep that's fixed it 🙂
I don't know if it's because it's a weekend or not but this has felt a tougher start than recent years
same 4
💯 4
m
It‘s a tough start for me because I’m so busy, always on the run while I’m coding AoC this season …
p
I cobbled together a solution this morning before having to go out - it worked for the solve but it was definitely write-only coding...
Copy code
@AoKSolution
object Day03 : PuzDSL({
    part1 {
        lines.mapIndexed { y, line ->
            "\\d+".toRegex().findAll(line).filter { m ->
                val sr = max(m.range.first - 1, 0)..min(m.range.last + 1, line.lastIndex)
                (max(y-1, 0)..min(y+1, lines.lastIndex))
                    .map { lines[it].substring(sr) }
                    .any { it.any { c -> c != '.' && !c.isDigit() } }
            }.sumOf { it.value.toInt() }
        }.sum()
    }
    part2 {
        lines.mapIndexed { y, line ->
            line.mapIndexedNotNull { idx, c -> idx.takeIf{ c == '*' } }.sumOf { x ->
                (max(y - 1, 0)..min(y + 1, lines.lastIndex)).flatMap {
                    "\\d+".toRegex().findAll(lines[it]).filter { m ->
                        x in m.range || (x - 1) in m.range || (x + 1) in m.range
                    }.map { it.value.toInt() }
                }.takeIf { it.size == 2 }?.let { (a, b) -> a * b } ?: 0
            }
        }.sum()
    }
})
t
I liked today's puzzle a lot. I managed to solve it quickly and figured out a couple of improvements while I was on a walk with my dog in the woods before writing it up. Basically, I create sets for where each of the symbols and numbers are. In the case of the numbers, I store all of its neighbors as well. The answers are a matter of testing points in sets. • Code • Blog
K 4
r
Mine is over-engineered. Trying to solve everything without mutability 😄 Open to suggestions 🙂 • Code
s
pretty happy with my solution, could likely be optimized a good amount for better performance but it’s nice and concise + readable: • code
K 1
j
m
I cleaned up my day 3, I always like to preparse my data into a sensible data structure so that answering the actual questions is just like how you would ask it in text.
Copy code
object Day3 : Challenge() {
    private var parts: Set<Part>
    private var symbols: Set<Symbol>
    init {
        val graph = buildMap<Point, Segment> {
            input.lines().forEachIndexed { y, line ->
                line.forEachIndexed { x, char ->
                    when {
                        char.isDigit() -> put(
                            key = y to x,
                            value = get(y to x - 1).let { it as? Part ?: Part() }.apply {
                                positions += y to x
                                value = value * 10 + char.digitToInt()
                            },
                        )
                        char != '.' -> put(
                            key = y to x,
                            value = Symbol(
                                positions = listOf(y to x),
                                char = char,
                            ),
                        )
                    }
                }
            }
        }.apply {
            values.forEach { segment ->
                listOf(-1 to -1, -1 to 0, -1 to 1, 0 to -1, 0 to 1, 1 to -1, 1 to 0, 1 to 1).forEach { (y, x) ->
                    segment.positions.forEach { (baseY, baseX) ->
                        this[baseY + y to baseX + x]?.also {
                            segment.neighbours.add(it)
                        }
                    }
                }
            }
        }
        parts = graph.values.filterIsInstance<Part>().toSet()
        symbols = graph.values.filterIsInstance<Symbol>().toSet()
    }

    sealed interface Segment {
        val neighbours: MutableSet<Segment>
        val positions: List<Pair<Int, Int>>
    }

    data class Part(
        override val positions: MutableList<Pair<Int, Int>> = mutableListOf(),
        var value: Int = 0,
    ) : Segment {
        override val neighbours: MutableSet<Segment> = mutableSetOf()
    }

    data class Symbol(
        override val positions: List<Pair<Int, Int>>,
        val char: Char,
    ) : Segment {
        override val neighbours: MutableSet<Segment> = mutableSetOf()
    }

    override fun part1() = parts
        .filter { it.neighbours.any { it is Symbol } }
        .sumOf { it.value }

    override fun part2() = symbols
        .filter { it.char == '*' }
        .filter { it.neighbours.size == 2 && it.neighbours.all { it is Part } }
        .sumOf { it.neighbours.filterIsInstance<Part>().let { (a, b) -> a.value * b.value } }
}
67 Views
Open in Slack
PreviousNext
Powered by