Advent of Code 2022 - Day 16: Proboscidea Volcanium Solution

Floyd-Warshal and bitmask

Part 1

Use Floyd-Warshal algorithm to calculate minimum travel time among tunnels

Ignore valves with flow rate of 0 during calculation

Use bitmask to represent openned valves

Use DFS to travese and calculate best flow rate through all possibilites

Implementation

1const fs = require("fs")
2
3const readData = () => {
4  const data = fs
5    .readFileSync("./input", "utf-8")
6    .split(/\r?\n/)
7    .map(line =>
8      /Valve (\w+) has flow rate=(\d+); tunnels? leads? to valves? (.+)/g.exec(
9        line
10      )
11    )
12    .map(([_, valve, rate, to]) => ({
13      valve,
14      rate: Number(rate),
15      to: to.split(", "),
16    }))
17    .reduce(
18      (acc, { valve, rate, to }) =>
19        Object.assign(acc, { [valve]: { rate, to } }),
20      {}
21    )
22
23  return data
24}
25
26const main = () => {
27  const data = readData()
28
29  const valves = Object.keys(data)
30
31  const valvesHavingPositiveRate = valves.filter(valve =>
32    Boolean(data[valve].rate)
33  )
34
35  const valveBitRepr = valvesHavingPositiveRate.reduce(
36    (acc, valve, i) => Object.assign(acc, { [valve]: 1 << i }),
37    {}
38  )
39
40  const minTime = valves.reduce((acc, valveFrom) => {
41    acc[valveFrom] = valves.reduce((acc, valveTo) => {
42      acc[valveTo] = data[valveFrom].to.includes(valveTo)
43        ? 1
44        : Number.POSITIVE_INFINITY
45      return acc
46    }, {})
47    return acc
48  }, {})
49
50  for (const mid of valves) {
51    for (const start of valves) {
52      for (const end of valves) {
53        minTime[start][end] = Math.min(
54          minTime[start][end],
55          minTime[start][mid] + minTime[mid][end]
56        )
57      }
58    }
59  }
60
61  const isVisited = (bitReprA, bitReprB) => bitReprA & bitReprB
62
63  const recursion = ({
64    minutesLeft,
65    currentValve,
66    openedBitRepr,
67    rate,
68    bitReprMaxRateMap,
69  }) => {
70    bitReprMaxRateMap[openedBitRepr] = Math.max(
71      bitReprMaxRateMap[openedBitRepr] || 0,
72      rate
73    )
74
75    for (const valve of valvesHavingPositiveRate) {
76      const newMinutesLeft = minutesLeft - (minTime[currentValve][valve] + 1)
77      const newRate = rate + newMinutesLeft * data[valve].rate
78      const newOpenedBitRepr = openedBitRepr | valveBitRepr[valve]
79
80      if (newMinutesLeft <= 0 || isVisited(valveBitRepr[valve], openedBitRepr))
81        continue
82
83      recursion({
84        minutesLeft: newMinutesLeft,
85        currentValve: valve,
86        openedBitRepr: newOpenedBitRepr,
87        rate: newRate,
88        bitReprMaxRateMap,
89      })
90    }
91
92    return bitReprMaxRateMap
93  }
94
95  const bitReprMaxRateMap = recursion({
96    minutesLeft: 30,
97    currentValve: "AA",
98    openedBitRepr: 0,
99    rate: 0,
100    bitReprMaxRateMap: {},
101  })
102
103  const res = Math.max(...Object.values(bitReprMaxRateMap))
104
105  console.log(res)
106}
107
108main()

Part 2

Like part 1, human go first and elephant avoid opened valves

1humanOpened & elephantOpened == 0

Implementation

1const fs = require("fs")
2
3const readData = () => {
4  const data = fs
5    .readFileSync("./input", "utf-8")
6    .split(/\r?\n/)
7    .map(line =>
8      /Valve (\w+) has flow rate=(\d+); tunnels? leads? to valves? (.+)/g.exec(
9        line
10      )
11    )
12    .map(([_, valve, rate, to]) => ({
13      valve,
14      rate: Number(rate),
15      to: to.split(", "),
16    }))
17    .reduce(
18      (acc, { valve, rate, to }) =>
19        Object.assign(acc, { [valve]: { rate, to } }),
20      {}
21    )
22
23  return data
24}
25
26const main = () => {
27  const data = readData()
28
29  const valves = Object.keys(data)
30
31  const valvesHavingPositiveRate = valves.filter(valve =>
32    Boolean(data[valve].rate)
33  )
34
35  const valveBitRepr = valvesHavingPositiveRate.reduce(
36    (acc, valve, i) => Object.assign(acc, { [valve]: 1 << i }),
37    {}
38  )
39
40  const minTime = valves.reduce((acc, valveFrom) => {
41    acc[valveFrom] = valves.reduce((acc, valveTo) => {
42      acc[valveTo] = data[valveFrom].to.includes(valveTo)
43        ? 1
44        : Number.POSITIVE_INFINITY
45      return acc
46    }, {})
47    return acc
48  }, {})
49
50  for (const mid of valves) {
51    for (const start of valves) {
52      for (const end of valves) {
53        minTime[start][end] = Math.min(
54          minTime[start][end],
55          minTime[start][mid] + minTime[mid][end]
56        )
57      }
58    }
59  }
60
61  const isVisited = (bitReprA, bitReprB) => bitReprA & bitReprB
62
63  const recursion = ({
64    minutesLeft,
65    currentValve,
66    openedBitRepr,
67    rate,
68    bitReprMaxRateMap,
69  }) => {
70    bitReprMaxRateMap[openedBitRepr] = Math.max(
71      bitReprMaxRateMap[openedBitRepr] || 0,
72      rate
73    )
74
75    for (const valve of valvesHavingPositiveRate) {
76      const newMinutesLeft = minutesLeft - (minTime[currentValve][valve] + 1)
77      const newRate = rate + newMinutesLeft * data[valve].rate
78      const newOpenedBitRepr = openedBitRepr | valveBitRepr[valve]
79
80      if (newMinutesLeft <= 0 || isVisited(valveBitRepr[valve], openedBitRepr))
81        continue
82
83      recursion({
84        minutesLeft: newMinutesLeft,
85        currentValve: valve,
86        openedBitRepr: newOpenedBitRepr,
87        rate: newRate,
88        bitReprMaxRateMap,
89      })
90    }
91
92    return bitReprMaxRateMap
93  }
94
95  const bitReprMaxRateMap = recursion({
96    minutesLeft: 26,
97    currentValve: "AA",
98    openedBitRepr: 0,
99    rate: 0,
100    bitReprMaxRateMap: {},
101  })
102
103  let res = Number.NEGATIVE_INFINITY
104
105  for (const human of Object.entries(bitReprMaxRateMap)) {
106    for (const elephant of Object.entries(bitReprMaxRateMap)) {
107      if (!(human[0] & elephant[0])) {
108        res = Math.max(res, human[1] + elephant[1])
109      }
110    }
111  }
112
113  console.log(res)
114}
115
116main()