Advent of Code 2022 - Day 23: Unstable Diffusion Solution

Part 1

Use 2 hash tables:

• one for counting next coords, this is to detect duplicate positions to skip
• one for keeping track of current elves' positions

Implementation

1const fs = require("fs")
2
3const readData = () => {
4  const data = fs
5    .readFileSync("./input", "utf-8")
6    .split(/\r?\n/)
7    .map(line => line.split(""))
8    .map((line, x) => line.map((cell, y) => (cell === "#" ? [x, y] : null)))
9    .flat()
10    .filter(Boolean)
11
12  return data
13}
14
15const main = () => {
16  const elfCoords = readData()
17  let elfCoordsSet = elfCoords.reduce(
18    (acc, el) => acc.add(String(el)),
19    new Set()
20  )
21
22  const dirNames = {
23    N: [-1, 0],
24    NE: [-1, 1],
25    E: [0, 1],
26    SE: [1, 1],
27    S: [1, 0],
28    SW: [1, -1],
29    W: [0, -1],
30    NW: [-1, -1],
31  }
32
33  let adjacentDirs = [
34    ["N", "NE", "NW"].map(dir => dirNames[dir]),
35    ["S", "SE", "SW"].map(dir => dirNames[dir]),
36    ["W", "NW", "SW"].map(dir => dirNames[dir]),
37    ["E", "NE", "SE"].map(dir => dirNames[dir]),
38  ]
39
40  let rounds = 10
41
42  while (rounds--) {
43    const nextCoords = Array(elfCoords.length).fill(null)
44    const nextCoordCountMap = new Map()
45
46    for (let i = 0; i < elfCoords.length; i++) {
47      // no other Elves are in one of those eight positions, the Elf does not do anything
48      const isStandStill = adjacentDirs
49        .flat()
50        .every(
51          dir =>
52            !elfCoordsSet.has(
53              String([elfCoords[i][0] + dir[0], elfCoords[i][1] + dir[1]])
54            )
55        )
56      if (isStandStill) continue
57
58      // "the Elf looks in each of four directions in the following order and proposes moving one step in the first valid direction"
59      const adjacentDirIndex = adjacentDirs.findIndex(adjacentDir =>
60        adjacentDir.every(
61          dir =>
62            !elfCoordsSet.has(
63              String([elfCoords[i][0] + dir[0], elfCoords[i][1] + dir[1]])
64            )
65        )
66      )
67
68      if (adjacentDirIndex === -1) {
69        continue
70      }
71
72      const dir = adjacentDirs[adjacentDirIndex][0]
73      const nextCoord = [elfCoords[i][0] + dir[0], elfCoords[i][1] + dir[1]]
74      nextCoords[i] = nextCoord
75      nextCoordCountMap.set(
76        String(nextCoord),
77        (nextCoordCountMap.get(String(nextCoord)) || 0) + 1
78      )
79    }
80
81    for (let i = 0; i < elfCoords.length; i++) {
82      // "two or more Elves propose moving to the same position, none of those Elves move"
83      if (nextCoords[i] && nextCoordCountMap.get(String(nextCoords[i])) === 1) {
84        elfCoordsSet.delete(String(elfCoords[i]))
85        elfCoords[i] = nextCoords[i]
86        elfCoordsSet.add(String(elfCoords[i]))
87      }
88    }
89
90    // "at the end of the round, the first direction the Elves considered is moved to the end of the list of directions"
91    adjacentDirs = [...adjacentDirs.slice(1), adjacentDirs[0]]
92  }
93
94  const [maxX, minX, maxY, minY] = [0, 1]
95    .map(idx => elfCoords.map(d => d[idx]))
96    .flatMap(values =>
97      ["max", "min"].map(method => Math[method].apply(null, values))
98    )
99
100  const res = (maxX - minX + 1) * (maxY - minY + 1) - elfCoords.length
101
102  console.log(res)
103}
104
105main()

Part 2

Like part 1, with additional flag to detect whether there is a at least a move in a round

Implementation

1const fs = require("fs")
2
3const readData = () => {
4  const data = fs
5    .readFileSync("./input", "utf-8")
6    .split(/\r?\n/)
7    .map(line => line.split(""))
8    .map((line, x) => line.map((cell, y) => (cell === "#" ? [x, y] : null)))
9    .flat()
10    .filter(Boolean)
11
12  return data
13}
14
15const main = () => {
16  const elfCoords = readData()
17  let elfCoordsSet = elfCoords.reduce(
18    (acc, el) => acc.add(String(el)),
19    new Set()
20  )
21
22  const dirNames = {
23    N: [-1, 0],
24    NE: [-1, 1],
25    E: [0, 1],
26    SE: [1, 1],
27    S: [1, 0],
28    SW: [1, -1],
29    W: [0, -1],
30    NW: [-1, -1],
31  }
32
33  let adjacentDirs = [
34    ["N", "NE", "NW"].map(dir => dirNames[dir]),
35    ["S", "SE", "SW"].map(dir => dirNames[dir]),
36    ["W", "NW", "SW"].map(dir => dirNames[dir]),
37    ["E", "NE", "SE"].map(dir => dirNames[dir]),
38  ]
39
40  let res
41  let rounds = 0
42
43  while (++rounds) {
44    const nextCoords = Array(elfCoords.length).fill(null)
45    const nextCoordCountMap = new Map()
46
47    for (let i = 0; i < elfCoords.length; i++) {
48      const isStandStill = adjacentDirs
49        .flat()
50        .every(
51          dir =>
52            !elfCoordsSet.has(
53              String([elfCoords[i][0] + dir[0], elfCoords[i][1] + dir[1]])
54            )
55        )
56      if (isStandStill) continue
57
58      const adjacentDirIndex = adjacentDirs.findIndex(adjacentDir =>
59        adjacentDir.every(
60          dir =>
61            !elfCoordsSet.has(
62              String([elfCoords[i][0] + dir[0], elfCoords[i][1] + dir[1]])
63            )
64        )
65      )
66
67      if (adjacentDirIndex === -1) {
68        continue
69      }
70
71      const dir = adjacentDirs[adjacentDirIndex][0]
72      const nextCoord = [elfCoords[i][0] + dir[0], elfCoords[i][1] + dir[1]]
73      nextCoords[i] = nextCoord
74      nextCoordCountMap.set(
75        String(nextCoord),
76        (nextCoordCountMap.get(String(nextCoord)) || 0) + 1
77      )
78    }
79
80    let noMove = true
81
82    for (let i = 0; i < elfCoords.length; i++) {
83      if (nextCoords[i] && nextCoordCountMap.get(String(nextCoords[i])) === 1) {
84        elfCoordsSet.delete(String(elfCoords[i]))
85        elfCoords[i] = nextCoords[i]
86        elfCoordsSet.add(String(elfCoords[i]))
87        noMove = false
88      }
89    }
90
91    adjacentDirs = [...adjacentDirs.slice(1), adjacentDirs[0]]
92
93    if (noMove) {
94      res = rounds
95      break
96    }
97  }
98
99  console.log(res)
100}
101
102main()

References

Original problem