Day 8: Playground

use aoc_2025::timed_run;
use std::cmp::Ordering;
use std::cmp::Reverse;
use std::collections::BinaryHeap;
use std::io;
use std::vec::Vec;

struct Point {
  x: u64,
  y: u64,
  z: u64,
}

impl Point {
  fn distance_to(&self, other: &Self) -> u64 {
    (self.x - other.x).pow(2) + (self.y - other.y).pow(2) + (self.z - other.z).pow(2)
  }
}

struct Input {
  points: Vec<Point>,
}

impl Input {
  fn read_from_stdin() -> Input {
    Input {
      points: io::stdin()
        .lines()
        .map(|l| {
          l.unwrap()
            .split(',')
            .map(|n| n.parse::<u64>().unwrap())
            .collect::<Vec<_>>()
        })
        .map(|ns| {
          assert_eq!(ns.len(), 3);
          Point {
            x: ns[0],
            y: ns[1],
            z: ns[2],
          }
        })
        .collect(),
    }
  }
}

struct PointPair {
  p1: usize,
  p2: usize,
  d: u64,
}

impl PartialEq for PointPair {
  fn eq(&self, other: &Self) -> bool {
    self.d.eq(&other.d)
  }
}

impl Eq for PointPair {}

impl PartialOrd for PointPair {
  fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
    self.d.partial_cmp(&other.d)
  }
}

impl Ord for PointPair {
  fn cmp(&self, other: &Self) -> Ordering {
    self.d.cmp(&other.d)
  }
}

impl PointPair {
  fn clone(&self) -> Self {
    Self {
      p1: self.p1,
      p2: self.p2,
      d: self.d,
    }
  }
}

struct DsuElement {
  parent: usize,
  size: usize,
}

struct DSU {
  map: Vec<DsuElement>,
}

impl DSU {
  fn new(size: usize) -> DSU {
    let mut map = vec![];
    map.reserve(size);
    for i in 0..size {
      map.push(DsuElement { parent: i, size: 1 })
    }
    DSU { map }
  }

  fn find(&mut self, i: usize) -> usize {
    let mut root = self.map[i].parent;
    if root != i {
      root = self.find(root);
      self.map[i].parent = root;
    }
    root
  }

  // Returns the new root
  fn join(&mut self, i: usize, j: usize) -> usize {
    let mut root_i = self.find(i);
    let mut root_j = self.find(j);
    if root_i != root_j {
      if self.map[root_i].size < self.map[root_j].size {
        (root_i, root_j) = (root_j, root_i);
      }
      self.map[root_j].parent = root_i;
      self.map[root_i].size += self.map[root_j].size;
    }
    root_i
  }
}

fn part1(input: &Input) -> u64 {
  let mut smallest_pairs = BinaryHeap::new();
  for i in 0..input.points.len() {
    for j in i + 1..input.points.len() {
      let d = input.points[i].distance_to(&input.points[j]);
      smallest_pairs.push(PointPair { p1: i, p2: j, d });
      if smallest_pairs.len() > 1000 {
        smallest_pairs.pop();
      }
    }
  }
  let mut sets = DSU::new(input.points.len());
  for pair in smallest_pairs {
    sets.join(pair.p1, pair.p2);
  }
  let mut largest_circuits = BinaryHeap::new();
  for i in 0..input.points.len() {
    let e = &sets.map[i];
    if e.parent == i {
      largest_circuits.push((Reverse(e.size), e.parent));
      if largest_circuits.len() > 3 {
        largest_circuits.pop();
      }
    }
  }
  let mut ret = 1;
  for (Reverse(size), _) in largest_circuits {
    ret *= size;
  }
  ret as u64
}

fn all_pairs(input: &Input) -> Vec<PointPair> {
  let mut pairs = vec![];
  pairs.reserve(input.points.len().pow(2));
  for i in 0..input.points.len() {
    for j in i + 1..input.points.len() {
      let d = input.points[i].distance_to(&input.points[j]);
      pairs.push(PointPair { p1: i, p2: j, d });
    }
  }
  pairs
}

fn part1_select(input: &Input) -> u64 {
  let mut pairs = all_pairs(input);
  let (smallest_pairs, _, _) = pairs.select_nth_unstable(1000);
  let mut sets = DSU::new(input.points.len());
  for pair in smallest_pairs {
    sets.join(pair.p1, pair.p2);
  }
  let mut circuits = vec![];
  circuits.reserve(input.points.len());
  for i in 0..input.points.len() {
    let e = &sets.map[i];
    if e.parent == i {
      circuits.push((Reverse(e.size), e.parent));
    }
  }
  let (largest_circuits, _, _) = circuits.select_nth_unstable(3);
  let mut ret = 1;
  for (Reverse(size), _) in largest_circuits {
    ret *= *size;
  }
  ret as u64
}

fn part2(input: &Input) -> u64 {
  let mut pairs = all_pairs(input);
  pairs.sort();
  let mut sets = DSU::new(input.points.len());
  for pair in pairs {
    let root = sets.join(pair.p1, pair.p2);
    if sets.map[root].size == input.points.len() {
      return input.points[pair.p1].x * input.points[pair.p2].x;
    }
  }
  panic!("unreachable");
}

// Sorts the given slice in-place and calls f on the sorted elements as we go. Early stops if f
// returns false, in which case, only the elements seen by f are guaranteed to be sorted.
fn iterate_sorted<F: FnMut(&PointPair) -> bool>(pairs: &mut [PointPair], f: &mut F) -> bool {
  if pairs.len() <= 32 {
    pairs.sort();
    for p in pairs {
      if !f(p) {
        return false;
      }
    }
    return true;
  } else {
    let pivot = pairs[0].clone();
    let mut i = 1;
    let mut large_idx = pairs.len() - 1;
    while i < large_idx {
      if pairs[i] < pivot {
        i += 1;
      } else {
        pairs.swap(i, large_idx);
        large_idx -= 1;
      }
    }
    if pairs[i] < pivot {
      pairs.swap(0, i);
    }
    iterate_sorted(&mut pairs[..i], f) && iterate_sorted(&mut pairs[i..], f)
  }
}

fn part2_iterate_sorted(input: &Input) -> u64 {
  let mut ret = 0;
  let mut sets = DSU::new(input.points.len());
  iterate_sorted(&mut all_pairs(input), &mut |pair: &PointPair| {
    let root = sets.join(pair.p1, pair.p2);
    if sets.map[root].size == input.points.len() {
      ret = input.points[pair.p1].x * input.points[pair.p2].x;
      return false;
    }
    true
  });
  ret
}

fn main() {
  let input = Input::read_from_stdin();
  timed_run("Part 1", || part1(&input));
  timed_run("Part 1 select", || part1_select(&input));
  timed_run("Part 2", || part2(&input));
  timed_run("Part 2 iterate sorted", || part2_iterate_sorted(&input));
}

JunctionBox = namedtuple("JunctionBox", ["x", "y", "z"])
Circuit: TypeAlias = frozenset[JunctionBox]


def solve(input: str) -> int:
    circuits = connected_circuits(input, connection_count=1000)
    return prod(sorted(map(len, circuits), reverse=True)[:3])


def connected_circuits(input: str, connection_count: int) -> Iterator[Circuit]:
    circuits = {jb: Circuit([jb]) for jb in junction_boxes(input)}
    shortest_combinations = sorted(combinations(circuits.keys(), r=2), key=distance)

    for a, b in shortest_combinations[:connection_count]:
        for c in (connected_circuit := circuits[a] | circuits[b]):
            circuits[c] = connected_circuit

    yield from set(circuits.values())


def junction_boxes(input: str) -> Iterator[JunctionBox]:
    for line in input.split():
        yield JunctionBox(*map(int, line.split(",")))


def distance(a_b: tuple[JunctionBox, JunctionBox]) -> float:
    a, b = a_b
    return hypot(a.x - b.x, a.y - b.y, a.z - b.z)

def solve(input: str) -> int:
    a, b = last_connection(input)
    return a.x * b.x


def last_connection(input: str) -> tuple[JunctionBox, JunctionBox]:
    circuits = {jb: Circuit([jb]) for jb in junction_boxes(input)}
    shortest_combinations = sorted(combinations(circuits.keys(), r=2), key=distance)

    for a, b in shortest_combinations:
        if a in circuits[b]:
            continue

        for c in (connected_circuit := circuits[a] | circuits[b]):
            circuits[c] = connected_circuit

        last_connection_ = a, b

    return last_connection_


def junction_boxes(input: str) -> Iterator[JunctionBox]:
    for line in input.split():
        yield JunctionBox(*map(int, line.split(",")))


def distance(a_b: tuple[JunctionBox, JunctionBox]) -> float:
    a, b = a_b
    return hypot(a.x - b.x, a.y - b.y, a.z - b.z)

import (Heap) "modules/heap"

var boxes = File.read_to_string("inputs/day_08.txt").split("\n").map(|line|
    line.split(",").map(String.parse_i).map(Option.unwrap)
)

var max_index = boxes.size() - 1
var tuples: Heap[Tuple[Integer, Integer, Integer]] = Heap(|a, b| a[2] < b[2])

for i in 0...max_index: {
    for j in i + 1...max_index: {
        var box_1 = boxes[i]
        var box_2 = boxes[j]

        var delta_x = box_2[0] - box_1[0]
        var delta_y = box_2[1] - box_1[1]
        var delta_z = box_2[2] - box_1[2]

        tuples.push(<[i, j, (
            delta_x * delta_x + delta_y * delta_y + delta_z * delta_z
        )]>)
    }
}

var circuits = List.fill(boxes.size(), (|index| [index => unit]))

var circuit_indices: Hash[Integer, Integer] = []
for i in 0...max_index: {
    circuit_indices[i] = i
}

var connections = 0
while tuples.size(): {
    var tuple = tuples.pop()
    var index_1 = circuit_indices[tuple[0]]
    var index_2 = circuit_indices[tuple[1]]

    if index_1 != index_2: {
        var circuit = circuits[index_1]
        circuits[index_2].keys().each(|key|
            circuit[key] = unit
            circuit_indices[key] = index_1
        )

        circuits.delete_at(index_2)
        circuit_indices.each_pair(|key, index|
            if index > index_2: {
                circuit_indices[key] -= 1
            }
        )
    }

    connections += 1
    if connections == 1000: {
        print("Part 1: {}".format(circuits
            .sort(|a, b| b.size() - a.size())
            .slice(0, 3)
            .fold(1, (|product, circuit| product * circuit.size()))
        ))
    }

    if circuits.size() == 1: {
        print("Part 2: {}".format(boxes[tuple[0]][0] * boxes[tuple[1]][0]))
        break
    }
}

# order_test should return whether the first value should be given higher
# priority than the second value. It determines whether the heap is a min or max
# heap. Operators aren't functions in Lily, and we can't fully qualify generic
# types, so unfortunately the function has to be defined manually even for
# primitive types supporting the < and > operators.
class Heap[A](private var @order_test: Function(A, A => Boolean)) {
    private var @values: List[A] = []

    public define size: Integer {
        return @values.size()
    }

    public define push(value: A): self {
        @values.push(value)

        var current_index = @values.size() - 1
        while current_index > 0: {
            var parent_index = (current_index - 1) / 2

            var current_value = @values[current_index]
            var parent_value = @values[parent_index]

            if @order_test(parent_value, current_value): {
                break
            }

            @values[current_index] = parent_value
            @values[parent_index] = current_value

            current_index = parent_index
        }

        return self
    }

    public define pop: A {
        var size = @values.size()

        if size == 0: {
            raise RuntimeError("Cannot pop from an empty heap.")
        }

        if size == 1: {
            return @values.pop()
        }

        var root_value = @values[0]
        @values[0] = @values.pop()
        size -= 1

        var current_index = 0
        do: {
            var left_index = current_index * 2 + 1
            var right_index = left_index + 1

            var has_left = left_index < size
            var has_right = right_index < size

            if !has_left && !has_right: {
                break
            }

            var child_index = (has_left ? (has_right ? (
                @order_test(@values[left_index], @values[right_index])
                ? left_index
                : right_index
            ) : left_index) : right_index)

            var current_value = @values[current_index]
            var child_value = @values[child_index]

            if @order_test(current_value, child_value): {
                break
            }

            @values[current_index] = child_value
            @values[child_index] = current_value

            current_index = child_index
        } while true

        return root_value
    }
}

import math

def get_distance(x1:int, y1:int, z1:int, x2:int, y2:int, z2:int) -> int:
  return math.sqrt((x2-x1)**2 + (y2-y1)**2 + (z2-z1)**2)

def get_ordered_connections(lines):# -> dict_keys:
  positions = [tuple(map(int, l.split(','))) for l in lines]
  distances = {}
  for i, p1 in enumerate(positions):
    for j, p2 in enumerate(positions[i+1:]):
      distances[(i,j+i+1)] = get_distance(*p1, *p2)
  return dict(sorted(distances.items(), key=lambda x: x[1])).keys()

def find_circuits(circuits: list[set], connections:list[set]) -> list[set]:
  for conn in connections:
    add_connection(circuits, conn)

  while connections != circuits:
    return find_circuits([], circuits)
  return circuits

def add_connection(circuits:list[set], connection:set) -> list[set]:
  set = next((c for c in circuits if not connection.isdisjoint(c)), None)
  if set:
    set.update(connection)
  else:
    circuits.append(connection)
  return circuits


def part_one(connections) -> int:
  # 10 for test data, 1000 otherwise
  sets = [set(key) for key in list(connections)[:10]]
  circuits = find_circuits([], sets)
  circuits.sort(key=len, reverse=True)
  return math.prod([len(c) for c in circuits[:3]])

def part_two(connections, lines) -> int:  
  sets = [set(key) for key in list(connections)]
  circuits = []
  for s in sets:
    find_circuits(circuits, [s])
    if len(circuits[0]) == len(lines):
      return int(lines[s.pop()].split(',')[0]) * int(lines[s.pop()].split(',')[0])
  return 0

with open('08.in') as file:
  lines = [line.rstrip() for line in file]

connections = get_ordered_connections(lines)
print('Part 1:', part_one(connections))
print('Part 2:', part_two(connections, lines))

  ### PARSING ###

  def parse() do
    parse(AocElixir.read_lines(8))
  end

  def line_to_point(line) do
    [x, y, z] = String.split(line, ",") |> Enum.map(&String.to_integer/1)
    {x, y, z}
  end

  def parse(lines) do
    lines |> Enum.map(&line_to_point/1)
  end

  ### PART ONE ###
  def part1(junctions, num_connections \\ 1000) do
    shortest_distances = shortest_distances(junctions)

    connections = Enum.take(shortest_distances, num_connections)

    circuits = make_circuits(connections)

    circuits
    |> Enum.map(&Enum.count/1)
    |> Enum.sort()
    |> Enum.take(-3)
    |> Enum.product()
  end

  def find_remove(enum, condition, results \\ {nil, []})

  def find_remove([], _, {element, list}), do: {element, list}

  def find_remove([head | tail], condition, {element, list}) do
    if condition.(head) do
      find_remove(tail, condition, {head, list})
    else
      find_remove(tail, condition, {element, [head | list]})
    end
  end

  def connect_to_circuits(connection, circuits) do
    {left, right} = connection

    {existing_circuit_left, circuits} = find_remove(circuits, &Enum.member?(&1, left))
    {existing_circuit_right, circuits} = find_remove(circuits, &Enum.member?(&1, right))

    case {existing_circuit_left, existing_circuit_right} do
      {nil, nil} ->
        [[left, right] | circuits]

      {_, nil} ->
        [Enum.uniq([right | existing_circuit_left]) | circuits]

      {nil, _} ->
        [Enum.uniq([left | existing_circuit_right]) | circuits]

      {_, _} ->
        [Enum.uniq(existing_circuit_left ++ existing_circuit_right) | circuits]
    end
  end

  def make_circuits(connections) do
    Enum.reduce(connections, [], &connect_to_circuits/2)
  end

  def distance({point_a, point_b}), do: distance(point_a, point_b)

  def distance({x1, y1, z1}, {x2, y2, z2}) do
    ((x1 - x2) ** 2 + (y1 - y2) ** 2 + (z1 - z2) ** 2) ** 0.5
  end

  def pairs(anys, results \\ [])
  def pairs([], results), do: results

  def pairs([head | tail], results) do
    ps = for el <- tail, do: {head, el}
    pairs(tail, ps ++ results)
  end

  def shortest_distances(points) do
    points |> pairs() |> Enum.sort_by(&distance/1)
  end

  ### PART 2 ###
  def part2(junctions) do
    shortest_distances = shortest_distances(junctions)
    num_junctions = Enum.count(junctions)

    last_connection =
      Enum.reduce_while(shortest_distances, [], fn connection, circuits ->
        new_circuits = connect_to_circuits(connection, circuits)

        if Enum.empty?(tl(new_circuits)) and Enum.count(hd(new_circuits)) === num_junctions do
          {:halt, connection}
        else
          {:cont, new_circuits}
        end
      end)

    {{x1, _y1, _z1}, {x2, _y2, _z2}} = last_connection
    x1 * x2
  end

It's... not very quick. But adequate.
The kinds of things some of y'all are cooking up to my amazement just demonstrate
how little time I spent on classical algorithms and data structures in my day job.

Name               ips        average  deviation         median         99th %
parse          2715.45      0.00037 s    ±13.12%      0.00035 s      0.00060 s
part one          3.06         0.33 s    ±12.98%         0.32 s         0.41 s
part two          0.80         1.25 s     ±2.45%         1.26 s         1.29 s

:- ['src/util.pl'].
:- initialization(main).
:- use_module(library(record)).
:- use_module(library(union_find)).

:- record point(x:integer=0, y:integer=0, z:integer=0).

main:-
    phrase_from_file(input(Points), 'inputs/day08.txt'), Merges = 1000,

    findall((D, P1, P2), point_pair(Points, P1, P2, D), PointPairs),
    sort(PointPairs, PointPairs1),
    maplist([(_, P1, P2), R]>>(nth1(I, Points, P1), nth1(J, Points, P2), R = (I, J)), PointPairs1, PointPairs2),

    solve_1(Points, PointPairs2, Merges, Result1),
    write("Part 1: "), write(Result1), nl,
    solve_2(Points, PointPairs2, Result2),
    write("Part 2: "), write(Result2), nl,

    halt.

solve_1(Points, PointPairs, Merges, Result):-
    take(Merges, PointPairs, PointPairs1),
    length(Points, N),
    union_find(UF, N),
    maplist([(P1, P2)]>>(union(UF, P1, P2)), PointPairs1),
    disjoint_sets(UF, DS),
    maplist(length, DS, Lengths),
    sort(Lengths, Lengths1),
    reverse(Lengths1, Lengths2),
    take(3, Lengths2, ToMult),
    prod_list(ToMult, Result).

solve_2(Points, PointPairs, Result):-
    length(Points, N),
    union_find(UF, N),
    solve_2_rec(UF, PointPairs, (A, B)),
    nth1(A, Points, P1),
    nth1(B, Points, P2),
    point_x(P1, X1),
    point_x(P2, X2),
    Result is X1 * X2.

solve_2_rec(UF, [(P1, P2)|_], LastPair):-
    disjoint_sets(UF, DS),
    length(DS, L),
    L == 2,
    find(UF, P1, R1),
    find(UF, P2, R2), 
    R1 =\= R2,
    LastPair = (P1, P2).
solve_2_rec(UF, [(P1, P2)|Pairs], LastPair):-
    union(UF, P1, P2),
    solve_2_rec(UF, Pairs, LastPair).

point_pair(Points, P1, P2, Distance):-
    member(P1, Points), member(P2, Points),
    distance_sq(P1, P2, Distance),
    Distance =\= 0,
    point_x(P1, X1), point_y(P1, Y1), point_z(P1, Z1),
    point_x(P2, X2), point_y(P2, Y2), point_z(P2, Z2),
    (X1 > X2 ; (X1 == X2, Y1 > Y2) ; (X1 == X2, Y1 == Y2, Z1 > Z2)).

distance_sq(Point1, Point2, Distance):-
    point_x(Point1, X1), point_y(Point1, Y1), point_z(Point1, Z1),
    point_x(Point2, X2), point_y(Point2, Y2), point_z(Point2, Z2),
    Distance is (X1 - X2)^2 + (Y1 - Y2)^2 + (Z1 - Z2)^2.

input([Point|Rest]) -->
    point_dcg(Point),
    "\n",
    input(Rest).
input([Point]) --> point_dcg(Point).

point_dcg(Point) --> 
    number_dcg(X),
    ",",
    number_dcg(Y),
    ",",
    number_dcg(Z),
    { make_point([x(X), y(Y), z(Z)], Point) }.