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.


Sunday, November 9, 2014

SRM 636 Div 2 250-pt

Problem
http://community.topcoder.com/stat?c=problem_statement&pm=13480&rd=16079

Note
This is one of the harder 250 point problems i've ran into. Looking at the stats this seems to be the case for others as well; only 67% correct and 195 avg points.

Code
public int count(int[] stones)
{
int stonesPerBucket = getStonePerBucket(stones);

int posActions = 0;
int negActions = 0;

for(int i = 0; i < stones.Length; i++)
{
int xFerAmt = stonesPerBucket - stones[i];
if (xFerAmt % 2 != 0)
return -1;

if(xFerAmt < 0)
negActions += xFerAmt;
else if (xFerAmt > 0)
posActions += xFerAmt;
}

if (posActions + negActions == 0)
return posActions / 2;
else
return -1;

}
public int getStonePerBucket(int[] stones)
{
int sum = 0;
foreach(int i in stones)
sum+=i;

int want = sum / stones.Length;

return want;

}

Analysis
i really overthought this one at first. My initial solution, which failed many cases, looped through and tried to add/substract stones between the buckets. After thinking about it some more I realized this didn't have to be that hard. Just need the difference between the # of stones in each bucket and the required stones per bucket, and the negative differences must balance with the positive balances.

Lesson learned - need to understand the problem statement fully before jumping into the coding. In other words, need to interpret the problem and come up with a design for the solution before jumping into implementing the code.

SRM 637 Div 2 250-pt

Problem
http://community.topcoder.com/stat?c=problem_statement&pm=13505&rd=16080

You're given two int[] with the same length. Count the number of times the second int[] has a larger value at i than the first int[].

Code
public int calc(int[] snuke, int[] sothe)
{
int win = 0;
for(int i = 0; i < snuke.Length; i++)
{
if (snuke[i] > sothe[i])
win++;
}
return win;

}

Analysis
O(n) where n is the length of the arrays. 

SRM 638 Div 2 250-pt

Problem
http://community.topcoder.com/stat?c=problem_statement&pm=13521&rd=16081

Convert a word in snake case to camel case. This means remove _'s and each letter after the _ needs to be capitalized.
For example: good_morning_world -> goodMorningWorld.

Code
public string toCamelCase(string variableName)
{
StringBuilder sb = new StringBuilder();
bool makeUpper = false;
foreach(char c in variableName)
{
if (c == '_')
makeUpper = true;
else
{
if (makeUpper)
{
makeUpper = false;
sb.Append(Char.ToUpper(c));
}
else
sb.Append(c);
}

}
return sb.ToString();

}

Analysis
Iterate through the string once. It's O(n) where n=length of string. 

Is it 'coder' or 'software engineer'?

Is it coder? Is it software engineer? Programmer? Software developer?

Those are just job titles meaning the same thing: get a problem, design the solution to that problem, code the solution, and then test the code you wrote. Depending on the size of the problem and the team these things might get partitioned out such that individuals are given a smaller problem to solve. But it always boils down to those four tasks:
1) receive requirements 
2) design the solution 
3) write the code
4) test what you wrote

Notice I said receive the requirements, which is quite vague? That's because sometimes you're going to be the one gathering the requirements from the customer, and other times you're going to get a detailed spec saying which component you're responsible for, and everything in between.

Testing is the same way; minimally you are going to unit test the code YOU wrote. If you're a one man shop you're going to also need to do full blown testing on the entire program.

Requirements and testing are jobs that can be done by non-programmers. Sometimes the programmers have to do those jobs though. In any case a programmer/coder/SWengineer is always going to do those 4 things mentioned above no matter what your job title.

Friday, November 7, 2014

Dexterity - Alternate form will not checkin to source safe

Problem
I modified a form and can't check it into the repository. I've tried several things, including hitting Update SCC state over and over, but it always stays as "Main Product"

Solution
Sometimes you just need to bypass Dexterity to get things to work. In this case I manually added the exported alternate form into the VSS and tricked it into working.

1. Export the alternate form as a text file
2. Copy it to the VSS server
3. Add it into the repository
4. In Dex do Update SCC state. Notice that it no longer says Main Product
5. Lock the resource and check it in.

Step 5 is important because when you check in an alternate resource it only saves the parts you modified, and since we had to force it into the repository it had everything, including all the original form's fields. So locking and checking in gets it into the right state.

Wednesday, November 5, 2014

Writing a spec

Over the last few years I've been developing at a crazy pace, and I haven't had the time to write long specs. Instead, how I write specs has evolved to adapt to the pace of development.

First im making the assumption that I'm given the requirements in some form, from highly detailed specs to vague UI mockups on napkins.

Steps to write the spec
1. For each requirement break it down into concrete coding tasks. These should explain the name (ex: a function name) and what it should do (ex: insert new record into table)

2. From this list of coding tasks a design will emerge. 

3. Illustrate the design with diagrams (ex: database, classes, data flow) 

4. Review and refactor the design until duplication is minimized.

Benefits
1. Instructions for writing the code.

2. Precise estimates. Because the coding tasks are concrete, ie not vague, explanations, precise estimates can be made.

3. Explanation of the design, which makes future maintenance easier.

4. Minimize design changes during coding because the design was reviewed and refactored. That doesn't mean it won't change if something was overlooked.



There was an error in this gadget