From 77c9806c3de6ee09130f2c5c2344b4ef054c1433 Mon Sep 17 00:00:00 2001 From: An0nSaiko Date: Sun, 18 Dec 2022 23:30:13 +0200 Subject: Day 18 --- day16/solution.nim | 297 ++++++++++++++++++++++++++++------------------------- 1 file changed, 155 insertions(+), 142 deletions(-) (limited to 'day16/solution.nim') diff --git a/day16/solution.nim b/day16/solution.nim index ae93568..66015d3 100644 --- a/day16/solution.nim +++ b/day16/solution.nim @@ -5,25 +5,26 @@ import tables import strformat import algorithm import sets +import sugar type NodeData = tuple pressure: int - neighbors: seq[string] + neighbors: seq[int64] Node = tuple - id: string + id: int64 data: NodeData - NodeGraph = Table[string, NodeData] + NodeGraph = Table[int64, NodeData] ExtendedNodeData = tuple pressure: int - neighbors: Table[string, int] + neighbors: Table[int64, int] - ExtendedNodeGraph = Table[string, ExtendedNodeData] + ExtendedNodeGraph = Table[int64, ExtendedNodeData] -proc parseLine(line: string): Node = +proc parseLine(line: string): auto = let tokens = line.replace("Valve ") .replace("has flow rate=") .replace(re"; tunnels? leads? to valves?") @@ -35,145 +36,157 @@ 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]}" - -type Agent = tuple - valv: string - time: int - -# Nodes with their neighbors -var Graph: ExtendedNodeGraph -# Node names -var nodes = newSeq[string]() - -proc playing(agent: Agent, time: int): bool = - agent.time == time - -proc agentScores(agent: Agent, time: int): int = - Graph[agent.valv].pressure * (time-1) - + # Create stringID to intID mapping + var nodeIDs: Table[string, int64] + for i, node in nodes: + nodeIDs[node[0]] = 1 shl i + + echo nodeIDs + # for i, node in nodes: + # result[nodeIDs[nodes[0]]] = (node[1][0], map(node[1][1], (stringID) => nodeIDs[stringID])) + +# 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]}" +# +# type Agent = tuple +# valv: string +# time: int +# +# # Nodes with their neighbors +# var Graph: ExtendedNodeGraph +# # Node names +# var nodes = newSeq[string]() +# +# proc playing(agent: Agent, time: int): bool = +# agent.time == time +# +# proc agentScores(agent: Agent, time: int): int = +# Graph[agent.valv].pressure * (time-1) +# # type ValveSet = uint64 +# # proc incl(set: var ValveSet, valve: uint64): void = # set = set or valve - -var part2 = false -proc dfs(visited: HashSet[string], time: int, human, elephant: Agent): int = - # echo fmt"time: {time}, human: {human}, elephant: {elephant}" - let remainingValves = nodes.len() - visited.len() - if time <= 1 or remainingValves == 0 or (part2 and human.valv == elephant.valv and remainingValves > 1): - return 0 - - let - neighborsHuman = Graph[human.valv].neighbors - neighborsElephant = Graph[elephant.valv].neighbors - var - # check for race - humanScore = if human.valv notin visited: human.agentScores(time) else: 0 - elephantScore = if elephant.valv notin visited: elephant.agentScores(time) else: 0 - - var bestNextScore = 0 - if human.playing(time) and elephant.playing(time): - for nextHuman in nodes: - for nextElephant in nodes: - if nextHuman in visited or nextElephant in visited: - continue - let - nextTimeHuman = time - 1 - neighborsHuman[nextHuman] - nextTimeElephant = time - 1 - neighborsElephant[nextElephant] - nextTime = max(nextTimeHuman, nextTimeElephant) - nextScore = dfs(union(visited, toHashSet(@[elephant.valv, human.valv])), nextTime, (nextHuman, nextTimeHuman), (nextElephant, nextTimeElephant)) - bestNextScore = max(bestNextScore, nextScore) - - # elephant keeps his score only if he isn't in the same valve as human - elephantScore = (if human != elephant: elephantScore else: 0) - return bestNextScore + humanScore + elephantScore - - if human.playing(time): - for nextHuman in nodes: - if nextHuman in visited: - continue - let - nextTimeHuman = time - 1 - neighborsHuman[nextHuman] - nextTime = max(nextTimeHuman, elephant.time) - nextScore = dfs(union(visited, toHashSet(@[human.valv])), nextTime, (nextHuman, nextTimeHuman), elephant) - bestNextScore = max(bestNextScore, nextScore) - - # Check for race - return bestNextScore + humanScore - - if elephant.playing(time): - for nextElephant in nodes: - if nextElephant in visited: - continue - let - nextTimeElephant = time - 1 - neighborsElephant[nextElephant] - nextTime = max(human.time, nextTimeElephant) - nextScore = dfs(union(visited, toHashSet(@[elephant.valv])), nextTime, human, (nextElephant, nextTimeElephant)) - bestNextScore = max(bestNextScore, nextScore) - - # Check for race - return bestNextScore + elephantScore - - assert(false) - -proc solve(initDelays: Table[string, int], time: int): int = - - if not part2: - for human in nodes: - let - humanStartTime = time - initDelays[human] - startTime = humanStartTime - result = max(result, dfs(initHashSet[string](), startTime, (human, humanStartTime), (human, -1))) - else: - for i, human in nodes[0 ..< ^1]: - for elephant in nodes[i+1 .. ^1]: - let - elephantStartTime = time - initDelays[elephant] - humanStartTime = time - initDelays[human] - startTime = max(elephantStartTime, humanStartTime) - result = max(result, dfs(initHashSet[string](), startTime, (human, humanStartTime), (elephant, elephantStartTime))) +# +# proc contains(set: ValveSet, valve: uint64): bool = +# return (set and valve) > 0 +# +# var part2 = false +# proc dfs(visited: ValveSet, time: int, human, elephant: Agent): int = +# # echo fmt"time: {time}, human: {human}, elephant: {elephant}" +# let remainingValves = nodes.len() - visited.len() +# if time <= 1 or remainingValves == 0 or (part2 and human.valv == elephant.valv and remainingValves > 1): +# return 0 +# +# let +# neighborsHuman = Graph[human.valv].neighbors +# neighborsElephant = Graph[elephant.valv].neighbors +# var +# # check for race +# humanScore = if human.valv notin visited: human.agentScores(time) else: 0 +# elephantScore = if elephant.valv notin visited: elephant.agentScores(time) else: 0 +# +# var bestNextScore = 0 +# if human.playing(time) and elephant.playing(time): +# for nextHuman in nodes: +# for nextElephant in nodes: +# if nextHuman in visited or nextElephant in visited: +# continue +# let +# nextTimeHuman = time - 1 - neighborsHuman[nextHuman] +# nextTimeElephant = time - 1 - neighborsElephant[nextElephant] +# nextTime = max(nextTimeHuman, nextTimeElephant) +# nextScore = dfs(union(visited, toHashSet(@[elephant.valv, human.valv])), nextTime, (nextHuman, nextTimeHuman), (nextElephant, nextTimeElephant)) +# bestNextScore = max(bestNextScore, nextScore) +# +# # elephant keeps his score only if he isn't in the same valve as human +# elephantScore = (if human != elephant: elephantScore else: 0) +# return bestNextScore + humanScore + elephantScore +# +# if human.playing(time): +# for nextHuman in nodes: +# if nextHuman in visited: +# continue +# let +# nextTimeHuman = time - 1 - neighborsHuman[nextHuman] +# nextTime = max(nextTimeHuman, elephant.time) +# nextScore = dfs(union(visited, toHashSet(@[human.valv])), nextTime, (nextHuman, nextTimeHuman), elephant) +# bestNextScore = max(bestNextScore, nextScore) +# +# # Check for race +# return bestNextScore + humanScore +# +# if elephant.playing(time): +# for nextElephant in nodes: +# if nextElephant in visited: +# continue +# let +# nextTimeElephant = time - 1 - neighborsElephant[nextElephant] +# nextTime = max(human.time, nextTimeElephant) +# nextScore = dfs(union(visited, toHashSet(@[elephant.valv])), nextTime, human, (nextElephant, nextTimeElephant)) +# bestNextScore = max(bestNextScore, nextScore) +# +# # Check for race +# return bestNextScore + elephantScore +# +# assert(false) +# +# proc solve(initDelays: Table[string, int], time: int): int = +# +# if not part2: +# for human in nodes: +# let +# humanStartTime = time - initDelays[human] +# startTime = humanStartTime +# result = max(result, dfs(initHashSet[string](), startTime, (human, humanStartTime), (human, -1))) +# else: +# for i, human in nodes[0 ..< ^1]: +# for elephant in nodes[i+1 .. ^1]: +# let +# elephantStartTime = time - initDelays[elephant] +# humanStartTime = time - initDelays[human] +# startTime = max(elephantStartTime, humanStartTime) +# result = max(result, dfs(initHashSet[string](), startTime, (human, humanStartTime), (elephant, elephantStartTime))) +# +# let content = readFile("./example.txt") - let input = parseFile(content) -Graph = setup(input) -# Table of delays to get from starting node "AA" to current -let initDelays = Graph["AA"].neighbors -Graph.del("AA") - -for node in Graph.keys(): - nodes.add(node) - -echo solve(initDelays, 30) -part2 = true -echo solve(initDelays, 26) +echo input + +# # Table of delays to get from starting node "AA" to current +# let initDelays = Graph["AA"].neighbors +# Graph.del("AA") +# +# for node in Graph.keys(): +# nodes.add(node) +# +# echo solve(initDelays, 30) +# part2 = true +# echo solve(initDelays, 26) -- cgit v1.2.3