CODEWITHSUNDEEP
c++algorithmdynamicgraphgraph-algorithm
Prash Som
Prash Som

Reputation: 173

Traveling a Grid for a Palindrome

I have been trying to solve this problem for quite a bit now and have not been able to come up with anything other than a naive solution. Basically, I am given a character grid of size N in which I have to find the number of distinct paths from the upper-left to the top-right when only traveling down and to the right that give a palindrome.

Here is an example of a grid:

ABCD

BXZX

CDXB

WCBA

There are 12 palindromes in this grid such as "ABXZXBA". My solution was to walk through all paths in the grid and check if that string was a palindrome by keeping a character stack for the first N characters and popping each character for the next N characters and checking if they were the same. This solution times out when N gets too big and I am not sure how to proceed. Any psuedocode or suggestions would be much appreciated.

Upvotes: 2

Views: 670

Answers (2)

גלעד ברקן
גלעד ברקן

Reputation: 23955

Something like this?

(At least it stops if the path is not forming a palindrome or is out of bounds/sync.)

JavaScript code:

function f(m){

  var stack = [[0,0,m.length - 1,m.length - 1,""]],
      count = 0;

  while(stack.length > 0){

    var next = stack.pop(),
        y = next[0],
        x = next[1],
        yr = next[2]
        xr = next[3];

    if (y - yr > 0 || x - xr > 0){
      continue;
    } else if (m[y][x] != m[yr][xr]){
      continue;
    } else if (y == yr && x == xr){
      count++;
    } else {
      stack.push([y + 1,x,yr - 1,xr]);
      stack.push([y + 1,x,yr,xr - 1]);
      stack.push([y,x + 1,yr - 1,xr]);
      stack.push([y,x + 1,yr,xr - 1]);
    }
  }

  return count;
}

Output:

var t = [["A","B","C","D"]
        ,["B","X","Z","X"]
        ,["C","D","X","B"]
        ,["W","C","B","A"]];

console.log(f(t));

12

Upvotes: 0

The Dark
The Dark

Reputation: 8514

Just a theory - I haven't tried to work out the code yet:

You could start at the top left and bottom right and keep the paths in sync. As it is a palindrome there would need to be the same letters in the path from the bottom as from the top.

Each time you look for the next step in a path, check to see that there is a matching letter in the reverse step.

The reverse step's available path can be further constrained in that it can't get to the left or above the forward step.

Stop when the paths meet, which is complicated by the fact that they might end up on the same grid location (odd number of rows), or they might just meet up (even number of rows).

The back tracking and stack keeping may be a bit more complicated, as you have to account for (possibly) several choices of reverse step, but it should cut down the number of possibilities. It might be better to think of it as each step in the forward and reverse paths gives you a new (smaller) grid to check for palindromes.

Upvotes: 1

Related Questions