122 lines
3.1 KiB
Odin
122 lines
3.1 KiB
Odin
package main
|
|
|
|
import "core:fmt"
|
|
import "core:math"
|
|
import "core:slice"
|
|
import "core:strconv"
|
|
import "core:strings"
|
|
import "core:time"
|
|
|
|
Vec3 :: [3]int
|
|
Edge :: struct {
|
|
a, b: Vec3,
|
|
dist: f64,
|
|
}
|
|
|
|
distance :: proc(a, b: Vec3) -> f64 {
|
|
dx, dy, dz := f64(b.x - a.x), f64(b.y - a.y), f64(b.z - a.z)
|
|
return math.sqrt(dx * dx + dy * dy + dz * dz)
|
|
}
|
|
|
|
find_circuit :: proc(circuits: ^[dynamic][dynamic]Vec3, pos: Vec3) -> int {
|
|
for circuit, idx in circuits {
|
|
if slice.contains(circuit[:], pos) do return idx
|
|
}
|
|
return -1
|
|
}
|
|
|
|
same_circuit :: proc(circuits: ^[dynamic][dynamic]Vec3, a, b: Vec3) -> bool {
|
|
return find_circuit(circuits, a) == find_circuit(circuits, b)
|
|
}
|
|
|
|
parse :: proc(line: string) -> Vec3 {
|
|
parts := strings.split(line, ",")
|
|
x, _ := strconv.parse_int(parts[0])
|
|
y, _ := strconv.parse_int(parts[1])
|
|
z, _ := strconv.parse_int(parts[2])
|
|
return Vec3{x, y, z}
|
|
}
|
|
|
|
make_edges :: proc(positions: []Vec3) -> [dynamic]Edge {
|
|
edges := make([dynamic]Edge)
|
|
for i in 0 ..< len(positions) {
|
|
for j in i + 1 ..< len(positions) {
|
|
append(&edges, Edge{positions[i], positions[j], distance(positions[i], positions[j])})
|
|
}
|
|
}
|
|
slice.sort_by(edges[:], proc(e1, e2: Edge) -> bool {return e1.dist < e2.dist})
|
|
return edges
|
|
}
|
|
|
|
merge_circuits :: proc(circuits: ^[dynamic][dynamic]Vec3, a, b: Vec3) {
|
|
idx_a := find_circuit(circuits, a)
|
|
idx_b := find_circuit(circuits, b)
|
|
append(&circuits[idx_a], ..circuits[idx_b][:])
|
|
ordered_remove(circuits, idx_b)
|
|
}
|
|
|
|
part_1 :: proc(lines: []string) {
|
|
positions := slice.mapper(lines, parse)
|
|
circuits := make([dynamic][dynamic]Vec3)
|
|
for pos in positions {
|
|
c := make([dynamic]Vec3)
|
|
append(&c, pos)
|
|
append(&circuits, c)
|
|
}
|
|
edges := make_edges(positions)
|
|
|
|
for edge, idx in edges {
|
|
if idx >= 1000 do break
|
|
if same_circuit(&circuits, edge.a, edge.b) do continue
|
|
merge_circuits(&circuits, edge.a, edge.b)
|
|
}
|
|
|
|
sizes := slice.mapper(circuits[:], proc(c: [dynamic]Vec3) -> int {return len(c)})
|
|
slice.reverse_sort(sizes)
|
|
result := slice.reduce(sizes[:3], 1, proc(acc, x: int) -> int {return acc * x})
|
|
fmt.printfln(" [Result] %v", result)
|
|
}
|
|
|
|
part_2 :: proc(lines: []string) {
|
|
result := 0
|
|
|
|
positions := slice.mapper(lines, parse)
|
|
circuits := make([dynamic][dynamic]Vec3)
|
|
for pos in positions {
|
|
c := make([dynamic]Vec3)
|
|
append(&c, pos)
|
|
append(&circuits, c)
|
|
}
|
|
edges := make_edges(positions)
|
|
|
|
for edge in edges {
|
|
if same_circuit(&circuits, edge.a, edge.b) do continue
|
|
if len(circuits) == 2 {
|
|
result = edge.a.x * edge.b.x
|
|
break
|
|
}
|
|
merge_circuits(&circuits, edge.a, edge.b)
|
|
}
|
|
|
|
fmt.printfln(" [Result] %v", result)
|
|
}
|
|
|
|
main :: proc() {
|
|
context.allocator = context.temp_allocator
|
|
defer free_all(context.temp_allocator)
|
|
|
|
INPUT :: #load("input.txt", string)
|
|
lines := strings.split_lines(strings.trim_space(INPUT))
|
|
|
|
fmt.println("[Part 1]")
|
|
start := time.tick_now()
|
|
part_1(lines)
|
|
duration := time.tick_diff(start, time.tick_now())
|
|
fmt.printfln(" [Time] %vms\n", time.duration_milliseconds(duration))
|
|
|
|
fmt.printfln("[Part 2]")
|
|
start = time.tick_now()
|
|
part_2(lines)
|
|
duration = time.tick_diff(start, time.tick_now())
|
|
fmt.printfln(" [Time] %vms", time.duration_milliseconds(duration))
|
|
}
|