3 kyu
Path Finder #3: the Alpinist
1,270 of 3,193evk
Loading description...
Algorithms
View
.avif)
This comment has been reported as {{ abuseKindText }}.
Show
This comment has been hidden. You can view it now .
This comment can not be viewed.
- |
- Reply
- Edit
- View Solution
- Expand 1 Reply Expand {{ comments?.length }} replies
- Collapse
- Spoiler
- Remove
- Remove comment & replies
- Report
{{ fetchSolutionsError }}
-
-
Your rendered github-flavored markdown will appear here.
-
Label this discussion...
-
No Label
Keep the comment unlabeled if none of the below applies.
-
Issue
Use the issue label when reporting problems with the kata.
Be sure to explain the problem clearly and include the steps to reproduce. -
Suggestion
Use the suggestion label if you have feedback on how this kata can be improved.
-
Question
Use the question label if you have questions and/or need help solving the kata.
Don't forget to mention the language you're using, and mark as having spoiler if you include your solution.
-
No Label
- Cancel
Commenting is not allowed on this discussion
You cannot view this solution
There is no solution to show
Please sign in or sign up to leave a comment.
Had to learn Dijkstra's algorithm and Min Heap for this. Great kata.
The tests passed, but I keep getting this warning.
tests/Fixture.cs(125,23): warning CS0659: 'SolutionTest.RefFinder.Tup' overrides Object.Equals(object o) but does not override Object.GetHashCode()
Am I doing something wrong?
It looks like you're pushing
Tupobjects in a HashSomething, while they do not implementhashCode, so you should use something else (than the Tup objects themselves).edit: oh, that's C#, right? I thougt it was Java. The reasonning will probably the same, tho.
I have a 100 test cases pass before I hit the timeout. Just to get a sense of how close I am, how many total tests are there? 7 initial + 100 random, or much more than that?
This comment has been hidden.
It has been interesting to learn and apply graph algoritm!
Hmm. I have an A* solution that is nice and quick, and passes the vast majority of tests, but occasionally fails to produce the right answer, and when it fails the given answer is always 2 higher than the correct answer!
I've been going crazy trying to work out what the common factor is on the failed tests. Why would it always be 2 out?!
your hueristic is not good enough. the total cost between two points on a grid is not the manhatten distance, but the total differences between each two nodes on the path.
btw, a* is overkill for this kata, if you don't believe me try having getHeuristic always return 0 ;)
Thanks for the tip. I was wondering about my heuristic. I know that Heuristic algorithms need to give an answer that is below the actual path length, but I forgot that there will be occasions in this Kata where the actual cost is zero!
Following your tip I removed the heuristic, and also needed to do a little optimisation of my "find the lowest cost" search. It's still overkill, but at least it's working.
A Swift port would be welcome please. :)
Please, help. I don´t know if its a language barrier or if I'm not that familiaryzed with this kind of problem, but I can't understand what kind of data I'm recieving a what I have to find.
I'd love some help from any Rubyists here for this kata!
How do I get someone to look at my code? Do I just post it here?
Any help appreciated!
The best way to get help, if it is an option for you, would be to visit the Codewars discord server, people there might be able to help. Otherwise a good idea might be to first just post an example input which your solution currently fails, as well as the expected answer, and the actual answer your solution makes.
Hey many thanks for your reply and pointers. Sorry I didn't see it till now!
does up and down climbs count equal weight of difference if starting from 9 -> 8 -> 7 differences would be still = 3 between these?
is it the same as going from 7->8->7 differences would still be 3?
The difference would be 2 in either case.
Everything is passing on the final tests, except there is always just one of the random ones failing. Yet all the other random ones pass.
e.g. 19 random ones with maze row length up to the mid-20's will pass, then 1 maze with length similar to this will fail. And next time, a random test with maze of the same size as the previous failure will pass, but a maze of different length will fail. And the failure is always just off the mark by 1-5 ish.
(by row length, I mean N)
Something is not right here, that doesn't make sense?
I've spent ages on this, (and have learned a bunch about different sorting algorithms so I've really enjoyed doing it) but now I just really want to submit it. Is there some condition I've not covered? How do I get someone to look at my code? Do I just post it here?
Any help appreciated! I'm coding in Ruby. Thanks in advance.
that's the definition of random. No issue here. Excpet maybe a fixed test lacking. You're the only one who can help you, here: find a way to extract an input that is making your code fail, then debug your code.
Your reply is very unhelpful.
I have done exactly what you suggest many times.
Since you've most frustratingly resolved my unresolved question, I now need to open another one.
The instructions for this Discourse page say "Leave feedback or ask for help", and I am doing exactly that: asking for help.
If you don't know how to/don't want to help, I politely request you leave my question open.
Thanks.
the thing is, you didn't actually post as a question, you posted as an issue, which is a different category, and because there is no issue with the kata, it was appropriately closed
meanwhile, you were in fact given some actual help with this:
i wish you the best of luck!
Ahhh I see! I'm so sorry, I completely misunderstood why this was being closed. @Blind4Basics: my apologies!
I've updated my reposting of my question above, and made it a more generic request for help.
Thanks heaps for your help, @rowcased.
Rust translation
Available for review.
Approved
It was a nice kata! Learned in the process! Thanks evk, Thanks Hobovsky!!
trying to solve this kata in two ways, about 75% passing tests, those failing are deflected by 2 mostly, one or two are 4, don't understand what am i doing wrong!!!
Hi! I have exactly the same problem, and have just posted above. Frustrating! Did you end up figuring it out?
Ya , Alhamdulillah, i did, Inshallah you will get it too
After hours of trying to optimize my algo to pass the "timeout" error, I came to the conclusion that Javascript unshift sucks
I'm confused. My code passes all given sample tests but fails on random ones. What could be the problem?
Possibly that means your code mutates the input and then it's used to calculate the expected answer. Not sure it's the case here.
You're right. My code solves sample tests by simply moving to the right and down.I think tests should be supplemented with something like this: "110000\n"+ "010111\n"+ "010101\n"+ "011101\n"+ "000001\n"+ "000001"
There seems to be an issue with Python implementation that is working and solving on my local machine but not on the server. Can someone give me a hand? :-)
What is not working specifically, can you provide an output? Is your local version of python the same as what you have selected on codewars?
I am in a similar situation in c# in the random tests and I am also looking for an explanation for the difference. Could you post the matrix and the expected result from CW and the result calculated by you?
not an issue, a question. With close to 1000 solves in python, the problem is not on the kata side. Most likely a wrong "backtracking" or branching, or not handling ties properly, ...
Upgraded to Node v18 with
chaiClojure translation.
Please review & approve, thanks a lot!!
On the js version of this my code passes tests fine until the big mazes. Mine finishes quickly enough with my implementation but I always end up with a little bit smaller final climb round than the expected. Does anyone have any ideas why that might be?
DP is totally WRONG!
Well I'm clearly not understanding something.
Why is this supposed to be 7 climb rounds?
1
20
79
2-1 + 7-2 + 9-7 = 8 by my logic.
This comment has been hidden.
This comment has been hidden.
Adding a path might be helpful, but you can make yourself one. If you do it, your code can timeout, either because constraints or bad implementation. However, shouldn't you be able to follow your algorithm yourself? and consequently 'see' the problem?
What I was saying is : the only tests that failed were grids of size 30x30 - and hand debugging that is difficult because you have to pre-compute the optimal path. In any case, I have solved the problem now. It had to do with using heapq and breaking ties.
Nice kata, just a small hint for people who are getting timeouts: A simple depth first search of breadth first search won't work. Timeout tests are designed to eliminate them.
Well... I found this one pretty tough
This comment has been hidden.
Very nice kata, and very nice series as well
tricky description but the problem is way easier than it seems. All in all a very enjoyable kata!
Yes, the description is really not clear. I guessed the aim only thanks to the test code.
I implemeted simple Dijkstra algorithm and it works fine for little test cases. But it is not fast enough for random test. Should I try Binary heap for Dijkstra or there is a better way?
If it is faster, why not just give it a shot?
You may want to have some unit test before you refactor your code. Under a good protection, changing any implementation should be safe :)
This comment has been hidden.
spoiler flag, thx...
I think it might be helpful to add below maze to basic tests.
It would cover most/all bases apart from performance.
At the very least, it would have been for me (in C++).
707777
707007
707077
707070
707077
777007
Answer: 0
This comment has been hidden.
I passed performance and your test and still failed a very small number of tests that were too big to debug by hand but pretty small in general (like 10x10)
The way I see it, if you didn't do all the tests yet, you don't know if you pass the 'performance test'. Also 10x10 is still not too big to debug by hand. I'd follow my algorithm to see if I disagree and if I don't, look for alternative paths. Those would be small or bigger deviations from my algorithm path.
99X99 maze is the real problem. Call stack gonna crash. So cycle takes more then 12s to do it and then throws an error message. Have no idea how to do it. Because we gona check all the paths to know the shortest.
Call stack? You can get by with a call stack of 3. And no, the whole point is that you obviously shouldn't/can't try every possible path. There are better ways.
Any suggestions for debugging? My tests seem to be failing one particular type of input.
This comment has been hidden.
I didn't understand what the kata is asking me to do :(
The kata is asking you to find the least amount of climbing steps needed to walk from start to end. The "height" of cells is given in the input, and the steps needed to get from one cell to the next is their difference. This is simply a variation on a very common graph problem, the name of which should be familiar to you if you've solved the preceding katas in this series.
This comment has been hidden.
Did anyone has passed this using C#? I got TLE when at least more than 99x99 size. Or I should use such more optimize language like C++.
May I know the maximum size for test case?
This comment has been hidden.
It's way more than enough to solve that kata. If it's too slow, that means you didn't implement it correctly (using inappropriate constructs that make grow the time complexity (or at best it's constant factor) too much)
Okay i will try my best, I am kinda new to this algo :) ty for your reply though, it means I am in the right direction
This comment has been hidden.
This serial is so well designed to guide programmer to Graph searching algorithms, really nice !!!
BTW, wondering why I get
182points for a 3kyu kata ... shouldn't it be30?it's supposed to be 32 points, yes. Maybe you ranked up at the same time? reaching 2 kyu gives you 150 extra points
Yeah, that's the case.
I want to like this kata. But I don't understand why I have to manipulate strings and deal with newline characters in the input. It distracts from the problem at hand. (C++)
Oh come on, format of the input could not be any simpler :) Parsing it is close to trivial for a kata of this rank.
I really don't fully understand the problem, and I think I need some help. My understanding is that the grid is a top-down view of a map, and the cells with numbers on them are showing their "altitude". So assuming my understanding of the problem is correct, the simplest of tests is expecting the following to return 2:
010 010 010
But I can only see how this could return 1. To get from 0,0 to n-1,n-1 you only need to climb once. Please can someone help me understand the question better?
You need to climb up, but you also need to climb down, as last cell is of height 0. (climbing down also counts towards total climb rounds)
bottom left corner is [0,0] size of map is NxN top right corner is [N-1, N-1] it's all because you starting count from ZERO, not from ONE
I need some more clarification on "Number of climb rounds between adjacent locations is defined as difference of location altitudes (ascending or descending).".I'm looking at the test examples and I still don't get it.I know that I can solve it but I just don't understand what is being asked of me.
A climb round is the absolute difference between the height of two locations. Moving through "0 1 0" results in 2 climb rounds because "0 -> 1" is ascending 1 and "1 -> 0" is descending 1, which is a total of 2.
Yes that helped a lot but what happens if you Move through: 9 3 9 8 7 ? post-Post Note:Ah with your wisdom I have gained enough knowledge to find a solution for this Kata,the only problem is that I'm too slow.Might be time for some memoization.
This comment has been hidden.
This is a bit stupid, I've change back to Java8, so that way I don't get the time out. At least not always. I am quite sure the solutions runtime are quite different on each platform.
Also, the same code passes 3 out of 5 times. There are many ways I can further optimize the code, but that are some trade of. And speed optimazition was not the initial goal of this kata, at least that was not market.
Hi,
It may happen that j8 is faster than J11 for some kind of task, yes. But a correct/reasonable solution passes consistently the tests with around 8s in J11 (and roughly the same in j8, actually). Meaning you really need to improve your code. Would be useful to spot what kind of structures are slowing J11 compared to J8, tho.
Can confirm what B4B said, just checked and my old solution still passes the test suite in 6.8-7.5s for both Java 8 and Java 11.
I can confirm i was stupid.
Awsome kata! Finished all the series and I learned some much from them...
Liked it. However I'm either missing a more efficient algorithm or Kata needs OPTIMIZATION tag. I coded a very concise solution using C# LINQ but had to optimize it down to low-level imperative style to fit the timeout, I passed it eventually in 7 sec but the idea and O(N) is about the same as in initial solution.
I learnt a lot from this problem , thank you !
Pleasantly challenging!!! Good job evk!
I do not understand one of the sample test cases. How does the test case for f equal 0? Based off the description and other sample test cases, should it be 28? My reasoning is that you climb down 7, move right 2 to climb up 7 and climb down 7, move right until right boundary, then move down until you reach location (N-1)(N-1), where you climb up 7 and exit. So 7 + 7 + 7 + 7 = 28. Am I doing this wrong?
Please state the language when you ask questions like these. From your profile I see it's C#.
The inital height (cell x = 0, y = 0) is 7, so if you just follow the path of cells where height is 7, you don't need to climb up or down at all. Which is why the result should be 0.
Note that it's not about having path of lowest heights, but total lowest difference of all climbs.
Does that make it any clearer?
This is very helpful, thank you!
No problem ! Best of luck with this one :D I recently solved it myself, but part 3 was the last one that I was able to solve :<
That was challenging but awesome.
If anyone wants to do performance testing in their local environment, this can help:
function testMap(size){ var hundo = ''; for (i=0; i<size; i++) { for (j=0; j<size; j++) { hundo += Math.floor(Math.random()*10); } hundo += '\n'; } console.log('Map of size '+size+'x'+size+' generated. Running pathFinder...'); console.time('pathFinder'); var answer = pathFinder(hundo.slice(0, -1)); console.timeEnd('pathFinder'); return answer; }
Thank you, it's very helpful! With your codes' help, I found out my code to exceed the Maximum call stack size when the maze's size is bigger than 64.
Thank you! I've used it for perfomance purpose) It helped me!
Got this error while attempting my code in Python : (7 Success, then this error :)
Traceback (most recent call last): File "main.py", line 92, in do() File "main.py", line 91, in do Test.assert_equals(path_finder(field[:]), solution(field)) File "main.py", line 14, in solution moves = list(map(lambda x: [x[0], x[1], abs(tmap[x[0]][x[1]] - tmap[a][b]) + mmap[a][b]], moves)) TypeError: 'list' object is not callable
Even with a minimalistic code like that I got the error :
def path_finder(maze): return 0
This comment has been hidden.
If the suite runs through 100% for a performant solution and is just flaky for some sub-obtimal solutions, not an issue for me. That is pretty often the case with many katas, i just try a couple of times if i see that i am close, and otehrwise i learn further and optimize my solution.
We need random tests to avoid cheaters, and with randomness comes the possibility that passing/failing is based on luck.
For the C# version, something seems broken for larger mazes. I can pass all the tests up to a 99x99 grid in about 2.2s, but I time out if I had not hardcoded an (obviously wrong) answer for larger mazes. My solution does work fine for a 100x100 maze I put in the sample tests manually (and completes that test in less than 100ms). I'm not sure where the issue lies.
print the inputs and print stuff into everyone of your while loops, to make sure that your videdoesn't get stuck into an infinite loop in some cases.
This doesn't really help in my case, as I don't get to see the console output if the execution times out.
I even added more tests with some of the 100x100 mazes from the randomized tests, which made it even more evident that my code probably should be performant enough, as each additional large example only added about 40ms.
I'll add my code in a separate, spoiler-marked comment.
This comment has been hidden.
I don't do C#, sorry. about the time out, the idea it's that if you print enough from the right place, you'll get a buffet limit error befits the time out. Then you get some feedback
Oh, I'll play around with that. Thanks for your time.
Alright, it turns out my implementation was just simply not quite fast enough. I managed to pass now.
Same issue, codewars passes randoms up to 99x99 in less than 4s and then hangs on 100 x 100 every time. I dumped the input it completes with correct result in matter of milliseconds locally. Must be some limitations of the codewars sandbox?
UPD: OK it times out because random tests run multiple times (not clear how many times exactly) not because of any particularly hard puzzle. Should description be more obvious about perfromance expectations?
Tho there are absolutely no differences between 99x99 and 100x100 on the tests side. :/
and a reasonnable amount of solutions already exists... So that should be on your side, even if hard to track (local executions aren't "trustful", since you bypass some kind of interactions. Like: would you have a global data structure that doesn't get updated/cleared correctly at some point? You won't ever see that on just one test, run locally)
My issue was simply due to speed. The test mazes have size 1, 2, 3, ..., 99, 100, but this is reapeated 6 times, so you need to be able to complete the first 100 random tests in less than 2s to pass.
@B4rrCH, already figured it out thanks. Trick was that test suite runs 1x1 up to 100x100 random tests five times not just once. What I did initally (and probably you too) was short-circuit to a wrong answer on first occurrance of 100x100 in which case it would halt in mere seconds, not 12 sec timeout. However short-circuiting on 2nd or 3rd occurrance of 100x100 makes it clear that randoms run multiple times.
This comment has been hidden.
This comment has been hidden.
What's the upper limit of N? (C#)
For clarity, please update your instructions to note that the map is given as a string and not a matrix.
C# Translation added.Please review and approve~
This comment has been hidden.
I had the same problem, the way I debugged it (1 hour of work):
but you probably have already solved it now
my c++ code is returning "exit code 139" when i attempt. is that a timeout error?
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
while I don't see your current solution, it's probably have to do with how you check if the node you're looking at has been visited already
Why are solutions locked for this and not the other Pathfinder problems? I'm so close.
I enjoyed this kata! I just did a C++ Translation. Your review is appreciated :)
approved
Is this Kata especially hard in Ruby because Ruby is slow? I have optimized and optimized and my code still isn't fast enough.
It is not especially difficult, but you need to take into account memory access time and structure your data accordingly. Smart iteration over a graph-like structure does the job well. FYI, for the sample tests, my code run in about 700ms, and around 10s for the complete test suite, so I guess you need to aim at 850ms top for the samples
Description is complete gibberish. Any chance of getting someone who has completed this to rewrite it?
ruby translation
Please review and approve
.
This comment has been hidden.
The test case expectation is correct. I would suggest paying a lot of attention to the first sentence of the challenge.
This comment has been hidden.
second sentence, actually.
To be less obscure, they are saying you climb the difference between the number given and where you came from, not the actual number.
Thanks:)
Don't understand this TC: testArea(0,
777000 007000 007000 007000 007000 007777);By the Spec, shouldn't this return 28?
It's the
difference, not their individualvalue;-)This comment has been hidden.
For the same reason maybe? You can't get from top left corner to bottom right corner without changing altitude.
Ask the opposite question then: why is this
0?If you can't construct an example that gives a result of
0, you can't claim it should be0.That's why I sent the first test case in the initial question. I assumed the answer should be 28 in lieu of 0. The best path starts at a 7, passes through a 7 and ends at a 7. The climb round is the difference, and it's not cumulative.
I'm really trying here to get this here so...come on, make me a believer. ;) How do these two TC's not contradict each other?
How 2 totally different test cases with totally different approaches to solve can contradict each other?
7. You walk through7's. You end up at7. You haven't changed your altitude even once - result is0.0. At some point you have to climb up to1. At some point you have to climb down from1, so you can end up at0. The result is2.Ohhhh.. Ok. I think I get you now. The objective here is to minimize climb rounds. I think it makes perfect sense to me now. Thanks and much appreciation!
I can't believe how much difference something as simple as a smart algortihm makes to executing code. I loved this Kata, and so far the series for that fact has been very fun. This kata was easy, yet so fundamentally challenging for me to do. It made me dig deep back into my old algorithm notes. I am so grateful for you guys here at codewars for the challenges and the learning. Lets keep the good times rolling!
Python tests are too strict, or JS is too lenient..
This comment has been hidden.
This comment has been hidden.
It seems to me you are computing the number of climb rounds of every square, you need to do better.
Java translation!
Please review and approve (Note: I included my slight change of the description I suggested below, tell me if you want I remove it or not).
Approved.
descending or ascendingin the description?.
Python translation. Please, review it.
NOTE: the amount of tests is tripled (
3tests per each size from1x1to50x50). The validation function is not super efficient but it only takes2700-2800 ms, therefore the actual time limit will be around9200-9300 ms(the numbers are average, just in case I'd say the lower limit is around9 sec). If you think I'm going overkill, I can make it lighter, but it would be too easy for a3 kyukata IMHO.Approved.
Ok, thanks.
My code is not fast enough for the final large mazes. Any suggestion?
This comment has been hidden.
Thanks! Let me learn something new :->
Let me have a look :)
Very good kata's series! It made me to study the algorithms for finding the shortest paths between nodes in graphs.
Me too)))
Approved!