Advent of Code 2022 - Day 14: Regolith Reservoir Solution

Part 1

Keep moving in a direction before switching to others. Order of direction: down, down-left, down-right.

1const dirs = [
2  [0, 1], // down
3  [-1, 1], // down left
4  [1, 1], // down right
5]
6
7for (let [dx, dy] of dirs) {
8  const [newX, newY] = [x + dx, y + dy]
9  if (!obstacles.has(coordToStr([newX, newY]))) {
10    return drop([newX, newY])
11  }
12}

When could not move, produce new sand.

1while (1) {
2  const hasNextDrop = drop([500, 0])
3  if (!hasNextDrop) break
4}
5
6const drop = ([x, y]) => {
7  // check abyss
8
9  // moving
10
11  // comes to rest
12  res++
13  obstacles.add(coordToStr([x, y]))
14
15  // signal new spawn
16  return true
17}

We know when falling into endless void when the movement never stops.

1if (y > maxY) {
2  // endless void
3  return false
4}

Implementation

1const fs = require("fs")
2
3const coordToStr = ([x, y]) => `${x} ${y}`
4
5const readData = () => {
6  const data = fs
7    .readFileSync("./input", "utf-8")
8    .split(/\r?\n/)
9    .map(line =>
10      line.split(" -> ").map(number => number.split(",").map(Number))
11    )
12
13  let obstacles = new Set()
14  let maxY = Number.NEGATIVE_INFINITY
15
16  for (const line of data) {
17    for (let i = 0; i < line.length - 1; i++) {
18      let [x1, y1] = line[i]
19      let [x2, y2] = line[i + 1]
20      ;[x1, x2] = [x1, x2].sort((a, b) => a - b)
21      ;[y1, y2] = [y1, y2].sort((a, b) => a - b)
22
23      for (let x = x1; x <= x2; x++) {
24        for (let y = y1; y <= y2; y++) {
25          obstacles.add(coordToStr([x, y]))
26          maxY = Math.max(maxY, y)
27        }
28      }
29    }
30  }
31
32  return { obstacles, maxY }
33}
34
35const main = () => {
36  const { obstacles, maxY } = readData()
37
38  let res = 0
39
40  const drop = ([x, y]) => {
41    if (y > maxY) {
42      // endless void
43      return false
44    }
45
46    const dirs = [
47      [0, 1], // down
48      [-1, 1], // down left
49      [1, 1], // down right
50    ]
51
52    for (let [dx, dy] of dirs) {
53      const [newX, newY] = [x + dx, y + dy]
54      if (!obstacles.has(coordToStr([newX, newY]))) {
55        return drop([newX, newY])
56      }
57    }
58
59    // comes to rest
60    res++
61    obstacles.add(coordToStr([x, y]))
62
63    return true
64  }
65
66  while (1) {
67    const hasNextDrop = drop([500, 0])
68    if (!hasNextDrop) break
69  }
70
71  console.log(res)
72}
73
74main()

Part 2

Like part 1

Stop the spawning when the flow is blocked

1if (obstacles.has(coordToStr([x, y]))) {
2  // stop the flow
3  return false
4}

Stop moving when touch the ground

1if (y < maxY + 1) {
2  // if not touch the floor yet, then keep moving
3}
4
5// else rest

Implementation

1const fs = require("fs")
2
3const coordToStr = ([x, y]) => `${x} ${y}`
4
5const readData = () => {
6  const data = fs
7    .readFileSync("./input", "utf-8")
8    .split(/\r?\n/)
9    .map(line =>
10      line.split(" -> ").map(number => number.split(",").map(Number))
11    )
12
13  let obstacles = new Set()
14  let maxY = Number.NEGATIVE_INFINITY
15
16  for (const line of data) {
17    for (let i = 0; i < line.length - 1; i++) {
18      let [x1, y1] = line[i]
19      let [x2, y2] = line[i + 1]
20      ;[x1, x2] = [x1, x2].sort((a, b) => a - b)
21      ;[y1, y2] = [y1, y2].sort((a, b) => a - b)
22
23      for (let x = x1; x <= x2; x++) {
24        for (let y = y1; y <= y2; y++) {
25          obstacles.add(coordToStr([x, y]))
26          maxY = Math.max(maxY, y)
27        }
28      }
29    }
30  }
31
32  return { obstacles, maxY }
33}
34
35const main = () => {
36  const { obstacles, maxY } = readData()
37
38  let res = 0
39
40  const drop = ([x, y]) => {
41    if (obstacles.has(coordToStr([x, y]))) {
42      // stop the flow
43      return false
44    }
45
46    const dirs = [
47      [0, 1], // down
48      [-1, 1], // down left
49      [1, 1], // down right
50    ]
51
52    if (y < maxY + 1) {
53      // if not touch the floor yet
54
55      for (let [dx, dy] of dirs) {
56        const [newX, newY] = [x + dx, y + dy]
57        if (!obstacles.has(coordToStr([newX, newY]))) {
58          return drop([newX, newY])
59        }
60      }
61    }
62
63    // comes to rest
64    res++
65    obstacles.add(coordToStr([x, y]))
66
67    return true
68  }
69
70  while (1) {
71    const hasNextDrop = drop([500, 0])
72    if (!hasNextDrop) break
73  }
74
75  console.log(res)
76}
77
78main()

Rock drawing

I stole the inspiration from a comment

So basically instead of checking whether to go backward or forward, upward or downward, we sort the coordinate to narrow the case to just go forward and downward

1for (const line of data) {
2  for (let i = 0; i < line.length - 1; i++) {
3    let [x1, y1] = line[i]
4    let [x2, y2] = line[i + 1]
5
6    ;[x1, x2] = [x1, x2].sort((a, b) => a - b)
7    ;[y1, y2] = [y1, y2].sort((a, b) => a - b)
8
9    for (let x = x1; x <= x2; x++) {
10      for (let y = y1; y <= y2; y++) {
11        obstacles.add(coordToStr([x, y]))
12      }
13    }
14  }
15}

References

Original problem