# 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

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}const 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 = fs10    .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
30  return { coords: data, set }31}32
33const main = () => {34  const { coords, set } = readData()35
36  const targetY = 200000037  let res = 038
39  for (const [sensor, beacon, distance] of coords) {40    const absX = distance - Math.abs(targetY - sensor)41    if (absX < 0) continue42    const possibleXs = [sensor + absX, sensor - absX].sort(43      (a, b) => a - b44    )45    for (let x = possibleXs; x <= possibleXs; 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 = fs10    .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
30  return { coords: data, set }31}32
33const main = () => {34  const { coords, set } = readData()35
36  const bound = [0, 4000000]37
38  let res39
40  const getUnion = ranges => {41    const union = []42    ranges.sort(43      (rangeA, rangeB) => rangeA - rangeB || rangeA - rangeB44    )45    for (const [start, end] of ranges) {46      const latestUnionRange = union.slice(-1)47      if (latestUnionRange && latestUnionRange >= start - 1) {48        latestUnionRange = Math.max(latestUnionRange, end)49      } else {50        union.push([start, end])51      }52    }53
54    return union55  }56
57  for (let targetY = 0; targetY <= bound; targetY++) {58    let xRanges = []59    for (const [sensor, beacon, distance] of coords) {60      const absX = distance - Math.abs(targetY - sensor)61      if (absX < 0) continue62      const possibleXs = [sensor + absX, sensor - absX].sort(63        (a, b) => a - b64      )65      possibleXs = Math.max(bound, possibleXs)66      possibleXs = Math.min(bound, possibleXs)67
68      xRanges.push(possibleXs)69      xRanges.push(70        ...[sensor, beacon]71          .filter(([x, y]) => y === targetY && bound <= x && x <= bound)72          .map(([x]) => [x, x])73      )74    }75
76    const union = getUnion(xRanges)77
78    if (union.length === 2) {79      const coord = [union + 1, targetY]80      res = coord * bound + coord81      break82    }83  }84
85  console.log(res)86}87
88main()```

## References

Original problem

Union of multiple ranges

hash table

union find

## Next Post

Advent of Code 2022 - Day 18: Boiling Boulders

Dec 18, 2022

## Previous Post

Advent of Code 2022 - Day 14: Regolith Reservoir

Dec 14, 2022

Move and tackle obstacles

Search Posts