solved

solved
Last edited on
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?
Last edited on
...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
Good point. I assumed potassium because of the K. Maybe it should be N for nitrogen.
Teacher did not constrict the ways to do it and ım still open for ideas guys help me
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.
Last edited on
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.

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
#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
Last edited on
@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"

Last edited on
I love that someone deleted the religious garbage, though!
Registered users can post here. Sign in or register to post.