Below is the sample code. The code uses several global variables for the reason that I created a debug function, print_array(), to aid me in checking the code prior to submission, to see whether the code actually does what it is intended to do. Instead of passing the arrays as arguments to the print_arrays() function, I thought it would be easier to use global variables. Using global variables is not good programming practice. However, since we are after performance and not beauty or maintainability, I thought it would be all write to deviate from good programming habits.
First, I explain the data structures used. Several array variables are utilized. In the real world, one would not do this to implement the algorithm to this problem. In the real world, one would probably use object-oriented programming and classes to implement the algorithm. However, once again, as the emphasis of UVA problems is speed rather than beauty, I resorted to this rather ugly but probably faster code implementation.
The problem specifies a 10x10 grid array where each element or node in the grid corresponds to an input node, output node, NOT gate, AND gate, or OR gate. We could have used a two-dimensional array to implement the code; however, it would probably easier to reduce and think of the problem in terms of only one dimension to simplify things. After all, every node in the 10x10 grid two-dimensional array would correspond to a unique element in a 100-element one-dimensional array. For instance the node [9][8] in the 2D array would correspond to node [98] in the 1D array, and node [0][0] in the 2D array would correspond to node [0] in the 1D array.
In object-oriented programming, a node would correspond to a class with several variables in it. The class would have a variable corresponding to the symbol of the node, which can be i, o, &, | or !, depending whether the node is an input, output, AND, OR or NOT gate. In addition, the class would have a variable corresponding to the x-coordinate of the node, and another variable corresponding to the y-coordinate of the node. Moreover, the class would have one or two inputs depending on what type of gate it is. If the node is an input, output or NOT gate, then the node would only have one input. If the node, however, were an AND gate or an OR gate, then it would require two input variables. Finally, the class would need an output variable to store the output of a gate.
The gates referred to in this problem are digital electronic gates which are very common in electronics. They are often called logic gates and are implemented using transistors. These gates can be very tiny and are almost always present inside most electronic devices such as laptops, televisions and cellphones. You may read more about logic gates in the wikipedia. I guess the most important aspect of a gate is the truth table which is a table which lists down all possible input combinations and the corresponding output values.
In the code below, no classes are used and we did not use a linked-list of class nodes or a similar data structure to store the nodes. Instead, the maximum number of nodes are pre-allocated. The maximum number of nodes is 100 since a 10x10 grid would have 100 nodes. One would think that this is a waste of memory resources since we are pre-allocating 100 nodes immediately when in fact maybe just a few nodes are needed. This argument is true; however, remember that we are after speed and not beauty or maintainability. Since 100 is not that large a number, pre-allocating them immediately may be faster than using some other complex data structure that allocates the exact number of nodes needed. Using a complex data structure may be more efficient in using memory resources; however, the added complexity will inevitably slow things down.
Though no classes are actually used, the concept of classes is somewhat indirectly embedded within the code. Each node is represented by an index alignment of several array variables. For instance, the node with an x-coordinate of 9 and a y-coordinate of 8 is represented by the elements with index 98 of the arrays arr_v, arr_s, arr_a and arr_c. Array arr_s is for storing the symbol and elements in it can have values of i, o, &, | or !. Array arr_v is for storing the calculated output of the nodes. If for example, node 98 is an AND gate, then arr_v[98] would correspond to the output of an AND gate.
Array arr_a stores the input arguments of the gate in reference form. arr_a is a 2D array and each node can have up to a maximum of two input arguments. If node 98 is an AND gate that takes as its inputs the output of nodes 72 and 25, then arr_a[98][0] and arr_a[98][1] would have the values 72 and 25. It should be noted that the code is written in such a way that arr[98][0] could have a value of 72 and arr[98][1] a value of 25, or vice-versa. The order in which 72 and 25 are stored does not matter. Similarly, a real AND gate will not mind the order in which its inputs are applied. A two-input AND gate can take a 1 in its first input and a 0 in its second input, and output a 0 based on these inputs. If a 0 were input in its first input and a 1 in its second input, the output will still be 0. So, the ordering does not really matter, and we actually use this fact to optimize the code, as will be explained in a while.
The array arr_c is used in relation to arr_a. Each node in arr_a has two elements corresponding to the input arguments of a given gate. For instance, the input arguments to node 98 are placed in the slots, arr_a[98][0] and arr_a[98][1]. arr_c is used to take note of the next slot to store an input argument. Ideally, arr_c should only store 0 or 1 values which would tell us whether to store an input argument into arr_a[98][0] or arr_a[98][1] for the case of gate 98. However, in order to save time, and avoid having to initialize all the elements in arr_c to 0 before testing each test case, we simply use the least significant bit of every element in arr_c.
The least significant bit of any number would be 0 or 1 at any given time. For instance, the number 7 would be presented in binary as 0b0111 and its least significant bit (LSB) would be 1. In this case, if we were to store an input argument for node 98, then we would store it in arr_a[98][1]. We then increment the number 7 by 1 to obtain 8, which in binary is 0b1000. Now, the least significant bit is 0, so storing another input argument to node 98 would be done in arr_a[98][0]. The protocol used in this code is to increment arr_c[98] whenever a new argument is stored in arr_a[98][i], where is either 0 or 1. To obtain the last input argument stored into arr_a[98], we then simply subtract 1 from arr_c[98]. If, for example, arr_c[98] has a value of 8, then to obtain the last input argument stored into arr_a[98], we simply subtract 1 from 8 to obtain 7, and then obtain the least significant bit of 7 which is 1. As 1 is obtained, then the last input argument stored for node 98 is found in arr_a[98][1].
Obtaining the LSB of a number can be done efficiently by bit-wise ANDing the number with 1. For instance to get the LSB of the number 7, we can simply bit-wise AND 7 with 1 to obtain 1. In binary form, this would be represented as:
0d7: 0b0111 0d1: 0b0001 =========== 0d1: 0b0001In bit-wise ANDing, the result will only be 1 if the inputs are both 1. In this case, as the LSB's of both 7 and 1 are both 1, then the result is 1, which is the LSB of 7.
We have explained the arrays, arr_v, arr_a, arr_c. Now, we explain array, arr_r. arr_r lists all the nodes present in a given circuit. In the example given in the problem specification, arr_r would have the values: 0, 2, 11, 21, 13, and 23. These values correspond to the first column of the program inputs:
00i 11 13 .. 02i 11 13 .. 11& 21 .. 21o .. 13| 23 .. 23o ..
arr_i is used to store the nodes that correspond to input gates. In the example of the problem specification, arr_i would contain 0 and 2. Lastly, arr_o is used to store the nodes corresponding to output gates. In the problem example, arr_o would contain gates 21 and 23.
Once all program inputs are encoded into the arrays, the program starts working by first doing some initialization for each test case for a given circuit. Initialization is done by setting all nodes in arr_v that are listed in arr_r to -1 to indicate unknown gate output values (lines 123-125). The following screen output shows the values of the arrays after this initialization of arr_v:
arr_i : 00 02 arr_o : 21 23 arr_r : 00 02 11 21 13 23 arr_v : -1 -1 -1 -1 -1 -1 arr_s : i i & o | o arr_c : 00 00 00 01 00 01 arr_a0: 00 00 00 11 00 13 arr_a1: 00 00 02 00 02 00
Notice that arr_i contains the input gates of the circuit, which are 00 and 02. arr_o contains the output gates, 21 and 23. arr_r lists all the gates present in the circuit. For the rest of the arrays, print_arrays() prints the elements with indices sourced from arr_r. For instance, arr_v lists the values of its elements with indices 0, 2, 11, 21, 13, 23. These indices are found in arr_r. arr_s lists the symbols stored in its elements with indices 0, 2, 11, 21, 13, and 23. Using the output of print_arrays(), we can see that node 11 is an AND gate that takes as its inputs the outputs of nodes 00 and 02. Similarly, node 21 is an output gate that takes as its input the output of node 11. For node 21, notice that arr_c[21] has a value of 01. This means that the last input argument for node 21 was stored in arr_a[21][1-1] which is arr_a[21][0]. Remember that arr_c[x] takes note of the next position in arr_a[x][i] to store an input argument for node x in, whether in arr_a[x][0] or in arr_a[x][1].
After initializing arr_v to -1 values to indicate unknown output values, we initialize arr_v with the inputs as specified by the test case (lines 130-132). For the first test case, 00, in the problem specification, the output of print_arrays() will show the following upon input initialization:
arr_i : 00 02 arr_o : 21 23 arr_r : 00 02 11 21 13 23 arr_v : 0 0 -1 -1 -1 -1 arr_s : i i & o | o arr_c : 00 00 00 01 00 01 arr_a0: 00 00 00 11 00 13 arr_a1: 00 00 02 00 02 00
Notice that gates 0 and 2 now have output values of 0 and 0.
Next, we iterate through the nodes, attempting to calculate the output values for each of the nodes. If a node in arr_v has a value of -1, then it means that the output value of that node is unknown, and so we try to calculate for it. If can be calculated, then we convert the output value from unknown to the calculated value. If the unknown output value of a given gate cannot be calculated because the output values of another gate to which it is connected to is also unknown, then we simply move on to the next gate. We keep iterating through the nodes until all output values of all gates are no longer unknown; that is arr_v does not contain any -1 values anymore (lines 134-178).
Let us view the output of print_arrays() every time there is an update in one of the values in arr_v:
arr_i : 00 02 arr_o : 21 23 arr_r : 00 02 11 21 13 23 arr_v : 0 0 0 -1 -1 -1 arr_s : i i & o | o arr_c : 00 00 00 01 00 01 arr_a0: 00 00 00 11 00 13 arr_a1: 00 00 02 00 02 00Notice above that the output value of gate 11 changes since now, the output values of gates 0 and 2, which are inputs to gate 11, are now known.
arr_i : 00 02 arr_o : 21 23 arr_r : 00 02 11 21 13 23 arr_v : 0 0 0 0 -1 -1 arr_s : i i & o | o arr_c : 00 00 00 01 00 01 arr_a0: 00 00 00 11 00 13 arr_a1: 00 00 02 00 02 00Since the output of gate 11 is connected to gate 21 which is an output gate, and since gate 11 has value of 0, then gate 21 gains an output value of 0.
arr_i : 00 02 arr_o : 21 23 arr_r : 00 02 11 21 13 23 arr_v : 0 0 0 0 0 -1 arr_s : i i & o | o arr_c : 00 00 00 01 00 01 arr_a0: 00 00 00 11 00 13 arr_a1: 00 00 02 00 02 00Since gate 13 is an OR gate and since its two inputs have values of both 0, then gate 13 obtains an output value of 0. An OR gate will output a 1 if at least one of its inputs is 1. In this case, however, both inputs into the OR gate are 0, so the output is 0.
arr_i : 00 02 arr_o : 21 23 arr_r : 00 02 11 21 13 23 arr_v : 0 0 0 0 0 0 arr_s : i i & o | o arr_c : 00 00 00 01 00 01 arr_a0: 00 00 00 11 00 13 arr_a1: 00 00 02 00 02 00Since gate 13 is connected to gate 23, which is an output gate, then gate 23 obtains a value of 0 as well. Once all output values are obtained, we print the output values of the output gates (lines 180-182). Here is the sample code for the algorithm:
001 #include <stdio.h>
002 #include <string.h>
003 #include <stdlib.h>
004
005 int num_nodes, num_i, num_o;
006
007 char arr_s[100];
008
009 int arr_i[100];
010 int arr_o[100];
011 int arr_r[100];
012 int arr_v[100];
013 int arr_a[100][2];
014 int arr_c[100];
015
016 void print_arrays() {
017 int j, k;
018
019 printf("arr_i : ");
020 for (j = 0; j < num_i; j += 1) {
021 printf("%02d ", arr_i[j]);
022 }
023 printf("\n");
024 printf("arr_o : ");
025 for (j = 0; j < num_o; j += 1) {
026 printf("%02d ", arr_o[j]);
027 }
028 printf("\n");
029 printf("arr_r : ");
030 for (j = 0; j < num_nodes; j += 1) {
031 printf("%02d ", arr_r[j]);
032 }
033 printf("\n");
034 printf("arr_v : ");
035 for (j = 0; j < num_nodes; j += 1) {
036 k = arr_v[arr_r[j]];
037 printf("%2d ", k);
038 }
039 printf("\n");
040 printf("arr_s : ");
041 for (j = 0; j < num_nodes; j += 1) {
042 printf(" %c ", arr_s[arr_r[j]]);
043 }
044 printf("\n");
045 printf("arr_c : ");
046 for (j = 0; j < num_nodes; j += 1) {
047 printf("%02d ", arr_c[arr_r[j]] & 1);
048 }
049 printf("\n");
050 printf("arr_a0: ");
051 for (j = 0; j < num_nodes; j += 1) {
052 printf("%02d ", arr_a[arr_r[j]][0]);
053 }
054 printf("\n");
055 printf("arr_a1: ");
056 for (j = 0; j < num_nodes; j += 1) {
057 printf("%02d ", arr_a[arr_r[j]][1]);
058 }
059 printf("\n\n");
060 }
061
062 int main() {
063 char line[100], ctmp[100];
064 char *pch;
065 int n, t, node, curr_node, curr_arg, num_unk;
066 int arg_a, arg_b;
067 int i, j, k;
068 char symbol;
069
070 fgets(line, 100, stdin);
071 sscanf(line, "%d", &n);
072
073 for (i = 0; i < n; i += 1) {
074 num_nodes = 0;
075 num_i = 0;
076 num_o = 0;
077
078 while (1) {
079 fgets(line, 100, stdin);
080 pch = strtok(line, " \t");
081
082 if (pch[0] == 'e') {
083 break;
084 }
085
086 ctmp[0] = pch[0];
087 ctmp[1] = pch[1];
088 ctmp[2] = 0;
089 curr_node = atoi(ctmp);
090 arr_r[num_nodes] = curr_node;
091 num_nodes += 1;
092
093 symbol = pch[2];
094 arr_s[curr_node] = symbol;
095 if (symbol == 'i') {
096 arr_i[num_i] = curr_node;
097 num_i += 1;
098 }
099 else if (symbol == 'o') {
100 arr_o[num_o] = curr_node;
101 num_o += 1;
102 }
103
104 pch = strtok(NULL, " \t");
105 while (pch != NULL) {
106 if (pch[0] == '.') {
107 break;
108 }
109
110 node = atoi(pch);
111 curr_arg = arr_c[node] & 1;
112 arr_a[node][curr_arg] = curr_node;
113 arr_c[node] += 1;
114
115 pch = strtok (NULL, " \t");
116 }
117 }
118
119 fgets(line, 100, stdin);
120 sscanf(line, "%d", &t);
121
122 for (j = 0; j < t; j += 1) {
123 for (k = 0; k < num_nodes; k += 1) {
124 arr_v[arr_r[k]] = -1;
125 }
126
127 fgets(line, 100, stdin);
128 pch = strtok(line, " \t");
129
130 for (k = 0; k < num_i; k += 1) {
131 arr_v[arr_i[k]] = (pch[k] == 48 ? 0 : 1);
132 }
133
134 while (1) {
135 num_unk = 0;
136
137 for (k = 0; k < num_nodes; k += 1) {
138 node = arr_r[k];
139
140 if (arr_v[node] == -1) {
141 symbol = arr_s[node];
142
143 arg_a = arr_v[arr_a[node][(arr_c[node] - 1) & 1]];
144
145 if (arg_a == -1) {
146 num_unk += 1;
147 continue;
148 }
149
150 if (symbol == '!') {
151 arr_v[node] = (arg_a == 0 ? 1 : 0);
152 continue;
153 }
154 else if (symbol == 'o') {
155 arr_v[node] = arg_a;
156 continue;
157 }
158
159 arg_b = arr_v[arr_a[node][arr_c[node] & 1]];
160
161 if (arg_b == -1) {
162 num_unk += 1;
163 continue;
164 }
165
166 if (symbol == '&') {
167 arr_v[node] = arg_a & arg_b;
168 }
169 else {
170 arr_v[node] = arg_a | arg_b;
171 }
172 }
173 }
174
175 if (num_unk <= 0) {
176 break;
177 }
178 }
179
180 for (k = 0; k < num_o; k += 1) {
181 printf("%d", arr_v[arr_o[k]]);
182 }
183 printf("\n");
184 }
185 printf("\n");
186 }
187
188 return 0;
189 }
No comments:
Post a Comment