I genuinly need help. Deadline is duea 4 hours - Pathfinding

[vague laurel]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

[void nest]

The "magic" is what you are supposed to perform. 🤷‍♂️

[pliant nimbus]

I know. If you want I can show yoiu my code

I already performed a lot of magic as ive been working on it since yesterday 4am. Now its 4am again and i have a redbull in me

Sample input:
4 3 R x S = rows x cols
1 0 1 3 Startx, Starty, Endx, Endy - x = col, y = row
1 1 1 2D grid of R x S with int values representing height of the cell
1 6 1
9 7 1
1 1 1

Sample output:
6 length of the longest route
1 0 coordinates of the route X, Y = col, row
1 1
1 2
0 2
1 2
1 3

[void nest]

This is a pathfinding task, so learn about pathfinding algorithms.

[pliant nimbus]

problem is that i solved it. Using DFS but its too slow since inputs can be very large R x S = 700 x 700

@void nest do you want to see my solution? Perhaps you can optimise it or tell me how to optimise it

so that it works faster at least

But ideally you would explain DAG and topological sort because that can perhaps be the solution

[void nest]

How to optimize it is to learn about pathfinding algorithms.

I won't explain them to you from the beginning either, because there are already plenty of resources online.

[trim copper]

DFS is O(n+m), and the input size seems small to me, so idk why you'd encounter "too slow"

dfs seems reasonable tbh

[pliant nimbus]

I can show you the algorithm and you tell me why it sucks. Please

I genuinly have been working on it whole night. Its 4am and i just want to finish it

[trim copper]

just post

i suspect your dfs is wrong. but also i don't understand the problem, with cell heights, versus a maze

[pliant nimbus]

My implementation of DFS

I use a few datastructures most notably LowerHigherDict.

I made it as recursive but remade it into this. I like it less but apparently it should run but faster. Not that I noticed anything

[trim copper]

this feels like a lot of code for DFS. also you're likely copying things all over the place with get(stack.top()) and stack.push

[pliant nimbus]

Thats caused by the constraints. And the copying should be imporved indeed

Obvioudly im not saying it cant be imporved. Thats why im here

If you see room for imporvement now is your time to say it

[trim copper]

learn about move vs copy in C++

[pliant nimbus]

I know how to use it. Just dont use it often, or at all'

[trim copper]

I think especially with whatever route is, you wanna avoid copying it each iteration, which I think you're doing

[pliant nimbus]

Will fix this right away

And when it commes to the algorithm, do you see any problems why its taking me so damn long?

I think I had to screw something up which makes the complexity worse than it should be

[vague laurel]

sbdswr /good orc is dead orc/

We Don't Do Your Homework

Welcome to Together C & C++ :wave:

We won't do your homework for you (#rules) but we are happy to help you learn and point you in the right direction.

Please send what you have so far and ask a specific question.

[spark shale]

I mean just because no one seem to said that

making a pressure with "a deadline is coming, help me now!" rather does not increase chances

[trim copper]

idk does it really count as doing the hw if it's cpp move/copy semantics that's causing his bad runtime vs the actual graph algo

[spark shale]

(I've also seen people trying to tell a stories about a bad live, low income, getting kicked from uni if not solving something, etc)

[spark shale]

I having been following all the details that closely, that was mostly regarding OP

any suggestion that OP can implement themselves is of course perfect

[trim copper]

tbh my brain isn't ready to read and understand this atm. but like, if you are copying a route which is idk, O(n), each iteration which there's O(n+m), that's quite a bit more than just dfs runtime

[pliant nimbus]

Its 4am. I am just saying plain truth and hoping for the best. 😄

[pliant nimbus]

i see

[pliant nimbus]

Awesoe

any other things you noticed about my code?

That slow things down? So far the time gain hasnt been huge. I think there has to be something small perhaps

[pliant nimbus]

I genuinl yidk what makes my alg so slow

@trim copper hey are you still here? I improved it a small bit but its still too slow. Can you hep? I think the problem is on algorithmic level. I looked at the algorithms profile while running and seemed normal.

[empty fiber]

Tbf, this isn’t like there’s a lack of effort

Assuming what he’s saying is true

[pliant nimbus]

Update: I solved the problem using python. Idk how but python is faster?????? wut ????