https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2023 day 25> :christmas_tree:
# advent-of-code
a
j
I do not see the trick to identify the edges (might be the time in the morning), so I'm gonna brute force it. (Will take some time)
m
My brute force is running but I don't know if it's going to finish in any good time, in the meantime I'm thinking about a better solution.
j
My input has 3345 edges, so it's gonna take a while
v
I've found a trick 🙂
just drew it 🙂
image.png
e
my graphviz layout wasn't so nicely separated but the bottleneck was still pretty easy to spot by eye. I had to go back into the input to figure out what the nodes were since they were overlapping and unreadable.
still thinking about how to code it… might come back to it after finishing up/cleaning up the past few days though
j
hm I have 5 lines crossing from one part into the other
m
same trick and generation as @ephemient it seems. Feels scummy to do again, but at least it gives me freedom to spent my christmas day however I want 😂
j
In mine I can not see which the edges are
out.svg
w
So what if you detect all the cycles using a dfs and count how many times each edge is part of a cycle. The minimum ones should be the ones to remove.
m
@Jonathan Kolberg use neato
I'd say: BFS on all startnodes and find the 3 points that averages the minimal distance to the startnode
j
@Michael de Kaste thanks for the tip
m
since you need to either pass edge1, edge2, or edge3 whenever you cross over to the other side, you see them earlier then the other points on average
just spitballing here
t
Finished without visualization 🙂 I used some heuristics for sorting the potential solutions and then the right ones were: • the ~200th potential solution on the test data • the first in the real data (so it was super fast) _Spoiler_: I looked at how deep connections are from a given component, and started with the components with the least depth (taking into account circularity - component is counted only once when resolving connections using BFS). Edit: I think it's kind of similar to what @Michael de Kaste just wrote (just approached from a different angle).
m
interestingly, my approach doesn't really rank the actual output favourably
🤔 1
v
this worked for me finally
Luckily I have python (and its networkx.minimum_cut()). Don't you know any similar library for graphs in Kotlin (/Java)?
also useful link
b
yea i woulda solved this problem much faster if i was using python
nteworkx library is great
for those using visual stuff, what is the easiest to use with kotlin?
m
I just use a graphviz library in kotlin https://github.com/RCHowell/Dotlin and then just use command line to graph it
e
I’ve just brute-forced all m^2 pairs of edges, checking if the resulting graph has a bridge in O(m) time, for a total of O(m^3). It works in a decent time (under a minute).
👍 1
w
Found the solution!: https://github.com/werner77/AdventOfCode/blob/master/src/main/kotlin/com/behindmedia/adventofcode/year2023/day25/Day25.kt The idea is that (just like in traffic) bridges are the most travelled edges in a graph. Just do a flood fill from every node and increment a global counter every time you traverse an edge. The three top most encountered edges will be your answer.
👍 3
m
Inspired by @Michael de Kaste's idea I pick randomly sampled nodes and find a path between them (simple DFS with node connections randomly chosen). I do this 1000 times and count the edge occurrences. The critical ones are top ranked although the margin is not too high. Just to be safe I disconnect the top-five connections (the two non-critical ones hopefully won't hurt). Again not pretty but I take it. https://github.com/fabmax/aoc-2023/blob/main/src/main/kotlin/day25/Day25.kt Also decently fast:
Copy code
Benchmark             Mode  Cnt    Score    Error  Units
Day25Benchmark.part1  avgt    5  140.037 ± 10.421  ms/op
b
@Max Thiele i did the same thing with only 500 repeats, the top 3 nodes were noticeably ahead of the others
m
With 500 repeats the critical ones are still on top but 3rd place is only 4 occurrences ahead of 4th (142 vs. 138, also depends on random seed obviously). Should still be safe since I'm disconnecting the top five
a
I wrote the least code among the few days 😂 With JGraphT it's as simple as
Copy code
// Create the graph
val clusters = GirvanNewmanClustering(graph, 2).clustering.clusters
println(clusters[0].size * clusters[1].size)
🆒 1
e
In my example the result is that it splits the graph in half (half rounded down in one part, rounder up in another). So you can compute it without much code at all. Is it so for everybody?
k
Used a BFS + brute-force approach that works in reasonable time (~480ms) https://github.com/kingsleyadio/adventofcode/blob/main/src/com/kingsleyadio/adventofcode/y2023/Day25.kt
t
My solution tries all edges as the first cut, then proceeds by searching for a path between the nodes we just separated. The second cut must be one of those edges on the path. Same for the third. So worst case same as brute force, but works well enough in practice
e
is it so for everybody?
no, mine cut into 706+717
same 1
m
Alright, as a final treat, I implemented my own version of the graph visualization approach and made one final visualization 😃 https://github.com/fabmax/aoc-2023/blob/main/src/main/kotlin/day25/Day25Kool.kt The approach would also work without visualization although it's probably not the most efficient one. I begin with random node positions and compute attraction forces for connected nodes and repelling forces for randomly chosen, unconnected nodes. Then update the node positions iteratively based on the forces and voila after a short time the two clusters separate.
day25.mp4
👍 2
e
https://github.com/ephemient/aoc2023/blob/main/kt/aoc2023-lib/src/commonMain/kotlin/com/github/ephemient/aoc2023/Day25.kt for my non-Python solutions, I did a BFS to build a tree from every node. the edge used most often in all the trees was then used as a candidate for removal. this seemed to work although I'm not 100% it's always correct.
p
A little late, but it's done. I used a BFS for each node to flood fill, took the three most used links, removed them and partitioned based on a flood fill from a random node. Not performant, but got me the stars.
🔥 4
advent of code intensifies 1
👏 1
p
18 Views
Open in Slack
PreviousNext
Powered by