FLAMES code

I think all of you would know the FLAMES game played by school students and teenagers.
Using this game, they predict the relationship between two persons.
F-Friends
L-Love
A-Affection
M-Marriage
E-Enemies
S-Siblings

Fist, you should take the two names:

ABCD
DEFA

The common letters are stroked off(Shown in bold here).
Then the remaining letters are counted. Here it is 4.

Now, the calculation is done as follows

FLAMES
FLA ES
F A ES
A ES
ES
S

So, the relationship is Siblings.

Till counting the number of remaining letters, it is easy. But to get the relationship, the logic is a little complicated.

Lets work it out here.

Code:

#include<iostream.h>
#include<conio.h>
#include<string.h>
main()
{
      int f[6]={0,0,0,0,0,0},n,ch;
      char n1[100],n2[100];
      gets(n1);
      gets(n2);
      int l1,l2;
      l1=strlen(n1);
      l2=strlen(n2);
      int i,j;
      for(i=l1-1;i>=0;i--)
      {
            if(n1[i]!='\0')
            {
            for(j=l2-1;j>=0;j--)
            {
                                if(n2[j]!='\0')
                                {
                                                              if(n1[i]==n2[j])
                                                               {
                                                                              n1[i]=n2[j]='\0';
                                                                              break;
                                                               }
                                }
                                
            }      
            }
      }
      int count=0;
      for(i=0;i<l1;i++)
      {
                       if(n1[i]!='\0')
                        count=count+1;
      }
      for(j=0;j<l2;j++)
      {
                       if(n2[j]!='\0')
                         count=count+1;
      }
cout<<"count is "<<count;
}

This code counts the number of letters left after striking out the common letters.

Cool something different to code but does your code takes care of following scenario?

If any of the two names are like following
ABCDA
DEFA

Then in above case, first name has two 'A' s and second name has only one 'A' so do the program should cancel all 3 'A's or should cancel only 2'A's -one from each name?

no. only 2 'A's will be cancelled.

The code currently does not gives the correct output. E.g., consider
Name 1: Pradeep
Name 2: Prad

The output should 3 but the code give output as 2.

The code need small correction for this:

Code:

n1[i]=n2[i]='\0';

need to be changed to

Code:

 n1[i]=n2[j]='\0';

Also the check

Code:

if(n1[i]!='\0')

inside the first for loop is not required (though it does not create and issue).

What if after removing common characters nothing is left-out (e.g., i compare Pradeep with Pradeep)?

-Pradeep

I get the output as 3 only. Try executing it once again.

i edited

Code:

  n1[i]=n2[j]='\0';

Thanks

And if nothing is left out, it will be considered as Friends

Below is my code for the given problem statement.

Code:

#include "stdio.h"
#include "string.h"


#define MAX_NAME_LEN 80
#define INVALID 0
#define VALID 1
#define ASCII_UPPER_CASE_LOWER_LIMIT 65
#define ASCII_UPPER_CASE_UPPER_LIMIT 90
#define ASCII_LOWER_CASE_LOWER_LIMIT 97
#define ASCII_LOWER_CASE_UPPER_LIMIT 122
#define UPPER_CASE_LOWER_CASE_DIFF ASCII_LOWER_CASE_LOWER_LIMIT - ASCII_UPPER_CASE_LOWER_LIMIT


typedef enum {EMPTY = 0, FRIENDS, LOVE, AFFECTION, MARRIAGE, ENEMIES, SIBLINGS} flames_t;


/* Validates if name contains only alphabets */
int validate_name(char* name, int len) {
  int i = 0;
  for(i = 0; i < len; i++) {
    if(!(((name[i] >= ASCII_LOWER_CASE_LOWER_LIMIT)
        && (name[i] <= ASCII_LOWER_CASE_UPPER_LIMIT))
        || ((name[i] >= ASCII_UPPER_CASE_LOWER_LIMIT)
        && (name[i] <= ASCII_UPPER_CASE_UPPER_LIMIT)))) {
      return INVALID;
    }
  }
  return VALID;
}


/* Convert all characters to upper case */
void convert_to_upper_case(char *name, int len) {
  int i = 0;
  for(i=0; i < len; i++) {
    if((name[i] >= ASCII_LOWER_CASE_LOWER_LIMIT)
        && (name[i] <= ASCII_LOWER_CASE_UPPER_LIMIT)) {
        name[i] -= UPPER_CASE_LOWER_CASE_DIFF;
    }
  }
}


/* Eliminates common characters from both name by replacing them by '/0' */
void eliminate_common_characters(char *name1, int len1, char *name2, int len2) {
  int i = 0, j = 0;
  for(i = 0; i < len1; i++) {
    for(j = 0; j < len2; j++) {
      if(name1[i] == name2[j]) {
        name1[i] = name2[j] ='\0';
        break;
      }
    }
  }
}


/* Count the number of characters in a string that has non-zero value */
int char_count(char *name, int len) {
  int count = 0;
  int i = 0;
  for(i = 0; i < len; i++) {
    if(name[i] !='\0') {
      count++;
    }
  }
  return count;
}


/* Determine applicable flames based on number of uncommon characters */
flames_t determine_applicable_flames(int count) {
  //declaring array containing each item of flames
  //all except 1 element will be one by one set to EMPTY based on calculation
  flames_t flames[6] = {FRIENDS, LOVE, AFFECTION, MARRIAGE, ENEMIES, SIBLINGS};

  //declaring variable to hold the result of calculation
  //initializing by EMPTY
  //if variable does not get reset, EMPTY will specify error in calculation
  flames_t result = EMPTY;

  //declaring a varibale to keep track of last deleted flames item
  int index = 0;

  int i = 0, j = 0;

  //checking number of uncommon characters
  //for 0 uncommon characters, flames should be Friends
  if(count != 0) {
    //five of six items of flames need to be removed
    //removing one item per loop
    for(i = 1; i <= 5; i++) {
      j = 0;
      while(1) {
        //considering flames items that still exist
        if(flames[index] != EMPTY) {
          j++;
        }

        //if the current item is "uncommon character count" item
        //remove the item by setting value to EMPTY
        if(j == count) {
          flames[index] = EMPTY;
          break;
        } else {
          index++;

          //flames items have index from 0 to 5
          //reseting index to 0, when it's incremented after checking last item
          index = index % 6;
        }
      }
    }

    for(i = 0; i <= 5; i++) {
      if(flames[i] != EMPTY) {
        result = flames[i];
        break;
      }
    }
  } else {
    //setting flames to Friends
    result = FRIENDS;
  }

  return result;
}


/* Display the applicable flames */
void display_applicable_flames(flames_t flames) {
  switch(flames) {
  case EMPTY:
    printf("Error in calculation\n");
    break;
  case FRIENDS:
    printf("Friends\n");
    break;
  case LOVE:
    printf("Love\n");
    break;
  case AFFECTION:
    printf("Affection\n");
    break;
  case MARRIAGE:
    printf("Marriage\n");
    break;
  case ENEMIES:
    printf("Enemies\n");
    break;
  case SIBLINGS:
    printf("Siblings\n");
   break;
  }
}


int main() {
  flames_t result = EMPTY;
  char name1[MAX_NAME_LEN] = {0};
  char name2[MAX_NAME_LEN] = {0};
  int len1 = 0, len2 = 0;
  int count = 0;
  int i = 0, j = 0;

  //taking names as input
  scanf("%s", name1);
  scanf("%s", name2);

  //determining length of names
  len1 = strlen(name1);
  len2 = strlen(name2);

  //validating names
  if((validate_name(name1, len1) == INVALID)
      || (validate_name(name2, len2) == INVALID)) {
    printf("Invalid names\n");
    return 0;
  }

  //converting all characters of string to upper case
  convert_to_upper_case(name1, len1);
  convert_to_upper_case(name2, len2);

  //eliminating common characters from both names
  eliminate_common_characters(name1, len1, name2, len2);

  //counting number of uncommon characters in both names
  count = char_count(name1, len1) + char_count(name2, len2);

  //determining the flames applicable based on the number of uncommon characters
  result = determine_applicable_flames(count);

  //displaying the applicable flame count
  display_applicable_flames(result);

  return 0;
}

Compile the file with above code and run as:
a.exe < input.txt > output.txt [on windows]
a.out < input.txt > output.txt [on linux]

Here,
a.exe or a.out are the executables generated after compilation

input.txt is the file containing two names for which FLAMES need to be calculated, e.g., if the names are Pradeep and Prad, then input.txt will be
Pradeep
Prad

P.S.:
1. The input can be in same line separated by space as
Pradeep Prad
2. The code considers that the maximum length of a name will be 79 characters. To change the maximum length modify the pre-processor directive MAX_NAME_LEN and recompile the code.

output.txt is the output file containing result, for given example output.txt will contain
Friends

-Pradeep

can u please explain your logic?

I have modified the code to make some items self-explanatory. Also added comments to the code.

The main logic to calculating FLAMES based on the calculated number of uncommon characters is written in function "determine_applicable_flames". Let me know if it need more explanation.

-Pradeep

Please ckeck my program also in Java for this Flames thing. Any doubts or flaws in this, feel free to speak.

Code:

/*
 * FlamesProgram.java
 *
 * Created on May 18, 2009, 9:54 AM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */
package myjava;
import java.util.ArrayList;
/**
 *
 * @author shalinig
 */
public class FlamesProgram {
    
    public static void main(String[] args) {
        
        /* Specify any name1 -hardcoded */
        StringBuilder name1 = new StringBuilder("Pradeep");
        /* Specify any name2 -hardcoded*/
        StringBuilder name2 = new StringBuilder("Pradeep");
        ArrayList<String> flamesArrayList = new ArrayList<String>();
        int count = 0;
        
        
        System.out.println("Name 1: " + name1.toString());
        System.out.println("Name 2: " + name2.toString());
        
        name1.replace(0,name1.length(),name1.toString().toUpperCase());
        name2.replace(0,name2.length(),name2.toString().toUpperCase());
        
        if(!name1.toString().equalsIgnoreCase(name2.toString())){
            
            
            /* Loop to replace all common letters in both names with 1 */
            for (int i = 0; i < name1.length(); i++) {
                
                for (int j = 0; j < name2.length(); j++) {
                    
                    if (name1.charAt(i)!='1' && name2.charAt(j)!='1' && (name1.charAt(i) == name2.charAt(j))) {
                        name1.replace(i, i + 1, "1");
                        name2.replace(j, j + 1, "1");
                        count+=2;
                        
                    }
                }
                
            }
            
            
            
            count=name1.length()+name2.length()-count;
            
            /* Adds the FLAMES into an arrayList */
            flamesArrayList.add("F");
            flamesArrayList.add("L");
            flamesArrayList.add("A");
            flamesArrayList.add("M");
            flamesArrayList.add("E");
            flamesArrayList.add("S");
            
            /* Loop that calculates Flames */
            for (int i = flamesArrayList.size(); i > 1; i--) {
                
                int index = count % (i);
                int temp = flamesArrayList.size() - index;
                if (index == 0) {
                    flamesArrayList.remove(flamesArrayList.size() - 1);
                } else {
                    flamesArrayList.remove(index - 1);
                }
                
                for (int k = 0; k <= temp && temp < flamesArrayList.size(); k++) {
                    
                    flamesArrayList.add(k, flamesArrayList.get(flamesArrayList.size() - temp));
                    flamesArrayList.remove(flamesArrayList.size() - temp);
                    temp--;
                    
                }
                
            }
            /* Finally arrayList is left with only one letter which determines flame */
            System.out.println("Flame in between is : " + determineFlameType(flamesArrayList.get(0)));
            
        }else{
            System.out.println("Both the names are same");
        }
        
    }
    
    /* Static method that returns the type of Flame based on the flame letter passed */
    public static String determineFlameType(String flameLetter) {
        
        String flameType = null;
        switch (flameLetter.charAt(0)) {
            
            case 'F':
                flameType = "Friends";
                break;
            case 'L':
                flameType = "Love";
                break;
            case 'A':
                flameType = "Affection";
                break;
            case 'M':
                flameType = "Marriage";
                break;
            case 'E':
                flameType = "Enemy";
                break;
            case 'S':
                flameType = "Siblings";
                break;
        }
        
        return flameType;
    }
}

Output :

@ Shalini
I am not good at Java. I cant understand anything. Seems like greek
If you dont mind, please do the same in C or C++. Please...

Like you don't understand Java, I don't undestand C/C++. By the way if you don't understand anything in it, you can ask and better start learning Java.

Shalini, i looked into the code, and it looks good to me. Just one correction, the code to remove common characters need some changes.
- Consider names as "Pradeep" and "Pradeep". Here the number of uncommon characters is 0, whereas your code gives number of uncommon characters as 2.
- To correct this, i feel you need to put a break statement inside the 'if' where you are comparing names.


The thing i really liked in the code:
1. Conversion of names to upper case before comparing characters (i validated names against both upper case and lower case but missed to consider this scenario while comparison , i have now updated my code also ).
2. Some optimization techniques used in the code while calculating flames type, e.g.,
int index = count % (i);
It's a simple way to determine the flames type to be removed.
3. The use of existing API's.


Below are few items where i feel the code can be improved (all in terms of optimization):
1. While comparing names every time you are doing "name1.toString().toUpperCase().charAt(i)"
Instead you can just convert the name to upper case and store the same so that every time you have to just call charAt(i).
2. Instead of combining the strings and then calculating the count, the count for each name can be separately calculated and then added.
3. The code

Code:

for (int i = 0; i < newString.length(); i++) {
    count++;
    if (newString.charAt(i) == '1') {
        count--;
    }
}

can be changed to

Code:

for (int i = 0; i < newString.length(); i++) {
    if (newString.charAt(i) == '1') {
        count++;
    }
}

4. The code to calculate flames type is of order n^2 and can be reduced to order n^2.

-Pradeep

Hi Pradeep,

Many thanks for the corrections.

Actually I made this program in very hurry, so could not think of optimized way(Ya ! can make it more optimized ) , but coming to your point no 3 in improvements required, I feel your piece of suggested code would give me the count for characters that are 1 though I wanted count of characters thar are not 1. Anyways , for this it would be better if I could count it in "if" block of changing value as 1.

For same name checking, BUG, need to look into it.

Upper case thing, yes you are right I knew it, it can be saved but I just showed my laziness in doing so just for finishing off this code quickly.

Point no 4, I am not clear , you want to say optimization can be done from n[sup]2[/sup] to n[sup]2[/sup] ?

Good to hear suggestions from you.

PS: I have edited my last program accordingly.
Thanks !

Ahhh, i too replied in hurry .

When i said

Code:

for (int i = 0; i < newString.length(); i++) {
    if (newString.charAt(i) == '1') {
        count++;
    }
}

I actually mean

Code:

for (int i = 0; i < newString.length(); i++) {
    if (newString.charAt(i) != '1') {
        count++;
    }
}

But the way you modified have the handling and currently calculating the count is also good.

Here i mean to say that optimization can be done from n^3 to n^2.

-Pradeep

Can you please explain how you got complexity as n[sup]3[/sup]. According to me, complexity is 2n[sup]2[/sup] ?

Correct me if I have any wrong concept ?

Why i said that it's of order n^3 because:
1. The loop "for (int i = flamesArrayList.size(); i > 1; i--)" cause order of n.
2. The inner loop "for (int k = 0; k <= temp && temp < flamesArrayList.size(); k++)" cause another order n, making total complexity as order n^2.
3. The implementation of add/remove function of ArrayList itself is of order n, making total complexity to order n^3.

-Pradeep

Oh yes thanks for reminding me point no 3.

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


typedef struct flames
{
char c;
struct flames *next;
}flames;

char* relation(char ch);

void main()
{
char s1[20],s2[20],s3[20],s4[20],f[]={"FLAMES"},ch;
int i=0,j=0,k=0,l1,l2,count=0,m=0;
flames *head,*ne2,*ne3,*ne4,*ne5,*ne6,*temp,*p;
char *relate;

printf("\n\nEnter First Name:: ");
gets(s1);
printf("\nEnter Second Name:: ");
gets(s2);

strcpy(s3,s1);
strcpy(s4,s2);

for(i=0;i<(l1=strlen(s1));i++)
{
for(j=0;j<(l2=strlen(s2));j++)
{
if(s1==s2[j])
{
s2[j]=-1;
s3=-1;
}

}
}


for(i=0;i<strlen(s3);i++)
{
if(s3!=-1)
count++;
}
for(j=0;j<strlen(s2);j++)
{
if(s2[j]!=-1)
count++;
}

printf("\n\n");
puts(s3);
puts(s2);
printf("\n\nLetters left are %d",count);


delay(100);
printf("\nchecking for F L A M E S..............\n\n");

///////////////////////////////////////////////////////////
/*Creating CLL for flames*/

head=(struct flames*)malloc(sizeof(struct flames));
ne2=(struct flames*)malloc(sizeof(struct flames));
ne3=(struct flames*)malloc(sizeof(struct flames));
ne4=(struct flames*)malloc(sizeof(struct flames));
ne5=(struct flames*)malloc(sizeof(struct flames));
ne6=(struct flames*)malloc(sizeof(struct flames));

head->c='f'; head->next=ne2;
ne2->c='l'; ne2->next=ne3;
ne3->c='a'; ne3->next=ne4;
ne4->c='m'; ne4->next=ne5;
ne5->c='e'; ne5->next=ne6;
ne6->c='s'; ne6->next=head;
/////displaying CLL
temp=head;
i=0;
while(i<6)
{
printf(" %c",temp->c-32);
temp=temp->next;
i++;
}
printf("\n");

temp=head;
while(m<5)
{
for(i=0;i<count-2;i++)
temp=temp->next;
printf("\nDeleting %c",temp->next->c);
p=temp->next;
temp->next=temp->next->next;
temp=temp->next;
free(p);
m++;
}
ch=temp->c;

printf("\n\tSo.....The Relation is :::::: ");
relate=relation(ch);

delay(500);
puts(relate);
printf("\n\n");
}

char* relation(char ch)
{
char *rel;

switch(ch)
{
case 'f':
return rel="FRIENDSHIP";


case 'l':
return rel="LOVE";


case 'a':
return rel="ATTRACTION";


case 'm':
return rel="MARRIAGE";


case 'e':
return rel="ENEMY";


case 's':
return rel="SISTER";
}
}

I am planning to work this out in PHP...