Tuesday, May 31, 2016

GenomicRangeQuery (Codility)

Problem Statement: GenomicRangeQuery

C++ Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

vector<int> solution(string &S, vector<int> &P, vector<int> &Q) {
    // write your code in C++11 (g++ 4.8.2)
    std::vector<int> A(S.size(), 0);
    std::vector<int> C(S.size(), 0);
    std::vector<int> G(S.size(), 0);
    std::vector<int> T(S.size(), 0);

    auto index = 0;

    for (auto const &e : S)
    {
        if (e == 'A')
        {
            A[index]++;
        }
        else if (e == 'C')
        {
            C[index]++;
        }
        else if (e == 'G')
        {
            G[index]++;
        }
        else if (e == 'T')
        {
            T[index]++;
        }

        if (index > 0)
        {
            A[index] += A[index - 1];
            C[index] += C[index - 1];
            G[index] += G[index - 1];
            T[index] += T[index - 1];
        }
        ++index;
    }

    // At this time, A[i] is the total number of times A 
    // has been seen in the input string S until index i
    // So on with C, G and T vectors

    // Now we will check A, C, G and T arrays in that order
    // as this is the impact order as well (low to high)
    std::vector<int> retVal(P.size(), 0);

    for (auto index = 0; index < P.size(); ++index)
    {
        auto begin = P[index];
        auto end = Q[index];
        
        auto value = 1;
        
        do 
        {
            value = 1;
            bool bASeen = (begin == 0 && A[end] > 0) || (begin > 0) && A[end] > A[begin - 1];
            if (bASeen) break;

            value = 2;
            bool bCSeen = (begin == 0 && C[end] > 0) || (begin > 0) && C[end] > C[begin - 1];
            if (bCSeen) break;

            value = 3;
            bool bGSeen = (begin == 0 && G[end] > 0) || (begin > 0) && G[end] > G[begin - 1];
            if (bGSeen) break;

            value = 4;
            bool bTSeen = (begin == 0 && T[end] > 0) || (begin > 0) && T[end] > T[begin - 1];
            if (bTSeen) break;
        } while (0);

        retVal[index] = value;
    }
    return retVal;
}

C# Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
using System;
// you can also use other imports, for example:
// using System.Collections.Generic;

// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");

class Solution {
    public int[] solution(string S, int[] P, int[] Q) {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
        int[] A = new int[S.Length];
        int[] C = new int[S.Length];
        int[] G = new int[S.Length];
        int[] T = new int[S.Length];

        for (var i = 0; i < S.Length; ++i)
        {
            A[i] = 0;
            C[i] = 0;
            G[i] = 0;
            T[i] = 0;
        }

        var index = 0;

        foreach (var e in S)
        {
            if (e == 'A')
            {
                A[index]++;
            }
            else if (e == 'C')
            {
                C[index]++;
            }
            else if (e == 'G')
            {
                G[index]++;
            }
            else if (e == 'T')
            {
                T[index]++;
            }

            if (index > 0)
            {
                A[index] += A[index - 1];
                C[index] += C[index - 1];
                G[index] += G[index - 1];
                T[index] += T[index - 1];
            }
            ++index;
        }

        // At this time, A[i] is the total number of times A 
        // has been seen in the input string S until index i
        // So on with C, G and T vectors

        // Now we will check A, C, G and T arrays in that order
        // as this is the impact order as well (low to high)
        int[] retVal = new int[P.Length];
        for (var j = 0; j < P.Length; ++j)
        {
            retVal[j] = 0;
        }

        for (var k = 0; k < P.Length; ++k)
        {
            var begin = P[k];
            var end = Q[k];

            var value = 1;

            do
            {
                value = 1;
                bool bASeen = (begin == 0 && A[end] > 0) || (begin > 0) && A[end] > A[begin - 1];
                if (bASeen) break;

                value = 2;
                bool bCSeen = (begin == 0 && C[end] > 0) || (begin > 0) && C[end] > C[begin - 1];
                if (bCSeen) break;

                value = 3;
                bool bGSeen = (begin == 0 && G[end] > 0) || (begin > 0) && G[end] > G[begin - 1];
                if (bGSeen) break;

                value = 4;
                bool bTSeen = (begin == 0 && T[end] > 0) || (begin > 0) && T[end] > T[begin - 1];
                if (bTSeen) break;
            } while (false);

            retVal[k] = value;
        }
        return retVal;
    }
}

Learnings

  • This website helped me a lot to understand the concept of prefix sum applied to this problem.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)