csharptrie project on Google Code

Added project csharptrie - a C# implementation of trie data structure to Google Code.

building tree view from given child-parent pairs in hashmap

Ex: The child-parent pairs are in a hashmap 'childParentMap' as shown below. The root node is with value 0.
1 -> 0
2 -> 1
3 -> 2
4 -> 2
5 -> 0

The tree node data structure has an int value and list of children tree nodes.

class TreeNode:
    int value
    IList children
   
    //constructor
    TreeNode(int value):
        this.value = value
        children = new List()


The code first traverses through the childParentMap hashmap to build the value->TreeNode hashmap 'valueNodeMap'. It traverses through it again to get child and parent values, their equivalent nodes and adds the child node to the parent node. The root node with value 0 is created separately (root of the tree).

TreeNode createTreeView(Hashmap childParentMap):
    // build value->TreeNode map
    Hashmap valueNodeMap = new Hashmap()
    foreach (KeyValuePair kvPair in childParentMap):
        int value = kvPair.Key
        TreeNode node = new TreeNode(value)
        if !valueNodeMap.ContainsKey(value):
            valueNodeMap.Add(value, node)
   
    // add root value 0 and root node to valueNodeMap
    int rootValue = 0;
    TreeNode rootNode = new TreeNode(rootValue);
    valueNodeMap.Add(rootValue, rootNode);
   
    // for child and parent values, find equivalent nodes and
    // add child node as child to parent node
    foreach (KeyValuePair kvPair in childParentMap):
        int childValue = kvPair.Key
        int parentValue = kvPair.Value
        TreeNode childNode = valueNodeMap[childValue]
        TreeNode parentNode = valueNodeMap[parentValue]
       
        parentNode.children.Add(childNode)
   
    // return root
    return rootNode


Time is O(n).

There is a recursive solution too but it takes O(n^2) time.

The code is similar to building a graph from an adjacency list.

[H/T ai, as, sc, jf, se]

bracket matching

Check for brackets matching - curly, square, round, {}[]() - and return boolean.
ex: return true for
{}
{[()]}
{()[]}
return false for
{
}


bool bracketMatching(char[] str):
    bool result = true
    Stack stack = new Stack()
   
    //close-open bracket map
    Hashmap bracketMap = new Hashmap()
    bracketMap.Add('}', '{')
    bracketMap.Add(')', '(')
    bracketMap.Add(']', '[')

    foreach (char c in str):
        if (c == '{' || c == '[' || c == '('):
            stack.Push(c)

        if (c == '}' || c == ']' || c == ')'):
            if (stack.isEmpty()):
                result = false
                break
            //tos should be open bracket and c close bracket
            char tos = stack.Pop()
            if (tos != bracketMap[c]):
                result = false
                break
    if (!stack.isEmpty()):
        result = false
    return result


[Hat tip to BR]

codejam 2010 qualifications

qualifications problems


A Snapper Chain

The snappers are same as incrementing binary bits. The overflow is discarded. ANDing K with 111...N bits gives the state of the snappers after K snaps. The count of 1 bits of that number if same as N means the state is ON else OFF.


string snapperChain(int n, int k)
    int nbit = (int) Math.Pow(2, n) - 1;
    int result = nbit & k;
    int count1 = count1bits(result);
   
    if (count1 == n)
        return "ON";
    else
        return "OFF";

int count1bits(int num)
    int n = num;
    int count = 0;
    while (n != 0)
        n = n & (n - 1);
        count++;
    return count;



B Fair Warning

I used this IntX code for 64+ bits data structure. The trick is to subtract the min of the array and find their gcd - which gives Tmax. ymin is calculated then. One way is to sort the array and find the gcd from index 1...N. Another way is to find the min and put checks for 0 in gcd function.

string fairWarning(IntX[] input)
    IntX Tmax = -1;
    IntX ymin = -1;

    //Array.Sort(input);
    IntX min = minf(input);
   
    for (int i = 0; i < input.Length; i++)
        input[i] = input[i] - min;
    Tmax = gcdf(input);

    if (Tmax == 0 || (min % Tmax) == 0)
        ymin = 0;
    else
        ymin = Tmax - (min % Tmax);
   
    return ymin.ToString()

//min of array
IntX minf(IntX[] input)
    IntX min = input[0];
    for (int i = 0; i < input.Length; i++)
        if (input[i] < min)
            min = input[i];
    return min;

//gcd of array
IntX gcdf(IntX[] input)
    IntX a = input[0];
    for (int i = 1; i < input.Length; i++)
        IntX b = input[i];
        if (i < input.Length-1 && a == 0)
            i++;
            a = input[i];
        if (i < input.Length-1 && b == 0)
            i++;
            b = input[i];
        a = gcdf(a, b);
    return a;

//gcd of a, b
IntX gcdf(IntX a, IntX b)
    if (a == 0 && b == 0)
        throw new ArgumentException();
    while (b != 0)
        IntX t = a % b;
        a = b;
        b = t;
    return a;



C Theme Park

Limits
1 <= T <= 50
gi <= k

Small dataset
1 <= R <= 1000
1 <= k <= 100
1 <= N <= 10
1 <= gi <= 10

Large dataset
1 <= R <= 10^8
1 <= k <= 10^9
1 <= N <= 1000
1 <= gi <= 10^7

My first solution was of O(R*N) time i.e. 10^8 * 10^3 which does not work for large dataset. The trick is to first calculate and cache the sums and save the next group position which takes O(N*N) time i.e. 10^6 and then add the sums in O(R) time i.e. 10^8 - the sum is calculated for each position i of N in cache[] and the next group index in nextCacheIndex[].

Int64 themePark(Int64 R, Int64 k, Int64[] q)
    Int64 totalMoney = 0;
    Int64 groups = q.Length;

    Int64[] cache = new Int64[q.Length];
    Int64[] nextCacheIndex = new Int64[q.Length];

    for (Int64 i = 0; i < groups; i++)
        Int64 sum = 0;
        Int64 nextIndex = i;

        Int64 groupCount = 0;
        //while sum <= k and not at the end of the *current* queue
        while ((sum + q[nextIndex] <= k) && (groupCount < groups))
            sum += q[nextIndex];
            nextIndex = (nextIndex + 1) % groups;
            groupCount++;
        cache[i] = sum;
        nextCacheIndex[i] = nextIndex;

    Int64 index = 0;
    for (Int64 r = 0; r < R; r++)
        totalMoney += cache[index];
        index = nextCacheIndex[index];

    return totalMoney;


[codejam]

permutations and combinations of string - derivative

This is a derivative of permutations of a string. For digits [1, 2, 3], we want [1, 12, 21, 123, 132, 213, 231, 312, 321]. The permute_wrapper loops through the input array to permute the sub-array with limit marking its end.

def permute_wrapper(digits):
    input = [i for i in range(1, digits+1)]
    print(input)
    output = [0 for x in range(len(input))]
    flags = [False for x in range(len(input))]
    depth = 0
   
    for i in range(len(input)):
        permute_(input, i+1, output, flags, depth, nums)
   
    return nums

def permute_(input, limit, output, flags, depth, nums):
    if depth == limit:
        num = 0
        factor = 1
        for i in range(limit, 0, -1):
            num = num + output[i - 1] * factor
            factor *= 10
        nums.append(num)
        return None
   
    for i in range(limit):
        if flags[i] == True:
            continue
        flags[i] = True
        output[depth] = input[i]
       
        permute_(input, limit, output, flags, depth + 1, nums)
       
        flags[i] = False


For combinations of digits, instead of using a string buffer for output, an int array is used. index is used to keep track of where to insert the digit. The number is between index and 0 of output array.


def combine_wrapper(digits):
    input = [i for i in range(1, digits+1)]
    print(input)
    output = [0 for x in range(len(input))]
    start = 0
    index = 0
   
    combine_(input, output, start, index, nums)
   
    return nums

def combine_(input, output, start, index, nums):
    if start == len(input):
        return None
   
    for i in range(start, len(input), 1):
        output[index] = input[i]
       
        num = 0
        factor = 1
        for x in range(index, -1, -1):
            num = num + output[x] * factor
            factor *= 10
        nums.append(num)
       
        index+=1
        combine_(input, output, i + 1, index, nums)
        index-=1


nine-digit polydivisible number with 1 to 9 exactly once: 381654729

Arrange the digits 1 to 9 in order so that the first two digits form a multiple of 2, the first three digits form a multiple of 3, the first four digits form a multiple of 4 etc. and finally the entire number is a multiple of 9. It contains the digits 1 to 9 exactly once each. [Polydivisible number]

There are 9^9 9-digit numbers; 9^9 = 387420489. There are only 9! numbers with 1-9 appearing only once; 9! = 362880 (1000 times smaller set). So, the trick is to find those 9! first (using permutations or otherwise) and then check for polydivisiblity. 381654729 is the only number.

#checks if a number is polydivisible
#polydivCheck(381654729)
def polydivCheck(n, digts):
    for i in range(digts, 0, -1):
        if (n % i != 0):
            return False
        n = int(n / 10)
    return True

#finds permutation for array 'input' and puts the numbers in list 'nums'
def permute(digits, input, output, flags, depth, nums):
    if depth == len(input):
        num = 0
        factor = 1
        for i in range(digits, 0, -1):
            num = num + output[i - 1] * factor
            factor *= 10
        nums.append(num)
   
    for i in range(len(input)):
        if flags[i] == True:
           continue

        flags[i] = True
        output[depth] = input[i]
       
        permute(digits, input, output, flags, depth + 1, nums)
       
        flags[i] = False

#wrapper function to call the recursive 'permute' function
def permute_wrapper(digits):
    input = [i for i in range(1, digits+1)]
    output = [0 for x in range(len(input))]
    flags = [False for x in range(len(input))]
    depth = 0
    nums = []
   
    permute(digits, input, output, flags, depth, nums);
   
    return nums

#calls 'permute_wrapper' and for each number checks for polydivisibility
def getPolydivNums(digits):
    nums = permute_wrapper(digits)
    numbers=[]
    for num in nums:
        if polydivCheck(num, digits):
            numbers.append(num)
    return numbers

#start(9)
def start(digits):
    nums = getPolydivNums(digits)
    for n in nums:
        print(n)


[Hat tip to JF]

print all word combinations from phone number

Print all words combinations from phone number.
ex: 111-1111 -> AAA-AAAA, AAA-AAAB ... CCC-CCCC

char charkeyMap(int digit, int position)
ex:
charkeyMap(1, 0) = 'A'
charkeyMap(1, 1) = 'B'
charkeyMap(1, 2) = 'C'


void printCombinations(int[] in):
    char[] out = new char[in.length]
   
    //first combination ex: 111-1111 -> AAA-AAAA
    for(int i = in.length -1; i >= 0; i--):
        out[i] = charkeyMap(in[i], 0)

    int i
    while (true):
        out.print()
        i = in.length - 1;
       
        while (true):
            //if A then B
            if out[i] == charkeyMap(in[i], 0):
                out[i] = charkeyMap(in[i], 1)
                break
           
            //if B then C
            if out[i] == charkeyMap(in[i], 1):
                out[i] = charkeyMap(in[i], 2)
                break
           
            //if C then A and let it loop for the adjacent digit
            if out[i] == charkeyMap(in[i], 2):
                out[i] = charkeyMap(in[i], 0)
                //let it loop
           
            i--
            if i < 0 break
       
        if i < 0 break


fix duplicates in sorted array

12233344445 -> 12345


//using 3 pointers
fixDuplicatesInSortedArray(Integer[] a):
    start = 0
    end = 0
    destination = 0

    while(start < a.length):
        while(end < a.length && a[end] == a[start]):
            end++
        end--
       
        //copy the distinct element
        a[destination] = a[start]
        destination++
       
        start = end + 1
        end = start

    //null out the rest
    while destination < a.length:
        a[destination] = null

    return

//using 2 pointers
fixDuplicatesInSortedArray(Integer[] a):
    prev = 0
    curr = 1
   
    while curr < a.length():
        while curr < a.length && a[curr] == c[prev]:
            curr++
        if curr == a.length() break
       
        prev++
        a[prev] = a[curr]
        curr++
   
    //null out the rest
    prev++
    while prev < a.length:
        a[prev] = null
   
    return



[Hat tip to MG]

topical arguments

[Hats off to xkcd - images from Time Travel, Voynich Manuscript]

induction too

My lame attempt at this.


[Hats off to xkcd - images from Fetishes, No Pun Intended, Voynich Manuscript, Designated Drivers]