solved

[master123]

solved

[tpb]

This is interesting. Apparently those are the chemical elements Hydrogen, Oxygen, Potassium (K), and Carbon. Have you been given any hints as to the best algorithm? Brute force? Greedy? Dynamic programming? I suspect that a greedy algorithm may work here.

Are you allowed to connect them in any way or are there some (chemical) rules?

Are you supposed to produce the "visualization" too?

[zaphraud]

...its not potassium. potassium doesnt work that way in organic systems, and organic systems dont exactly work that way either.

I would sum the number of links first. If its an odd number, just give up right away. That will eliminate 50% of your random test cases right away. After that you've only got to handle a few more to get up to a 70% and pass the assignment :D

[tpb]

Good point. I assumed potassium because of the K. Maybe it should be N for nitrogen.

[master123]

Teacher did not constrict the ways to do it and ım still open for ideas guys help me

[b00bless]

I've got the same homework, I assume we are in same class :)

Could anyone guide us? I am not asking for solution, but a little help to start coding it.

[lastchance]

Strip out the hydrogen atoms and focus on joining up the higher-valency atoms. Leave exactly enough bonds to link to the hydrogen atoms later. Your main (non-hydrogen) chain here can be either a straight chain or a ring - this program won't deal with any funny groups linked to a benzene ring.

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int ATOM[1+4] = { 0 };                           // number of atoms of each VALENCY ( ATOM[0] isn't used )
char          NAME[]  = { ' ',  'H',        'O',        'K',        'C'      };
map<char,int> VALENCY = {     { 'H', 1 }, { 'O', 2 }, { 'K', 3 }, { 'C', 4 } };
vector< pair<char,int> > chain;


//======================================================================


void splitFormula( string formula )
{
   for ( int i = 0; i <= 4; i++ ) ATOM[i] = 0;

   stringstream ss( formula );
   int num;
   char type;
   while ( ss >> num >> type ) ATOM[ VALENCY[type] ] += num;
}


//======================================================================


bool analyse()
{
   chain.clear();
   int numH = ATOM[1];                           // number of hydrogen
   int numR = ATOM[2] + ATOM[3] + ATOM[4];       // number of non-hydrogen atoms
   int bonds = 2 * ATOM[2] + 3 * ATOM[3] + 4 * ATOM[4];
                                                 // bonds available at non-hydrogen atoms

   if ( numR == 0 )                              // if there is nothing other than hydrogen, only possibility is H2 molecule
   {
      return ( numH == 2 );
   }
   else if ( numR == 1 )                         // if there is only one non-hydrogen, VALENCY must match number of hydrogen
   {
      chain.push_back( { NAME[bonds], bonds } );
      return ( numH == bonds );
   }
   else                                          // all hydrogen must bond to main chain
   {
      bonds -= numH;                             // strip off the bonds to hydrogen
      if ( bonds % 2 ) return false;             // links between other atoms are paired
      bonds /= 2;                                // number of bonds between non-hydrogen atoms
      bonds -= ( numR - 1 );                     // number of bonds after subtracting single bonds in a chain
      if ( bonds < 0 ) return false;             // not enough bonds available

      // Construct initial chain - single bonds only
      for ( int a = 4; a >= 2; a-- )
      {
         for ( int i = 1; i <= ATOM[a]; i++ ) chain.push_back( { NAME[a], 1 } );      // add atom and single bond to right
      }
      chain[numR-1].second = 0;                  // start with no final link (i.e. straight chain)

      // Still have to fill bonds places; add from left, filling as many as possible at each stage
      for ( int i = 0; i < numR; i++ )
      {
         if ( bonds <= 0 ) break;
         int inext = ( i + 1 ) % numR;           // next atom (allowing for any ring)
         int iprev = ( i + numR - 1 ) % numR;    // previous atom (allowing for any ring)
         int available = min( VALENCY[ chain[i    ].first ] - chain[i].second - chain[iprev].second,
                              VALENCY[ chain[inext].first ] - chain[i].second - chain[inext].second );
         int added = min( bonds, available );
         chain[i].second += added;
         bonds -= added;
      }
      if ( bonds > 0 ) return false;             // can't do with either straight chain or ring
   }
   return true;
}


//======================================================================


void output()
{
   int ATOMTALLY[1+4] = { 0 };
   int numR = chain.size();

   // Trivial case
   if ( numR == 0 )
   {
      cout << "H1 ---> H2\nH2 ---> H1\nLinear formula: H2\n";
      return;
   }


   //===============
   // Cross-linking
   //===============
   map< string,vector<string> > crossLink;       // map from atom name/number to its links
   for ( int a = 1; a <= 4; a++ )
   {
      for ( int i = 1; i <= ATOM[a]; i++ )
      {
         string s;   s += NAME[a];   s += to_string( i );  // name/number of atom
         crossLink[s] = vector<string>();                  // create an entry in the map
      }
   }

   string s, sprev, snext;
   vector<string> schain( numR );                // strings representing (numbered) non-hydrogen atoms in the chain
   for ( int i = 0; i < numR; i++ )
   {
      char c = chain[i].first;
      int a = VALENCY[c];
      ATOMTALLY[a]++;
      schain[i] += c;
      schain[i] += to_string( ATOMTALLY[a] );
   }

   for ( int i = 0; i < numR; i++ )
   {
      int iprev = ( i + numR - 1 ) % numR;
      int inext = ( i + 1        ) % numR;
      char c = chain[i].first;
      int numHydrogen = VALENCY[c] - chain[iprev].second - chain[i].second;
   
      // Name/number of neighbouring atoms in the chain
      s = schain[i];
      sprev = schain[iprev];
      snext = schain[inext];

      // Deal with hydrogen first
      for ( int j = 1; j <= numHydrogen; j++ )
      {
         ATOMTALLY[1]++;
         string sH = 'H' + to_string( ATOMTALLY[1] );
         crossLink[s ].push_back( sH );
         crossLink[sH].push_back( s  );
      }

      // Then the links in the main chain
      for ( int j = 1; j <= chain[i    ].second; j++ ) crossLink[s].push_back( snext );
      for ( int j = 1; j <= chain[iprev].second; j++ ) crossLink[s].push_back( sprev );
   }

   // Output the crosslinks
   for ( auto e : crossLink )
   {
      cout << e.first << " ---> ";
      for ( auto f : e.second ) cout << f << ' ';
      cout << '\n';
   }


   //===============
   // Linear formula
   //===============
   string linearFormula;
   for ( int i = 0; i < numR; i++ )
   {
      int iprev = ( i + numR - 1 ) % numR;
      char a = chain[i].first;                   // symbol for atom
      int numHydrogen = VALENCY[a] - chain[iprev].second - chain[i].second;
   
      // Update linear formula
      linearFormula += a;
      if ( numHydrogen > 0 ) linearFormula += 'H';
      if ( numHydrogen > 1 ) linearFormula += to_string( numHydrogen );
      for ( int bond = 1; bond <= chain[i].second; bond++ ) linearFormula += '-';
   }
   cout << "Linear formula: " << linearFormula << '\n';
}


//======================================================================


int main()
{
   vector<string> tests = { "4H 1O 1C",
                            "2K 1O",
                            "2K 2O",
                            "1K 1O" };

   for ( string formula : tests )
   {
      cout << "\nTest formula: " << formula << '\n';

      splitFormula( formula );

      bool ok = analyse();

      if ( ok ) output();
      else      cout << "Impossible";

      cout << "\n------------\n";
   }
}

(Bond - at end of linear formula implies a ring structure.
Single bonds are -, double bonds are -- etc. )

Test formula: 4H 1O 1C
C1 ---> H1 H2 H3 O1 
H1 ---> C1 
H2 ---> C1 
H3 ---> C1 
H4 ---> O1 
O1 ---> H4 C1 
Linear formula: CH3-OH

------------

Test formula: 2K 1O
K1 ---> K2 K2 O1 
K2 ---> O1 K1 K1 
O1 ---> K1 K2 
Linear formula: K--K-O-

------------

Test formula: 2K 2O
K1 ---> K2 K2 O2 
K2 ---> O1 K1 K1 
O1 ---> O2 K2 
O2 ---> K1 O1 
Linear formula: K--K-O-O-

------------

Test formula: 1K 1O
Impossible

[lastchance]

@master123, please don't delete your post. That is not how the forum should be.

For the record your original post was the following.

master123 wrote:

guys ı have a homework to do but ı dont know how to start this.Can you guys show me a way to start.

"STABILITY CONTROL:

In this project we have four different type of nodes named as (H , O , K , and C ).
These nodes love to be connected to each other. In a given condition all nodes
tries to fill all connections.
If one connection left unrelated they all fight each other.

The connection capacity of our Node types as below:

H can make 1 connection
O can make 2 connections
K can make 3 connections
C can make 4 connections

So here is the goal. The user enters the count of each node type like this:

INPUT: 4H 1O 1C
And you have to figure out the best match for connecting every one to each other without giving a
unconnected link.
So the result of this input must be like;

OUTPUT:
H1 -> C1
H2 -> C1
H3 -> C1
H4 -> O1
O1 -> H4,C1
C1 -> H1,H2,H3,O1

OUTPUT Visualization (optianal):
H
|
H-C-O-H
|
H


Example2:
INPUT: 2K 1O
OUTPUT:
K1 -> K2,K2,O1
K2 -> K1,K1,O1
O1 -> K1,K2
Visualization:
K
|\
2 O
|/
K

Example3:
INPUT 2K 2O
OUTPUT:
K1 -> O1,K2,O2
K2 -> O1,K1,O2
O1 -> K1,K2
O2 -> K1,K2
Visualization:
K
/ | \
O | O
\ | /
K

Example4:
INPUT: 1K 1O
OUTPUT: UNSTABLE"

[tpb]

I love that someone deleted the religious garbage, though!