#Day 08 Solutions

94 messages · Page 1 of 1 (latest)

pure glade
#

A Milking

whole rune
#

a milking

#

damn

pure glade
#

This feels more like advent of code now

#

I probably did a bunch of unnecessary stuff

weak rampart
#

naive and slow

#

you're not supposed to commit your inputs btw

#

cc @pure glade

pure glade
#

Hmm why?

weak rampart
#

Can I copy/redistribute part of Advent of Code? Please don't. Advent of Code is free to use, not free to copy. If you're posting a code repository somewhere, please don't include parts of Advent of Code like the puzzle text or your inputs. If you're making a website, please don't make it look like Advent of Code or name it something similar

#

because erik asks nicely 🙂

pure glade
#

Oh :( But then my tests won't work hmmm
Let me think how to do this

weak rampart
#

how does your find and union work?

#

ah, https://en.wikipedia.org/wiki/Disjoint-set_data_structure

Disjoint-set data structure

In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that stores a collection of disjoint (non-overlapping) sets. Equivalently, it stores a partition of a set into disjoint subsets. It provides operations for adding new sets, merging sets (replacing them with their...

#

TIL

pure glade
#

Yeah this

#

Basically map where the key is the element and the value is the root of the element

weak rampart
#

I sm0l brain just created a graph for each edge that I added xD

pure glade
#

union find is really helpful for some problems, Ill add it as helper with some more useful functions on it

weak rampart
#

new edge? Better try finding a cluster again. Cluster != len(coords)? Add edge

#

not very efficient xD

#

Just fast enough for this input size

whole rune
#

damn that was yucky

#

both of my parts too like 10 seconds to run but idrk how to optimize them in ex

whole rune
#

damnnnn i'm so dumb why did I think i would have to generate 1000! pairs

#

this is just handshake problem

pure glade
whole rune
# pure glade What's that

if u have x ppl in a room and they all shake hands with each other how many handshakes will happen in total. and the answer is the sum from 1 to x-1 aka (x*x-1)/2

worn gulch
#

part2 is simpler than part1

#

with all the printing
Part 2: Result: 136 624 [17194 12279 10275] [6238 3377 1071] 107256172

real 0m1.465s
user 0m0.578s
sys 0m0.118s

#

commenting out the intermediate printing

#

real 0m0.104s
user 0m0.099s
sys 0m0.005s

whole rune
worn gulch
#

grol version is about 1/2 into generating distances

#

Point 510 done.

#

later will use pprof on these

#

lol

Part 2: Result: 136 624 [17194,12279,10275] [6238,3377,1071] 107256172
10:57:27.584 [INF] All done - retcode: 0

real    15m13.313s
user    14m40.921s
sys     0m6.037s

slightly slower than go - but easier to write, including that it sorts by distance and points automatically

whole rune
#

damnnnnnnnn just redid this by pregenerating the pairs and this is so much faster

onyx wedge
# 
day 8 bench             time:   [14.200 ms 14.350 ms 14.527 ms]
#

part 1 + part 2 but my part 1 is slower

#

oh nvm

#

part 2 is nasty

#

took me 13ms

#

wait

#

nah its alright let me profiel this tho

#

clap my cheeks spending an hour to do disjoint set union on smallest edges
78% of time is spent on building the heap

image.png
whole rune
worn gulch
#

SortFunc in go right?

onyx wedge
#

isnt sort a full one though?

whole rune
whole rune
onyx wedge
#

n.log(n)

#

quicksort or whatever

#

the conceit of this problem is you only need to pull a small number of all the edges

#

so you want a heap

#

unless youre doing fuckass computer graphics algos which idk

whole rune
#

i don't think that's the overall trick. the overall trick is just realizing that it's a (doably) finite number of pairs so u can precompute distances then sort then merge til u have one left. the heap is just one way of sorting the distances

worn gulch
#

n(n-1)/2 pairs

whole rune
#

NOT 1000! as my smart ass friend blake pointed out to me

worn gulch
#

ie loop for i 0 to < len-1; then from i+1 to < len

onyx wedge
#

ya you need to precompute all the distances

#

but u could still use a heap to pull the shortest ones

#

its definitely huge for part 1

#

idk about part 2 tbh, i just assumed youll be iterating over a small sample of the edges to get the MST

worn gulch
#

given in part 2 you have to do the whole thing, not sure what "small number of all the edges" does

#

but yeah topK if there was only part1

#

or if brute force sorting wasn't plenty fast enough for 500k entries

whole rune
worn gulch
#

I guess maybe part2 can be instant as in finding max distance?

onyx wedge
#

no?

worn gulch
#

ah no because max can be close to another in the set

whole rune
#

yeah i think u just gotta keep merging but it's fast

worn gulch
#

maybe some sort of bounding box though

#

btw I wonder if they actually setup the data such as if you don't use euclidian distance you get screwed (eg if you use say sum(abs(Ai-Bi)))

whole rune
onyx wedge
#

do i not know how to read perf files or is my recording broken

#

anyway

onyx wedge
#

oh yeah

#

i managed to do p1 without "merging" subgraphs

#

i built a graph with all the edges first, then iterated over that to create a forest

#

also

#

you can see that i spend 10x as long in building the heap as popping from it

image.png
#

heap building is O(n), pops are log(n) each, so clearly we're using a very tiny amount of the possible edges

#

(this should be pretty obvious, there are ~N^2 edges and the MST will have ~N edges)

whole rune
#

this is pissing me off

image.png image.png
onyx wedge
#

man the lore with this problem goes deep