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'
5
6def md(a, b)
7 (a[0] - b[0]).abs + (a[1] - b[1]).abs
8end
9
10def wmd(a, b)
11 ax, _ay = a[0], a[1]
12 d = md(a, b)
13 x_min, x_max, y_min, y_max = a[0] - d, a[0] + d, a[1] - d, a[1] + d
14
15 (x_min..x_max).map do |x|
16 xd = (ax - x).abs
17 yf, yt = y_min + xd, y_max - xd
18 [Vector[x, yf], Vector[x, yt]]
19 end
20end
21
22pairs = ARGF.read.scan(/-?\d+/).map(&:to_i).each_slice(4).map { [Vector[_1, _2], Vector[_3, _4]] }
23
24beacons = Set[*pairs.map(&:last)]
25invalid = Set[]
26
27Y = 2_000_000
28
29pairs.each do |s, b|
30 cols = wmd(s, b).to_a
31 cols.each do |c|
32 invalid.add(c[0][0]) if (c[0][1]..c[1][1]).include?(Y) && !beacons.include?(Vector[c[0][0], Y])
33 end
34end
35
36puts invalid.size
37
38def perimiter(s, b)
39 d = md(s, b)
40
41 left = s[0] - d
42 steps = (1..d).to_a
43 steps = steps + [nil] + steps.reverse
44
45 result = []
46
47 ((s[0] - d)..(s[0] + d)).each do |x|
48 y_step = steps[x - left]
49 unless y_step.nil?
50 result.push Vector[x, s[1] + y_step]
51 result.push Vector[x, s[1] - y_step]
52 end
53 end
54
55 result
56end
57
58distances = pairs.map { |s, b| [s, md(s, b)] }
59
60MAX = 4_000_000
61
62pairs.each do |sensor, beacon|
63 perims = perimiter(sensor, beacon).reject { |v| v[0] < 0 || v[0] > MAX || v[1] < 0 || v[1] > MAX }
64 others = distances.reject { |s, _| s == sensor }
65
66 perims.each do |v|
67 if others.all? { |o, d| md(o, v) > d }
68 puts (v[0] * MAX) + v[1]
69 exit
70 end
71 end
72end