385 - DNA Translation WA

[md6nguyen]

Hi, I got a WA in 385 (DNA Translation) and cannot find out why. My algorithm is straightforward, I go forward and if I cannot find a valid primary or complentary strand then I go backward.

Can someone give me a test case to show that my program is wrong?

/* @JUDGE_ID: 39439PK 385 C */

#include <stdio.h>

#define NUM_BASES 4
#define MAX_LEN 256
#define CODON_LEN 3

#define ph "Phe"
#define le "Leu"
#define se "Ser"
#define ty "Tyr"
#define cy "Cys"
#define tr "Trp"
#define pr "Pro"
#define hi "His"
#define gl "Gln"
#define ar "Arg"
#define il "Ile"
#define me "Met"
#define th "Thr"
#define as "Asn"
#define ly "Lys"
#define va "Val"
#define al "Ala"
#define ap "Asp"
#define gu "Glu"
#define gy "Gly"

/* Amino Acid table lookup */
char *aminoAcid[NUM_BASES][NUM_BASES][NUM_BASES] = {
{{ph,ph,le,le}, {se,se,se,se}, {ty,ty,"",""},{cy,cy,"",tr}},
{{le,le,le,le}, {pr,pr,pr,pr}, {hi,hi,gl,gl},{ar,ar,ar,ar}},
{{il,il,il,me}, {th,th,th,th}, {as,as,ly,ly},{se,se,ar,ar}},
{{va,va,va,va}, {al,al,al,al}, {ap,ap,gu,gu},{gy,gy,gy,gy}},
};

/* index to Amino acid table */
#define U 0
#define C 1
#define A 2
#define G 3

int findStartCodon(char *s) {
int n = CODON_LEN;
return strncmp(s,"TAC",n)==0 || strncmp(s,"ATG",n)==0;
}

int findStopCodon(char *s, int isPrimary) {
int n = CODON_LEN;
if (isPrimary) {
return strncmp(s,"ATT",n)==0 || strncmp(s,"ATC",n)==0 ||
strncmp(s,"ACT",n)==0;
}
else {
return strncmp(s,"TAA",n)==0 || strncmp(s,"TAG",n)==0 ||
strncmp(s,"TGA",n)==0;
}
}

struct {
char *seq[MAX_LEN/CODON_LEN];
int len;
} proteinSeq;

int getline(char s[], int lim) {
int c, i;
i = 0;
while (--lim > 0 && (c=getchar()) != EOF && c != '\n') {
s[i++] = c;
}
s[i] = '\0';
if (c == EOF) return -1;
return i;
}

void printProteinSeq() {
int i;
for (i = 0; i < proteinSeq.len; i++) {
printf("%s", proteinSeq.seq[i]);
if (i < proteinSeq.len-1) printf("-");
}
printf("\n");
}

int baseConvert(char base, int isPrimary) {
switch(base) {
case 'A':
return isPrimary ? U : A;
case 'T':
return isPrimary ? A : U;
case 'G':
return isPrimary ? C : G;
case 'C':
return isPrimary ? G : C;
}
}

/* Generate Protein sequence for a forward order DNA strand */
int processForward(char *s) {
int i, j, sLen = strlen(s);
int idx[CODON_LEN]; /* index to aminoAcid lookup */
char *amino;
int isPrimary;

proteinSeq.len = 0; /* Number of amino acids in protein */
if (sLen <= CODON_LEN) return 0;
isPrimary = s[0] == 'T' ? 1 : 0;
for (i = CODON_LEN; i <= sLen-CODON_LEN; i += CODON_LEN) {
if (findStopCodon(&s[i], isPrimary)) break;
for (j = 0; j < CODON_LEN; j++) {
idx[j] = baseConvert(s[i+j], isPrimary);
}
amino = aminoAcid[idx[0]][idx[1]][idx[2]];
if (strlen(amino)==0) return 0;
proteinSeq.seq[proteinSeq.len++] = amino;
}
if (proteinSeq.len == 0 || i > sLen-CODON_LEN) {
return 0;
}
else {
printProteinSeq();
return 1;
}
}

int main() {
int i, sLen;
int goBackward = 0;

char DNAStrand[MAX_LEN];

char *s, *start, *end, c;

/* Read DNA strand */
while (getline(DNAStrand, MAX_LEN) != -1) {
if (strcmp(DNAStrand, "*") == 0) break;
s = DNAStrand;
goBackward = 0;
while (*s != '\0') {
if ( findStartCodon(s) && processForward(s) ) {
break;
}
s++;
if (*s == '\0' && !goBackward) {
goBackward = !goBackward;

/* Reverse DNA strand */
for (start=DNAStrand, end=s-1; start < end; start++, end--) {
c = *start;
*start = *end;
*end = c;
}
s = DNAStrand;
}
}
if (*s=='\0') printf("*** No translatable DNA found ***\n");

}

}

[d91-lek]

Test cases my way too, please!

[c]
/* @JUDGE_ID: 49998ME 385 C "Brute force" */

/* Work in DNA, not mRNA. */


#include <stdio.h>
#include <string.h>


char *strrev(char *str)
{
char *b = str, *e = str + strlen(str) - 1;
char tmp;
while(b < e) {
tmp = *e;
*e = *b;
*b = tmp;
b++;
e--;
}
return str;
}

/* {T, C, A, G}
A <-> T, C <-> G
10 <-> 00, 01 <-> 11
dna ^= 2
*/
char *dnacomplement(char *dna)
{
char *c = dna;
while(*c) {
switch(*c) {
case 'T': *c = 'A'; break;
case 'A': *c = 'T'; break;
case 'C': *c = 'G'; break;
case 'G': *c = 'C'; break;
};
c++;
}
return dna;
}


enum basecode {T = 0, C = 1, A = 2, G = 3};
/* dnacode[1:st][3:rd][2:nd] */
char dnacode[4][4][4][4] = {{{{"Phe"},{"Ser"},{"Tyr"},{"Cys"}},
{{"Phe"},{"Ser"},{"Tyr"},{"Cys"}},
{{"Leu"},{"Ser"},{"---"},{"---"}},
{{"Leu"},{"Ser"},{"---"},{"Trp"}}},
{{{"Leu"},{"Pro"},{"His"},{"Arg"}},
{{"Leu"},{"Pro"},{"His"},{"Arg"}},
{{"Leu"},{"Pro"},{"Gln"},{"Arg"}},
{{"Leu"},{"Pro"},{"Gln"},{"Arg"}}},
{{{"Ile"},{"Thr"},{"Asn"},{"Ser"}},
{{"Ile"},{"Thr"},{"Asn"},{"Ser"}},
{{"Ile"},{"Thr"},{"Lys"},{"Arg"}},
{{"Met"},{"Thr"},{"Lys"},{"Arg"}}},
{{{"Val"},{"Ala"},{"Asp"},{"Gly"}},
{{"Val"},{"Ala"},{"Asp"},{"Gly"}},
{{"Val"},{"Ala"},{"Glu"},{"Gly"}},
{{"Val"},{"Ala"},{"Glu"},{"Gly"}}}};



int synthesize(char* dna) {
char *base = strstr(dna, "ATG");
enum basecode bc[3];
int bcidx = 0;
char *aminoacid, protein[(4*255)/3+1];
char *pend = protein;

if(!base)
return 0;


base += 3; /* ATG */
while(*base) {
switch(*base) {
case 'T': bc[bcidx] = T; break;
case 'A': bc[bcidx] = A; break;
case 'C': bc[bcidx] = C; break;
case 'G': bc[bcidx] = G; break;
};
if(bcidx == 2){
aminoacid = dnacode[bc[0]][bc[2]][bc[1]];
if(*aminoacid == '-'){
*(--pend) = ""[0];
printf("%s\n", protein);
return 1;
}
*(pend++) = *(aminoacid++);
*(pend++) = *(aminoacid++);
*(pend++) = *(aminoacid);
*(pend++) = '-';
bcidx = 0;
} else
bcidx++;
base++;
}

return 0;
}

main()
{
char dna[256];

while(scanf("%s", dna), dna[0]!='*')
if(!synthesize(dna)
&& !synthesize(strrev(dna))
&& !synthesize(dnacomplement(dna))
&& !synthesize(strrev(dna)))
printf("*** No translatable DNA found ***\n");
}

[/c]

[Gigi's Baby]

To d91-lek:
I have seen your code. You just find the first "ATG" in the string as the head of the
strand , but maybe the head of the strand is not the first "ATG", so you should try all the
"ATG" as the head.

[d91-lek]

To Gigi's Baby:
The first ATG is the start of the strand. All codes in dna are meaningful
so the only thing stopping protein synthesizing once you have started is
strand end or a stop code. Admittedly, there could be more proteins in
the strand, but not according to the problem specification.

Actually my fault was ...ATGTGA... - valid but empty strands. The output
for these should be *** No translatable DNA found ***. Besides that, I
did *(--pend) = '\0', writing before the string when no protein was found.
With no string-end the last protein was printed (in the best case).

The test case I needed was:

<a valid protein>
ATGTGA
*

OK, over and out. I'll be at 179.

[Gigi's Baby]

I didn't read the problem description carefully.
My AC code tried all the ATG

[d91-lek]

Please don't be sorry because you
are generous and I am cheap. :wink:

[Robert Gerbicz]

I get only WA. What is the correct output for the above posted tricky:

Code: Select all

ATGTGA
*


I would appreciate more (critical) input/output!

[brianfry713]

My AC program prints "*** No translatable DNA found ***" for any sequence of less than 9 characters.