Advent of Code 2022 - Day 15: Beacon Exclusion Zone Solution

Union of ranges

Part 1

Count number of coords that have distance less than or equal to the distance of each sensor to its nearest beacon

Implementation

1const fs = require("fs")
2
3const coordToStr = ([x, y]) => `${x} ${y}`
4
5const calculateDistance = ([x1, y1], [x2, y2]) =>
6  Math.abs(x1 - x2) + Math.abs(y1 - y2)
7
8const readData = () => {
9  const data = fs
10    .readFileSync("./input", "utf-8")
11    .split(/\r?\n/)
12    .map(line => line.match(/-?\d+/g).map(Number))
13    .map(([x1, y1, x2, y2]) => [
14      [x1, y1],
15      [x2, y2],
16    ])
17    .map(([sensor, beacon]) => [
18      sensor,
19      beacon,
20      calculateDistance(sensor, beacon),
21    ])
22
23  const set = new Set()
24
25  for (const [sensor, beacon] of data) {
26    set.add(coordToStr(sensor))
27    set.add(coordToStr(beacon))
28  }
29
30  return { coords: data, set }
31}
32
33const main = () => {
34  const { coords, set } = readData()
35
36  const targetY = 2000000
37  let res = 0
38
39  for (const [sensor, beacon, distance] of coords) {
40    const absX = distance - Math.abs(targetY - sensor[1])
41    if (absX < 0) continue
42    const possibleXs = [sensor[0] + absX, sensor[0] - absX].sort(
43      (a, b) => a - b
44    )
45    for (let x = possibleXs[0]; x <= possibleXs[1]; x++) {
46      if (!set.has(coordToStr([x, targetY]))) {
47        res++
48        set.add(coordToStr([x, targetY]))
49      }
50    }
51  }
52
53  console.log(res)
54}
55
56main()

Part 2

In each row, find the ranges covered by sensors

Find the union of those ranges

If a row has over than one union ranges, then the distress beacon is in the between

Implementation

1const fs = require("fs")
2
3const coordToStr = ([x, y]) => `${x} ${y}`
4
5const calculateDistance = ([x1, y1], [x2, y2]) =>
6  Math.abs(x1 - x2) + Math.abs(y1 - y2)
7
8const readData = () => {
9  const data = fs
10    .readFileSync("./input", "utf-8")
11    .split(/\r?\n/)
12    .map(line => line.match(/-?\d+/g).map(Number))
13    .map(([x1, y1, x2, y2]) => [
14      [x1, y1],
15      [x2, y2],
16    ])
17    .map(([sensor, beacon]) => [
18      sensor,
19      beacon,
20      calculateDistance(sensor, beacon),
21    ])
22
23  const set = new Set()
24
25  for (const [sensor, beacon] of data) {
26    set.add(coordToStr(sensor))
27    set.add(coordToStr(beacon))
28  }
29
30  return { coords: data, set }
31}
32
33const main = () => {
34  const { coords, set } = readData()
35
36  const bound = [0, 4000000]
37
38  let res
39
40  const getUnion = ranges => {
41    const union = []
42    ranges.sort(
43      (rangeA, rangeB) => rangeA[0] - rangeB[0] || rangeA[1] - rangeB[1]
44    )
45    for (const [start, end] of ranges) {
46      const latestUnionRange = union.slice(-1)[0]
47      if (latestUnionRange && latestUnionRange[1] >= start - 1) {
48        latestUnionRange[1] = Math.max(latestUnionRange[1], end)
49      } else {
50        union.push([start, end])
51      }
52    }
53
54    return union
55  }
56
57  for (let targetY = 0; targetY <= bound[1]; targetY++) {
58    let xRanges = []
59    for (const [sensor, beacon, distance] of coords) {
60      const absX = distance - Math.abs(targetY - sensor[1])
61      if (absX < 0) continue
62      const possibleXs = [sensor[0] + absX, sensor[0] - absX].sort(
63        (a, b) => a - b
64      )
65      possibleXs[0] = Math.max(bound[0], possibleXs[0])
66      possibleXs[1] = Math.min(bound[1], possibleXs[1])
67
68      xRanges.push(possibleXs)
69      xRanges.push(
70        ...[sensor, beacon]
71          .filter(([x, y]) => y === targetY && bound[0] <= x && x <= bound[1])
72          .map(([x]) => [x, x])
73      )
74    }
75
76    const union = getUnion(xRanges)
77
78    if (union.length === 2) {
79      const coord = [union[0][1] + 1, targetY]
80      res = coord[0] * bound[1] + coord[1]
81      break
82    }
83  }
84
85  console.log(res)
86}
87
88main()