308
votes
Accepted
Dijkstra path finding in C# is 15x slower than C++ version
First of all, you should run the FindPath method a couple of times before measuring, to give the C# runtime a chance to optimize the code.
...
- 2,146
53
votes
Dijkstra path finding in C# is 15x slower than C++ version
For the moment, I'm ignoring the C# code (and its speed), and reviewing the C++ code for ways it might be open to improvement in readability (but with a decent compiler, what I'm suggesting shouldn't ...
- 33.5k
15
votes
Accepted
Handling a maze in JavaScript
Whenever you're dealing with a tile map like this, you should make your best effort to avoid writing code for each direction, replacing it with generalized operations.
The most basic such ...
- 711
15
votes
Accepted
Find the correct path through a 5 x 5 grid (coderbyte 'Correct path')
Unnecessary Import
numpy is not required for this challenge. You are using none of its special capabilities. The following:
...
- 33.3k
13
votes
Accepted
Shortest Path For Google Foobar (Prepare The Bunnies Escape)
Basically you need a breadth-first search with a minor tweak:
each node represents a cell in the grid (x- and y-coordinates),
each node knows its "saldo" (how many walls it may penetrate).
What ...
- 27k
13
votes
Accepted
Python program to find a word ladder transforming "four" to "five"
By performing recursion, you are performing a depth-first search of four-letter words. However, this task involves finding a shortest path, and shortest-path problems are generally better done using ...
- 144k
11
votes
Accepted
Path finding algorithm using recursion in Python
What's in a name?
This code is pretty easy to follow, and I could mostly understand it on the first read through. However, we could do better. Let's take a look at ...
- 18.4k
11
votes
Accepted
BFS shortest path for Google Foobar challenge "Prepare the Bunnies' Escape"
The algorithm in the post is to iterate over the walls, and for each wall, to remove that wall from the maze, and then solve the maze using breadth-first-search.
If the maze is \$n×n\$, then there ...
- 49.6k
11
votes
Dijkstra path finding in C# is 15x slower than C++ version
The multidimensional array might be the weakness of the C# implementation. Try using jagged arrays that are faster though not so easy to use.
You can read more about it in What are the differences ...
- 44.1k
11
votes
Bellman-Ford optimisation in C
for (uint _ = 0; _ < nb_nodes - 1; _++)
Maybe this was python code translated into C?!?
Repect the norms of the community.
Even though ...
- 16.6k
10
votes
"Simple" pathfinding algorithm
Let's just review this vector; there's plenty to talk about here.
This may seem like nit picking but hey, first, you asked, and second, build strong foundations in your helper types. If they are weak,...
- 14.7k
9
votes
Accepted
BFS shortest path for Google Foobar "Prepare the Bunnies' Escape"
One problem might be your custom Queue class. The list you use as underlying data structure has O(n) behaviour for ...
- 40.8k
9
votes
Dijkstra path finding in C# is 15x slower than C++ version
More speed for both C++ and C#
Revisiting an older question. While reading this question and its already very good answers the ...
- 2,475
9
votes
Accepted
9
votes
Accepted
Implementation of A* algorithm in C++
Euclidean distance is used to calcualte the cost from current node to goal
The code implements Manhattan distance, so the comment is wrong, or perhaps the code is wrong, but in any case it doesn't ...
- 9,049
9
votes
Optimizing Python BFS Code
I have only a couple of nitpicks:
Nitpick 1
while len(queue) > 0:
You can write just as:
while queue:
Nitpick 2
Instead of ...
- 27k
8
votes
Maze solver for 2D matrix in Ruby
I think your code shows ability of writing readable code, understanding and implementing algorithms, writing helpful comments, and if the code works like I believe it does, providing a working ...
- 197
8
votes
Dijkstra path finding in C# is 15x slower than C++ version
The worst problem is probably the use of the SortedSet collection. In my experience, the Sorted* collections are rarely what you ...
- 181
8
votes
Compute shortest path in undirected graph
Intro code:
There's a lot of "instant fail"s here:
Include only the headers you need!
Debugging macros are probably not acceptable for something like this. We can step through in a ...
- 11.6k
7
votes
"Simple" pathfinding algorithm
After looking at this code some more I'll expand on my initial comment.
Your stack variable keeps track of the path from start to end. You push the same ...
- 7,666
7
votes
"Simple" pathfinding algorithm
Finally, your path finding algorithm itself.
I am not going to criticize the algorithm; others have already talked about how it revisits ground its been over before, backtracks unnecessarily, and so ...
- 14.7k
7
votes
Path sum in binary tree
If recursion has reached a leaf node then either you have accumulated
the correct sum or not, but in no case it is necessary to check the
left or right child node. Therefore I would change the first
...
- 23.1k
7
votes
Accepted
Dijkstra's algorithm in C99
Generally the variable and function naming is clear and makes the code easier to read. If this program is for a first
or second year computer science class it's really very good. If you are new to C ...
- 23.5k
7
votes
Maze solver and generator in Python
Some notes to your coding styles (different from PEP 8 — Style Guide for Python Code and others):
...
- 1,866
7
votes
Accepted
Maze solver and generator in Python
Just reviewing generator.py.
1. Review
There are no docstrings. What do these functions do? What arguments do they take? What do they return?
"verticies" is a typo for "vertices".
There's repetitive ...
- 49.6k
7
votes
Accepted
A* Algorithm in C# for pathfinding 2D tile grid
There is a lot of code here, so there is a lot to say; no way I'll covered everything! I'll do the easy things first, and then assume lots of them before we look at the algorithm.
Style
Usually C#ers ...
- 7,421
7
votes
Accepted
Fastest path on a snakes and ladders board
Don't use mutable default arguments. If you need to default to a list then default to None and then change to an empty list.
Take the following example code:
<...
- 42.7k
7
votes
Implementation of Dijkstra's algorithm in Python
[x for x in range(1, 1001)] can be written as just list(range(1, 1001)).
It would be good to give that ...
- 16.2k
7
votes
Accepted
Optimizing Python BFS Code
current = queue.pop()
What this actually does, which perhaps you did not notice, is remove the last element of the list. So the queue is really a stack, and ...
- 9,049
Only top scored, non community-wiki answers of a minimum length are eligible