From c19d3d6d50862b8847e87f018736252dc5e3129f Mon Sep 17 00:00:00 2001 From: An0nSaiko Date: Sat, 17 Dec 2022 06:04:19 +0200 Subject: Day 16 (part1) --- day14/solution.nim | 4 +- day16/example.txt | 10 +++++ day16/input.txt | 54 ++++++++++++++++++++++++ day16/solution.nim | 118 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 184 insertions(+), 2 deletions(-) create mode 100644 day16/example.txt create mode 100644 day16/input.txt create mode 100644 day16/solution.nim diff --git a/day14/solution.nim b/day14/solution.nim index 0056704..7816d25 100644 --- a/day14/solution.nim +++ b/day14/solution.nim @@ -33,7 +33,7 @@ proc parseFile(content: string): HashSet[Point] = # a = begin, b = end for i, a in rocks[0..^2]: let b = rocks[i+1] - echo fmt"a = {a}, b = {b}" + # echo fmt"a = {a}, b = {b}" for col in min(a.col, b.col) .. max(a.col, b.col): let toPush = Point((a.row, col)) result.incl(toPush) @@ -105,7 +105,7 @@ let content = readFile("./input.txt") let occupied = parseFile(content) occupied.draw() -echo fmt"{maxRow}, {minCol}-{maxCol}" +# echo fmt"{maxRow}, {minCol}-{maxCol}" echo solve(occupied) part2 = true echo solve(occupied) 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) -- cgit v1.2.3