#Day 8

1 messages · Page 1 of 1 (latest)

hidden prawn
#

Well that was a little difficult, but I got there eventually

# 
Ran 2025 day 8:
  Part 1: ✅ (in 764.884 ms)
  Part 2: ✅ (in 801.146 ms)

definitely my worst performing day so far

#

wondering if there's a smarter solution

remote island
#

I have 339.824ms ±₁₁.₆₈₂ 278.739ms ±₂.₂₇₇

#

That was rough

#

It will need a lot of cleaning up

hidden prawn
humble cosmos
#

This was painful xD. I'm very proud of this part for breaking out of all the folding

panic as {
  int.multiply(pair.0.0, pair.1.0)
  |> int.to_string
}
#

I'm happy you could get away with combination_pairs in this problem

hidden prawn
#

yeah if i couldnt i didnt know what i was gonna do

humble cosmos
#

I don't have any better idea up tbh

drowsy sigil
#

Didn’t had time to do it in gleam this morning

#

So it’s in ruby despair

#

Union Finder goes brbrbrbrbr

#

I love this kind of problems that acts as a reminder that such data structure exists

spiral mirage
#

Another case of not reading the problem properly for me today got me stuck for quite a while 🤦

After making the ten shortest connections

drowsy sigil
vocal basin
#

can someone help me understand what pb2 is asking ?

#

i really don't get it

hidden prawn
vocal basin
#

are they asking to just identify boxes that are in their own unconnected circuit leftover from pb1?

hidden prawn
vocal basin
#

so where before i wouldve had an allowance of 1000 connections, now there's no limit?

hidden prawn
#

Yeah

#

The ending condition is just when a connection results in there only being one circuit remaining

vocal basin
#

alright got it, thanks

#

I hear the winds whispering... list.fold_until...

hidden prawn
#

It's easier with a recursive function imo

distant pecan
drifting apex
# 
Ran 2025 day 8:
  Part 1: ✅ met expected value: 98696 (in 599.815 ms)
  Part 2: ✅ met expected value: 2245203960 (in 509.012 ms)

😬

#

but don't have any time to optimize today, so whatever

drifting apex
ionic oar
#

Pfff, just finding the shortest edges with

  let edges =
    list.combination_pairs(input)
    |> list.sort(fn(a, b) {
      let #(a1, a2) = a
      let #(b1, b2) = b
      float.compare(distance(a1, a2), distance(b1, b2))
    })

takes like 2.5 seconds on my machine. Is there anything I can do or should I just stick that in parse and pretend it doesn't exist?

hidden prawn
ionic oar
#

Ooohh

#

That's a fair point

hidden prawn
#

Apart from that all you can really do is slightly improve the iteration of those combinations with a recursive function instead of folds/etc

ionic oar
#

Comparing floats and sqrts:
Part 1: _ (in 2.666 s)
Part 2: _ (in 2.639 s)
Comparing squared distances:
Part 1: _ (in 765.692 ms)
Part 2: _ (in 939.669 ms)

#

That's a rather huge difference

hidden prawn
#

Yup

#

sqrt is slow

#

Both my parts take around 700ms as well

drifting apex
vocal basin
#

alright, finally we made it

vocal basin
#

why re-invent the wheel

spiral mirage
vocal basin
#

I wonder if others used the gleam_community_maths package

#

specifically euclidian_distance

ionic oar
#

It's not that I don't know how to compute euclidian distance in 3d, but doing the square root part made it take about five times longer. Better to just compare the squared distances.

vocal basin
#

ALSO

#

my lord and savior

#

set.is_disjoint

#

to merge circuits

#

a circuit is just a set of boxes. If two sets have at least one box in common (meaning set.is_disjoint returns False), they should be merged

#

from there I just convert each connection to a 2-boxes circuit and iterate through all known circuits to merge them

hidden prawn
#

that's a cool way to do it, i just did

let circuits = case
  list.partition(state.circuits, fn(c) {
    set.contains(c, connection.from) || set.contains(c, connection.to)
  })
{
  #([c], circuits) -> [c, ..circuits]
  #([c, d], circuits) -> [set.union(c, d), ..circuits]
  _ -> panic as "Expected to find one or two circuits"
}
vocal basin
#

mhm

#

i guess it's functionally the same

hidden prawn
#

with is_disjoint, wouldnt you have to go through all pairs of circuits to find which ones to merge?

vocal basin
#

no you only have to attempt to merge existing circuits with the new connection you're considering

#

so i mean, yeah you do have to iterate through all existing circuits i guess

#

if that's what you're asking

#

i'm confused by what you mean by "pairs of circuits"

#

because no

hidden prawn
#

wait do your circuits just contain the boxes, or do they contain connections?

vocal basin
#

boxes

#

only

hidden prawn
#

hm, same here

#

how do you know which circuits the two boxes in the connection you want to make come from?

vocal basin
#

I don't

#

so yes I do iterate through all circuits

#

for each new connection i want to add

hidden prawn
#

so you iterate through the circuits once to find a circuit containing one of the boxes in the connection you want to make, add the second box to that circuit, then iterate the circuits again with is_disjoint to find if there's a circuit that needs to merge with it?

vocal basin
#

ok hold on maybe it'll be simpler if i show you

hidden prawn
#

yea, that would help

vocal basin
# 

type JunctionBox {
  JunctionBox(x: Int, y: Int, z: Int)
}

type WeighedConnection {
  WeighedConnection(box1: JunctionBox, box2: JunctionBox, distance: Float)
}

type Circuit {
  Circuit(boxes: Set(JunctionBox))
}
pub fn pb2() -> Int {
  let junction_boxes = get_junction_boxes(filename)
  let limitless_connections =
    list.combination_pairs(junction_boxes)
    |> list.map(fn(boxes) {
      let #(box1, box2) = boxes
      compute_distance(box1, box2)
    })
    |> list.sort(fn(weighed_connection1, weighed_connection2) {
      float.compare(weighed_connection1.distance, weighed_connection2.distance)
    })
  let #(_all_circuits_should_just_be_one, _remaining_boxes, last_connection) =
    list.fold_until(
      limitless_connections,
      #(
        [],
        junction_boxes |> set.from_list,
        limitless_connections |> list.first |> should.be_ok,
      ),
      fn(acc, weighed_connection) {
        let #(current_circuits, remaining_boxes, _last_connection) = acc

        let new_remaining_boxes =
          set.difference(
            remaining_boxes,
            [weighed_connection.box1, weighed_connection.box2] |> set.from_list,
          )

        let new_circuits =
          merge_circuits_with_new_connection(
            current_circuits,
            weighed_connection,
          )

        let new_acc = #(new_circuits, new_remaining_boxes, weighed_connection)
        case new_circuits, set.size(new_remaining_boxes) {
          [_one], 0 -> list.Stop(new_acc)
          _, _ -> list.Continue(new_acc)
        }
      },
    )

  last_connection.box1.x * last_connection.box2.x
}
# 

fn connection_to_circuit(conn: WeighedConnection) -> Circuit {
  Circuit([conn.box1, conn.box2] |> set.from_list)
}

fn merge_circuits(circuit1: Circuit, circuit2: Circuit) -> Result(Circuit, Nil) {
  let c1_set = circuit1.boxes
  let c2_set = circuit2.boxes
  case set.is_disjoint(c1_set, c2_set) {
    False -> set.union(c1_set, c2_set) |> Circuit |> Ok
    True -> Error(Nil)
  }
}

fn merge_circuits_with_new_connection(
  circuits: List(Circuit),
  new_connection: WeighedConnection,
) -> List(Circuit) {
  let new_circuit = new_connection |> connection_to_circuit

  let #(new_circuit, existing_circuits) =
    list.fold(
      circuits,
      #(new_circuit, []),
      fn(acc, next_circuit_to_check_against) {
        let #(new_circuit, merged_circuits) = acc

        case merge_circuits(new_circuit, next_circuit_to_check_against) {
          Error(_) -> #(new_circuit, [
            next_circuit_to_check_against,
            ..merged_circuits
          ])
          Ok(new_new_circuit) -> #(new_new_circuit, merged_circuits)
        }
      },
    )

  [new_circuit, ..existing_circuits]
}

fn get_junction_boxes(filename: String) -> List(JunctionBox) {
  simplifile.read(filename)
  |> should.be_ok
  |> string.split("\n")
  |> list.map(line_to_junction_box)
}

fn line_to_junction_box(line: String) -> JunctionBox {
  let assert Ok([x, y, z]) =
    string.split(line, ",") |> list.map(int.parse) |> result.all
  JunctionBox(x, y, z)
}

fn compute_distance(box1: JunctionBox, box2: JunctionBox) -> WeighedConnection {
  let distance =
    maths.euclidean_distance([
      #(box1.x |> int.to_float, box2.x |> int.to_float),
      #(box1.y |> int.to_float, box2.y |> int.to_float),
      #(box1.z |> int.to_float, box2.z |> int.to_float),
    ])
    |> should.be_ok
  WeighedConnection(box1, box2, distance)
}
#

The core part is this:

let #(_all_circuits_should_just_be_one, _remaining_boxes, last_connection) =
    list.fold_until(
      limitless_connections,
      #(
        [],
        junction_boxes |> set.from_list,
        limitless_connections |> list.first |> should.be_ok,
      ),
      fn(acc, weighed_connection) {
        let #(current_circuits, remaining_boxes, _last_connection) = acc

        let new_remaining_boxes =
          set.difference(
            remaining_boxes,
            [weighed_connection.box1, weighed_connection.box2] |> set.from_list,
          )

        let new_circuits =
          merge_circuits_with_new_connection(
            current_circuits,
            weighed_connection,
          )

        let new_acc = #(new_circuits, new_remaining_boxes, weighed_connection)
        case new_circuits, set.size(new_remaining_boxes) {
          [_one], 0 -> list.Stop(new_acc)
          _, _ -> list.Continue(new_acc)
        }
      },
    )
#

Basically the secret sauce is in the merge_circuits_with_new_connection function

#

In the merge_circuits_with_new_connection:
Lets say I start with the circuits [{1, 2, 3}, {4, 5}] and my new connection is {3, 4}
I list.fold over the circuits with an #(Circuit, List(Circuit)) accumulator, so in our case #({3, 4}, []). acc.0 is the circuit resulting from merging the new connection with all connecting circuits we find, and acc.1 is the other circuits previously found that do not touch the new connection.
If the currently evaluated circuit touches the new connection, they get merged and become the new acc.0, and acc.1 remains unchanged. If not, acc.0 remains unchanged, and the currently evaluated circuit gets prepended to acc.1

#

So I end up with a #(new_circuit_after_merging_new_connection_with_old_circuits, other_circuits_that_didnt_get_merged)

#

i then combine the two into a new list of circuits

#

idk if my explanations make it clearer lol lucypensive

green pendant
#

anyone do union find disjoint set?

# 
// with warmup
Ran 2025 day 8:
  Part 1: _ (in 481.028 ms)
  Part 2: _ (in 542.833 ms)
#

There's some easy optimisation wins I can get, but I do have to study for an exam tomorrow lucypensive

vocal basin
green pendant
#

it would have been so easy to write out in C++, but it took me a while to figure out how to do it in Gleam

lunar notch
#

I really liked this one... I look forward to seeing how other people did it.

Part 1 (262 ms)
Part 2 (714 ms)
hidden prawn
lunar notch
#

Wow... it's faster as well

maiden aurora
# 
Ran 2025 day 8:
  Part 1: _ (in 1.392 s)
  Part 2: _ (in 1.930 s)

definitely not the best solutions lol

drowsy marsh
# 
nick@scooty-puff-jr$ time gleam run -m day8 inputs/day8/input.txt
   Compiled in 0.03s
    Running day8.main
Part 1: _
Part 2: _

________________________________________________________
Executed in   11.39 secs    fish           external
   usr time   10.36 secs  479.00 micros   10.36 secs
   sys time    1.61 secs  367.00 micros    1.61 secs

speed demon over here

#

I keep reading about DFUs, I'll have to try that after work

green pendant
#

what's a DFU?

drowsy marsh
#

errr

#

DSU

hidden prawn
#

I'm guessing it's not Device Firmware Update which is what I'm thinking of lol

drowsy marsh
#

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...

remote island
#

That's not the bottleneck in my solution despair

drowsy marsh
remote island
#

I want to make it 40x

#

Could you please make yours twice as slow? 🥺

drowsy marsh
#

so - yes

#

oh god, reddit is talking about kruskal's algorithm

#

I should have paid attention in discrete math

green pendant
remote island
#

It's about 300ms for each part

green pendant
#

including parsing?

remote island
#

Yeah, I'm not cheating

green pendant
#

hmph

remote island
#

I have a plan to make it a lot faster 😈

green pendant
#

yours is faster even if I "cheat" lmao

#

fastest i could get it was ~350-400 ms, each part

#

not seconds

remote island
green pendant
#

though I wonder how much machine capabilities factor into this

remote island
#

Yeah that's why I want to make it 10x fast

#

So there's no doubt it's actually faster eevee

green pendant
#

you have an apple silicon mac, yes?

remote island
#

Yeah! M2

green pendant
#

hmm... would be cool to see how fast my solution runs on your computer, and how much the machine affects speeds. no worries if you're busy or anything, really, just a thought

remote island
#

I'll make sure to try it!

green pendant
#

350ms was with warmup though, so without warmup, it was 500ms on my system (just for reference)

remote island
#

No I don't have any particular plans so I'm really happy to try that

#

Could you link your solution again?

green pendant
#

gleam run run 8 --timed (for gladvent)

remote island
# 
Part 1: 75582 (in 208.898 ms)
Part 2: 59039696 (in 333.215 ms)
green pendant
#

ooh

remote island
#

Part 1 is consistently faster than mine, part 2 is roughly the same

#

That's interesting

green pendant
#

interesting. definitely a big jump from my machine's times

#

thank you so much!

#

if I had made a proper ufds, it would have been faster. didn't have arrays and I didn't want to pull in iv, so I just used a dict instead, but even without iv, I could have first mapped each box to an index, and then used those indices in the parent dict

#

would probably have been ever so slightly faster for dict lookups and comparisons

humble cosmos
#

It is combination_pairs+ sort that is slow for me.. anyone figured out a better way to do that?

remote island
#

I'm trying

#

(And failing despair)

hidden prawn
lunar jolt
# 
Ran 2025 day 8:
  Part 1: --- (in 312.794 ms)
  Part 2: --- (in 462.280 ms)
#

there's a priority queue in gleamy_structures that helped speed up making the list of sorted pairs for me

hidden prawn
#

You also don't technically need to sort all the combinations since neither part uses all of the combinations, so you only need the lowest 1000 to be sorted for part 1, and like 20-50k sorted for part 2

lunar jolt
#

I think I kind of stumbled on the idea of disjoint set unions with my weird list of sets structure I used to keep track of things

ionic oar
#

Is the kd idea that you insert all nodes in (N log N) time and then whenever you want to find the shortest distance for any nodes, you do N*log(N) lookups?

lunar jolt
ionic oar
#

Finding the lowest K numbers in N total numbers is O(N log k) but since you'd be searching in the combination_pairs list that'd still be O(N^2) at least

hidden prawn
lunar jolt
#

yeah

#

the list remained relatively small for all of p1 so it wasn't too bad, at least

#

I'll take any solution under a second, honestly

hidden prawn
#

Just found this info. I'm not sure how exactly you quickly find that cutoff point, but assuming you can find it or at least approximate it, that's like an easy 100x speedup

Screenshot_20251209_032709_Firefox.jpg
#

In the solution I'm looking at it seems like they just hardcoded the cutoff in their solution, but that seems kinda cheaty cause you kinda need to run it without the cutoff first to know where to set the cutoff

drifting apex
#

yeah, but how do you even find that

lunar jolt
#

yeah I don't know how you'd apply that cutoff before actually finding it

#

it'd be dependent on the shape of the graph and you don't know that until you've examined it

#

the extreme version of saying you’ve got a fast solution if the parsing doesn’t count

hidden prawn
#

You can maybe random sample the points and estimate?

#

But again there's no guarantee the graph follows a uniform distribution

#

So there are inputs you could craft that it wouldn't work against

lunar jolt
#

999 points all clustered around the origin and the 1000th point a mile away would defeat that pretty consistently, depending on the sample size

stable mesa
#

holy hell

#

I did it

#

I completed today

#

legit thought I hit the wall today & would fail

humble cosmos
# hidden prawn I used a list of sets for the circuits too, but I think a dishoit set union is a... 
  State(
    used_pairs: [],
    lut: coordinates
      |> list.index_map(fn(coord, index) { #(coord, index) })
      |> dict.from_list,
    circuits: coordinates
      |> list.index_map(fn(coord, index) { #(index, set.from_list([coord])) })
      |> dict.from_list,
  )

I initialized my state like that, basically give each circuit an ID and then have another dict to lookup coordinate -> ID.

Then it just a matter of keeping track of it while merging the sets

fn connect(state: State, pair: #(Coord, Coord)) {
  case dict.get(state.lut, pair.0), dict.get(state.lut, pair.1) {
    Ok(a), Ok(b) if a == b ->
      State(..state, used_pairs: [pair, ..state.used_pairs])
    Ok(a), Ok(b) -> {
      let assert Ok(left) = dict.get(state.circuits, a)
      let assert Ok(right) = dict.get(state.circuits, b)

      State(
        lut: set.fold(right, state.lut, fn(lut, coord) {
          dict.insert(lut, coord, a)
        }),
        circuits: state.circuits
          |> dict.delete(b)
          |> dict.insert(a, set.union(left, right)),
        used_pairs: [pair, ..state.used_pairs],
      )
    }
    _, _ -> panic
  }
}
hidden prawn
#

Huh, that's a good idea

#

If you had access to raw pointers you could skip the IDs and just have the lut values directly point to the correct set

humble cosmos
#

half of the fun is to figure out how to do it FP-style

vocal basin
lunar jolt
#

yeah, tried implementing that instead of just mashing list items together and it cut the time down by about half

#

at this point I think making the pairs of points is the bottleneck and there's not much more to do there

#

got it under half a second on my WSL VM so I'll take it

maiden aurora
#

found a few things that got me a decent boost

Ran 2025 day 8:
  Part 1: _ (in 819.712 ms)
  Part 2: _ (in 1.263 s)
remote island
#

And the implementation is so nice using disjoint sets, so much better

green pendant
#

i just realised i could easily speed up part 2 if I kept a count of how many circuits there were and didn't count them each time

#

that's just what I did at the time in a rush

remote island
#

My part 2 is this

fn part_2_loop(
  pairs: List(#(Box, Box, Int)),
  groups: DisjointSet(Box),
) -> Result(DisjointSet(Box), Int) {
  case pairs {
    [] -> Ok(groups)
    [#(one, other, _), ..rest] -> {
      let groups = disjoint_set.merge(groups, one, other)
      case disjoint_set.set_size(groups, one) {
        Error(_) -> panic as "unreachable"
        Ok(#(1000, _)) -> Error(one.x * other.x)
        Ok(#(_, set)) -> part_2_loop(rest, set)
      }
    }
  }
}
#

I check if the size has become 1000 after joining them

green pendant
#

nice!

#

that's a very good way to do it

#

extracting dsu into its own module is a good idea as well

#

much cleaner

spiral mirage
#

What’s the Disjoint Set interface?

safe mason
#

Wow I REALLY misread the task

# 
  Part 1: _ (in 661.920 ms)
  Part 2: _ (in 580.338 ms)```
#

I have no idea what a disjoint set or that algorithm that people are using on reddit are but this seems like an ok solution

lunar notch
#

Everyone was talking about that Disjoint Set data structure, I had to try it myself.

Part 1 (243 ms): ...
Part 2 (223 ms): ...
drowsy marsh
#

...yeah ok now I see why everyone was using one

pocket_watch [part1]: took 3.3ms
pocket_watch [part2]: took 333.5ms
drowsy marsh
#

I did have to make a couple adjustments for mine to be solved but

floral sigil
#

I was amused by the fact that I thought it was a MST problem so I dusted off my old algorithms book and the first thing I see is this. 😅 Coincidence? I think not!

IMG_5004.jpg
drowsy marsh
#

part 2 can be solved as one!