# Advent of Code 2022 - Day 16: Proboscidea Volcanium Solution

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

```.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 =>8      /Valve (\w+) has flow rate=(\d+); tunnels? leads? to valves? (.+)/g.exec(9        line10      )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 data24}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        ? 144        : Number.POSITIVE_INFINITY45      return acc46    }, {})47    return acc48  }, {})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 & bitReprB62
63  const recursion = ({64    minutesLeft,65    currentValve,66    openedBitRepr,67    rate,68    bitReprMaxRateMap,69  }) => {70    bitReprMaxRateMap[openedBitRepr] = Math.max(71      bitReprMaxRateMap[openedBitRepr] || 0,72      rate73    )74
75    for (const valve of valvesHavingPositiveRate) {76      const newMinutesLeft = minutesLeft - (minTime[currentValve][valve] + 1)77      const newRate = rate + newMinutesLeft * data[valve].rate78      const newOpenedBitRepr = openedBitRepr | valveBitRepr[valve]79
80      if (newMinutesLeft <= 0 || isVisited(valveBitRepr[valve], openedBitRepr))81        continue82
83      recursion({84        minutesLeft: newMinutesLeft,85        currentValve: valve,86        openedBitRepr: newOpenedBitRepr,87        rate: newRate,88        bitReprMaxRateMap,89      })90    }91
92    return bitReprMaxRateMap93  }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 = fs5    .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        line10      )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 data24}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        ? 144        : Number.POSITIVE_INFINITY45      return acc46    }, {})47    return acc48  }, {})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 & bitReprB62
63  const recursion = ({64    minutesLeft,65    currentValve,66    openedBitRepr,67    rate,68    bitReprMaxRateMap,69  }) => {70    bitReprMaxRateMap[openedBitRepr] = Math.max(71      bitReprMaxRateMap[openedBitRepr] || 0,72      rate73    )74
75    for (const valve of valvesHavingPositiveRate) {76      const newMinutesLeft = minutesLeft - (minTime[currentValve][valve] + 1)77      const newRate = rate + newMinutesLeft * data[valve].rate78      const newOpenedBitRepr = openedBitRepr | valveBitRepr[valve]79
80      if (newMinutesLeft <= 0 || isVisited(valveBitRepr[valve], openedBitRepr))81        continue82
83      recursion({84        minutesLeft: newMinutesLeft,85        currentValve: valve,86        openedBitRepr: newOpenedBitRepr,87        rate: newRate,88        bitReprMaxRateMap,89      })90    }91
92    return bitReprMaxRateMap93  }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_INFINITY104
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()```

## References

Original problem

Floyd-Warshall Algorithm (Brilliant)

Floyd-Warshall Algorithm (e-maxx-eng)

## Tags

recursion

dfs

dynamic programming

bit manipulation

## Next Post

Advent of Code 2022 - Day 21: Monkey Math

Dec 21, 2022

Complex number

## Previous Post

Advent of Code 2022 - Day 20: Grove Positioning System

Dec 20, 2022

Handling indexes with care

Search Posts