Thursday, November 13, 2014

SRM 523 DIV 2

Problem
Given a string[] verify that there is a path from A to Z such that each letter is adjacent to the previous letter (not diagnol)


Code
public class AlphabetPath
{
    public class Point
    {
    public int row = -1;
    public int col = -1;
    public bool notFound()
    {
     return (row == -1 || col == -1);
    }
    public bool isAdj(Point p)
    {
    /*
     Left = same row, 1 left of col
     Right = same row, 1 right of col
     Below = same col, 1 row below
     Above = same col, 1 row above
    */
   
    if (p.row == row)
    {
    if ((p.col - 1) == col)
    return true;
    else if ((p.col +1) == col)
    return true;
    }
    else if (p.col == col)
    {
    if ((p.row - 1) == row)
    return true;
    else if ((p.row + 1) == row)
    return true;
    }
    return false;
    }
    }
 
    public Point find(char c, string[] letterMaze)
    {
    Point p = new Point();
    for(int i = 0; i < letterMaze.Length; i++)
    {
    p.col = letterMaze[i].IndexOf(c);
    if (p.col != -1)
    {
    p.row = i;
    break;
    }
    }
    return p;
    }
public string doesItExist(string[] letterMaze)
{
Point prev = new Point();
for(char c = 'A'; c <= 'Z'; c++)
{
Point p = find(c, letterMaze);
if(p.notFound())
return "NO";

if (c != 'A')
{
if(!p.isAdj(prev))
return "NO";
}

prev = p;
}

return "YES";
}

}

Analysis
This passed all 5 test cases. However, this is brute force and would probably fail a performance test.

This is O(rows*columns*n). I say N because this problem can be generalized to work on any sequence of letters/numbers. Using the 26 letter alphabet is just a special case. 

The primary constraint is that letters must be adjacent to the previous letter. This means we really only need to look in the adjacent spots. Therefore an optimization would be:
1) find the position of A
2) loop through B to Z, only looking in spots adjacent to the previous letter. 

Finding A would be O(rows*columns). Looping through N-1 letters and looking only in the four possible adjacent spots would be O(4*(n-1)). The constant is dropped leaving O(n-1). Combining these gives us O(rows*columns) + O(n-1). O(rows*columns) >= O(n-1), therefore it becomes O(rows*columns).

So this optimization improves the performance from O(r*c*n) to O(r*c), a factor of N. 

Lessons learned
I wasn't thinking of the performance when doing the problem at first, and ended up with a brute force algorithm. I just started coding the solution right away, doing the first solution that came to mind. I think it's normal to think of brute force first. The lesson here is that I should've thought out some solutions on paper before starting to code.


No comments:

Post a Comment

There was an error in this gadget