/home/toolbox/public_html/solutions/1/122/c.c
1 #include <stdio.h>
2 #include <string.h>
3 #include <sys/types.h>
4 #include <sys/stat.h>
5 #include <fcntl.h>
6 #include <stdint.h>
7 #include <math.h>
8 #include <stdlib.h>
9 #include <ctype.h>
10
11 #define TRUE (1 == 1)
12 #define FALSE (1 != 1)
13
14 #define DEBUG if (FALSE)
15
16 #define MAX_LINE 280
17
18 /*
19 * Author: Isaac Traxler
20 * Date:
21 * Purpose: fun
22 * Problem:
23 */
24
25 /*
26 * This template reads lines of data at a time until end of file.
27 */
28
29 #define MAX_LEAVES 275
30
31 typedef struct LEAF_STRUCT
32 {
33 /* struct LEAF_STRUCT */
34 int vl;
35 char pth[MAX_LINE];
36 } /* struct LEAF_STRUCT */ LEAF_STRUCT;
37
38 int leafCnt;
39 int duplicateLeaves;
40 LEAF_STRUCT tree[MAX_LEAVES];
41
42 void init()
43 {
44 /* FUNCTION init */
45 } /* FUNCTION init */
46
47 void dump()
48 {
49 /* FUNCTION dump */
50 int i;
51
52 for (i=0; leafCnt>i; i++)
53 {
54 /* for */
55 printf("%3d: %4d [%s]\n", i, tree[i].vl, tree[i].pth);
56 } /* for */
57 } /* FUNCTION dump */
58
59 int compareAscending(const void * a, const void * b)
60 {
61 /* FUNCTION compareAscending */
62 int i;
63 LEAF_STRUCT * A;
64 LEAF_STRUCT * B;
65 int aln;
66 int bln;
67
68 A = (LEAF_STRUCT *)a;
69 B = (LEAF_STRUCT *)b;
70
71 aln = strlen(A->pth);
72 bln = strlen(B->pth);
73 i = aln - bln;
74 if (0 == i)
75 {
76 /* same length */
77 i = strcmp(A->pth, B->pth);
78 duplicateLeaves = duplicateLeaves || (0 == i);
79 } /* same length */
80 return i;
81 } /* FUNCTION compareAscending */
82
83 int compareSpecial(const void * a, const void * b)
84 {
85 /* FUNCTION compareSpecial */
86 int i;
87 LEAF_STRUCT * A;
88 LEAF_STRUCT * B;
89 int aln;
90 int bln;
91
92 A = (LEAF_STRUCT *)a;
93 B = (LEAF_STRUCT *)b;
94
95 if (A->pth[0] != B->pth[0])
96 {
97 /* first letter differ -- just sort */
98 i = strcmp(A->pth, B->pth);
99 duplicateLeaves = duplicateLeaves || (0 == i);
100 } /* first letter differ -- just sort */
101 else
102 {
103 /* first letter same -- length override alpha */
104 aln = strlen(A->pth);
105 bln = strlen(B->pth);
106 i = aln - bln;
107 if (0 == i)
108 {
109 /* same length */
110 i = strcmp(A->pth, B->pth);
111 duplicateLeaves = duplicateLeaves || (0 == i);
112 } /* same length */
113 } /* first letter same -- length override alpha */
114 return i;
115 } /* FUNCTION compareSpecial */
116
117
118 int getInput()
119 {
120 /* FUNCTION getInput */
121 int dataReadFlag;
122 char strng[MAX_LINE];
123
124 dataReadFlag = (1 == scanf(" (%s) ", strng));
125 if (dataReadFlag)
126 {
127 /* if a line of data was read */
128 leafCnt = 0;
129 while (1 != strlen(strng))
130 {
131 /* read in all leaves */
132 tree[leafCnt].pth[0] = 0;
133 strng[strlen(strng)-1] = 0; /* get rid of close parenthesis */
134 sscanf(strng, " %d , %s ", &tree[leafCnt].vl, tree[leafCnt].pth);
135 DEBUG printf("(len %d) [%s] (leafCnt %d) (vl %d) (pth [%s])\n", strlen(strng), strng, leafCnt, tree[leafCnt].vl, tree[leafCnt].pth);
136 leafCnt++;
137 scanf(" (%s) ", strng);
138 } /* read in all leaves */
139 } /* if a line of data was read */
140 return (dataReadFlag);
141 } /* FUNCTION getInput */
142
143 int invalidTree()
144 {
145 /* FUNCTION invalidTree */
146 /*
147 * sort by pth ascending (setting flag if dup found)
148 * Invalid if:
149 * 1) duplicate leaf
150 * if dup flag set
151 * 2) missing parent of a leaf
152 * compare each leaf to next, ????
153 */
154 int missingLeaf = FALSE;
155 int i;
156 int cnt;
157 int cur;
158 int tmp;
159
160 duplicateLeaves = FALSE;
161 qsort(tree, leafCnt, sizeof(LEAF_STRUCT), compareSpecial);
162 dump();
163 if (! duplicateLeaves)
164 {
165 /* now check for missing leaf */
166 cnt = strlen(tree[0].pth);
167 missingLeaf = (0 != cnt); /* first leaf should be root */
168 if (! missingLeaf)
169 {
170 /* root leaf found */
171 i = 1;
172 while ((leafCnt>i) && ('L' == tree[i].pth[0]) && (! missingLeaf))
173 {
174 /* found another left */
175 cur = strlen(tree[i].pth);
176 tmp = cur - cnt;
177 missingLeaf = ((0 != tmp) && (1 != tmp));
178 DEBUG printf("L (pth[%d] %s) (cur %d) (cnt %d) (tmp %d)\n", i, tree[i].pth, cur, cnt, tmp);
179 cnt = cur;
180 i++;
181 } /* found another left */
182 if (leafCnt > i)
183 {
184 /* must have some rights */
185 cnt = 0; /* pretend at root for start of rights */
186 while ((leafCnt>i) && ('R' == tree[i].pth[0]) && (! missingLeaf))
187 {
188 /* found another right */
189 cur = strlen(tree[i].pth);
190 tmp = cur - cnt;
191 missingLeaf = ((0 != tmp) && (1 != tmp));
192 DEBUG printf("R (pth[%d] %s) (cur %d) (cnt %d) (tmp %d)\n", i, tree[i].pth, cur, cnt, tmp);
193 cnt = cur;
194 i++;
195 } /* found another right */
196 } /* must have some rights */
197 } /* root leaf found */
198 } /* now check for missing leaf */
199 return (duplicateLeaves || missingLeaf);
200 } /* FUNCTION invalidTree */
201
202 void dumpTree()
203 {
204 /* FUNCTION dumpTree */
205 int i;
206
207 printf("%d", tree[0].vl);
208 for (i=1; leafCnt>i; i++)
209 {
210 /* for */
211 printf(" %d", tree[i].vl);
212 } /* for */
213 printf("\n");
214 } /* FUNCTION dumpTree */
215
216 void process()
217 {
218 /* FUNCTION process */
219 if (invalidTree())
220 {
221 /* invalid tree */
222 printf("not complete\n");
223 } /* invalid tree */
224 else
225 {
226 /* found a valid tree */
227 qsort(tree, leafCnt, sizeof(LEAF_STRUCT), compareAscending);
228 dump();
229 dumpTree();
230 } /* found a valid tree */
231 } /* FUNCTION process */
232
233 int main()
234 {
235 /* main */
236 int moreToDo;
237
238 moreToDo = getInput();
239 while (moreToDo)
240 {
241 /* while */
242 process();
243 moreToDo = getInput();
244 } /* while */
245
246 return EXIT_SUCCESS;
247 } /* main */
248