2
$\begingroup$

The problem is stated as the following:

We are given a grid graph $G$ of $N \times N$, represented by a series of strings that describe vertices s.t.

  • $L$ is the vertice we're interested in
  • $P$ are vertices that are unavailable
  • $.$ are vertices that are available

e.g.:

.... 
...L 
..P. 
P...

Would mean a graph that looks like this

   0    1    2    3
 +-------------------+
0|    |    |    |    |
 |    |    |    |    |
 +-------------------+
1|    |    |    |    |
 |    |    |    |    |
 +-------------------+
2|    |    |XXXX|    |
 |    |    |XXXX|    |
 +-------------------+
3|XXXX|    |    |    |
 |XXXX|    |    |    |
 +-------------------+

Where $v_{2,3}$ and $v_{0,3}$ are unavailable and we're interested in $v_{3,1}$.

From each vertice we're only allowed to move on the axis (we can't move on the diagonal) and a move is valid from $v_{x,y}$ to $v_{q,p}$ if

  • $ |x-q| + |y-p| \leq s$ and $v_{q,p}$ is available.
  • Staying in the same spot is also a valid move

Given $m$ - maximal number of moves and $s$ what is the number of ways we can make $m$ moves from vertice designated by $L$.

My attempt was to

  • First compute the neighbors reachable from each node. Create a look s.t. $\forall v N[v]$ is the list of reachable nodes from $v$
  • Then build a starting record $M_0$ s.t. if node is reachable $M[i][j] = 1$ and $0$ otherwise.
  • Then for each step calculate for $\forall i,j \in N$ (all the grid) $ M_{i}[i][j] = \sum_{v\in N[v]} M_{i-1}[v_i][v_j]$ (where $v_i, v_j$ are the coordinates of $v$ on the grid) and store in a matrix $M_i$

We iterate until $i==m$.

  1. for each $v_{i,j}$: 1. for each neighbor $n$ of $v_{i,j}$: 1. $M[i][j] += M'[n_i][n_j]$

Unfortunately this doesn't work (tried to do it with a pen and paper as well to make sure) and I get fewer results then the expected answer, apparently there should be 385 ways but I only get to 187.

Here are the intermediate states for the above mentioned board:

----------------------------

  5   6   5   5 

  5   7   6   6 

  4   6   0   5 

  0   5   4   5 

----------------------------

 25  34  27  27 

 27  41  33  34 

 20  33   0  27 

  0  27  20  25 

----------------------------

133 187 146 149 

146 229 182 187 

105 182   0 146 

  0 146 105 133 

----------------------------

This did work for e.g. m=2 and s=1 for the following board:

   0   1   2
 +---+---+---+
0|   |   |   |
 |   |   |   |
 +-----------+
1|   |   |   |
 |   |   |   |
 +-----------+
2|   |   |   |
 |   |   |   |
 +---+---+---+

Here's my reference code (findWalks is the main function)

using namespace std;
using Cord = std::pair<size_t, size_t>;

auto hash_pair = [](const Cord& c)
{
    return std::hash<size_t>{}(c.first) ^ (std::hash<size_t>{}(c.second) << 1);
};

using NeighborsMap = unordered_map<Cord, vector<Cord>, decltype(hash_pair)>;


inline vector<vector<int>> initBoard(size_t n)
{
    return vector<vector<int>>(n, vector<int>(n, 0));
}


Cord findPOI(vector<string>& board)
{
    for (size_t i=0; i < board.size(); i++) {
        for (size_t j=0; j < board.size(); j++) {
            if (board[i][j] == 'L')
            {
                return make_pair(i, j);
            }
        }
    }
    return make_pair(-1, -1);
}


NeighborsMap BuildNeighbors(const vector<string>& board, size_t s)
{
    NeighborsMap neighbors(board.size() * board.size(), hash_pair);

    for (size_t i = 0; i < board.size(); i++)
    {
        for (size_t j = 0; j < board.size(); j++)
        {
            size_t min_i = i > s ? i - s : 0;
            size_t max_i = i + s > board.size() - 1 ? board.size() - 1 : i + s;
            size_t min_j = j > s ? j - s : 0;
            size_t max_j = j + s > board.size() - 1 ? board.size() - 1 : j + s;

            auto key = make_pair(i, j);


            if (board[i][j] != 'P')
            {
                for (size_t x = min_i; x <= max_i; x++)
                {
                    if (board[x][j] != 'P' && x != i)
                    {
                        neighbors[key].push_back(make_pair(x, j));
                    }
                }

                for (size_t y = min_j; y <= max_j; y++)
                {
                    if (board[i][y] != 'P' && y != j)
                    {
                        neighbors[key].push_back(make_pair(i, y));
                    }
                }
                neighbors[key].push_back(key);
            }
            else
            {
                neighbors[key].clear();
            }
        }
    }

    return neighbors;
}

int GetNeighboursWalks(const Cord& cord, NeighborsMap& neighbors, const vector<vector<int>>& prevBoard)
{
    int sum{ 0 };
    const auto& currentNeighbors = neighbors[cord];
    for (const auto& neighbor : currentNeighbors)
    {
        sum += prevBoard[neighbor.first][neighbor.second];
    }
    return sum;
}


int findWalks(int m, int s, vector<string> board) {
    vector<vector<int>> currentBoard = initBoard(board.size());
    vector<vector<int>> prevBoard = initBoard(board.size());
    std::unordered_map<int, std::vector<Cord>> progress;

    auto poi = findPOI(board);
    NeighborsMap neighbors = BuildNeighbors(board, s);
    for (const auto& item : neighbors)
    {
        const auto& key = item.first;
        const auto& value = item.second;
        prevBoard[key.first][key.second] = value.size();
    }

    for (size_t k = 1; k <= static_cast<size_t>(m); k++)
    {
        for (size_t i = 0; i < board.size(); i++)
        {
            for (size_t j = 0; j < board.size(); j++)
            {
                auto currentKey = make_pair(i, j);
                currentBoard[i][j] = board[i][j] != 'P' ? GetNeighboursWalks(currentKey, neighbors, prevBoard) : 0;
            }
        }

        std::swap(currentBoard, prevBoard);
    }
    return prevBoard[poi.first][poi.second];
}
$\endgroup$
2
$\begingroup$

Let $A$ be the set of available vertices (including $L$) and let $A(v)$ be the set of available vertices reachable by $v$ with a single move.

Let $M[v,\ell]$ be the number of walks of length exactly $\ell \ge 0$ from vertex $v \in A$.

You have that:

  • $M[v,0] = 1 \quad \forall v \in A$;
  • $M[v,\ell] = \sum_{u \in A(v)} M[u,\ell-1] \quad \forall v \in A, \forall \ell > 0$.

Intuitively, the second bullet means that every walk $\langle v, u, w_1, w_2, \dots \rangle$ of length $\ell$ from $v$ can be decomposed into an initial move to a vertex $u$ in $A(v)$, plus the walk $\langle u, w_1, w_2, \dots \rangle$ which has length $\ell-1$ and starts from $u$. The converse is also true (that is, if you have a walk $\langle u, w_1, w_2, \dots \rangle$ of length $\ell-1$ from a vertex $u \in A(v)$, then this also induces the walk $\langle v, u, w_1, w_2, \dots \rangle$ of length $\ell$ from $A(v)$). Since, by definition of $M[\cdot, \cdot]$, there are exactly $M[u,\ell-1]$ walks of length $\ell-1$ from $u \in A(v)$, it follows that the overall number of walks of length $\ell$ from $v$ is exactly the one given in the formula.

The value you are looking for is exactly $M[L, \ell]$.

Computing all sets $A(v)$ takes time $O(|A| s^2)$. Once this is done, computing each of the $O(|A| \ell)$ values $M[v,\ell]$ takes time $O(|A(v)|) = O(s^2)$. This leads to a dynamic programming algorithm requiring $O(|A| \ell s^2)$ time.

$\endgroup$
5
  • $\begingroup$ Thanks, Steven I was wondering what I missed in my assumptions, at first glance it seems that you too have step in which we're creating a set of all reachable $v'$ from $v$ and then a summation for every reachable $v'$ from $v$ using the previous $l$, so I might be missing some difference. Also could you please provide a little more detail about the rationale of each step you mention ? $\endgroup$ – CaptainTeemo Mar 12 '20 at 19:19
  • $\begingroup$ There are a few typos in your question so it's hard for me to fully understand it and point out what you are doing wrong. Could you give a precise definition of what you're storing in $M[i][j]$? I have now commented on the second bullet. I think it was the only step that was not immediately clear. $\endgroup$ – Steven Mar 12 '20 at 19:42
  • $\begingroup$ I think the main difference is that your solution has the sum go for $M[v,\ell] = \sum_{u \in A(v)} M[u,\ell-1] \quad \forall v \in A, \forall \ell > 0$ and mine Has $M[i,j] = \sum_{u \in A(v)} M[u,\ell-1] \quad \forall v \in A$ Meaning I'm only reaching to the paths length $l-1$ and not all of $l-1, l-2, \dots , 1$ $\endgroup$ – CaptainTeemo Mar 12 '20 at 20:26
  • $\begingroup$ I also tried to clarify my iteration steps $\endgroup$ – CaptainTeemo Mar 12 '20 at 20:48
  • $\begingroup$ There are still some issues, e.g., $i$ refers to 2 different things in $M_i[i,j]$. Anyway, it looks like you want to define $M_k[i,j]$ as the number of walks of length exactly $k$ from $L$ to the vertex at coordinates $(i,j)$. If this is the case then the idea behind your approach would work. You need to be careful in your base case, it seems that you are computing $M_1[\cdot,\cdot]$ instead of $M_0[\cdot,\cdot]$. Also, the final answer is the sum of $M_m[i,j]$ over all $(i,j)$. A final detail: according to your definition of move, $L$ is a neighbor of itself. I'm not sure if this is intended. $\endgroup$ – Steven Mar 12 '20 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.