Timeline for Find the longest rectilinear path in a matrix with descending entries
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 2, 2017 at 3:11 | history | edited | Jamal | CC BY-SA 3.0 |
Stack Snippets don't work with Python
|
| Apr 15, 2017 at 19:35 | comment | added | RoyaumeIX | @kezzos Sorry if the goal wasn't that clear, here it is: * Find the longest path following these rules. Longest path means the maximum number of nodes where we are always going down. * If we have many longest paths with equal distance ( number of nodes), then we should get the one with the maximum drop ( value of 1st node - value of the last node). | |
| Apr 15, 2017 at 19:28 | vote | accept | RoyaumeIX | ||
| Apr 15, 2017 at 19:28 | |||||
| Apr 14, 2017 at 5:52 | comment | added | kezzos | Ah yes I can see, I misread the question sorry. I'll fix at some point | |
| Apr 13, 2017 at 20:45 | comment | added | Janne Karila | Just eyeballing your example data, near the left side, the path 88-57-49-41-25-8 is longer that the answer you indicate. | |
| Apr 13, 2017 at 20:30 | comment | added | Janne Karila | I mean it is wrong to consider no other than the steepest edges, the assignment only requires skiing downhill on each move. | |
| Apr 13, 2017 at 17:59 | comment | added | kezzos | Only the steepest edges are kept before applying nx.dag_longest, not sure what you mean sorry. Creating a big graph and then pruning it is not very efficient however hence the slowish speed. Would be Better to loop over the array and construct the graph as you go | |
| Apr 13, 2017 at 16:30 | comment | added | Janne Karila |
There's no steepness requirement on individual moves -- only on the whole path, and only as a tie-breaker. You could adapt the code of nx.dag_longest_path accordingly, though.
|
|
| Apr 13, 2017 at 14:41 | comment | added | ChatterOne |
I'd be really curious to see the results if you tried my code on your machine. That's because using the same generation (100 reshaped to 10x10), I get 0.0019... with your code and 0.00036... with my code. I find it hard to believe my code is 10x faster. There must be something I'm missing.
|
|
| Apr 13, 2017 at 13:19 | comment | added | RoyaumeIX | This approach is very interesting, this is what I needed! running it on 1000 x 1000 array took me just 45 seconds. | |
| Apr 13, 2017 at 13:08 | vote | accept | RoyaumeIX | ||
| Apr 15, 2017 at 19:21 | |||||
| Apr 13, 2017 at 10:50 | history | undeleted | kezzos | ||
| Apr 13, 2017 at 10:50 | history | edited | kezzos | CC BY-SA 3.0 |
added 1385 characters in body
|
| Apr 13, 2017 at 10:01 | history | deleted | kezzos | via Vote | |
| Apr 13, 2017 at 9:52 | history | answered | kezzos | CC BY-SA 3.0 |