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
|
# include <stdlib.h>
# include <stdio.h>
# include <string.h>
# include <unistd.h>
# include <limits.h>
# include <ctype.h>
# include <stdbool.h>
# define NR_OF_LETTERS 26
/*
* See ../README.md
*/
/*
* Run as: cc -o ch-2.o ch-2.c; ./ch-2.o -f FILE < input-file
*/
/*
* Helper method to allocate memory for a string.
*/
char * malloc_char (size_t size) {
char * string = (char *) malloc (size * sizeof (char));
if (string == NULL) {
perror (NULL);
exit (1);
}
return (string);
}
/*
* Given a bag of letters, and a file name, print out
* all the words in the file which can be made with the letters
*/
void extract_words (char * file_name, size_t letter_bag [NR_OF_LETTERS]) {
FILE * fh;
char * word = NULL;
size_t len = 0;
size_t str_len;
/*
* Open the file
*/
if ((fh = fopen (file_name, "r")) == NULL) {
perror (NULL);
exit (1);
}
/*
* Iterate over the file, one word at a time.
*/
while ((str_len = getline (&word, &len, fh)) != -1) {
bool winner = true;
size_t word_bag [NR_OF_LETTERS]; /* Count letters in each word */
/*
* Initialize the bag
*/
for (size_t i = 0; i < NR_OF_LETTERS; i ++) {
word_bag [i] = 0;
}
/*
* Iterate over the characters of the word (case insensitively),
* and count how often they occur. If for a character, we need
* more than there are in the letter bag, we cannot form the word.
*/
for (size_t i = 0; i < str_len && winner; i ++) {
ssize_t index = islower (word [i]) ? word [i] - 'a'
: isupper (word [i]) ? word [i] - 'A'
: -1;
/*
* Set winner to false if we don't have enough letters.
*/
winner = winner && (index < 0 ||
++ word_bag [index] <= letter_bag [index]);
}
if (winner) {
printf ("%s", word);
}
}
/*
* Close the file
*/
if (fclose (fh)) {
perror (NULL);
exit (1);
}
free (word);
return;
}
int main (int argc, char ** argv) {
char * letters = NULL;
size_t len = 0;
size_t str_len;
int ch;
char * file_name = NULL;
/*
* Parse the command line
*/
while ((ch = getopt (argc, argv, "f:")) != -1) {
switch (ch) {
case 'f':
file_name = malloc_char (PATH_MAX);
stpncpy (file_name, optarg, PATH_MAX);
break;
}
}
if (file_name == NULL) {
fprintf (stderr, "Requires a -f FILE parameter\n");
exit (1);
}
/*
* Read lines of input; each line is a letter set.
* Iterate over the letters, and count them, ingoring case.
* Then call method to extract the right words
*/
while ((str_len = getline (&letters, &len, stdin)) != -1) {
size_t letter_bag [NR_OF_LETTERS];
for (size_t i = 0; i < NR_OF_LETTERS; i ++) {
letter_bag [i] = 0;
}
for (size_t i = 0; i < str_len; i ++) {
if (islower (letters [i])) {
letter_bag [letters [i] - 'a'] ++;
}
if (isupper (letters [i])) {
letter_bag [letters [i] - 'A'] ++;
}
}
extract_words (file_name, letter_bag);
}
free (letters);
free (file_name);
return (0);
}
|
