Day 16 (part1)

3 files changed, 182 insertions, 0 deletions

diff --git a/day16/example.txt b/day16/example.txt
new file mode 100644
index 0000000..9f30acc
--- /dev/null
+++ b/day16/example.txt
@@ -0,0 +1,10 @@
+Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
+Valve BB has flow rate=13; tunnels lead to valves CC, AA
+Valve CC has flow rate=2; tunnels lead to valves DD, BB
+Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE
+Valve EE has flow rate=3; tunnels lead to valves FF, DD
+Valve FF has flow rate=0; tunnels lead to valves EE, GG
+Valve GG has flow rate=0; tunnels lead to valves FF, HH
+Valve HH has flow rate=22; tunnel leads to valve GG
+Valve II has flow rate=0; tunnels lead to valves AA, JJ
+Valve JJ has flow rate=21; tunnel leads to valve II
diff --git a/day16/input.txt b/day16/input.txt
new file mode 100644
index 0000000..6cc1dee
--- /dev/null
+++ b/day16/input.txt
@@ -0,0 +1,54 @@
+Valve OK has flow rate=0; tunnels lead to valves RW, FX
+Valve JY has flow rate=13; tunnel leads to valve TT
+Valve FX has flow rate=16; tunnels lead to valves OK, LF, GO, IV
+Valve TD has flow rate=0; tunnels lead to valves XZ, ED
+Valve VF has flow rate=9; tunnels lead to valves DS, LU, TR, WO
+Valve TT has flow rate=0; tunnels lead to valves XZ, JY
+Valve KR has flow rate=8; tunnels lead to valves VL, CI, GO, JJ, TQ
+Valve HN has flow rate=0; tunnels lead to valves YG, AA
+Valve MC has flow rate=24; tunnels lead to valves MI, EE, TH, YG
+Valve XM has flow rate=0; tunnels lead to valves AF, JL
+Valve XE has flow rate=0; tunnels lead to valves XP, AF
+Valve ZF has flow rate=0; tunnels lead to valves EM, EI
+Valve DS has flow rate=0; tunnels lead to valves VF, LF
+Valve AF has flow rate=7; tunnels lead to valves AW, XE, CI, BJ, XM
+Valve NL has flow rate=0; tunnels lead to valves KF, EM
+Valve LF has flow rate=0; tunnels lead to valves FX, DS
+Valve XZ has flow rate=25; tunnels lead to valves TD, TT
+Valve TQ has flow rate=0; tunnels lead to valves AA, KR
+Valve WO has flow rate=0; tunnels lead to valves VF, NE
+Valve TH has flow rate=0; tunnels lead to valves LU, MC
+Valve AA has flow rate=0; tunnels lead to valves TQ, KF, HN, XP, TY
+Valve KB has flow rate=0; tunnels lead to valves WP, XL
+Valve IV has flow rate=0; tunnels lead to valves PK, FX
+Valve MI has flow rate=0; tunnels lead to valves JF, MC
+Valve EX has flow rate=22; tunnels lead to valves JL, ZZ, SL
+Valve ZZ has flow rate=0; tunnels lead to valves EX, JS
+Valve KF has flow rate=0; tunnels lead to valves NL, AA
+Valve PK has flow rate=11; tunnels lead to valves IV, HP
+Valve TR has flow rate=0; tunnels lead to valves DI, VF
+Valve YG has flow rate=0; tunnels lead to valves HN, MC
+Valve JL has flow rate=0; tunnels lead to valves EX, XM
+Valve VL has flow rate=0; tunnels lead to valves JS, KR
+Valve XP has flow rate=0; tunnels lead to valves AA, XE
+Valve TY has flow rate=0; tunnels lead to valves JS, AA
+Valve EM has flow rate=4; tunnels lead to valves JJ, NL, ZF, WP, AW
+Valve BJ has flow rate=0; tunnels lead to valves WK, AF
+Valve JJ has flow rate=0; tunnels lead to valves EM, KR
+Valve RW has flow rate=14; tunnels lead to valves NE, OK
+Valve EI has flow rate=0; tunnels lead to valves ZF, JS
+Valve SL has flow rate=0; tunnels lead to valves HP, EX
+Valve EE has flow rate=0; tunnels lead to valves MC, XL
+Valve WK has flow rate=0; tunnels lead to valves BJ, JS
+Valve AW has flow rate=0; tunnels lead to valves EM, AF
+Valve XL has flow rate=21; tunnels lead to valves EE, KB
+Valve JF has flow rate=0; tunnels lead to valves MI, ED
+Valve LU has flow rate=0; tunnels lead to valves TH, VF
+Valve CI has flow rate=0; tunnels lead to valves AF, KR
+Valve ED has flow rate=23; tunnels lead to valves JF, TD
+Valve JS has flow rate=3; tunnels lead to valves VL, ZZ, EI, TY, WK
+Valve NE has flow rate=0; tunnels lead to valves RW, WO
+Valve DI has flow rate=12; tunnel leads to valve TR
+Valve WP has flow rate=0; tunnels lead to valves KB, EM
+Valve GO has flow rate=0; tunnels lead to valves FX, KR
+Valve HP has flow rate=0; tunnels lead to valves SL, PK
diff --git a/day16/solution.nim b/day16/solution.nim
new file mode 100644
index 0000000..b6d39e6
--- /dev/null
+++ b/day16/solution.nim
@@ -0,0 +1,118 @@
+import strutils
+import sequtils
+import re
+import tables
+import strformat
+import algorithm
+
+type
+  NodeData = tuple
+    pressure: int
+    neighbors: seq[string]
+
+  Node = tuple
+    id: string
+    data: NodeData
+
+  NodeGraph = Table[string, NodeData]
+
+  ExtendedNodeData = tuple
+    pressure: int
+    neighbors: Table[string, int]
+
+  ExtendedNodeGraph = Table[string, ExtendedNodeData]
+
+proc parseLine(line: string): Node =
+  let tokens = line.replace("Valve ")
+                   .replace("has flow rate=")
+                   .replace(re"; tunnels? leads? to valves?")
+                   .replace(", ", " ")
+                   .split(" ")
+  (tokens[0], (tokens[1].parseInt(), @tokens[2..^1]))
+
+proc parseFile(content: string): NodeGraph =
+  let lines = content.strip().splitLines()
+  let nodes = map(lines, parseLine)
+
+  for node in nodes:
+    result[node.id] = node.data
+
+proc bfs(input: NodeGraph, src: string): Table[string, int] =
+  var q = @[(src, 0)]
+  result[src] = 0
+
+  while q.len() > 0:
+    let (curr, pathLen) = q[0]
+    q.delete(0)
+
+    for neighbor in input[curr].neighbors:
+      if result.contains(neighbor):
+        continue
+      result[neighbor] = pathLen+1
+      q.add((neighbor, pathLen+1))
+
+proc setup(input: NodeGraph): ExtendedNodeGraph =
+  for node in input.keys():
+    # Exclude all 0 pressure nodes except the entry node "AA"
+    if (input[node].pressure == 0 and node != "AA"):
+      continue
+    let allConnected = bfs(input, node)
+    var filtConnected: Table[string, int]
+    for conn in allConnected.keys():
+      if input[conn].pressure == 0:
+        continue
+      filtConnected[conn] = allConnected[conn]
+
+    result[node] = (input[node].pressure, filtConnected)
+    # echo fmt"{node} : {result[node]}"
+
+
+var dp: Table[string, int]
+proc normalize(visited: string): string =
+  var s: seq[string]
+  for i in countup(0, visited.len()-1, 2):
+    s.add(visited[i..i+1])
+  result = s.sorted(system.cmp[string]).join()
+
+proc dfs(input: ExtendedNodeGraph, src: string, visited: string, time: int): int =
+  if time <= 1 or visited.len() == input.len():
+    return 0
+
+  # if dp.contains(visited):
+  #   return dp[visited]
+
+  let visitedNorm = visited.normalize()
+  let selfScore = (time-1) * input[src].pressure
+  var maxSubscore = 0
+  var maxNeighbor = "undefined" 
+  # echo fmt"{src}({selfScore}): "
+  for neighbor in input[src].neighbors.keys():
+    if neighbor in visited:
+      continue
+    let distance = input[src].neighbors[neighbor]
+    let subScore = dfs(input, neighbor, visitedNorm & neighbor, time - 1 - distance)
+    if subScore > maxSubscore:
+      maxSubscore = subScore
+      maxNeighbor = neighbor
+
+  # echo fmt"{src}({selfScore}) => {maxNeighbor}({maxSubscore})"
+  result = selfScore + maxSubscore
+  # dp[visitedNorm & maxNeighbor] = result
+  # echo result
+
+proc solve(input: NodeGraph, time: int): int =
+  let completeGraph = setup(input)
+  # Table of delays to get from starting node "AA" to current
+  let initDelays = completeGraph["AA"].neighbors
+
+  for node in completeGraph.keys():
+    if node == "AA":
+      continue
+    let startTime = time - initDelays[node]
+    result = max(result, dfs(completeGraph, node, node, startTime))
+    echo fmt"{node}({startTime}) : {result}"
+
+let content = readFile("./example.txt")
+
+let input = parseFile(content)
+echo solve(input, 30)