day 16 aoc thread: the np is complete

i am unbelievably filtered

Well after a lot of time trying to find the bug, i realized that we are always supposed to start at 'AA', but instead i started at the first line of the input. Literally would have been done like after like 30 minutes if I had paid attention to that...

I solve part two simply by dfs through the part once, and then if time gets to zero, i restart the dfs.

Part one ran in 661ms, Part two in 38004ms. Could most likely really speed this up by turning nodes with a flow rate of 0, into longer tunnels, but really don't care anymore.

#include <iostream>
#include <vector>
#include <utility>
#include <tuple>
#include <unordered_map>
#include <map>
#include <format>
#include <chrono>

struct input_set {
	std::vector<int64_t> flow_rates;
	std::vector<std::vector<int64_t>> tunnels;
};

input_set test_set{
	{ 0, 13, 2, 20, 3, 0, 0, 22, 0, 21 },
	{{3,8,1},{2,0},{3,1},{2,0,4},{5,3},{4,6},{5,7},{6},{0,9},{8}} 
};

input_set real_set{
	{0,0,0,0,0,0,0,19,0,0,0,0,24,7,6,8,18,14,0,0,0,0,0,0,12,0,0,0,0,0,0,0,4,0,0,0,11,17,0,0,0,0,0,0,0,0,23,0,0,16,5,0,0,0,0,15},
	{{49,14},{55,47},{12,6},{45,24},{46,41},{13,34},{2,49},{22,40},{35,13},{48,24},{36,32},{50,28},{2},{21,5,51,8,27},{18,19,0,42,30},{38,34,52,20},{22},{41,54},{50,14},{32,14},{15,36},{53,13},{7,16},{49,38},{3,52,9,39},{31,55},{32,27},{13,26},{11,53},{44,50},{14,53},{37,25},{43,10,44,19,26},{36,39},{5,15},{8,50},{20,10,33,47},{40,31},{15,23},{33,24},{37,7},{17,4},{51,14},{53,32},{32,29},{3,55},{4},{1,36},{53,9},{23,0,6},{54,18,35,11,29},{42,13},{15,24},{43,21,48,28,30},{50,17},{45,25,1}}
};

typedef std::tuple<int64_t, int64_t, int64_t, int64_t> key_type;
typedef std::map<key_type, int64_t> map_type;

int64_t dfs(int64_t location, int64_t time, int64_t turned_on, map_type& dp, const input_set& input, int runs) {
	key_type key = std::make_tuple(runs, location, time, turned_on);
	if (dp.count(key) == 1) return dp[key];

	if (time < 1) {
		if (runs > 1) return dfs(53, 26, turned_on, dp, input, runs - 1);
		else return 0LL;
	}

	auto rate = input.flow_rates[location];
	int64_t ans{0};
	// turned on is a a bitmap with a 1 at bit location, if location is turned
	// we are checking if it is not turned on
	if ((turned_on & (1LL << location)) == 0 && rate > 0) {
		int64_t turned_on_new = turned_on + (1LL << location);
		ans = (time - 1) * rate + dfs(location, time - 1, turned_on_new, dp, input, runs);
	}
	for (auto next_location : input.tunnels[location]) {
		ans = std::max(dfs(next_location, time - 1, turned_on, dp, input, runs), ans);
	}

	dp[key] = ans;
	return ans;	
}

int main()
{
	map_type dp_test;
	map_type dp;
	map_type dp_p2;

	auto a = std::chrono::high_resolution_clock::now();
	std::cout << "Test:" << dfs(0, 30, 0, dp_test, test_set, 1) << '\n';
	auto b = std::chrono::high_resolution_clock::now();
	std::cout << "Part One:" << dfs(53, 30, 0, dp, real_set, 1) << '\n';
	auto c = std::chrono::high_resolution_clock::now();
	std::cout << "Part Two:" << dfs(53, 26, 0, dp_p2, real_set, 2) << '\n';
	auto d = std::chrono::high_resolution_clock::now();

	auto ba = std::chrono::duration_cast<std::chrono::microseconds>(b - a);
	auto cb = std::chrono::duration_cast<std::chrono::microseconds>(c - b);
	auto dc = std::chrono::duration_cast<std::chrono::microseconds>(d - c);

	std::cout << std::format("TIMES: TEST: {}ms PART ONE: {}ms PART TWO: {}ms", ba, cb, dc);
}

part 1 optimized code

About 1.1s runtime on input, which is tremendous compared to early iterations of the code.

What I do is shortcut paths that take zero-flow nodes, prune those zero-flow nodes (all but AA), compute floyd-warshall and replace the actual graph by this one, which basically skips having to go to already activated nodes or travel through useless nodes. Also replaced my queue BFS with a recursive DFS since most of the BFS was spent inserting into the queue (like 89% lmao). Removed the useless dict to skip identical situations (happened literally only once ever).

Got a tip on part 2

officially filtered

im just so fricking sick of my solution working on the test input but not the real input. it's happened like 4 days in a fricking row now. how am i supposed to debug this shit?

Have a solution that works for the test case in p1, but not sure if it works with the real data or just take a bit.

The idea is basically a depth first search and some memoization to store path we have already tried.

>finally catch back up to current day with a few hours to go

>graphshit

APLsisters, this might be the end of the line.....

Goddamn this one was a fucking nightmare. I thought I was hot shit realizing that you can turn the problem into travelling salesman based on the shortest paths between all nonzero valves since you can reasonably assume you'll be beelining between them at all times, but figuring out how to adapt to multiple salesmen took me ages despite it being fairly simple in the end. Just glad I squeezed through the filter tbh.

import re

class Valve:
    def __init__(self, id, name, flow):
        self.name = name
        self.id = id
        self.flow = flow
        self.out_dir = []

foo, valves, valves_of_interest = [], [], []
start_valve = None
with open('day16_input.txt', 'r') as inp:
    foo = inp.read().split('\n')

for f in range(len(foo)):
    foo[f] = re.split(' |=', foo[f].replace(',','').replace(';',''))
    valves.append(Valve(f, foo[f][1], int(foo[f][5])))
    if foo[f][1] == 'AA':
        start_valve = valves[-1]
    elif int(foo[f][5]) > 0:
        valves_of_interest.append(valves[-1])
for f in range(len(foo)):
    for v in range(len(foo)):
        if f != v and valves[v].name in foo[f][10:]:
            valves[v].out_dir.append(valves[f])

dist = [[1000 for x in range(len(valves))] for y in range(len(valves))]
for v in valves:
    dist[v.id][v.id] = 0
    check = [v]
    n = 1
    while len(check) > 0:
        for c in range(len(check)):
            for o in check[0].out_dir:
                if dist[v.id][o.id] > n:
                    dist[v.id][o.id] = n
                    check.append(o)
            check = check[1:]
        n += 1

solutions = []
def max_pressure(current_valve, score, elapsed, visited, turn_count, record_sols):
    if record_sols:
        global solutions
        solutions.append([score, visited])
    vals = []
    for v in valves_of_interest:
        time_after = dist[current_valve.id][v.id]+elapsed+1
        if v is not current_valve and time_after <= turn_count and v.id not in visited:
            vals.append(max_pressure(v, score+(v.flow*(turn_count-time_after)), time_after, visited + [v.id], turn_count, record_sols))
    if len(vals) == 0:
        return score
    return max(vals)

print(max_pressure(start_valve, 0, 0, [], 30, False)) 

m = 0
count = 0
max_pressure(start_valve, 0, 0, [], 26, True)
for s in solutions:
    second_go = max_pressure(start_valve, s[0], 0, s[1], 26, False)
    if second_go > m:
        m = second_go
print(m)

AOC's Nipples?

Sneeds-Feeduck-And-Seeduck make an account already!

Oh boy. More CGI nonsense for mentally underdeveloped manchildren. Wonderful.

The MCU films have become an endless and risk-free pack of Taco Bell mild sauce that is slowly dumbing down moviegoers and re-calibrating what a blockbuster film can be.

Disney is a black hole swallowing everything in its path until it is the only universe we have left. I bet you dollars to donuts no one here saw Silence or The Nice Guys in theaters but borrowed their dad's Subaru so you could see Ant-Man and the Wasp opening weekend.

I come from a generation where a creative "face-swapping" blockbuster film with $100M+ budget and an R-Rating from a foreign director could get a prime wide release date and make money. Now because of infantile consoomers who routinely get excited to pay for toy commercials with DoD propaganda, budgets are being slashed, young filmmakers are selling out, legends are relegated to streaming, and less people are getting laid.

To be clear, if you're a grown adult and you're genuinely excited for a fringe piece of shit superhero movie like Spider-Man: We Brought Back the Gambling Addict Who Dates Women Half His Age, you're a goddarn useless dork.

The MCU is crack for dumb people. They got you strung out and morons just blindly line up saying “the last couple MCU flicks have been lame, but I've seen all 47 of them to this point so I better watch Man-Ant vs The Gobots vs Dr Doom!”

McDonalds is quick, easy, cheap, and completely average in every way. Sure, from time to time it hits the spot but I usually end up feeling like shit and my butt leaks for 24 hours. It's more work, more of a challenge, and sometimes can be disappointing but I'd much prefer to seek out a unique burger joint that at least will try to offer their own spin on things. I'm not 100% sure what I'll get but it might be something interesting. Now everything is built on franchise recognition and familiarity and more and more people are conceding everyday - which puts my ability to go to my kind of restaurant at risk. Companies follow the money and may offer the occasional artisan option - but if it ain't, selling it'll be replaced something easier to sell. Heck, these lazy morons don't even dine out anymore - they sit on their couch and have their compressed, shitty, and inoffensive content delivered directly to their homes.

Happy Meal fricks who justify watching a decade of toy commercials and hand every nickel to corporations who call movies “content” not realizing they're setting the rest of us up are the worst.

Watch what you want, but when I can't see something like First Reformed or Portrait of a Lady on Fire or American Animals or Only God Forgives on a big screen because the theaters have got 16 screens all playing Hawkeye vs Han Solo, I'm blaming you.