# Advent of Code 2022 - Day 23: Unstable Diffusion Solution

Read the problem description carefully, the rest is straigthforward implementation

## 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

```.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 readData = () => {4  const data = fs5    .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 data13}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 = 1041
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 anything48      const isStandStill = adjacentDirs49        .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) continue57
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        continue70      }71
72      const dir = adjacentDirs[adjacentDirIndex][0]73      const nextCoord = [elfCoords[i][0] + dir[0], elfCoords[i][1] + dir[1]]74      nextCoords[i] = nextCoord75      nextCoordCountMap.set(76        String(nextCoord),77        (nextCoordCountMap.get(String(nextCoord)) || 0) + 178      )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.length101
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 = fs5    .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 data13}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 res41  let rounds = 042
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 = adjacentDirs49        .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) continue57
67      if (adjacentDirIndex === -1) {68        continue69      }70
71      const dir = adjacentDirs[adjacentDirIndex][0]72      const nextCoord = [elfCoords[i][0] + dir[0], elfCoords[i][1] + dir[1]]73      nextCoords[i] = nextCoord74      nextCoordCountMap.set(75        String(nextCoord),76        (nextCoordCountMap.get(String(nextCoord)) || 0) + 177      )78    }79
80    let noMove = true81
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 = false88      }89    }90
93    if (noMove) {94      res = rounds95      break96    }97  }98
99  console.log(res)100}101
102main()```

Original problem

hash table

math

## Next Post

Toptal Interview Process Guide and Review

Jul 2, 2021

Journey of a non-native English-speaker developer on looking for a remote opportunity

Search Posts