Lab 4: Genetics - K-mer Analysis 
CS1234: Small-Scale Application Development

Background
What is a Gene Sequence?
Deoxyribonucleic acid (DNA) is the molecule that carries genetic instructions in all living things.
The information in DNA is stored as a code made up of four chemical bases: Adenine (A), Cytosine (C), Guanine (G), and Thymine (T).
A gene sequence is simply a linear string of these four characters (e.g., ACGTTAGC).

In Bioinformatics, analyzing the frequency of short, fixed-length subsequences (called k-mers) is fundamental.
It helps in assembling genomes from small fragments, identifying species, and finding repeating motifs that control gene expression.
For example, a high frequency of specific k-mers might indicate a binding site for a regulatory protein.

In Computer Science, this concept is identical to N-grams used in Natural Language Processing (NLP)
for tasks like plagiarism detection, text search indexing, and data compression.


Problem Description
You are building a tool to analyze a gene sequence.
We are investigating a specific biological phenomenon where we are only interested in a subset of k-mers, which we will call valid k-mers.

A k-mer is considered valid only if a specific 'restricted_base' (a single character supplied by the user) appears at most once in that k-mer.

Your task is to:
+ Generate all possible valid k-mers of length 'k' from the alphabet {A, C, G, T} using recursion.
+ Count how many times each of these valid k-mers appears in a provided 'gene' sequence.
+ Print the frequency of all valid k-mers in alphabetical order.

Input Format
1. First line: k (Integer) - The length of the k-mers to generate.
2. Second line: gene (String) - The gene sequence.
3. Third line: restricted_base (Character) - The base (a single character from the set {A, C, G, T}) that is allowed max once per k-mer.

Output Format
For every valid k-mer generated (in alphabetical order), print the k-mer and its count in the gene sequence on a new line.
Format: <K-mer>:<space><Count>

Constraints
+ 2 <= k <= 8
+ The input gene will only contain uppercase characters 'A', 'C', 'G', 'T'.
+ k <= lenth of the input gene <= 100
+ restricted_base will only be a single uppercase character from {'A', 'C', 'G', 'T'}

Sample Input 0:
2
ACGCGTACCC
C

Sample Output 0:
AA: 0
AC: 2
AG: 0
AT: 0
CA: 0
CG: 2
CT: 0
GA: 0
GC: 1
GG: 0
GT: 1
TA: 1
TC: 0
TG: 0
TT: 0

Sample Explaination 0:
Task: Count k-mers of length 2. Restricted Base: 'C' (Maximum 1 'C' allowed per k-mer).
Gene: ACGCGTACCC
We slide a window of size 2 across the gene. For each window, we check if it exists in our valid list (k-mers with at most one 'C').

Gene Indices:  0 1 2 3 4 5 6 7 8 9
Sequence:      A C G C G T A C C C

i=0  Window:   A C                 -> Valid (One 'C'). Count for "AC" increases.
i=1  Window:     C G               -> Valid (One 'C'). Count for "CG" increases.
i=2  Window:       G C             -> Valid (One 'C'). Count for "GC" increases.
i=3  Window:         C G           -> Valid (One 'C'). Count for "CG" increases.
i=4  Window:           G T         -> Valid (Zero 'C'). Count for "GT" increases.
i=5  Window:             T A       -> Valid (Zero 'C'). Count for "TA" increases.
i=6  Window:               A C     -> Valid (One 'C'). Count for "AC" increases.
i=7  Window:                 C C   -> INVALID (Two 'C's). Ignored.
i=8  Window:                   C C -> INVALID (Two 'C's). Ignored.

Sample Input 1:
3
GCTAGCTAGCTAGCT
A

Sample Output 1:
ACC: 0
ACG: 0
ACT: 0
AGC: 3
AGG: 0
AGT: 0
ATC: 0
ATG: 0
ATT: 0
CAC: 0
CAG: 0
CAT: 0
CCA: 0
CCC: 0
CCG: 0
CCT: 0
CGA: 0
CGC: 0
CGG: 0
CGT: 0
CTA: 3
CTC: 0
CTG: 0
CTT: 0
GAC: 0
GAG: 0
GAT: 0
GCA: 0
GCC: 0
GCG: 0
GCT: 4
GGA: 0
GGC: 0
GGG: 0
GGT: 0
GTA: 0
GTC: 0
GTG: 0
GTT: 0
TAC: 0
TAG: 3
TAT: 0
TCA: 0
TCC: 0
TCG: 0
TCT: 0
TGA: 0
TGC: 0
TGG: 0
TGT: 0
TTA: 0
TTC: 0
TTG: 0
TTT: 0


Notes & Submission Guidelines
+ Memory Management: Ensure all dynamically allocated memory (using malloc) is freed before the program terminates.
                     Failure to do so will result in a 0.5 mark deduction.
+ File Naming: Rename your .c file to your roll number (e.g., CS25B001.c) and create a .zip before uploading to Moodle.
+ Compilation: Your code will be compiled using gcc Q1.c -lm.
+ Autograding: ./check.sh
+ For Private Testcases: ./submit.sh

Practice Problems (Ungraded)
1. Modify your code to handle a 5th base, 'U' (Uracil), which replaces Thymine in RNA. The alphabet size becomes 5 {A, C, G, T, U}.
Ensure the recursion and array calculations adapt to this size dynamically.

2. Instead of a fixed alphabet, allow the user to input a string of unique characters to define the alphabet (e.g., "XYZ").
The system should generate k-mers based on this custom alphabet.

3. Instead of a simple character count constraint, implement a "Hamming Filter."
The user provides a "Reference K-mer" (e.g., "AAA"). 
Only generate and count k-mers that have a Hamming distance of exactly 1 from this reference (i.e., they differ by exactly one character).
Example: If Ref="AAA", valid k-mers are "AAC", "AAG", "AAT", "ACA", "AGA", etc. "AAA" (dist 0) and "ABC" (dist 2) are invalid.

