/home/toolbox/public_html/solutions/1/122/a.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 int left;
37 int right;
38 } /* struct LEAF_STRUCT */ LEAF_STRUCT;
39
40 int leafCnt;
41 int duplicateLeaves;
42 LEAF_STRUCT tree[MAX_LEAVES];
43
44 void init()
45 {
46 /* FUNCTION init */
47 } /* FUNCTION init */
48
49 void dump()
50 {
51 /* FUNCTION dump */
52 int i;
53
54 for (i=0; leafCnt>i; i++)
55 {
56 /* for */
57 printf("%3d: %4d [%s] %d(l) (r)%d\n", i, tree[i].vl, tree[i].pth, tree[1].left, tree[i].right);
58 } /* for */
59 } /* FUNCTION dump */
60
61 int compareAscending(const void * a, const void * b)
62 {
63 /* FUNCTION compareAscending */
64 int i;
65 LEAF_STRUCT * A;
66 LEAF_STRUCT * B;
67 int aln;
68 int bln;
69
70 A = (LEAF_STRUCT *)a;
71 B = (LEAF_STRUCT *)b;
72
73 aln = strlen(A->pth);
74 bln = strlen(B->pth);
75 i = aln - bln;
76 if (0 == i)
77 {
78 /* same length */
79 i = strcmp(A->pth, B->pth);
80 duplicateLeaves = duplicateLeaves || (0 == i);
81 } /* same length */
82 return i;
83 } /* FUNCTION compareAscending */
84
85 int getInput()
86 {
87 /* FUNCTION getInput */
88 int dataReadFlag;
89 char strng[MAX_LINE];
90
91 dataReadFlag = (1 == scanf(" (%s) ", strng));
92 if (dataReadFlag)
93 {
94 /* if a line of data was read */
95 leafCnt = 0;
96 while (1 != strlen(strng))
97 {
98 /* read in all leaves */
99 tree[leafCnt].pth[0] = 0;
100 strng[strlen(strng)-1] = 0; /* get rid of close parenthesis */
101 sscanf(strng, " %d , %s ", &tree[leafCnt].vl, tree[leafCnt].pth);
102 tree[leafCnt].left = -1;
103 tree[leafCnt].right = -1;
104 DEBUG printf(": (len %d) [%s] (leafCnt %d) (vl %d) (pth [%s])\n", strlen(strng), strng, leafCnt, tree[leafCnt].vl, tree[leafCnt].pth);
105 leafCnt++;
106 scanf(" (%s) ", strng);
107 } /* read in all leaves */
108 } /* if a line of data was read */
109 return (dataReadFlag);
110 } /* FUNCTION getInput */
111
112 int buildTree()
113 {
114 /* FUNCTON buildTree */
115 int toReturn = TRUE;
116
117 return toReturn;
118 } /* FUNCTON buildTree */
119
120 int noMissingLeaves()
121 {
122 /* FUNCTON noMissingLeaves */
123 int toReturn = TRUE;
124 int i;
125 int j;
126 int tmp;
127 char tstr[MAX_LINE];
128 int fnd = TRUE;
129
130 for (i=leafCnt-1; (toReturn) && (0<i) && (1 < strlen(tree[i].pth)); i--)
131 {
132 /* check each leaf */
133 tmp = strlen(tree[i].pth) - 1;
134 /* copy all but last char of path to look for -- this should be parent node */
135 for (j=0; tmp>j; j++)
136 {
137 tstr[j] = tree[i].pth[j];
138 }
139 tstr[tmp] = 0;
140 DEBUG printf(": (tree[%d].pth %s) (tstr %s) (tmp %d)\n", i, tree[i].pth, tstr, tmp);
141 /* hunt for parent */
142 fnd = FALSE;
143 for (j=i-1; (0<=j) && (strlen(tree[j].pth) >= tmp) && (! fnd); j--)
144 {
145 /* compare each possible parent same length */
146 DEBUG printf(": (tstr %s) (tree[%d].pth %s)\n", tstr, j, tree[j].pth);
147 fnd = 0 == strcmp(tstr, tree[j].pth);
148 } /* compare each possible parent same length */
149 toReturn = toReturn && fnd;
150 } /* check each leaf */
151 return toReturn;
152 } /* FUNCTON noMissingLeaves */
153
154 void dumpTree()
155 {
156 /* FUNCTION dumpTree */
157 int i;
158
159 printf("%d", tree[0].vl);
160 for (i=1; leafCnt>i; i++)
161 {
162 /* for */
163 printf(" %d", tree[i].vl);
164 } /* for */
165 printf("\n");
166 } /* FUNCTION dumpTree */
167
168 int validate()
169 {
170 /* FUNCTION validate */
171 int valid;
172
173 valid = (! duplicateLeaves);
174 /* now check for root */
175 valid = valid && (0 == strlen(tree[0].pth));
176 /* check for missing leaves */
177 valid = valid && noMissingLeaves();
178
179 return valid;
180 } /* FUNCTION validate */
181
182 void process()
183 {
184 /* FUNCTION process */
185 int okay;
186
187 duplicateLeaves = FALSE;
188 qsort(tree, leafCnt, sizeof(LEAF_STRUCT), compareAscending);
189 DEBUG dump();
190 if (validate())
191 {
192 /* got a good tree */
193 dumpTree();
194 } /* got a good tree */
195 else
196 {
197 /* problem with tree */
198 printf("not complete\n");
199 } /* problem with tree */
200 } /* FUNCTION process */
201
202 int main()
203 {
204 /* main */
205 int moreToDo;
206
207 moreToDo = getInput();
208 while (moreToDo)
209 {
210 /* while */
211 process();
212 moreToDo = getInput();
213 } /* while */
214
215 return EXIT_SUCCESS;
216 } /* main */
217