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.6k
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:
...
- 34k
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 ...
- 29.8k
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
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.3k
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.7k
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 ...
- 34.9k
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 ...
- 41.1k
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 ...
- 10.7k
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 ...
- 29.8k
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
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,916
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.7k
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,431
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:
<...
- 43.5k
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.3k
7
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.9k
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 ...
- 10.7k
6
votes
Find the correct path through a 5 x 5 grid (coderbyte 'Correct path')
calcpath should be calc_path as per PEP8. This seems like it's a name decided on by the challenge, but I thought I'd mention it.
...
- 16.3k
6
votes
Accepted
Speeding up Dijkstra's algorithm
PEP-8 Violations
Variables (unseenNodes, currentNode) should be snake_case, not ...
- 34k
6
votes
Accepted
A* (shortest path) with the ability to remove up to one wall
The high level approach
What would be a good way of implementing the wall logic to be within the A* algorithm? I've tried to simply add a canRemove boolean to the Cell object (which is holding the ...
- 10.7k
6
votes
Bellman-Ford optimisation in C
A few pieces of advice you can consider:
As far as I'm aware, documentation comments are conventionally immediately before the declaration, not between the signature and the body of the ...
- 1,566
6
votes
Accepted
Multithreading a shortest path algorithm
Avoid redefining integer types
I see types like sint and uint, I think somewhere you have lines like:
...
- 61.7k
5
votes
Accepted
Google Foobar challenge: Exiting a space station maze, where one wall may be removed
It looks like your current implementation is wrong. Running it on a simple 2x2 square without walls should give 2 steps (move right, move down). But your program answers with 4.
Because it's wrong, ...
- 4,297
5
votes
Accepted
Find the shortest path through a maze with a twist: you can knock down one wall
So here is my version of your code. Changes made:
1. pep8:
I changed the code to more closely conform to pep8. This is important when sharing code as the consistent style makes it much easier for ...
- 4,214
5
votes
Fastest path on a snakes and ladders board
continue # Forbid a dice-roll that lands on a snake
This may prevent finding the shortest path - it's possible to imagine a board with two long ladders, ...
- 81.7k
5
votes
Implementation of A* algorithm in C++
Just off the cuff, before I fully code review this, I would tell you:
1) There are not enough comments. You add comments like this:
...
- 106
Only top scored, non community-wiki answers of a minimum length are eligible