Tag: finding

I am attempting an online coding challenge wherein I am to implement a pathfinding algorithm that finds the shortest path between two points on a 2D grid. The code that is submitted is tested against a number of test cases that I, unfortunately, am unable to see, but it will however tell me if my answer for shortest distance is correct or not. My implementation of the A* algorithm returns a correct answer on 2/3 test cases and I cannot seem to figure out what scenario might create an incorrect answer on the third?

I have tried several of my own test cases and have gotten correct answers for all of those and at this point am feeling a little bit lost. There must be something small in my code that I am not seeing that is causing this third case to fail.

More details

• The grid is w by h and contains only 1’s (passable) and 0’s (impassable) with every edge having a cost of 1 and the pathway cannot move diagonally It all starts with the FindPath function which is to return the length of the shortest path, or -1 if no path is available
• pOutBuffer is used to contain the path taken from beginning to end (excluding the starting point). If multiple paths are available then any will be accepted. So it isnt looking for one path in particular
• I know the issue is not the result of time or memory inefficiency. I has to be either the distance returned is incorrect, or the values in pOutBuffer are incorrect.

Any help would be greatly appreciated as I am just about out of ideas as to what could possibly be wrong here. Thank you.

#include <set> #include <vector> #include <tuple> #include <queue> #include <unordered_map>  inline int PositionToIndex(const int x, const int y, const int w, const int h) {     return x >= 0 && y >= 0 && x < w  && y < h? x + y * w : -1; }  inline std::pair<int, int> IndexToPosition(const int i, const int w) {     return std::make_pair<int, int>(i % w, i / w); }  inline int Heuristic(const int xa, const int ya, const int xb, const int yb) {     return std::abs(xa - xb) + std::abs(ya - yb); }  class Map { public:     const unsigned char* mapData;     int width, height;      const std::vector<std::pair<int, int>> directions = { {1,0}, {0,1}, {-1,0}, {0,-1} };      Map(const unsigned char* pMap, const int nMapWidth, const int nMapHeight)     {         mapData = pMap;         width = nMapWidth;         height = nMapHeight;     }      inline bool IsWithinBounds(const int x, const int y)      {         return x >= 0 && y >= 0 && x < width && y < height;     }      inline bool IsPassable(const int i)     {         return mapData[i] == char(1);     }       std::vector<int> GetNeighbours(const int i)     {         std::vector<int> ret;          int x, y, neighbourIndex;         std::tie(x, y) = IndexToPosition(i, width);          for (auto pair : directions)         {             neighbourIndex = PositionToIndex(x + pair.first, y + pair.second, width, height);             if (neighbourIndex >= 0 && IsWithinBounds(x + pair.first, y + pair.second) && IsPassable(neighbourIndex))                 ret.push_back(neighbourIndex);         }          return ret;     } };  int FindPath(const int nStartX, const int nStartY,     const int nTargetX, const int nTargetY,     const unsigned char* pMap, const int nMapWidth, const int nMapHeight,     int* pOutBuffer, const int nOutBufferSize) {     int ret = -1;      // create the map     Map map(pMap, nMapWidth, nMapHeight);      // get start and end indecies     int targetIndex = PositionToIndex(nTargetX, nTargetY, nMapWidth, nMapHeight);     int startIndex = PositionToIndex(nStartX, nStartY, nMapWidth, nMapHeight);          // if start and end are same exit     if (targetIndex == startIndex) return 0;          std::unordered_map<int, int> pathway = { {startIndex, startIndex} };     std::unordered_map<int, int> distances = { {startIndex, 0} };      // queue for indecies to process     typedef std::pair<int, int> WeightedLocation;     std::priority_queue<WeightedLocation, std::vector<WeightedLocation>, std::greater<WeightedLocation>> queue;      queue.emplace(0, startIndex);          while (!queue.empty())     {         int currentWeight, currentIndex;         std::tie(currentWeight, currentIndex) = queue.top();         queue.pop();          if (currentIndex == targetIndex)             break;          int newDistance = distances[currentIndex] + 1;         for (int n : map.GetNeighbours(currentIndex))         {             if (distances.find(n) == distances.end() || newDistance < distances[n])             {                 distances[n] = newDistance;                  int weight = newDistance + Heuristic(n % nMapWidth, n / nMapWidth, nTargetX, nTargetY);                 queue.emplace(weight, n);                 pathway[n] = currentIndex;             }         }     }      if (pathway.find(targetIndex) != pathway.end())     {         int current = targetIndex;          while (current != startIndex)         {             int outIndex = distances[current] - 1;             pOutBuffer[distances[current] - 1] = current;             current = pathway[current];         }         ret = distances[targetIndex];     }          return ret; }