1
require 'set'
2
3
def dist(a, b)
4
((b[0] - a[0]).abs ** 2.0 +
5
(b[1] - a[1]).abs ** 2.0 +
6
(b[2] - a[2]).abs ** 2.0) ** (1.0 / 2.0)
7
end
8
9
lines = File.readlines('8.input')
10
# lines = DATA.readlines
11
12
boxes = lines.map { |l| l.strip.split(",").map(&:to_i) }
13
N = boxes.length
14
15
distances = {}
16
17
N.times do |i|
18
(i + 1).upto(N - 1) do |j|
19
distances[[i, j]] = dist(boxes[i], boxes[j])
20
end
21
end
22
23
distances = distances.sort_by { |k,v| v }
24
25
circuits = N.times.map { |n| Set.new([n]) }
26
27
distances.each do |(a, b), _dist|
28
ca = circuits.index { |c| c.include?(a) }
29
cb = circuits.index { |c| c.include?(b) }
30
31
if ca == cb
32
puts "#{a} and #{b} directly connected"
33
else
34
puts "Joining #{a} and #{b} by merging #{ca} (n=#{circuits[ca].length}) and #{cb} (n=#{circuits[cb].length})"
35
circuits << (circuits[ca] | circuits[cb])
36
circuits.delete_at [ca, cb].max
37
circuits.delete_at [ca, cb].min
38
if circuits.length == 1
39
p boxes[a][0] * boxes[b][0]
40
exit
41
end
42
end
43
end
44
45
46
__END__
47
162,817,812
48
57,618,57
49
906,360,560
50
592,479,940
51
352,342,300
52
466,668,158
53
542,29,236
54
431,825,988
55
739,650,466
56
52,470,668
57
216,146,977
58
819,987,18
59
117,168,530
60
805,96,715
61
346,949,466
62
970,615,88
63
941,993,340
64
862,61,35
65
984,92,344
66
425,690,689
67
