Saturday, October 23, 2010

Are you a TopCoder?

I haven't done a TopCoder algorithm problem for years. From what I remembered the 250-point level problems were a lot easier back then. I can't believe there are folks who can complete a such task within 15 minutes. I didn't time myself, but it took me about 4 hours to get this particular 250-point problem submitted. During my first attempt I tried searching all possible digits, but it didn't come out too well and it was difficult because I could not consider all the possible cases. After a few tries I knew there is got to be an easier approach. Since the problem is only interested in looking for the longest digits, I should start looking from the longest possible digits and if all the rules applied then I'm done. I started working through this greedy concept and still took me a few more tries and below is what I came up with.

Problem statement: SRM 192 DIV 1 250-point DigitMultiples
You are given two strings of digits, single and multiple. Your job is to find the length of the longest substring (which may be the whole string) of digits in single such that there is a corresponding substring (of the same length) in multiple which satisfies the following constraint. Each digit in the substring of multiple is the same exact integer multiple of the corresponding digit in the substring of single. So "48" is a multiple (4) of "12", but "72" is not a multiple of "36". Multiplication factors from 0 to 9 are possible. Leading zeros are *allowed* in single and multiple and all substrings.



class DigitMultiples {
    //Main rule logic
    private bool Rules(string subM, string subS) {
        int Factor;
        if (subS[0] == '0') {
            Factor = 0;
        } else {
            Factor = (subM[0] - '0') / (subS[0] - '0');
        }
        for (int i = 0; i < subM.Length; i++) {
            int iM = subM[i] - '0';
            int iS = subS[i] - '0';
            if (iS * Factor != iM) {
                if (Factor == 0 && iS != 0) {
                    Factor = iM / iS;
                    continue;
                }
                return false;
            }
        }
        return true;
    }
    //Feed all the possible digits from single and multiple
    private bool RuleHelper(string single, string multiple, int digit) {
        for (int m = 0; m + digit - 1 < multiple.Length; m++) {
            string subM = multiple.Substring(m, digit);
            for (int s = 0; s + digit - 1 < single.Length; s++) {
                string subS = single.Substring(s, digit);
                if (Rules(subM, subS)) {
                    return true;
                }
            }
        }
        return false;
    }
    //Search through string multiple using the longest possible digits
    public int getLongest(string single, string multiple) {
        int PossibleDigits;
        //Getting the longest possible digits
        if (multiple.Length < single.Length) {
            PossibleDigits = multiple.Length;
        } else {
            PossibleDigits = single.Length;
        }
        //Search from top down and quit once it is found
        for (int digit = PossibleDigits; digit >= 1; digit--) {
            if (RuleHelper(single, multiple, digit)) {
                return digit;
            }
        }
        return 0;
    }
}

Tuesday, October 19, 2010

Sharpen your skill as a programmer

The last couple months I've been involved with iPhone (2G / 3G / 3GS / 4) hardware and software repairs. Learning and practicing all the components that makes up an iPhone and reviving them even when it is completely dead from water damage. I've learned a great deal about them (You can read all about it on http://www.dociphone.com). However, I haven't had the time to do much coding at all.

I spoke with a very good friend of mine Money Mike about the issue. We brain-stormed on different ideas and we approached as if we were athletes training for an event. As a swimmer I practiced the fundamentals of kicking and breathing of swimming as part of my daily routine and I'm sure Kobe Bryant practices his basic free throws daily. As a programmer we ought keep our mind sharp and below are the routine that we came up with.

Updated on December 7th, 2010: I've revised the routine to something I've been doing.
First thing upon awake at 6:40am & last thing before going to sleep at 10:30pm (twice a day):


Prior watching a movie or a TV show:
  • Solve Rubik's cube 3x3x3 or 4x4x4 or 5x5x5 Rubik's Cube at least once


Once awhile:

To keep track of my progress. I have recorded my results on a Google doc spreadsheet and compiled the arithmetic portion into an annotated chart here.