Advent of Code | Turing Complete | Page 2

radiant pilot Dec 14, 2022, 5:39 AM

#

my sleep schedule is fucked enough

#

I did the parsing and wrote a function to check the extremal coordinates so I could see if the naive algorithm would be enough for part 1 and ||it turns out it totally would be so I'll do that tomorrow and then cry when it's not enough for part 2||

#

I have an idea for a not-naive algorithm but

flint tinsel Dec 14, 2022, 5:41 AM

#

part 2 isnt that hard lol

radiant pilot Dec 14, 2022, 5:41 AM

#

lol ofc you're done with p1 already

flint tinsel Dec 14, 2022, 5:42 AM

#

lmao check the leaderboards

radiant pilot Dec 14, 2022, 5:42 AM

#

ya 3000 people done

#

did you just copy from 2018/17 or did you have to implement it?

#

maybe im missing something with the not-naive idea I have cuz it seems tricky to implement

#

maybe i'll have an insight when its not midnight

#

I have a presentation to prepare for tomorrow anyway so I can't get too distracted by this tonight sadly :/

flint tinsel Dec 14, 2022, 5:43 AM

#

wouldve taken me longer to figure out what i did 4 years ago than to reimplement it, naive solution should be enough here

#

oh the message isnt pinned

#

#1048377654061047858 message

muted wharf Dec 14, 2022, 6:33 AM

#

radiant pilot Dec 14, 2022, 6:41 AM

#

flint tinsel wouldve taken me longer to figure out what i did 4 years ago than to reimplement...

Ok that's reassuring, I'll do it tmrw

radiant pilot Dec 14, 2022, 9:18 PM

#

did you actually look at your map?

#

this is a slice of mine lmao

thorn surge Dec 14, 2022, 9:29 PM

#

Mine had some of ``` #####

                       ##### #####


                    ##### ##### #####


                 ##### ##### ##### #####


              ##### ##### ##### ##### #####


          ######

       ###### ######

    ###### ###### ######

 ###### ###### ###### ######

###### ###### ###### ######``` Strangest cave I've seen.

thorn ibex Dec 14, 2022, 9:30 PM

#

That's not mine but it's nice so I share:

radiant pilot Dec 14, 2022, 9:51 PM

#

thorn surge Mine had some of ``` ##### ...

mine has a pile of this at the bottom

flint tinsel Dec 15, 2022, 5:33 AM

#

wasted half an hour because i forgot the numbers could be negative ._.

radiant pilot Dec 15, 2022, 5:38 AM

#

??? all of mine are very positive

#

I take it back, there is a single negative number

#

thanks

flint tinsel Dec 15, 2022, 5:47 AM

#

dafaq how did i make it in top 1000 for part 2 despite wasting so much time in part 1 lol

flint tinsel Dec 15, 2022, 5:47 AM

#

radiant pilot I take it back, there is a single negative number

watch out for the single beacon that's at y=2e6 lol

radiant pilot Dec 15, 2022, 5:47 AM

#

scheme has arbitrary precision numbers but thanks

flint tinsel Dec 15, 2022, 5:50 AM

#

i meant the answer should be 1 lower than what your program outputs, if you didnt take into account that beacon

#

thats the other gotcha that tripped me up

radiant pilot Dec 15, 2022, 5:55 AM

#

oh you mean because it's in the row

#

yes I was accounting for that

#

I didn't connect 2e6 with the not-scientific-notation for 2mil

radiant pilot Dec 15, 2022, 6:46 AM

#

my algorithm for part 2 had so many bugs.

#

First it was off-by-one errors. Then it was adding when I should've been overwriting. Then it was being too greedy with assuming that ||any improvement would be enough as opposed to having to work harder to get the best possible point to skip to||

#

I mean i'm asking for it by programming at 1 am

#

but

#

still comfortably top 3000, which says a lot about the difficulty of part 2 I guess

#

I think as a curiosity I'd like to implement inversion lists, they are directly applicable to this problem and lead to a very fast algorithm for both parts

flint tinsel Dec 15, 2022, 6:57 AM

#

inversion lists would have to be non-overlapping

radiant pilot Dec 15, 2022, 6:59 AM

#

the algorithm for taking the union of two inversion lists ensures that

#

wouldn't be a very useful representation of sets otherwise

flint tinsel Dec 15, 2022, 7:00 AM

#

the problem has overlapping intervals though, dunno how you would account for that

radiant pilot Dec 15, 2022, 7:13 AM

#

compute the (simple) interval associated with each sensor in a particular row, take the union of all of those

flint tinsel Dec 15, 2022, 7:24 AM

#

oh, i thought it was a way more optimized algorithm lol

radiant pilot Dec 15, 2022, 7:25 AM

#

i mean inversion lists are asymptotically optimal for what they do

flint tinsel Dec 15, 2022, 7:36 AM

#

i have a solution in O(n^2 logn) time where n=#sensors

radiant pilot Dec 15, 2022, 7:40 AM

#

The runtime of my solution depends on the actual density of coverage (but it runs instantly so)

#

Inversion lists would be O(n) in the number of sensors

#

The multi-union might actually be nlogn

flint tinsel Dec 15, 2022, 7:49 AM

#

wait, are you talking about part 1 or 2 here?

radiant pilot Dec 15, 2022, 7:59 AM

#

2

flint tinsel Dec 15, 2022, 8:17 AM

#

would be interesting to see how fast your code runs then, got mine down to 12ms

radiant pilot Dec 15, 2022, 8:20 AM

#

I didn't try to optimize further, my general AOC feeling is if i have to wait long enough for the answer that i can react to the fact it hasn't shown up yet, it's too slow

#

(I'm not at my computer anymore)

thorn ibex Dec 15, 2022, 12:41 PM

#

for part 2 || I've just run part 1 for every y and keep the only line with two intervals (I was merging intervals for part 1) ||

#

Btw I didn't have to subtract 1 for part 1 as no beacon where on my line

flint tinsel Dec 15, 2022, 2:19 PM

#

that's what I initially did too

urban lagoon Dec 16, 2022, 2:05 AM

#

I think I might be a few days behind

elder bane Dec 16, 2022, 4:16 AM

#

I feel like I could do Day 15 by hand...

urban lagoon Dec 16, 2022, 4:18 AM

#

just do it in desmos

#

the correct answer to day 15 is to get better scanners obviously

elder bane Dec 16, 2022, 4:24 AM

#

Well, even given just a distance and the devices knowing their location, you could triangulate the position with three in 2D, or four in 3D.

radiant pilot Dec 16, 2022, 4:29 AM

#

im sure part 1 could be done by hand. gfl on part 2 tho

urban lagoon Dec 16, 2022, 4:29 AM

#

I haven't even started day 15

#

still working on day 13

#

I have the logic done

#

(not tested but who cares about testing)

#

the input parsing is the problem

#

(also I switched to an oop solution)

elder bane Dec 16, 2022, 4:30 AM

#

Part 1: At x=2000000, how many squares will be taken up?

urban lagoon Dec 16, 2022, 4:30 AM

#

and part 2 is how many total squares I assume?

radiant pilot Dec 16, 2022, 4:34 AM

#

Answering that would be spoilers!

urban lagoon Dec 16, 2022, 4:34 AM

#

lol

#

oh uh btw

#

how bad is part 2 of day 13

elder bane Dec 16, 2022, 4:36 AM

#

urban lagoon and part 2 is how many total squares I assume?

You could do that by hand, too. He said "gfl on part 2 tho", which implies I don't wanna do it by hand.

urban lagoon Dec 16, 2022, 4:36 AM

#

maybe it's some kind of product mess?

elder bane Dec 16, 2022, 4:39 AM

#

I'm wondering if it is to do all of them...

flint tinsel Dec 16, 2022, 4:57 AM

#

elder bane Well, even given just a distance and the devices knowing their location, you cou...

it doesnt give you the distance to the uncovered tile, it gives you the distance to the closest beacon

#

triangulation wont work here, since its perfectly valid to have 3 sensor-beacon pairs that dont cover each other's ranges at all

elder bane Dec 16, 2022, 1:37 PM

#

Yep. My solution idea for Day 15 is to crunch some numbers.

radiant pilot Dec 16, 2022, 1:54 PM

#

Yeah part 1 is just some math. Interval merging is optimal but just actually computing the set of points covered is very fast too

thorn surge Dec 16, 2022, 10:29 PM

#

I've hit a brick wall in AoC day 16 part 1. While I can solve the example input, the puzzle input is taking too long. After taking a peek at reddit || it appears that people are using DFS to find the optimal path in under a second. I've left my implementation running for over 15 minutes, until I cancelled it. I'd prefer to figure this out with resorting to reading other peoples code, but I have no idea what I might be getting wrong. Clearly my O(n_valves !) algo is bonkers, even after some short cutting.||

radiant pilot Dec 16, 2022, 10:34 PM

#

I haven't done day 16 yet, but i was going to now. Unfortunately I forgot to put my code on GitHub before I left Montreal so I've lost my AOC library that I've been adding to over the month.

thorn surge Dec 16, 2022, 10:56 PM

#

It's too late for me to do any more - hopefully tomorrow is nicer for me.

muted wharf Dec 16, 2022, 10:56 PM

#

thorn surge I've hit a brick wall in AoC day 16 part 1. While I can solve the example input...

||If you are doing DFS, how are you getting O(n_valves!) ?||

#

||If you visit a valve, you can store what happened till now, you don't need to revisit a node||

thorn surge Dec 16, 2022, 10:59 PM

#

|| There are n_valves! possible paths, I don't see how to reduce that number significantly.||

elder bane Dec 16, 2022, 11:03 PM

#

thorn surge || There are n_valves! possible paths, I don't see how to reduce that number sig...

You can reduce n by a bit of handwork. Each valve whose flow=0, you can prune off.

#

Then you could run it in less time...

thorn surge Dec 16, 2022, 11:15 PM

#

Yes, I'm already ||examining only the rooms with non-zero valves.||

elder bane Dec 16, 2022, 11:18 PM

#

Even the worst algorithm I can think of only runs in O(2^x) time...

radiant pilot Dec 16, 2022, 11:19 PM

#

In a tree with n nodes and e edges, there are significantly fewer than n! Paths

thorn surge Dec 16, 2022, 11:23 PM

#

Moving through e.g. {A, B, C}, has you can visit them as ABC, ACB, BAC, or BCA etc, which is 3! (perhaps "paths" is not the correct technical term?)

muted wharf Dec 16, 2022, 11:23 PM

#

thorn surge Moving through e.g. {A, B, C}, has you can visit them as ABC, ACB, BAC, or BCA e...

That is not 3!

#

And also, that doesn'T account for edges

thorn surge Dec 16, 2022, 11:25 PM

#

huh? n options for the choice of the first node, then (n-1) for the next, etc? I think we're getting to the centre of my confusion. I don't see how number of edges affects this.

#

I don't have a tree of valves, not clear how I'd transform this into one?

muted wharf Dec 16, 2022, 11:32 PM

#

thorn surge huh? n options for the choice of the first node, then (n-1) for the next, etc? I...

Can you visit the nodes in any order?

thorn surge Dec 16, 2022, 11:35 PM

#

Yes, you can activate the valves in any order.

muted wharf Dec 16, 2022, 11:37 PM

#

Sure, but is any order sensible?

#

Also, you very much have a graph of valves

thorn surge Dec 16, 2022, 11:39 PM

#

That might the the insight I need, I'll think on it.

#

Graph, yes, tree, no.

elder bane Dec 16, 2022, 11:46 PM

#

I'm only thinking of a multi-linked list that I can traverse...
Breadth-First, though.

muted wharf Dec 16, 2022, 11:58 PM

#

elder bane I'm only thinking of a multi-linked list that I can traverse... Breadth-First, t...

... That's a graph

elder bane Dec 17, 2022, 12:06 AM

#

...You'd actually have a multi-graph (a vertex connected multiple times to another vertex).
Breadth-first, while being wildly inefficient, can tell you exactly where you'll be in 30 moves.

muted wharf Dec 17, 2022, 12:07 AM

#

elder bane ...You'd actually have a multi-graph (a vertex connected multiple times to anoth...

From what I can see it's not a multi graph, it's just a directed graph were all back edges are added in anyway

radiant pilot Dec 17, 2022, 12:36 AM

#

I possibly see what you're missing. ||The DFS is not searching the graph.||

#

Imagine the input graph

   AA:0
  /    \
BB:1  CC:1

thorn ibex Dec 17, 2022, 12:54 AM

#

DFS is O(V + E) so very fast

#

you are doing brute force, not DFS

#

btw I havn't done day 16 yet

thorn surge Dec 17, 2022, 12:57 AM

#

The tree I'm searching has over n! nodes, so I'm looking at the wrong tree.

thorn ibex Dec 17, 2022, 12:58 AM

#

It looks like || DFS is not the solution, but maybe only a step to compute the graph of the non-zero valves, and the brute force should only branch between non-zero valves ||

#

But in that case || DFS is not the right choice I think, it must be a Dijkstra like to compute the minimum path between the current valve and the next non-zero one||

thorn surge Dec 17, 2022, 1:08 AM

#

I used || Floyd–Warshall || for that.

thorn ibex Dec 17, 2022, 1:10 AM

#

yep and even with that the brute force is too long?

#

I'll do it tomorrow

#

btw I searched a bit and in english it's called || https://en.wikipedia.org/wiki/Backtracking I don't think a DFS would be useful in that problem, don't know where you found that||

Backtracking

Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.The classic textbook exam...

radiant pilot Dec 17, 2022, 1:22 AM

#

"DFS" is commonly used in english interchangeably with that term.

#

it's a DFS over ||the search space||

elder bane Dec 17, 2022, 3:53 AM

#

thorn surge The tree I'm searching has over n! nodes, so I'm looking at the wrong tree.

Yes, you are. It should be at most exponential with respect to n.

flint tinsel Dec 17, 2022, 4:14 AM

#

good enough >_>

radiant pilot Dec 17, 2022, 4:52 AM

#

someone on the haskell sub says the greedy algorithm solved his part 2

#

which is so unfair

#

for me it gives a (surprisingly close but) incorrect answer

#

but the sort of naive extension of part 1 did work, it just takes like 15s

#

part 1 is pretty much instantaneous

#

OTOH the new one seems easy enough.

flint tinsel Dec 17, 2022, 6:34 AM

#

got into top 100 today, yay

thorn ibex Dec 17, 2022, 10:35 AM

#

thorn ibex I'll do it tomorrow

day 16 part 1 ~~under 10ms (not reliable)~~ I was using the example data set, 1.4s now.
with Clojure, without trying to optimize, but as Clojure is natively immutable backtracking algorithms are fast

#

Using || Floyd-Warshall + backtracking on non-zeros valves ||

radiant pilot Dec 17, 2022, 10:30 PM

#

Very curious what ||periods and offsets|| you guys had today. My ||period is quite large|| but on the subreddit I see some people who have ||very small ones||.

flint tinsel Dec 17, 2022, 10:31 PM

#

mine was ||period=1745||

radiant pilot Dec 17, 2022, 10:32 PM

#

For the record, mine was ||period=3500||

#

Someone on the subreddit is saying theirs was ||period=35|| unless I'm really misunderstanding their code.

flint tinsel Dec 17, 2022, 10:33 PM

#

that feels incredibly unlikely

radiant pilot Dec 17, 2022, 10:33 PM

#

i know

#

he ||adds the height difference every time a rock stops|| and found ||period over that data||

flint tinsel Dec 17, 2022, 10:34 PM

#

lmao a huge coincidence that it worked out

radiant pilot Dec 17, 2022, 10:34 PM

#

but something about the jupyter notebook its in doesn't make sense because ||some of those differences are big, like >200, but obviously the most possible is 3. And yet nowhere in his code does it indicate that he drops many rocks before tracking the next difference...||

thorn surge Dec 17, 2022, 10:41 PM

#

I found a ||period of 17457430|| but compared to yours I think I may have over counted.

#

My input ||length was~~ 10092~~10091|| does that vary between people?

radiant pilot Dec 17, 2022, 10:51 PM

#

my input was one less than that

thorn surge Dec 17, 2022, 10:52 PM

#

Sorry yes, mine was too.

radiant pilot Dec 17, 2022, 10:53 PM

#

My guess is that ||however you're finding the period uses a metric for saying "yes, this is repeating" which is too strong||

thorn surge Dec 17, 2022, 11:01 PM

#

My procedure was || don't check every cycle, instead I assumed it would be a multiple of the two cycle lengths (rock*wind) so I checked that often.|| Your answer tells me that was not necessarily the case.

radiant pilot Dec 17, 2022, 11:03 PM

#

that is certainly not true, ||each rock cycle uses an inconsistent number of wind cycles||

#

well, not necessarily true, anyway.

thorn surge Dec 17, 2022, 11:08 PM

#

I wasn't trying to find ||the minimum cycle length, it just hadn't occurred to me that shorter ones would exist.|| I just made sure that I would fine one.

radiant pilot Dec 17, 2022, 11:09 PM

#

But you'll also find one if you just ||check every period until one works|| lol

#

I ||dropped the first 1000 deltas to give it time to converge|| and then ||checked every period from 10 to 5000 until one worked||

#

that all runs in less than half a second, the only slow part is generating ||enough deltas||

thorn surge Dec 17, 2022, 11:10 PM

#

True, that would have been quicker, but I also had no idea ||when it would become periodic.||

flint tinsel Dec 18, 2022, 6:03 AM

#

another easy one today lol

urban lagoon Dec 18, 2022, 6:05 AM

#

"easy"

#

I probably shouldn't've even attempted AoC lol

#

it wasn't that bad until day 8

radiant pilot Dec 18, 2022, 6:38 AM

#

part 1 was easy, part 2 looks also easy but im pretty tired so itll take me a while

#

||I'm thinking complement the input w.r.t. the bounding box; delete everything that can be reached from 0,0,0; use p1 solution to compute the surface area of the result and subtract it from the p1 result. If that's not right then I can also iterate that and PIE says it'll be correct once the complement set is empty||

radiant pilot Dec 18, 2022, 7:16 AM

#

Nope, no issue. ||No mean solid things inside air pockets. I was fully expecting there to be some.||

#

I did waste about 15 minutes because I accidentally named a global variable min in my repl and couldn't figure out why all my functions broke when I reloaded the source file into the repl...

#

@urban lagoon this one really is easy (not "is really easy," though). The last two days were quite a difficulty spike for sure, but today's is back to reasonable levels. You can do it!

urban lagoon Dec 18, 2022, 7:39 AM

#

wait

#

it actually is really easy

#

||if 2 cubes share 2 coords then they are connected||

#

||then, subtract one from the number of connected cubes, multiply it by 2, and subtract that from the number of cubes multiplied by 6||

#

oh btw I still haven't gotten 11 working

#

I really don't know what's wrong with it

radiant pilot Dec 18, 2022, 7:45 AM

#

That algorithm sounds n^2 and nlogn is possible (effectively just n)

urban lagoon Dec 18, 2022, 7:45 AM

#

idc if it's n^2

radiant pilot Dec 18, 2022, 7:46 AM

#

But sure it should work i think

urban lagoon Dec 18, 2022, 7:46 AM

#

this computer is fast enough to do it in 10 seconds

#

(I think)

thorn surge Dec 18, 2022, 7:15 PM

#

radiant pilot That algorithm sounds n^2 and nlogn is possible (effectively just n)

|| O(n) is also possible.||

radiant pilot Dec 18, 2022, 8:43 PM

#

How? I'm not sure I believe that.

#

||Hashmaps are O(n log n).||

thorn surge Dec 18, 2022, 8:46 PM

#

I'm talking about day 18, ||data can be stored in a 3D array. I only used a hash based store cause I was too lazy to set up the array.||

#

In case I got my wires crossed about which day we're talking.

radiant pilot Dec 18, 2022, 8:48 PM

#

Oh. I mean, sure, that takes a lot more space though

#

but yeah, of course

#

🤦‍♂️

flint tinsel Dec 19, 2022, 10:12 PM

#

everyone's having trouble with today's problem?

urban lagoon Dec 19, 2022, 10:39 PM

#

flint tinsel everyone's having trouble with today's problem?

it's basically factory optimization

#

which very much seems like a job for an AI

flint tinsel Dec 19, 2022, 11:17 PM

#

it's definitely do-able under a second via tree search with some aggressive pruning

#

and i kinda doubt AI would get the optimal path

urban lagoon Dec 19, 2022, 11:21 PM

#

I was hoping it'd just ask for the best blueprint, since then I could just guess

#

unfortunately not

thorn surge Dec 19, 2022, 11:23 PM

#

Since day 19 looks like it uses ||the same algorithm as day 16, I've gone back to it.||

thorn ibex Dec 19, 2022, 11:56 PM

#

flint tinsel everyone's having trouble with today's problem?

why because you had?

#

ho you looked the leaderboard

#

didn't have time to do it yet + it's ||backtracking|| again so not very fun

thorn surge Dec 19, 2022, 11:58 PM

#

Is this the right idea (in C++) for Day 16? ||``` void visit(int node, int time, int state, int flow, map<int, int> & cache) {
// Are we at a better point with the current valves turned on than last time we were at this point? if so, update value
cache[state] = std::max(cache[state], flow);
for(int next_valve = 1; next_valve < network->valve_count; next_valve++) { //For all valves
// Time remaining is time minus walking time, minus 1 minute to open valve
auto new_time = time - network->valve_dists.at(node).at(next_valve) - 1;
int valve_mask = (1 << next_valve);
if( (valve_mask & state) != 0 | | new_time <= 0 ) {
continue; // Don't go to the same valve twice, don't go to a valve if it means we run out of time.
}
// Go to new valve, update state so it's turned on, add its flow, repeat everything above.
auto new_flow = flow + (new_time * network->valve_flows.at(next_valve));
auto new_state = state | valve_mask;
visit(next_valve, new_time, new_state, new_flow, cache);
}
}

flint tinsel Dec 20, 2022, 12:15 AM

#

that looks like it should work

#

actually, that pretty much matches 80% of my alrogithm for both parts

radiant pilot Dec 20, 2022, 12:27 AM

#

The key to day 16 is reducing the search space which it looks like you've already done so yeah 👍

#

I haven't been able to look at today's sadly and probably can't until tomorrow

urban lagoon Dec 20, 2022, 12:28 AM

#

radiant pilot I haven't been able to look at today's sadly and probably can't until tomorrow

today's is basically factorio optimization

thorn surge Dec 20, 2022, 12:40 AM

#

Thank you both for the feedback. There must be something else wrong somewhere in my mess of code.

urban lagoon Dec 20, 2022, 12:40 AM

#

I'm not looking at it because spoilers

#

even though I have basically no chance at day 16

radiant pilot Dec 20, 2022, 12:51 AM

#

thorn surge Thank you both for the feedback. There must be something else wrong somewhere in...

Just in case the bug is there (idk), a clean way to write algorithms like this is to separate the tree search (visiting all nodes in a list) from the actual visit

thorn ibex Dec 20, 2022, 12:58 AM

#

thorn surge Is this the right idea (in C++) for Day 16? ||``` void visit(int node, int ti...

Hmm, network is non-zeros valves or all valves? Because it would be slow to do it on all valves.
Do the code gives you the right answer for the example?
I have just returned the max of all "sub" visits, not sure why you need a cache here
Are you sure int is 32 bits for the mask?

thorn surge Dec 20, 2022, 1:00 AM

#

It's AA and the non-zero valves only. It gives the correct answer for the example. int is at least 32 bits.

thorn ibex Dec 20, 2022, 1:01 AM

#

then can you show your floyd-warshall maybe?

#

at the end you take which value of cache? AA (first) one? The max?

thorn surge Dec 20, 2022, 1:12 AM

#

||for(auto i: rooms) { for(auto j: rooms) { // room_dists is populated as nodes are inserted. if(room_dists.count(std::pair(i.second.name, j.second.name)) == 0) { room_dists[std::pair(i.second.name, j.second.name)] = INT32_MAX; } } } for(auto k: rooms) { for(auto i: rooms) { for(auto j: rooms) { if( room_dists[std::pair(i.second.name, j.second.name)] > room_dists[std::pair(i.second.name, k.second.name)] + room_dists[std::pair(k.second.name, j.second.name)] ) { room_dists[std::pair(i.second.name, j.second.name)] = room_dists[std::pair(i.second.name, k.second.name)] + room_dists[std::pair(k.second.name, j.second.name)]; } } } } for(Valve_ID i = 0; i < valve_count; i++) { for(Valve_ID j = 0; j < valve_count; j++) { valve_dists[i][j] = room_dists[std::pair(valves[i].name, valves[j].name)]; } }||

#

I take the max of the cache, which works for the example, but it doesn't get that far with the puzzle input.

#

I haven't made a careful comparison of the output of my F-W, but it looks sensible.

#

I don't really know how to debug this - with logging there's too much, and stepping through a debugger is not very illuminating.

thorn ibex Dec 20, 2022, 1:16 AM

#

Is room_dists initialized before?

thorn surge Dec 20, 2022, 1:16 AM

#

yes as the rooms are added.

thorn ibex Dec 20, 2022, 1:16 AM

#

by value of 1s?

thorn surge Dec 20, 2022, 1:17 AM

#

yes

#

with ones for the adjacnet rooms, ~~and 0 otherwise~~ the map defaults to 0

thorn ibex Dec 20, 2022, 1:18 AM

#

why do you count room_dists?

#

instead of room_dists[std::pair(i.second.name, j.second.name)] == 0

thorn surge Dec 20, 2022, 1:20 AM

#

no good reason, I'll change that, thanks

thorn ibex Dec 20, 2022, 1:21 AM

#

else it seems ok, btw C++ syntax is horrible but I'm not used to it

thorn surge Dec 20, 2022, 1:22 AM

#

maps are a pain in C++

thorn ibex Dec 20, 2022, 1:24 AM

#

Are you sure the parsing is ok?

#

because there's a different text when it leads to one valve or several

#

but it the example there is the case too

thorn surge Dec 20, 2022, 1:26 AM

#

yes, that caught me out at first, but reading the flows and some spot checks of the room_dists, it looks good.

thorn ibex Dec 20, 2022, 1:27 AM

#

because you used INT32_MAX, do you have any overflow when doing the sum?

#

try to change to like 1000

flint tinsel Dec 20, 2022, 6:03 AM

#

okay i hope today's problem doesnt waste anyone else's 60 minutes so here's a clarification they didnt put in the prompt for some stupid reason:
if the number is greater than the length of the list, then you have to skip over the current number
e.g. [3],x,y -> x,[3],y not [3],x,y -> [3],x,y

#

incredibly dumb that they fail to mention it at all in the problem, and im demanding to speak to the manager for a refund on my hour wasted

thorn ibex Dec 20, 2022, 8:59 AM

#

I don’t understand why it wouldn’t be x,3,y?

#

3,x,y -> x,3,y -> x,y,3 -> x,3,y

#

It’s just a circular list and there are many examples with rolling numbers

flint tinsel Dec 20, 2022, 1:12 PM

#

:v what

#

oh my god I feel dumb now

#

in my defense, all the numbers in the example are small so I never see that case happening

thorn surge Dec 20, 2022, 1:17 PM

#

I've wasted so much time on the other gotcha hidden in the input.

flint tinsel Dec 21, 2022, 5:08 AM

#

ayy got rank 3 on part 2 🎉

thorn ibex Dec 21, 2022, 3:42 PM

#

and not top 100 in part 1 😛

flint tinsel Dec 21, 2022, 3:51 PM

#

lol was 109 for part 1

urban lagoon Dec 24, 2022, 6:22 AM

#

day 24 just seems exteremely memory intensive

flint tinsel Dec 24, 2022, 6:35 AM

#

I didn't use much memory

#

the blizzards positions are the same with respect to time

urban lagoon Dec 24, 2022, 6:38 AM

#

what

#

I was thinking to just generate a really big tree

#

also no

#

the blizzards' positions are not the same with respect to time

flint tinsel Dec 24, 2022, 6:39 AM

#

the tree size should be at maximum the size of your grid at each time interval

#

I meant it only changes with time lol

urban lagoon Dec 24, 2022, 6:39 AM

#

yeah

#

the idea is that ||each child represents a position of your character||

#

||if the child represents a state where you are on a wall/blizzard, discard it||

#

||your character has 5 possible actions, so each chile generates 5 more||

#

||if a child has no children, discard it||

#

||also if a state is repeated, delete it||

#

||at the end of this process, find the shortest path to a completed scenario||

urban lagoon Dec 25, 2022, 7:33 AM

#

day 25 actually seems doable

#

it's just base conversions

#

ok turns out conversion to this weird base is actually hard

urban lagoon Dec 25, 2022, 8:03 AM

#

alright part 1 is basically solved

#

nvm then

#Advent of Code

###### ###### ###### ######``` Strangest cave I've seen.