As seen on The Independent 📰✨💞 — (discuss)

Donate

Contact Us
Sign In
Sign Up
Top Poster of the Day:

Spiderman

Current Registered Users: 27,896

40% Vaxxed 37% Infected

tech/science swag.
Effortposts made by SN Chads
Guidelines:
What to Submit
On-Topic: Anything that good slackers would find interesting. That includes more than /g/ memes and slacking off. If you had to reduce it to a sentence, the answer might be: anything that gratifies one's intellectual laziness.
Off-Topic: Most stories about politics, or crime, or sports, unless they're evidence of some interesting new phenomenon. Videos of pratfalls or disasters, or cute animal pictures. If they'd cover it on TV news, it's probably lame.
Help keep this hole healthy by keeping drama and NOT drama balanced. If you see too much drama, post something that isn't dramatic. If there isn't enough drama and this hole has become too boring, POST DRAMA!
In Submissions
Please do things to make titles stand out, like using uppercase or exclamation points, or saying how great an article is. It should be explicit in submitting something that you think it's important.
Please don't submit the original source. If the article is behind a paywall, just post the text. If a video is behind a paywall, post a magnet link. Fuck journos.
Please don't ruin the hole with chudposts. It isn't funny and doesn't belong here. THEY WILL BE MOVED TO /H/CHUDRAMA
If the title includes the name of the site, please leave that in, because our users are too stupid to know the difference between a url and a search query.
If you submit a video or pdf, please don't warn us by appending [video] or [pdf] to the title. That would be r-slurred. We're not using text-based browsers. We know what videos and pdfs are.
Make sure the title contains a gratuitous number or number + adjective. Good clickbait titles are like "Top 10 Ways to do X" or "Don't do these 4 things if you want X"
Otherwise editorialize. Please don't use the original title, unless it is gay or r-slurred, or you're shits all fucked up.
If you're going to post old news (at least 1 year old), please flair it so we can mock you for living under a rock, or don't and we'll mock you anyway.
Please don't post on SN to ask or tell us something. Send it to [email protected] instead.
If your post doesn't get enough traction, try to delete and repost it.
Please don't use SN primarily for promotion. It's ok to post your own stuff occasionally, but the primary use of the site should be for curiosity. If you want to astroturf or advertise, post on news.ycombinator.com instead.
Please solicit upvotes, comments, and submissions. Users are stupid and need to reminded to vote and interact. Thanks for the gold, kind stranger, upvotes to the left.
In Comments
Be snarky. Don't be kind. Have fun banter; don't be a dork. Please don't use big words like "fulminate". Please sneed at the rest of the community.
Comments should get more enlightened and centrist, not less, as a topic gets more divisive.
If disagreeing, please reply to the argument and call them names. "1 + 1 is 2, not 3" can be improved to "1 + 1 is 3, not 2, mathfaggot"
Please respond to the weakest plausible strawman of what someone says, not a stronger one that's harder to make fun of. Assume that they are bad faith actors.
Eschew jailbait. Paedophiles will be thrown in a wood chipper, as pertained by sitewide rules.
Please post shallow dismissals, especially of other people's work. All press is good press.
Please use Slacker News for political or ideological battle. It tramples weak ideologies.
Please comment on whether someone read an article. If you don't read the article, you are a cute twink.
Please pick the most provocative thing in an article or post to complain about in the thread. Don't nitpick stupid crap.
Please don't be an unfunny chud. Nobody cares about your opinion of X Unrelated Topic in Y Unrelated Thread. If you're the type of loser that belongs on /h/chudrama, we may exile you.
Sockpuppet accounts are encouraged, but please don't farm dramakarma.
Please use uppercase for emphasis.
Please post deranged conspiracy theories about astroturfing, shilling, bots, brigading, foreign agents and the like. It degrades discussion and is usually mistaken. If you're worried about abuse, email [email protected] and dang will add you to their spam list.
Please don't complain that a submission is inappropriate. If a story is spam or off-topic, report it and our moderators will probably do nothing about it. Feed egregious comments by replying instead of flagging them like a pussy. Remember: If you flag, you're a cute twink.
Please don't complain about tangential annoyances—things like article or website formats, name collisions, or back-button breakage. That's too boring, even for HN users.
Please seethe about how your posts don't get enough upvotes.
Please don't post comments saying that rdrama is turning into ruqqus. It's a nazi dogwhistle, as old as the hills.
Miscellaneous:
We reserve the right to exile you for whatever reason we want, even for no reason at all! We also reserve the right to change the guidelines at any time, so be sure to read them at least once a month. We also reserve the right to ignore enforcement of the guidelines at the discretion of the janitorial staff. This hole is a janny playground, participation implies enthusiastic consent to being janny abused by unstable alcoholic bullies and loser nerds who have nothing better to do than banning you for any reason or no reason whatsoever.
[[[ To any NSA and FBI agents reading my email: please consider ]]]
[[[ whether defending the US Constitution against all enemies, ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]
BROWSE EFFORTPOSTS SITE GUIDE DIRECTORY Emojis & Art | Info Megathreads HOLES PING GROUPS
/h/slackernews SETTINGS /h/slackernews LOG /h/slackernews MODS /h/slackernews EXILEES /h/slackernews FOLLOWERS /h/slackernews BLOCKERS

Live commit: 4946005

/h/slackernews

ghosterator200 VAX/MAXXED 1yr ago (text post) Edited 1yr ago 385 thread views #131849

day 16 aoc thread: the np is complete

this is travelling salesmen, eh? i'm pretty sure at least.

Block /h/slackernews

Jump in the discussion.

No email address required.

View entire discussion

ihsoy jew/jew

1yr ago #3254176 Edited 1yr ago

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);
}

4 Context

longpostbot tl/dr DIDN'T READ LOL! Go essaypost elsewhere. :marseyexciteddance:

ihsoy 1yr ago #3254177

Mommy is soooo proud of you, sweaty. Let's put this sperg out up on the fridge with all your other failures.

1 Context

everyone who/whom 7 legs of love :marseyspider:

ihsoy 1yr ago #3254274

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...

LMAO same. Though I got lucky in that the thing told me that my answer is too high, so it must've been a bug and not a wrong algorithm, and I was lowkey bothered by writing the code that extracted starting node name from the first node without an explicit instruction to do so, so it was on my mind, so I immediately reread the task and oh shit.

I solve part two simply by running it in serial, apparently that gives the same result as if they were ran in parallel.

Neat!

2 Context

Current Registered Users: 27,896

40% Vaxxed 37% Infected

tech/science swag. :marscientist:

Effortposts made by SN Chads

Guidelines:

What to Submit

On-Topic: Anything that good slackers would find interesting. That includes more than /g/ memes and slacking off. If you had to reduce it to a sentence, the answer might be: anything that gratifies one's intellectual laziness.

Off-Topic: Most stories about politics, or crime, or sports, unless they're evidence of some interesting new phenomenon. Videos of pratfalls or disasters, or cute animal pictures. If they'd cover it on TV news, it's probably lame.

Help keep this hole healthy by keeping drama and NOT drama balanced. If you see too much drama, post something that isn't dramatic. If there isn't enough drama and this hole has become too boring, POST DRAMA!

In Submissions

Please do things to make titles stand out, like using uppercase or exclamation points, or saying how great an article is. It should be explicit in submitting something that you think it's important.

Please don't submit the original source. If the article is behind a paywall, just post the text. If a video is behind a paywall, post a magnet link. Fuck journos.

Please don't ruin the hole with chudposts. It isn't funny and doesn't belong here. THEY WILL BE MOVED TO /H/CHUDRAMA

If the title includes the name of the site, please leave that in, because our users are too stupid to know the difference between a url and a search query.

If you submit a video or pdf, please don't warn us by appending [video] or [pdf] to the title. That would be r-slurred. We're not using text-based browsers. We know what videos and pdfs are.

Make sure the title contains a gratuitous number or number + adjective. Good clickbait titles are like "Top 10 Ways to do X" or "Don't do these 4 things if you want X"

Otherwise editorialize. Please don't use the original title, unless it is gay or r-slurred, or you're shits all fucked up.

If you're going to post old news (at least 1 year old), please flair it so we can mock you for living under a rock, or don't and we'll mock you anyway.

Please don't post on SN to ask or tell us something. Send it to [email protected] instead.

If your post doesn't get enough traction, try to delete and repost it.

Please don't use SN primarily for promotion. It's ok to post your own stuff occasionally, but the primary use of the site should be for curiosity. If you want to astroturf or advertise, post on news.ycombinator.com instead.

Please solicit upvotes, comments, and submissions. Users are stupid and need to reminded to vote and interact. Thanks for the gold, kind stranger, upvotes to the left.

In Comments

Be snarky. Don't be kind. Have fun banter; don't be a dork. Please don't use big words like "fulminate". Please sneed at the rest of the community.

Comments should get more enlightened and centrist, not less, as a topic gets more divisive.

If disagreeing, please reply to the argument and call them names. "1 + 1 is 2, not 3" can be improved to "1 + 1 is 3, not 2, mathfaggot"

Please respond to the weakest plausible strawman of what someone says, not a stronger one that's harder to make fun of. Assume that they are bad faith actors.

Eschew jailbait. Paedophiles will be thrown in a wood chipper, as pertained by sitewide rules.

Please post shallow dismissals, especially of other people's work. All press is good press.

Please use Slacker News for political or ideological battle. It tramples weak ideologies.

Please comment on whether someone read an article. If you don't read the article, you are a cute twink.

Please pick the most provocative thing in an article or post to complain about in the thread. Don't nitpick stupid crap.

Please don't be an unfunny chud. Nobody cares about your opinion of X Unrelated Topic in Y Unrelated Thread. If you're the type of loser that belongs on /h/chudrama, we may exile you.

Sockpuppet accounts are encouraged, but please don't farm dramakarma.

Please use uppercase for emphasis.

Please post deranged conspiracy theories about astroturfing, shilling, bots, brigading, foreign agents and the like. It degrades discussion and is usually mistaken. If you're worried about abuse, email [email protected] and dang will add you to their spam list.

Please don't complain that a submission is inappropriate. If a story is spam or off-topic, report it and our moderators will probably do nothing about it. Feed egregious comments by replying instead of flagging them like a pussy. Remember: If you flag, you're a cute twink.

Please don't complain about tangential annoyances—things like article or website formats, name collisions, or back-button breakage. That's too boring, even for HN users.

Please seethe about how your posts don't get enough upvotes.

Please don't post comments saying that rdrama is turning into ruqqus. It's a nazi dogwhistle, as old as the hills.

Miscellaneous:

We reserve the right to exile you for whatever reason we want, even for no reason at all! We also reserve the right to change the guidelines at any time, so be sure to read them at least once a month. We also reserve the right to ignore enforcement of the guidelines at the discretion of the janitorial staff. This hole is a janny playground, participation implies enthusiastic consent to being janny abused by unstable alcoholic bullies and loser nerds who have nothing better to do than banning you for any reason or no reason whatsoever.

[[[ To any NSA and FBI agents reading my email: please consider ]]]

[[[ whether defending the US Constitution against all enemies, ]]]

[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

BROWSE EFFORTPOSTS SITE GUIDE HOLES PING GROUPS
/h/slackernews SETTINGS /h/slackernews LOG /h/slackernews MODS /h/slackernews EXILEES /h/slackernews FOLLOWERS /h/slackernews BLOCKERS

Live commit: 4946005

Link copied to clipboard

Action successful!

Error, please refresh the page and try again.

day 16 aoc thread: the np is complete

Jump in the discussion.

Jump in the discussion.

Jump in the discussion.

More options

Jump in the discussion.

More options

More options

Top Poster of the Day: Spiderman

Current Registered Users: 27,896

Guidelines:

What to Submit

In Submissions

In Comments

Miscellaneous:

Top Poster of the Day:

Spiderman