Skip to content

Latest commit

 

History

History
185 lines (139 loc) · 5.2 KB

16.md

File metadata and controls

185 lines (139 loc) · 5.2 KB
Raw

Day 16

Part 1 Part 2 Total
Time 15:56:59 >24h >24h

Yeah... I threw in the towel around 2:30 AM. Finished Part 2 on 12/19.

Part 1

DFS. Need I say more? Probably, but don't feel like it.

Ok fine. I precomputed all the shortest paths between non-zero valves. Then I did a Depth First Search of all possible paths. Instead of running the simulation minute-wise, I just skip to the minute that the valve is reached. It doesn't matter how we get to the valve, just need to know the shortest distance as there is no way taking any longer path would be better. The base cases are if we run out of time or if all non-zero valves have been visited. Then we just get the highest pressure released from all the paths we tried.

from helpers.datagetter import data_in, submit
from helpers.matrix import Matrix
import re
from collections import Counter, defaultdict
import time
import math
from tqdm import tqdm

ans = 0
din = data_in(split=True, numbers=False)

paths = {}
for line in din:
    linez = line.split(" ")
    paths[linez[1]] = [int(linez[4].split("=")[1].split(";")[0]), " ".join(linez[9:]).split(", ")]
print(paths)


def get_shortest_path(fro, to):
    queue = [[fro]]
    visited = []

    while queue:
        path = queue.pop(0)
        node = path[-1]
        if node not in visited:
            visited.append(node)
            if node == to:
                return path
            else:
                for thing in paths[node][1]:
                    queue.append(path + [thing])


# Compute distances from each node to each other node
dists = {}
for node1 in paths.keys():
    for node2 in paths.keys():
        if node1 != node2:
            dists[f"{node1}->{node2}"] = len(get_shortest_path(node1, node2))

# Get all valves of concern (where flow rate is > 0)
valves = []
for key, val in paths.items():
    if val[0] != 0:
        valves.append(key)

all_paths = {}


def dfs(curr, path, mins, pressure):
    global all_paths
    for node in valves:
        if node in path:
            continue
        new_time = mins - dists[f"{curr}->{node}"]
        if new_time <= 0:
            continue

        best_flow = pressure + new_time * paths[node][0]
        all_paths["->".join(path + [node])] = best_flow
        dfs(node, path + [node], new_time, best_flow)


dfs('AA', [], 30, 0)
ans = 0
for thing in all_paths:
    ans = max(ans, all_paths[thing])

print(ans)
submit(ans)

Part 2

This code tries all combinations of hitting all the valves. So, for my input with 15 non-zero valves, It tries (1, 14), (2, 13), etc. up to (7, 8). There is no need to check any further because you and the elephant are indistinguishable with regards to the answer.

So, I used the same code as I did in Part 1 except added a maximum number of valves into my recursive DFS and also a list of available valves. For the first person, he has all non-zero valves available, and the second player has all the non-zero valves minus the ones that the first player visited.

In all, this took 1420 seconds (or 23 minutes and 40 seconds), which is long but acceptable for me.

from helpers.datagetter import data_in, submit
import time

ans = 0
din = data_in(split=True, numbers=False)

paths = {}
for line in din:
    linez = line.split(" ")
    paths[linez[1]] = [int(linez[4].split("=")[1].split(";")[0]), " ".join(linez[9:]).split(", ")]
print(paths)


def get_shortest_path(fro, to):
    queue = [[fro]]
    visited = []

    while queue:
        path = queue.pop(0)
        node = path[-1]
        if node not in visited:
            visited.append(node)
            if node == to:
                return path
            else:
                for thing in paths[node][1]:
                    queue.append(path + [thing])


# Compute distances from each node to each other node
dists = {}
for node1 in paths.keys():
    for node2 in paths.keys():
        if node1 != node2:
            dists[f"{node1}->{node2}"] = len(get_shortest_path(node1, node2))

# Get all valves of concern (where flow rate is > 0)
valves = []
for key, val in paths.items():
    if val[0] != 0:
        valves.append(key)


def dfs_helper(a, b):
    print("Trying", a, b)
    global all_paths
    all_paths = {}
    dfs('AA', [], 26, 0, a, valves)
    all_your_paths = all_paths.copy()
    best = 0

    for thing in all_your_paths:
        all_paths = {}
        dfs('AA', [], 26, 0, b, list(set(valves) - set(thing.split("->"))))
        best = max(best, all_your_paths[thing] + max(all_paths.values()))

    return best


def dfs(curr, path, mins, pressure, length, valid):
    global all_paths, ans

    if mins <= 0 or len(path) > length - 1:
        return

    for you in valid:
        if you in path:
            continue
        new_time_you = mins - dists[f"{curr}->{you}"]
        best_flow = pressure + new_time_you * paths[you][0]

        if new_time_you > 0:
            all_paths["->".join(path + [you])] = best_flow
            dfs(you, path + [you], new_time_you, best_flow, length, valid)


start = time.time()
ans = 0
for i in range(len(valves)):
    for j in range(i, len(valves)):
        if i + j == len(valves):
            ans = max(ans, dfs_helper(i, j))
            print(time.time() - start)

print(time.time() - start)
print(ans)
submit(ans)