# Tag Info

## Hot answers tagged pathfinding

304

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. // Warmup iterations for profiling for (int j = 0; j < 10; j++) { FindPath(start, end, CellFilter); } Doing this gets the time down to about 17 ms on my machine (from 38 ms initially). Running the code ...

48

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 affect its speed). Cell Rather than having code in main that reads in components, then composes them into a cell, I'd rather the cell knew how to read itself ...

23

I'm one of the developers of Untrusted (neunenak). Your solution is completely ethical/fair/okay. The whole idea behind the game was that the player could write whatever code they needed to be able to progress to the next level. We do have a lot of code in the game's framework designed to make really easy and uncreative solutions impossible, but that's just ...

21

This is quite good and professional-looking code. There are many small aspects which I really like: Using Collections.unmodifiableMap instead of a shallow copy is brilliant. The use of a generic nodeId is clever and makes for elegant code. There are input checks in all public methods (well, there are some exceptions: only the AStar and NodeData constructors,...

18

$O(1)$ Discussion Is it possible to calculate the distance in $O(1)$ time complexity? Yes, it is. This problem is called the "Knight's distance" problem, and googling it find a number of references. This problem was posed as part of the South African "Computer Olympiad" in 2007 for high-school students to solve.... (I know, kids these days.... :) )....

15

Unnecessary Import numpy is not required for this challenge. You are using none of its special capabilities. The following: arry = np.array([[0]*5 for i in range(5)]) could easily and simply be replaced with arry = [[0] * 5 for _ in range(5)] Notice the throw-away _ variable being used for the unused loop comprehension variable. If you don't use it, ...

14

A few notes (with efficiency aside, as you said): Your defined ABS surrounded by parenthesis is not the usual way that C programmers declare macros so that they aren't problematic. #define ABS(a) do { typeof (a) _a = (a); _a > 0 ? _a : -_a; } while(0) Also, there is no point of using typeof in this instance. Just use the abs() function from <math.h&...

14

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 generalization is to use vectors like [-1, 0] instead of code specific to a direction. You can create tables of all direction-specific things, like this: var left = {...

13

Here are a few comments about the style. You'll find comments about the algorithm itself at the end. Naming The 3 at the end of the class names is a bit awkward. The same kind of things are sometimes called x, dx or row. (Coordinate and Direction look pretty similar too but trying to merge them showed me they were actually different in the spirit.) ...

13

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 comes to that saldo, if a node has zero saldo, it may not generate those its neighbors that are occupied by wall. If saldo is $s > 0$, and the node has a wall ...

12

Some points to consider... Sorting is slow. Really slow. At the end of your loop you call OpenList.Sort() to order your nodes by relative cost so that you can work on the lowest-cost nodes first. Depending on how far your search extends, this can lead to large amounts of time doing nothing but sorting the list. Instead of a per-iteration sort, use a ...

12

Couple things that I see that would make this a lot more efficient: First, you don't need to determine all of the valid edges before you start the Dijkstra algorithm. Assuming that the only constraint on whether two points have a valid edge is that "the distance between them is smaller or equal than the D", there is no reason to determine the complete ...

12

Complete and Incomplete Algorithms Search algorithms can be classed into two categories: complete and incomplete. A complete algorithm will always succeed in finding what your searching for. And not surprisingly an incomplete algorithm may not always find your target node. For arbitrary connected graphs, without any a priori knowledge of the graph ...

12

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 breadth-first search. With BFS, the first solution you encounter will be an optimal solution — which is not the case with DFS.

11

@CarySwoveland is on the right track. The original code and several other solutions so far get the wrong answer. For example, GetMinimumSequence(12) should not return 8, but rather 5, based on the optimal sequence 1, 2, 3, 6, 12. One straightforward solution uses recursion: public static int GetMinimumSequence(int n) { if (n <= 0) { throw ...

11

C++-specific: You're mixing C and C++ libraries: You already have <iostream>, so you don't need <stdio.h>. However, if you can only use printf and scanf for whatever reason, then remove <iostream>. Otherwise, just use std::cout and std::cin, and remove <stdio.h>. The C++ library version of <stdlib.h> is <cstdlib>. The ...

11

Try and engage the move constructor: m.data.push_back(temp); Because temp is a named variable it will hit the version that uses const& T. To try and get the alternative version that engages the move constructor add std::move m.data.push_back(std::move(temp)); The input operator does not make any attempt to make sure each line is the same size. ...

11

Teach a Man to Fish If you have a program that is running slower than you expect, and you want to know where it is slow, the right answer is to profile the code. There's a question at StackOverflow that describes a number of tools that will allow you to run the code and find the hotspots. Alternatively, the poor man's profiler is to just to dump stack ...

11

PriorityQueue For openList, you could use a PriorityQueue instead of an ArrayList for better performance. With the ArrayList, every time you insert new elements, you need to sort the whole list, taking $O(n\log n)$ time. With the PriorityQueue, inserting a new element should only take $O(\log n)$ time. If you need to change an existing element, you ...

11

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 are $Θ(n^2)$ walls, and it takes $Θ(n^2)$ to do a breadth-first search on the resulting maze, for $Θ(n^4)$ overall runtime. No wonder you are exceeding the ...

11

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 between a multidimensional array and an array of arrays in C#? on SO. This answer compares both array systems. EDIT: I've tested it myself and the difference is ...

10

1 point to remember: the subsequence *2 +1 +1 can be simplified to +1 *2 (because n*2+2 is the same as (n+1)*2) this means you can work backwards, odd numbers need a *2 +1 at the end of the sequence and even numbers get just a *2 count=1; while(n>1){ if(n%2==0) count++; else count+=2; n/=2;//integer on positive number divide rounds down } ...

10

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, you will build a weak, buggy program on top of them. Make them do exactly what they say on the tin. This is a 2-vector of integers, so make it follow the ...

10

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 possible_paths(). This function doesn't return paths - it returns neighbors. It returns all the adjacent squares. Moreover, what is path[0] and what is path[1]? Let's name these things too. ...

9

I have a bit of a bone to pick with this: #define ABS(a) ({ typeof (a) _a = (a); _a > 0 ? _a : -_a; }) Firstly, typeof is a gcc extension, so by using this, you're making your code less portable. To be fair, for something small like this, it's not a big problem, but it's a bit of a bad habit to get into. In this case, it's also not even needed. #define ...

9

Reviewing Code: Names When naming classes in hierarchies, share the naming conventions used in the standard libraries. Therefore, your top level interface should be Maze, not IMaze. Likewise, IMazePosition. Repetition You are repeating yourself both small and large here. Small: notice that you repeat yourself for each of the cardinal directions (north,...

9

public static ReadOnlyDictionary<int, int[]> AvailableMoveIndexes => new ReadOnlyDictionary<int, int[]> ( new Dictionary<int, int[]> { [0] = new[] { 1, 2 }, ... Nice clean representation, but why public? I would expect private or (perhaps better) internal with an InternalsVisibleTo attribute ...

9

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 match. You can use this page to review heuristics for grid worlds, I don't recommend Euclidean distance because it's either too optimistic (causing unnecessary ...

8

A few items: solve should be a member function Since solve actively manipulates the maze and makes no sense outside the context of a maze, it really ought to be a member function. size_t is unsigned Since size_t is an unsigned type it will never be less than zero and so checks for x < 0 || y < 0 within solve should be removed. Several methods ...

Only top voted, non community-wiki answers of a minimum length are eligible