You need to sign in or sign up before continuing.×
5 kyu
Minimum path in squares
106 of 425Frederikbh
Loading description...
Dynamic Programming
Algorithms
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.
although it can be deduced, it should be mentioned that this is the minimum path to reach the bottom right. It is important, since we are provided with a target point and it is not always the bottom right.
description should be language-agnostic.
python new test framewprks
Really funny kata on dynamic programming and algorithms optimization.
I used dynamic programming with memoization, but still got an execution timeout with just 114 tests passed in JS. Any hints ?
I think the Python one needs tuning again. These close-to-the-borderline performance tests need regular retesting to make sure they're still reasonable, given the server's decreasing performance of late. If you're going to make efficiency a critical component of the solution, you can't afford to submit these and forget about them.
Is it me or does djikstra work on java, but times out on python?
This description and reversed test-cases is utter trash. Better solving leetcode.
This comment has been hidden.
Why is Y a row of the matrix and X a column ? this is logical for the XOY coordinate grid, but not logical for other tasks where X == row and Y == col. It would be nice to write this in the description.
Thanks for this kata!
I could not do it recursively so I try another approach :)
define a 'cache' decorator or just import from functools
My solution fails only for the very big squares. It's probably something to do with the array reference issue, but I give up
I don't understand that at (4,2) if a minimum path of 21 exist, then why the answer is 24.
That's a question. What is the exact example you're talking about? What's that matrix?
In the given sample test and coordinate is (4,2), since the minimum path can be as follows-1,2,3,2,3,2,8
Clearly mentioned in the description: Note: Coordinates are marked as x horizontally and y vertically.
You are taking first(which is named as
x) coordinate as y and second coordinate asx.Python tests and/or the reference solution should be reviewed and adjusted: I could only submit my solution after several tries, when I got lucky and it didn't time out. I then tried the 5 top voted solutions, but all of them timed out.
hint: try to precalculate all the results for the big tests and just read the results
Lowered the number of tests. Now it takes ~9 sec to pass.
This comment has been hidden.
I think that title and description or tests of this kata should be changed. It looks like author forgot than minimal path can be also something like that below.
Tests in this kata are not checking for actual minimal path.
A key part to this problem that makes it much easier is that you can only move right or down. If you could move in any direction(up, down, left, or right)how would you go about solving it. Would it be neccasary to calculate every possible path(which would probably become impossible with bigger arrays) or is there some other way?
yes, still possible. That would become a classical path finding problem, and yes, you would have to check all the possible paths (algo: depth first search, breadth first search, best first search,
A*, ...).When I am checking all possible paths then sometimes I have got a little better result than in tests. Are the test correct for sure?
This comment has been hidden.
This reminds me something from Project Euler..!
From the kata's task: "Coordinates are marked as x horizontally and y vertically." Then in the test task does not correctly consider "Assert.AreEqual (5, MinPathSquare.MinPath (smallSquare, 0, 1));". Starting from the condition of the problem x = 0 and y= 1. Number of rows = x = 1; Number of columns = and y = 2; Therefore, the minimum path can be calculated only horizontally and it is equal to 3. But you consider the minimum vertical path that you have equal to 5. That is, you think as though two rows of the array are given, but x = 0, and this is one line. I think that the answer should be 3. According to the test example "Assert.AreEqual (5, MinPathSquare.MinPath (smallSquare, 4, 2));" I think that the answer is 21, not 24, if x = 4, and y = 2 Please explain how you calculated the minimum path.
You always start at the upper left corner. Then, each nested array represents a row in the 2D-grid.
In the test-case you're referencing you're given the following grid:
The end coordinate is
x = 0, y = 1, which is where the4is in the grid. Therefore the minimum path will be1 + 4 = 5.Why with coordinates (0,0) the value of the minimum path is equal to 1, y = 0 is the very first column. And with the coordinates (0, 1), y = 1 and this is also the first column of the array. As far as I understood from the task, the counting of rows and columns of the array begins with 0.And the first test example with coordinates (0,0) confirms this. Tell us how you count the columns and rows? x = 0 - this is what row (please give the value of the row)? y = 1 - this is which column (give the value of the column)?
Xdenotes the column of the endpoint, or the horizontal point if you will.Ydenotes the row of the endpoint, or the vertical point if you will.With coordinates
(0, 0)it should be obvious why the minimum path is1, since you're starting and ending at the same position with the value1.Here is the minimum path of the grid given before, when the endpoint is in
(0, 1):Solved this problem, using recursion, my computer thinks everything is fine, and in tests does not pass due to the delay more than 12 seconds, help you how to send a decision?
The tests have been made in a way that requires you to come up with an implementation that runs pretty fast. (Hint: dynamic programming)
I have the same problem and i think my code is efficient because i use recursion to go trough all possible paths and storing the total sum in a list, at the end i return the smallest element of the list. Does it still have to be more efficient? Or is it probaby because i use a global list to solve the problem? (i'll put the code as a reply to this msg marked as spoiler)
This comment has been hidden.
The problem with this approach is that you're calculating the cost of every possible path in the matrix. As you can imagine, that is quite a lot of possibilities. There is a much smarter way solve this problem, that gives you a running time of O(n^2) if the matrix is quadratic (Hint: Dynamic programming).
I had change one's mind problem using the dynamic programming method, all tests passes except the very big square, with what it can be connected?
I think changing the description as follow is better. Because in this way, parameter x and y are nolonger needed. Which makes this kata more concise. "Your job is to calculate the minimum total cost when moving from the upper left corner to the lower right corner".
Btw, I wonder why is this kata 5kyu since "Pyramid Slide Down" is 4kyu. Obviously this one is a little more difficult. https://www.codewars.com/kata/pyramid-slide-down/python
You're not always asked to move to the lower right corner. The goal-coordinated can be any point in the grid.
Just a suggestion. And tasks are the same if you cut a (y*x) grid from the original one.
I agree with you. When I am checking best path then I have got sometimes a little better solution than expected.
Because the grid is reference type, each run is not independent of the last as you are passing in the same grid for many tests. As such the tests will fail on subsequent runs if the data therein is manipulated unless the programmer starts by making a local copy of the grid on each run. This is out of spec. I suggest changing your testing methods such that every grid tested has a unique reference. It is a cool problem otherwise.
You're right. I've made the individual tests copy the original grid, to fix this. Thanks for pointing that out.
The random tests and sample tests still pass in the same grid copy.
Oh yeah. That should be fixed now. I've allowed the very big squares to be reused, as it would take to long to copy them.
Sample tests still pass in the same grid copy in C#.
That's intentional as to not clutter the test cases.
I made it work, just don't know how to make it past the timeout.
This comment has been hidden.
Nice kata! The dynamic programming tag tipped me off on how to solve it ;)