sharparam.com
Code for the Advent of Code event
aoc
advent-of-code
1#!/usr/bin/env ruby
2# frozen_string_literal: true
3
4require 'matrix'
5require 'pry'
6
7DEBUG = false
8
9def debug(msg = nil, &block)
10 return unless DEBUG
11 warn msg if msg
12 block.call if block_given?
13end
14
15class Vector
16 def x = self[0]
17 def y = self[1]
18 def z = self[2]
19
20 def x=(v) self[0] = v end
21 def y=(v) self[1] = v end
22 def z=(v) self[2] = v end
23
24 def to_s = "(#{x}, #{y}, #{z})"
25 def inspect = to_s
26end
27
28V = Vector
29
30TRANSFORMS = [
31 ->(p) { V[p.z, p.y, -p.x] },
32 ->(p) { V[-p.y, p.z, -p.x] },
33 ->(p) { V[-p.z, -p.y, -p.x] },
34 ->(p) { V[p.y, -p.z, -p.x] },
35 ->(p) { V[p.z, p.x, p.y] },
36 ->(p) { V[-p.x, p.z, p.y] },
37 ->(p) { V[-p.z, -p.x, p.y] },
38 ->(p) { V[p.x, -p.z, p.y] },
39 ->(p) { V[p.y, p.x, -p.z] },
40 ->(p) { V[-p.x, p.y, -p.z] },
41 ->(p) { V[-p.y, -p.x, -p.z] },
42 ->(p) { V[p.x, -p.y, -p.z] },
43 ->(p) { V[p.y, p.z, p.x] },
44 ->(p) { V[-p.z, p.y, p.x] },
45 ->(p) { V[-p.y, -p.z, p.x] },
46 ->(p) { V[p.z, -p.y, p.x] },
47 ->(p) { V[p.x, p.z, -p.y] },
48 ->(p) { V[-p.z, p.x, -p.y] },
49 ->(p) { V[-p.x, -p.z, -p.y] },
50 ->(p) { V[p.z, -p.x, -p.y] },
51 ->(p) { V[p.x, p.y, p.z] },
52 ->(p) { V[-p.y, p.x, p.z] },
53 ->(p) { V[-p.x, -p.y, p.z] },
54 ->(p) { V[p.y, -p.x, p.z] }
55].freeze
56
57def rotate(map)
58 TRANSFORMS.map { |t| map.map { |p| t[p] } }
59end
60
61def manhattan(a, b)
62 (a.x - b.x).abs + (a.y - b.y).abs + (a.z - b.z).abs
63end
64
65maps = ARGF.read.strip.split("\n\n").map { |s| s.lines[1..].map { Vector[*_1.split(',').map(&:to_i)] } }
66maps_dict = maps.each_with_index.to_a.to_h(&:reverse)
67
68current = maps_dict[0]
69current_i = 0
70solved = { 0 => current }
71scanner_positions = [Vector[0, 0, 0]]
72
73loop do
74 unsolved_is = maps_dict.keys - solved.keys
75 debug "Solved indices: #{solved.keys}"
76 debug "Unsolved indices: #{unsolved_is}"
77 debug "Trying to find a match for #{current_i}"
78 break if solved.size == maps_dict.size
79 solution = nil
80 solution_i = nil
81 solution_score = 0
82 unsolved_is.each do |i|
83 candidate = maps_dict[i]
84 rotations = rotate candidate
85 rotations.each do |rotation|
86 diffs = current.product(rotation).map { _1 - _2 }
87 diffs.each do |diff|
88 translation = rotation.map { _1 + diff }
89 common_count = (current & translation).size
90 if common_count >= 12 && common_count > solution_score
91 debug "Scanner #{i} matches with score #{common_count}"
92 solution = translation
93 solution_i = i
94 solution_score = common_count
95 scanner_positions << diff
96 break
97 end
98 break if solution
99 end
100 break if solution
101 end
102 break if solution
103 end
104 if solution
105 debug "Best match for #{current_i} is #{solution_i} (score: #{solution_score})"
106 solution = solution.union current
107 solved[solution_i] = solution
108 current = solution
109 current_i = solution_i
110 else
111 abort 'Failed to find a match'
112 end
113 debug ''
114end
115
116puts solved.values.flatten.uniq.size
117puts scanner_positions.combination(2).map { manhattan(_1, _2) }.max
118
119# binding.pry