https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2023 day 13> :thread:
# advent-of-code
a
kodee happy 1
j
I'm not sure if a reflection in the last two rows counts as reflection
b
i mean it meets the requirements
that one was.. interesting. p2 not as hard as i origionally thought
j
what should one do for part1 if one finds horizontal and vertical reflection, which one to take?
b
i coded it to count both, but i didn't check if there were any that had both
j
I checked an I had both for part1, and I still have not the right answer, so I'm not sure, if I messed up detection or if you should first take horizontals and then verticals or the other way around
b
well you're not modifying anything so order shouldn't matter, you might want to check your detection algorithm though
m
I only check for first found, and I check vertical reflection lines first, and that seemed to work fine.
☝️ 1
j
Oh the example the second has horizontal and vertical according to my implementation it also has a vertical between column 7 and 8
which is incorrect
b
i just scanned mine, looks like i only ever have a single mirror line, either horizontal or vertical
w
I think there can be both horizontal and vertical reflections at the same time, at least in my input
m
for part2 is it guaranteed that there is only one smudge?
b
that never happened in my input (for part 1)
yes
the questions states that
m
oh okay, thank you
w
hmm maybe you’re right with a second look it does not seem to happen
Rather easy day for a change
b
nice compared to yesturday
e
e
Today the second part did not have any unexpected surprises
m
Messed up today quite a bit, didn't read some crucial parts and overdid some others, but alas thats adventofcode for you 😂
j
Messed up for part2, generated infinite sequences of smudge replacements and never terminated, oops
j
I have the feelings that today’s puzzle was all about “who can debug faster” 🙂
👌 5
j
Yep, agreed. Algorithm was pretty straight forward, but lots silly issues to debug (off by 1) to get it working. Now to clean up this horrible code...
a
hi all! I think I took a straightforward approach using a fuzzy diff that forgives <=1 wrong chars.. here's my code https://github.com/andriyo/advent-of-code-kotlin-2023/blob/main/src/Day13.kt plenty of optimizations could be made (for example, to transpose a matrix, I create a copy which is obviously not efficient) anyway, my goal as always was to have immutable data structures, no vars, no recursion
p
Just kept to the same logic but instead of requiring string equality, I required total mismatched chars to be == 1
Day13.kt
a
also XOR comes to mind - I haven't tried it but it might be another way to do it
m
Lots of functions on this one
day13.txt.kt
j
Bit surprising that part2 was so easy to brute force. Even without any optimisations it finishes very quickly. https://github.com/JBeet/MyAdventOfCode2023/blob/main/src/aoc13/Day13.kt
d
What if there are 2 ( or more) lines of reflection ?
j
@Dave it is not specified, and (thus?) it was not in the input
j
You do have to ignore the old reflection lines (for Part 2)
p
If you're asserting that you only have exactly one smudge, the old reflection line isn't going to count any more anyway
At least for my input I didn't need to filter/check for "normal" reflection.
m
depends on your logic, I could 'unsmudge' one spot, and my logic was "find the first line that has a reflection" and the old reflection was still present, so now I had two reflections possible
e
I also looked for reflections with a single smudge. Thus previous perfect reflections are not candidates.
p
Given you unsmudge a single spot at a time, I'm not sure how the old reflection would still apply - do you have an example?
n
Hamming distance was useful to solve today’s puzzle
j
@phldavies If the smudge is outside the reflected area; eg “.S..##.#.|.#.##“, where S is the smudge, and I added a ‘|' as the mirror
j
Which even happens in the first puzzle of the explanation data
d
@Jaap Beetstra This is in the input and seems to have two lines of vertical reflection (2-3 & 10-11)
Copy code
....#....##....
.##..##.####.##
#..#.#...##...#
.##.####....###
#..#.##.####.##
#..###.#.##.#.#
.##.##.##..####
e
Copy code
....##....
##.####.##
....##...#
###....###
##.####.##
#.#.##.#.#
#.##..####
10-11 is not a reflection, isn't it?
d
Copy code
.##.
####
.##.
....
####
.##.
#..#
j
@Dave to count for reflection you need to consider all lines, not only two
e
Only those 2 columns, but you must include all of them until you reach an edge
d
if you have to reach an edge...then some grids do not have any line of reflection ?
(and there are 4 columns !)
m
Im not sure if I understand your question
it can reflect along every line horizontal line or vertical line. e.g. reflect between 1 and 2 or reflect between 5 and 6 you walk from that middlepoint outwards over the lines, until one side reached an end, then you stop comparing (because over the edge MIGHT be the reflection of the other side)
d
I must be missing something in the requirements / puzzel description. From the input grids I find either, • reflections must hit an edge - in which case some have no reflection point • or, multiple lines of reflection
m
remember the puzzle from yesterday? where '?' could be both values?
Copy code
....#....##....
.##..##.####.##
#..#.#...##...#
.##.####....###
#..#.##.####.##
#..###.#.##.#.#
.##.##.##..####
is equal to
Copy code
....#....##....????????
.##..##.####.##????????
#..#.#...##...#????????
.##.####....###????????
#..#.##.####.##????????
#..###.#.##.#.#????????
.##.##.##..####????????
you can pretend the grid extends both ways with a potential reflection
m
What's the nicest solution to group the input at blank lines? I'm using fold but the mutableLists() do annoy me a bit:
Copy code
val patterns = input.fold(mutableListOf(mutableListOf<String>())) { groups, line ->
    groups.apply {
        when {
            line.isBlank() -> add(mutableListOf())
            else -> last().add(line)
        }
    }
}.map { Pattern(it) }
m
so this reflection:
Copy code
....#....#|#....????????
.##..##.##|##.##????????
#..#.#...#|#...#????????
.##.####..|..###????????
#..#.##.##|##.##????????
#..###.#.#|#.#.#????????
.##.##.##.|.####????????
cannot occur because the 4th value on the bottom row differs if you walk outwards from the reflection centre
does that help @Dave?
d
@Michael de Kaste so you are saying that the reflection must hit the edge..yes ?
m
well beyond the edge, everything matches. So if one side reaches an edge (there is fog at the edge, so you can't see further), the other side reflects with whatevers in the fog
d
then where is the reflection point for this (also in the input)
Copy code
...##....
.#.##.#..
.#....#..
.##..##..
...##....
..####.##
#..##..##
using the obvious vertical reflect line does it not hit the edge ?
m
I cant seem to find a reflection in there, since one above the bottom left, doesn't match with its potential reflection along the reflection on 4|5
but
there is one at the end
e
m
Copy code
...##...|.
.#.##.#.|.
.#....#.|.
.##..##.|.
...##...|.
..####.#|#
#..##..#|#
equals
Copy code
...##...|.???????
.#.##.#.|.???????
.#....#.|.???????
.##..##.|.???????
...##...|.???????
..####.#|#???????
#..##..#|#???????
d
Ah!!!! Thanks for clarifying
m
No problem, I get that it can be confusing 🙂
m
@ephemient Ah nice one. I somehow always forget to use the builder functions for lists and sets 😅
e
@Max Thiele To avoid MutableLists altogether you can try with Sequences:
Copy code
fun readPatterns2(lines: Sequence<String>) = sequence {
    val lastOne = lines.fold( listOf<String>()) { acc, line ->
        if (line.isEmpty()) {
            yield( Pattern(acc))
            listOf<String>()
        }
        else acc + line
    }
    yield (Pattern(lastOne))
}
p
I have this in my toolbox but I don't tend to use it:
Copy code
fun <T> List<T>.cutAt(idx: Int) = subList(0, idx) to subList(idx + 1, size)
fun <T> List<T>.cutAt(p: (T) -> Boolean) = indexOfFirst(p).let { if (it >= 0) cutAt(it) else this to null }
fun <T> List<T>.splitOn(p: (T) -> Boolean) = Iterable {
    iterator {
        var remaining = this@splitOn
        while (remaining.isNotEmpty()) {
            val (a, b) = remaining.cutAt(p)
            yield(a)
            remaining = b ?: break
        }
    }
}
I tend to just do 
input.split("\n\n").map(String::lines)
(assumes 
input
doesn't have any trailing new lines)
e
repeatedly appending to a non-mutable list is O(N^2) though
e
There's no free meal 🙂. For me 
input.split("\n\n").map(String::lines)
is probably the shortest and highest performing solution.
m
Ok, I think I'm settling on buildList with a runningFold:
Copy code
val patterns = buildList {
    input.plus("").runningFold(mutableListOf<String>()) { group, line ->
        when {
            line.isBlank() -> mutableListOf<String>().also { add(Pattern(group)) }
            else -> group.also { it.add(line) }
        }
    }
}
p
Given you're not using the output sequence of 
runningFold
, a 
fold
would do?
m
Ah yes that is true
k
m
Alright final one, this time I do use the output of 
runningFold
^^
Copy code
val patterns = input
    .runningFold(mutableListOf<String>()) { group, line ->
        if (line.isBlank()) mutableListOf() else group.apply { add(line) }
    }
    .distinct()
    .map { Pattern(it) }
m
Part 2 took me forever because I used a firstOrNull where I would have needed a filter (to skip an entry) in one of three call sites. Damn! https://github.com/MikeEnRegalia/advent-of-code/blob/master/src/main/kotlin/aoc2023/day13.kt
j
Now in the launch break part 2 was solved, the computing lists of reflections was a bit tedious, but works https://github.com/bulldog98/advent-of-code/blob/main/advent2023/src/main/kotlin/year2023/Day13.kt
m
So after some refactoring I think this is about as short as it can be: https://github.com/fabmax/aoc-2023/blob/main/src/main/kotlin/day13/Day13.kt
c
A useful trick @Max Thiele with input like this is to split on "\n\n". e.g.
Copy code
private val input = readFile("13.txt").split("\n\n").map { s ->
    val matrix = s.lines()
    val transposed = matrix.transposed()
    matrix to transposed
}
m
Jup, unfortunately my framework is a little too smart there and provides the input as already splitted list of individual lines. I guess I could change that but in mopst cases the list of lines is what you need
a
think better split by 
System.lineSeparator()
m
Yeah I do 
System.lineSeparator()
myself too, but I wrote on extension as 
String.splitOnEmptyLine()
Reading input as just that, a string, is something I started doing 2 years back, I used to do List<String> as well, but that was too much hassle in the end, and writing 
.lines
or 
splitOnEmptyLine
isn't a hassle 😄
c
I have two utility functions. 
readFileAsLines
is the most common usage but 
readFile
when I want to go manual.
m
> Jup, unfortunately my framework is a little too smart there and provides the input as already splitted list of individual lines. Mine did too originally, but a year or two ago I added a second variant to get the whole input. 😄
a
Right, I have similar
m
It's my first year of aoc, so probably I'm gonna change it as well in a year or two 😆
j
@Max Thiele You could also do it like this:
Copy code
fun split(input: List<String>): List<List<String>> =
    (listOf(-1) + input.indices.filter { input[it].isBlank() } + input.size).zipWithNext { prev, cur ->
        input.subList(prev + 1, cur)
    }
m
@Jaap Beetstra also a nice solution! It seems for today splitting the input in a nice way is more challenging than the puzzle itself 🙂
n
I have a little 
Collection.chunkedBy
helper which allows to use 
input.chunkedBy { it.isEmpty() }
. Not the most efficient, but easy on the eye.
j
I have built a similarly named helper, but I use it in different scenario’s: if you provide a Collection (or Sequence) sorted by country, then 
Collection.chunkedBy { it.country }
will turn it into a list of lists with the same country. For this situation I have a helper named ‘split’ (similar to String.split) 
fun <T> List<T>.split(predicate: (T) -> Boolean)
. So e.g. 
input.split { it.isEmpty() }
n
Yes, might be better naming
t
I was tempted to create a set of points and do all the work with that but ended up using strings directly. Not a huge fan of my input.joinToString.map/split thing but it gets the job done. • Blog • Code
n
I used my CharArea which is an Array<CharArray> after learning that CharArray has a concatToString method which mimics substring
p
That was another fun one! K Part 1: • Doing a zipWithNext to find two columns / rows which are the same • Expand from there in both directions and check if it’s valid reflection lines Part 2: • Building a sequence of smudge reflections by replacing one char per index and checking if it’s a valid reflection using code from pt 1 • Taking first smudge reflection that’s different from the original reflection https://github.com/PaulWoitaschek/AdventOfCode/blob/e563429ffd2fb6aa1f2f064aae21f1ba80e993cf/2023/src/main/kotlin/aoc/year2023/Day13.kt
e
I tried to improve the solution by using a set of points, but it takes longer. I think the problem is so simple that it's not worth doing any additional work to parse the input. I also tried a third version using parallel processing and it has been worse, probably the extra time to initialize the routine is comparable to the time to process a single pattern. https://github.com/bayesiano/AoC-2023/blob/master/src/main/kotlin/Day13c.kt
p
I naturally went with sequences. That turned out to be twice as fast for me for part 2
p
I avoided any mutations in part2 (beyond transposing the input lists) by finding a possible reflection point with at most one char difference, reversing the lost beforehand and zipping with the after list, and summing for exactly one char difference. Worked nicely and seemed fairly quick. https://github.com/tKe/aoc/blob/main/kt/src/main/kotlin/year2023/Day13.kt
Should probably try using asReversed and stopping after a single difference rather than summing them all and checking 
== 1
t
@phldavies When refactoring my solution, I used your idea for counting mismatches - it's brilliant! Not only it allows for using the original input easily as well as omitting the previous mirror line but it also allows to break early during the comparison 🙂 edit: you just mentioned what I wrote about breaking early 😄
p
Yeah I liked the simplicity of leaving it as a sum equality, rather than unwrapping to break earlier.
👍 1
g
Finally I found some time to finish the task. From the beginning I wasn't sure how columns/rows will be compared so I started using hashCodes and it works too 🙂 https://github.com/grzegorz-aniol/Kotlin-AoC-2023/blob/main/src/main/kotlin/pl/appga/aoc2023/days/Day13.kt
12 Views
Open in Slack
PreviousNext
Powered by