C++

Forum

 
crossword puzzle

Pages: 1... 3456
dhayden (5798)
Don't delete the post. It may help others.

The speedup comes from reading the dictionary only once instead of each time you need a new word. Here's a version of randomword() with lots of comments.
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
 
//Function randomly retrieving words from the dictionary
std::string randomword() {
    // 22000 words in the dictionary. "static" means doesn't get destroyed each time the function returns
    static std::vector<std::string> words;
    std::string s;

    if (words.size() == 0) {
        // If the size is zero then this must be the first time it's called. Read the dictionary
        // file into the words array. This only happens the first time the function is called
        std::string ifileName = "dictionary.txt";
        std::ifstream f(ifileName);

        if (!f) {
            std::cerr << "File '" << ifileName << "' couldn't opened!\n";
            exit(1);            // fatal error
        }
        for (int i = 0; i <= 22000; i++) {
            std::getline(f, s);
            std::transform(s.begin(), s.end(), s.begin(), [](unsigned char c) {
                                                              return std::tolower(c);
                                                          });
            words.push_back(s); // save the word
        }
    }

    // When you get here, the dictionary file has been read into the words vector.
    int randomline = random(20, 22000); // pick a random number 20 - 22,000
    return words[randomline];           // return that word from the dictionary
}

oneidacharisse (81)
Okay, thank you very much, and I also hadn't modified the loop that checks the letters common to the two common words. By doing the test, it's faster, and actually doing the random_word function like you do is much more efficient.

On line 187 the for that checks the score at the same time as it iterates each intersection letter avoids finding itself without an intersection letter.

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
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
 
#include <iostream>

#include <string>

#include <algorithm>

#include <bits/stdc++.h>

#include <stdlib.h>

#include <sstream>

#include <ctime>

#include <vector>

using namespace std;

//Vectors for recording word coordinates
std::vector < double > coord_col;
std::vector < double > coord_row;
//Vectors for recording words
std::vector < std::string > words_vect;

constexpr char empty = '.';
constexpr int GridSize = 26;
char grid[GridSize][GridSize];

//Random number generating function
int random(int from, int to) {
  return rand() % (to - from + 1) + from;
}

//Function searching for letters common to two words
std::string find_intersection(std::string first, std::string second) {
  std::sort(first.begin(), first.end());
  std::sort(second.begin(), second.end());
  int length = std::min(first.length(), second.length());
  std::string result(length, ' ');
  std::set_intersection(first.begin(), first.end(), second.begin(), second.end(),
    result.begin());
  return result;
}

//Horizontal word placement function
//Horizontal word placement function
void PlaceHorizontal(int col, int row, int id_word, std::string & word) {
  words_vect.push_back(word);
  coord_col.push_back(col);
  coord_row.push_back(row);
  unsigned taille = word.length();
  for (unsigned int j = 0; j < taille; j++) {
    grid[col][row + j] = word[j];
  }
}

//Function placing words vertically
void PlaceVertical(int col, int row, int id_word, std::string & word) {
  words_vect.push_back(word);
  coord_col.push_back(col);
  coord_row.push_back(row);
  unsigned taille = word.length();
  for (unsigned int j = 0; j < taille; j++) {
    grid[col + j][row] = word[j];
  }
}

//function that assigns a score to the place chosen for the word
bool can_place(int col, int row, int id_word, std::string & word) {
  int score = 0;
  unsigned taille = word.length();

  if (id_word % 2 != 0) {
    if (col < 0 || col >= GridSize || row < 0 || row + taille >= GridSize) return false;
    for (unsigned int j = 0; j < taille; j++) {
      char word_letter = word[j];
      if (grid[col][row + j] == empty) {
        score = score + 1;
      } else if (grid[col][row + j] != word_letter) {
        return false;
      }
    }
  } else if (id_word % 2 == 0) {
    if (col < 0 || col + taille >= GridSize || row < 0 || row >= GridSize) return false;

    for (unsigned int j = 0; j < taille; j++) {
      char word_letter = word[j];
      if (grid[col + j][row] == empty) {
        score = score + 1;
      } else if (grid[col + j][row] != word_letter) {
        return false;
      }
    }
  }

  if (score < taille) {
    return true;
  } else {
    return false;
  }
}

//Function randomly retrieving words from the dictionary
std::string randomword() {
    // 22000 words in the dictionary. "static" means doesn't get destroyed each time the function returns
    static std::vector<std::string> words;
    std::string s;

    if (words.size() == 0) {
        // If the size is zero then this must be the first time it's called. Read the dictionary
        // file into the words array. This only happens the first time the function is called
        std::string ifileName = "dictionary.txt";
        std::ifstream f(ifileName);

        if (!f) {
            std::cerr << "File '" << ifileName << "' couldn't opened!\n";
            exit(1);            // fatal error
        }
        for (int i = 0; i <= 22000; i++) {
            std::getline(f, s);
            std::transform(s.begin(), s.end(), s.begin(), [](unsigned char c) {
                                                              return std::tolower(c);
                                                          });
            words.push_back(s); // save the word
        }
    }

    // When you get here, the dictionary file has been read into the words vector.
    int randomline = random(20, 22000); // pick a random number 20 - 22,000
    return words[randomline];           // return that word from the dictionary
}

void showGrid() {
  //grid view
  for (unsigned int i = 0; i < GridSize; i++) {
    for (int j = 0; j < GridSize; j++) {
      std::cout << grid[i][j];
      std::cout << " ";
    }

    std::cout << "\n";
  }
}

int Align(float value, float size) {
  int pos = (size / 2) - value / 2;
  return pos;
}

int main(int argc, char * argv[]) {
  srand(time(0));
  memset(grid, '.', sizeof(grid));
  bool score;
  //number of words to place
  int rand0 = random(20, 30);
  int num = rand0;

  //position of the horizontal and vertical intersection letter
  int cur_word_pos_inter;
  int prec_word_pos_inter;

  std::string prec_word;
  std::string current_word;
  int prec_intersec;
  int cur_intersec;

  std::string intersec;

  std::string word1 = randomword();
  unsigned len_word1 = word1.length();
  int pos_word1 = Align(len_word1, GridSize);
  PlaceVertical(pos_word1, (GridSize / 2), 0, word1);

  // For each word to place
  for (int k = 1; k < num; k++) {

    std::cout << " Testing word " << k << "/" << num << "\n";
    // Loop to try to place random words
    do {

      current_word = randomword();
      prec_word = words_vect[k - 1];

      intersec = find_intersection(words_vect[k - 1], current_word);
      score = false;

      for (unsigned int j = 0; !score && j < intersec.length(); j++) {
        //temporary position of the selected intersection letter
        cur_intersec = current_word.find_last_of(intersec[j]);
        prec_intersec = prec_word.find_last_of(intersec[j]);

        if (k % 2 != 0) {
          score = can_place(coord_col[k - 1] + cur_intersec, coord_row[k - 1] - prec_intersec, k, current_word);
          if (score) {
            cur_word_pos_inter = cur_intersec;
            prec_word_pos_inter = prec_intersec;
          }
        } else if (k % 2 == 0) {
          score = can_place(coord_col[k - 1] - prec_intersec, coord_row[k - 1] + cur_intersec, k, current_word);
          if (score) {
            cur_word_pos_inter = cur_intersec;
            prec_word_pos_inter = prec_intersec;
          }
        }

      }

    } while (!score);

    if (k % 2 != 0) {
      PlaceHorizontal(coord_col[k - 1] + cur_word_pos_inter, coord_row[k - 1] - prec_word_pos_inter, k, current_word);
    } else if (k % 2 == 0) {
      PlaceVertical(coord_col[k - 1] - prec_word_pos_inter, coord_row[k - 1] + cur_word_pos_inter, k, current_word);
    }
  }
  showGrid();

}
Last edited on
oneidacharisse (81)
I think I get the idea, I'm just missing one detail but I don't think I need to recode everything to understand it.

It's like this: 

1
2
 
col += dc;
row += dr;


and these, nothing is defined in the main function of the program? 
1
2
3
4
5
 
    if (col < 0 || col + dc*size >= GridSize ||
	row < 0 || row + dr*size >= GridSize) {
	std::cout << "no\n";
	return false;
    }


How do you select the direction of placement with these lines?
Last edited on
dhayden (5798)
The direction of placement is defined by dr and dc. These are passed in as parameters.
1
2
3
4
5
6
7
8
9
10
 
    // Place it horizontally
    score = can_place(coord_row[k - 1] + prev_intersec,
		      coord_col[k - 1] - cur_intersec,
		      0, 1, current_word);  // dr=0, dc=1, so placement is horizontal
} else {
    // Place it vertically
    score = can_place(coord_row[k - 1] - cur_intersec,
		      coord_col[k - 1] + prev_intersec,
		      1, 0, current_word);   // dr=1, dc=0, so placement is vertical
}
oneidacharisse (81)
Ah ok and I guess that opens up the possibility of placing the word in all directions 1,1 for a diagonal -1,0 to go up and so on... I think I've entered your entire code then.
oneidacharisse (81)
Like this, for example?

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
201
202
 
#include <iostream>

#include <string>

#include <algorithm>

#include <bits/stdc++.h>

#include <stdlib.h>

#include <sstream>

#include <ctime>

#include <vector>

using namespace std;

//Vectors for recording word coordinates
std::vector < double > coord_col;
std::vector < double > coord_row;
//Vectors for recording words
std::vector < std::string > words_vect;

constexpr char empty = '.';
constexpr int GridSize = 26;
char grid[GridSize][GridSize];

//Random number generating function
int random(int from, int to) {
  return rand() % (to - from + 1) + from;
}

//Function searching for letters common to two words
std::string find_intersection(std::string first, std::string second) {
  std::sort(first.begin(), first.end());
  std::sort(second.begin(), second.end());
  int length = std::min(first.length(), second.length());
  std::string result(length, ' ');
  std::set_intersection(first.begin(), first.end(), second.begin(), second.end(),
    result.begin());
  return result;
}

//Function placing words
void Place(int col, int row, int id_word, int dr, int dc, std::string & word) {
  words_vect.push_back(word);
  coord_col.push_back(col);
  coord_row.push_back(row);
  unsigned taille = word.length();
  for (unsigned int j = 0; j < taille; j++) {
    grid[col][row] = word[j];
    col += dc;
    row += dr;
  }
}
//function that assigns a score to the place chosen for the word
bool can_place(int col, int row, int id_word, int dr, int dc, std::string & word) {
  int score = 0;
  unsigned taille = word.length();

  if (col < 0 || col + dc * taille >= GridSize || row < 0 || row + dr * taille >= GridSize) return false;
  for (unsigned int j = 0; j < taille; j++) {
    char word_letter = word[j];

    if (grid[col][row] == empty) {
      score = score + 1;
    } else if (grid[col][row] != word_letter) {
      return false;
    }
    row += dr;
    col += dc;
  }

  if (score < taille) {
    return true;
  } else {
    return false;
  }
}

//Function randomly retrieving words from the dictionary
std::string randomword() {
  // 22000 words in the dictionary. "static" means doesn't get destroyed each time the function returns
  static std::vector < std::string > words;
  std::string s;

  if (words.size() == 0) {
    // If the size is zero then this must be the first time it's called. Read the dictionary
    // file into the words array. This only happens the first time the function is called
    std::string ifileName = "dictionary.txt";
    std::ifstream f(ifileName);

    if (!f) {
      std::cerr << "File '" << ifileName << "' couldn't opened!\n";
      exit(1); // fatal error
    }
    for (int i = 0; i <= 22000; i++) {
      std::getline(f, s);
      std::transform(s.begin(), s.end(), s.begin(), [](unsigned char c) {
        return std::tolower(c);
      });
      words.push_back(s); // save the word
    }
  }

  // When you get here, the dictionary file has been read into the words vector.
  int randomline = random(20, 22000); // pick a random number 20 - 22,000
  return words[randomline]; // return that word from the dictionary
}

void showGrid() {
  //grid view
  for (unsigned int i = 0; i < GridSize; i++) {
    for (int j = 0; j < GridSize; j++) {
      std::cout << grid[i][j];
      std::cout << " ";
    }

    std::cout << "\n";
  }
}

int Align(float value, float size) {
  int pos = (size / 2) - value / 2;
  return pos;
}

int main(int argc, char * argv[]) {
// x-axis direction table
  int x[] = { -1,  -1,  -1,  0,  0,  1,  1,  1 };
// y-axis direction table
  int y[] = {  -1,  0,  1,  -1,  1,  -1,  0,  1 };

  srand(time(0));
  memset(grid, '.', sizeof(grid));
  bool score;
  //number of words to place
  int rand0 = random(15, 30);
  int num = rand0;

  //position of the horizontal and vertical intersection letter
  int cur_word_pos_inter;
  int prec_word_pos_inter;

  std::string prec_word;
  std::string current_word;
  int prec_intersec;
  int cur_intersec;
  int index_direction;
  std::string intersec;

  std::string word1 = randomword();
  unsigned len_word1 = word1.length();
  int pos_word1 = Align(len_word1, GridSize);
  Place(pos_word1, (GridSize / 2), 0, 0, 1, word1);

  // For each word to place
  for (int k = 1; k < num; k++) {

    // Loop to try to place random words
    do {

      current_word = randomword();
      prec_word = words_vect[k - 1];

      intersec = find_intersection(words_vect[k - 1], current_word);
      score = false;

      for (unsigned int j = 0; !score && j < intersec.length(); j++) {
        //temporary position of the selected intersection letter
        cur_intersec = current_word.find_last_of(intersec[j]);
        prec_intersec = prec_word.find_last_of(intersec[j]);
        
         // test every possible direction to place the word
        for (unsigned int i = 0; !score && i < 8; i++) {
          score = can_place(coord_col[k - 1] + cur_intersec, coord_row[k - 1] - prec_intersec, k, x[i], y[i], current_word);

          if (score) {
            cur_word_pos_inter = cur_intersec;
            prec_word_pos_inter = prec_intersec;
           // if placement in the direction is possible keep the index of the chosen direction
            index_direction = i;

          }
        }

      }

    } while (!score);
    // place the word in the chosen direction
    Place(coord_col[k - 1] + cur_word_pos_inter, coord_row[k - 1] - prec_word_pos_inter, k, x[index_direction], y[index_direction], current_word);

  }
  showGrid();
  // Show the word list
  std::cout << "\n Word List:\n";
  for (auto & word: words_vect) {
    std::cout << word << '\n';
  }

}
Last edited on
dhayden (5798)
Yes! Very nice.
oneidacharisse (81)
Thank you, but it's only because of your help. To find the words in the grid, I just have to retrieve the coordinates in the two vectors: coord_col and coord_row and keep in another one the direction or simply the index of the chosen direction? To do like a path to store a sentence for example.
dhayden (5798)
Correct.
oneidacharisse (81)
Hello, I'm now trying to place all the words of a sentence contained in a text file (comment.txt), I've modified the code, but I think I have to remove the double words from the account for it to work? 

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
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
 
#include <iostream>

#include <string>

#include <algorithm>

#include <bits/stdc++.h>

#include <stdlib.h>

#include <sstream>

#include <ctime>

#include <vector>

using namespace std;

//Vectors for recording word coordinates
std::vector < double > coord_col;
std::vector < double > coord_row;
//Vectors for recording words
std::vector < std::string > words_vect;

constexpr char empty = '.';
constexpr int GridSize = 26;
char grid[GridSize][GridSize];

//Random number generating function
int random(int from, int to) {
  return rand() % (to - from + 1) + from;
}

//Function searching for letters common to two words
std::string find_intersection(std::string first, std::string second) {
  std::sort(first.begin(), first.end());
  std::sort(second.begin(), second.end());
  int length = std::min(first.length(), second.length());
  std::string result(length, ' ');
  std::set_intersection(first.begin(), first.end(), second.begin(), second.end(),
    result.begin());
  return result;
}

//Function placing words vertically
void Place(int col, int row, int id_word, int dr, int dc, std::string & word) {
  words_vect.push_back(word);
  coord_col.push_back(col);
  coord_row.push_back(row);
  unsigned taille = word.length();
  for (unsigned int j = 0; j < taille; j++) {
    grid[col][row] = word[j];
    col += dc;
    row += dr;
  }
}
//function that assigns a score to the place chosen for the word
bool can_place(int col, int row, int id_word, int dr, int dc, std::string & word) {
  int score = 0;
  unsigned taille = word.length();

  if (col < 0 || col + dc * taille >= GridSize || row < 0 || row + dr * taille >= GridSize) return false;
  for (unsigned int j = 0; j < taille; j++) {
    char word_letter = word[j];

    if (grid[col][row] == empty) {
      score = score + 1;
    } else if (grid[col][row] != word_letter) {
      return false;
    }
    row += dr;
    col += dc;
  }

  if (score < taille) {
    return true;
  } else {
    return false;
  }
}
//function that returns the size of the dictionary (number of words in the sentence or text)
int dict_size() {
	int count = 0;

  std::ifstream file("comment.txt");
  for (std::string word; file >> word;) {
    count = count+1;
  }

  
  return  count;
}

//function that reads the file and extracts words from the sentence or text and returns a random word
std::string randomword() {
  static std::vector < std::string > words;
  std::ifstream file("comment.txt");
  for (std::string word; file >> word;) {
    words.push_back(word);
  }

  // When you get here, the dictionary file has been read into the words vector.
  int randomline = random(0, words.size());
  return words[randomline];
}

void showGrid() {
  //grid view
  for (unsigned int i = 0; i < GridSize; i++) {
    for (int j = 0; j < GridSize; j++) {
      std::cout << grid[i][j];
      std::cout << " ";
    }

    std::cout << "\n";
  }
}

int Align(float value, float size) {
  int pos = (size / 2) - value / 2;
  return pos;
}

int main(int argc, char * argv[]) {
  int x[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
  int y[] = { -1,  0, 1, -1, 1, -1,  0, 1 };
  srand(time(0));
  memset(grid, '.', sizeof(grid));
  bool score;
  //number of words to place
  int rand0 = random(5, 12);
  int num = dict_size();
  //	int num = 3;

  //position of the horizontal and vertical intersection letter
  int cur_word_pos_inter;
  int prec_word_pos_inter;

  std::string prec_word;
  std::string current_word;
  int prec_intersec;
  int cur_intersec;
  int index_direction;
  std::string intersec;
  std::string random_word;
  int score_unplaced;
  bool unplaced;
 int id_word;
  std::string word1 = randomword();
  unsigned len_word1 = word1.length();
  int pos_word1 = Align(len_word1, GridSize);
  Place(pos_word1, (GridSize / 2), 0, 0, 1, word1);

  // For each word to place
  for (int k = 1; k < num; k++) {

    // Loop to try to place random words
    do {

      //as long as the chosen word is already placed, we look for a new word.	
      do {
        score_unplaced = 0;
        unplaced = false;
        random_word = randomword();
        for (int l = 0; l < words_vect.size(); l++) {

          if (random_word != words_vect[l]) {
            score_unplaced = score_unplaced + 1;
          } else if (random_word == words_vect[l]) {
            score_unplaced = score_unplaced - 2;
          }

        }
        if (score_unplaced == words_vect.size()) {
          unplaced = true;
        } else if (score_unplaced != words_vect.size()) {
          unplaced = false;
        }
      } while (!unplaced);

      //if the chosen word is not already placed, it becomes the current word to be placed.
      current_word = random_word;

	  
          //look for an intersection letter with a word already placed in the grid
	  for (int m = 0; m < words_vect.size(); m++) {	
	  id_word = m;
      prec_word = words_vect[id_word];
	  
      intersec = find_intersection(words_vect[id_word], current_word);
      
      score = false;

      for (unsigned int j = 0; !score && j < intersec.length(); j++) {

        //temporary position of the selected intersection letter
        cur_intersec = current_word.find_last_of(intersec[j]);
        prec_intersec = prec_word.find_last_of(intersec[j]);
        //if the horizontal score of the position is equal to the size of the word 

        for (unsigned int i = 0; !score && i < 8; i++) {
          score = can_place(coord_col[id_word] + cur_intersec, coord_row[id_word] - prec_intersec, id_word, x[i], y[i], current_word);

          if (score) {
            cur_word_pos_inter = cur_intersec;
            prec_word_pos_inter = prec_intersec;
            index_direction = i;

          }
        }

      }
}
    } while (!score);

    Place(coord_col[id_word] + cur_word_pos_inter, coord_row[id_word] - prec_word_pos_inter,id_word, x[index_direction], y[index_direction], current_word);
    showGrid();
    cout<<"Word "<<k<<" on "<<dict_size()<<" total of words placed"<<"\n";
  }
  showGrid();
  // Show the word list
  std::cout << "\n Word List:\n";
  for (auto & word: words_vect) {
    std::cout << word << '\n';
  }

}
Last edited on
oneidacharisse (81)
I'm thinking of eliminating double words, but the program blocks. My goal is to place all the words of a sentence or a text contained in a text file.

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
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
 
#include <iostream>

#include <string>

#include <algorithm>

#include <bits/stdc++.h>

#include <stdlib.h>

#include <sstream>

#include <ctime>

#include <vector>

using namespace std;

//Vectors for recording word coordinates
std::vector < double > coord_col;
std::vector < double > coord_row;
//Vectors for recording words
std::vector < std::string > words_vect;

constexpr char empty = '.';
constexpr int GridSize = 26;
char grid[GridSize][GridSize];

//Random number generating function
int random(int from, int to) {
   return rand() % (to - from + 1) + from;
}

//Function searching for letters common to two words
std::string find_intersection(std::string first, std::string second) {
   std::sort(first.begin(), first.end());
   std::sort(second.begin(), second.end());
   int length = std::min(first.length(), second.length());
   std::string result(length, ' ');
   std::set_intersection(first.begin(), first.end(), second.begin(), second.end(),
      result.begin());
   return result;
}

//Function placing words vertically
void Place(int col, int row, int id_word, int dr, int dc, std::string & word) {
   words_vect.push_back(word);
   coord_col.push_back(col);
   coord_row.push_back(row);
   unsigned taille = word.length();
   for (unsigned int j = 0; j < taille; j++) {
      grid[col][row] = word[j];
      col += dc;
      row += dr;
   }
}
//function that assigns a score to the place chosen for the word
bool can_place(int col, int row, int id_word, int dr, int dc, std::string & word) {
   int score = 0;
   unsigned taille = word.length();

   if (col < 0 || col + dc * taille >= GridSize || row < 0 || row + dr * taille >= GridSize) return false;
   for (unsigned int j = 0; j < taille; j++) {
      char word_letter = word[j];

      if (grid[col][row] == empty) {
         score = score + 1;
      } else if (grid[col][row] != word_letter) {
         return false;
      }
      row += dr;
      col += dc;
   }

   if (score < taille) {
      return true;
   } else {
      return false;
   }
}
//function that returns the size of the dictionary (number of words in the sentence or text)
int dict_size() {
   std::vector < std::string > words_count;
   bool to_add = false;

   std::ifstream file("comment.txt");
   for (std::string word; file >> word;) {

      if (std::find(words_count.begin(), words_count.end(), word) != words_count.end()) {
         to_add = false;
      } else {
         to_add = true;

      }
      if (to_add) {
         words_count.push_back(word);
      }

   }

   unsigned int vect_size = words_count.size();
   return vect_size;
}

//function that reads the file and extracts words from the sentence or text and returns a random word
std::string randomword(int id_word) {
   bool to_add = false;
   static std::vector < std::string > words;
   std::ifstream file("comment.txt");
   for (std::string word; file >> word;) {
      if (std::find(words.begin(), words.end(), word) != words.end()) {
         to_add = false;
      } else {
         to_add = true;

      }
      if (to_add) {
         words.push_back(word);
      }

   }
   //If it is the first word to be placed (id_word = 0) then look for the longest word of the word vector to be 
   //placed to maximize the chances of finding a letter of intersection later!
   if (id_word == 0) {
      std::sort(words.begin(), words.end(), [](const std::string & s1,
         const std::string & s2) {
         return s1.size() < s2.size();
      });
      int test = words.size() - 1;
      return words[test];

   } else if (id_word > 0) {
      // When you get here, the dictionary file has been read into the words vector.
      int randomline = random(0, words.size());
      return words[randomline];
   }

}

void showGrid() {
   //grid view
   for (unsigned int i = 0; i < GridSize; i++) {
      for (int j = 0; j < GridSize; j++) {
         std::cout << grid[i][j];
         std::cout << " ";
      }

      std::cout << "\n";
   }
}

int Align(float value, float size) {
   int pos = (size / 2) - value / 2;
   return pos;
}

int main(int argc, char * argv[]) {
  int x[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
  int y[] = { -1,  0, 1, -1, 1, -1,  0, 1 };
   srand(time(0));
   memset(grid, '.', sizeof(grid));
   bool score;
   //number of words to place
   int rand0 = random(5, 12);
   int num = dict_size();
   //	int num = 3;

   //position of the horizontal and vertical intersection letter
   int cur_word_pos_inter;
   int prec_word_pos_inter;

   std::string prec_word;
   std::string current_word;
   int prec_intersec;
   int cur_intersec;
   int index_direction;
   std::string intersec;
   std::string random_word;
   int score_unplaced;
   bool unplaced;
   int id_word;

   int k = 0;
   std::string word1 = randomword(k);
   unsigned len_word1 = word1.length();
   int pos_word1 = Align(len_word1, GridSize);
   Place(pos_word1, (GridSize / 2), 0, 0, 1, word1);

   // For each word to place
   //Instead of the for loop which was no longer useful I put the while loop which runs as long as the 
   //number of words placed is not equal to the number of words to be placed.
   do {
      k = k + 1;

      // Loop to try to place random words
      do {

         //as long as the chosen word is already placed, we look for a new word.	
         do {
            score_unplaced = 0;
            unplaced = false;
            random_word = randomword(k);

            if (std::find(words_vect.begin(), words_vect.end(), random_word) != words_vect.end()) {
               unplaced = false;
            } else {

               unplaced = true;
            }

         } while (!unplaced);

         //if the chosen word is not already placed, it becomes the current word to be placed.
         current_word = random_word;
         // std::cout << "testing for : " << current_word << "\n";

         for (int m = 0; m < words_vect.size(); m++) {
            id_word = m;
            prec_word = words_vect[id_word];

            intersec = find_intersection(words_vect[id_word], current_word);

            score = false;

            for (unsigned int j = 0; !score && j < intersec.length(); j++) {

               //temporary position of the selected intersection letter
               cur_intersec = current_word.find_last_of(intersec[j]);
               prec_intersec = prec_word.find_last_of(intersec[j]);
               //if the score of the position is equal to the size of the word 

               for (unsigned int i = 0; !score && i < 8; i++) {
                  score = can_place(coord_col[id_word] + cur_intersec, coord_row[id_word] - prec_intersec, id_word, x[i], y[i], current_word);

                  if (score) {
                     cur_word_pos_inter = cur_intersec;
                     prec_word_pos_inter = prec_intersec;
                     index_direction = i;

                  }
               }

            }
         }
      } while (!score);

      Place(coord_col[id_word] + cur_word_pos_inter, coord_row[id_word] - prec_word_pos_inter, id_word, x[index_direction], y[index_direction], current_word);
      showGrid();
      cout << "Word " << k << " on " << dict_size() << " total of words placed" << "\n";
   } while (words_vect.size() < num);

   showGrid();
   // Show the word list
   std::cout << "\n Word List:\n";
   for (auto & word: words_vect) {
      std::cout << word << '\n';
   }

}

Last edited on
dhayden (5798)
Line 134 should be int randomline = random(0, words.size() - 1);

The program loops infinitely because it gets to a point where none of the words can be placed with the previous word.
oneidacharisse (81)
Okay, I thought we had to do a test grid or something too complicated! Thank you
oneidacharisse (81)
Hello, it's working better, but it's blocking.
Last edited on
oneidacharisse (81)
I have modified the function that returns the words at random so that each word is in lower case as in the dictionary versions. I haven't tried it yet but the solution may be simply to enlarge the grid according to the number of words to place.

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
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
 
#include <iostream>

#include <string>

#include <algorithm>

#include <bits/stdc++.h>

#include <stdlib.h>

#include <sstream>

#include <ctime>

#include <vector>

using namespace std;

//Vectors for recording word coordinates
std::vector < double > coord_col;
std::vector < double > coord_row;
//Vectors for recording words
std::vector < std::string > words_vect;

constexpr char empty = '.';
constexpr int GridSize = 26;
char grid[GridSize][GridSize];

//Random number generating function
int random(int from, int to) {
   return rand() % (to - from + 1) + from;
}

//Function searching for letters common to two words
std::string find_intersection(std::string first, std::string second) {
   std::sort(first.begin(), first.end());
   std::sort(second.begin(), second.end());
   int length = std::min(first.length(), second.length());
   std::string result(length, ' ');
   std::set_intersection(first.begin(), first.end(), second.begin(), second.end(),
      result.begin());
   return result;
}

//Function placing words 
void Place(int col, int row, int id_word, int dr, int dc, std::string & word) {
   words_vect.push_back(word);
   coord_col.push_back(col);
   coord_row.push_back(row);
   unsigned taille = word.length();
   for (unsigned int j = 0; j < taille; j++) {
      grid[col][row] = word[j];
      col += dc;
      row += dr;
   }
}
//function that assigns a score to the place chosen for the word
bool can_place(int col, int row, int id_word, int dr, int dc, std::string & word) {
   int score = 0;
   unsigned taille = word.length();

   if (col < 0 || col + dc * taille >= GridSize || row < 0 || row + dr * taille >= GridSize) return false;
   for (unsigned int j = 0; j < taille; j++) {
      char word_letter = word[j];

      if (grid[col][row] == empty) {
         score = score + 1;
      } else if (grid[col][row] != word_letter) {
         return false;
      }
      row += dr;
      col += dc;
   }

   if (score < taille) {
      return true;
   } else {
      return false;
   }
}
//function that returns the size of the dictionary (number of words in the sentence or text)
int dict_size() {
   std::vector < std::string > words_count;
   bool to_add = false;

   std::ifstream file("comment.txt");
   for (std::string word; file >> word;) {

      if (std::find(words_count.begin(), words_count.end(), word) != words_count.end()) {
         to_add = false;
      } else {
         to_add = true;

      }
      if (to_add) {
         words_count.push_back(word);
      }

   }

   unsigned int vect_size = words_count.size();
   return vect_size;
}

//function that reads the file and extracts words from the sentence or text and returns a random word
std::string randomword(int id_word) {
   bool to_add = false;
   static std::vector < std::string > words;
   std::ifstream file("comment.txt");
   for (std::string word; file >> word;) {
      std::transform(word.begin(), word.end(), word.begin(), [](unsigned char c) {
         return std::tolower(c);
      });
      if (std::find(words.begin(), words.end(), word) != words.end()) {
         to_add = false;
      } else {
         to_add = true;

      }
      if (to_add) {
         words.push_back(word);
      }

   }
   //If it is the first word to be placed (id_word = 0) then look for the longest word of the word vector to be 
   //placed to maximize the chances of finding a letter of intersection later!
   if (id_word == 0) {
      std::sort(words.begin(), words.end(), [](const std::string & s1,
         const std::string & s2) {
         return s1.size() < s2.size();
      });
      int test = words.size() - 1;
      return words[test];

   } else if (id_word > 0) {
      // When you get here, the dictionary file has been read into the words vector.
      int randomline = random(0, words.size() - 1);
      return words[randomline];
   }

}

void showGrid() {
   //grid view
   for (unsigned int i = 0; i < GridSize; i++) {
      for (int j = 0; j < GridSize; j++) {
         std::cout << grid[i][j];
         std::cout << " ";
      }

      std::cout << "\n";
   }
}

int Align(float value, float size) {
   int pos = (size / 2) - value / 2;
   return pos;
}

int main(int argc, char * argv[]) {
  int x[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
  int y[] = { -1,  0, 1, -1, 1, -1,  0, 1 };
   srand(time(0));
   memset(grid, '.', sizeof(grid));
   bool score;
   bool complete_grid;
   //number of words to place
   int num = dict_size();

   //position of the intersection letter
   int cur_word_pos_inter;
   int prec_word_pos_inter;

   std::string prec_word;
   std::string current_word;
   int prec_intersec;
   int cur_intersec;
   int index_direction;
   std::string intersec;
   std::string random_word;
   int score_unplaced;
   bool unplaced;
   int id_word;

   int k = 0;
   std::string word1 = randomword(k);
   unsigned len_word1 = word1.length();
   int pos_word1 = Align(len_word1, GridSize);
   Place(pos_word1, (GridSize / 2), 0, 0, 1, word1);

   // For each word to place
   //Instead of the for loop which was no longer useful I put the while loop which runs as long as the 
   //number of words placed is not equal to the number of words to be placed.
   do {
      k = k + 1;

      // Loop to try to place random words
      do {

         //as long as the chosen word is already placed, we look for a new word.	
         do {
            score_unplaced = 0;
            unplaced = false;
            random_word = randomword(k);

            if (std::find(words_vect.begin(), words_vect.end(), random_word) != words_vect.end()) {
               unplaced = false;
            } else {

               unplaced = true;
            }

         } while (!unplaced);

         //if the chosen word is not already placed, it becomes the current word to be placed.
         current_word = random_word;

         for (unsigned int m = 0; m < words_vect.size(); m++) {
            id_word = m;
            prec_word = words_vect[id_word];

            intersec = find_intersection(prec_word, current_word);

            score = false;

            for (unsigned int j = 0; !score && j < intersec.length(); j++) {

               //temporary position of the selected intersection letter
               cur_intersec = current_word.find_last_of(intersec[j]);
               prec_intersec = prec_word.find_last_of(intersec[j]);
               //if the score of the position is equal to the size of the word 

               for (unsigned int i = 0; !score && i < 8; i++) {
                  score = can_place(coord_col[id_word] + cur_intersec, coord_row[id_word] - prec_intersec, id_word, x[i], y[i], current_word);

                  if (score) {
                     cur_word_pos_inter = cur_intersec;
                     prec_word_pos_inter = prec_intersec;
                     index_direction = i;

                  }
               }

            }
         }
      } while (!score);

      Place(coord_col[id_word] + cur_word_pos_inter, coord_row[id_word] - prec_word_pos_inter, id_word, x[index_direction], y[index_direction], current_word);
      showGrid();
      // Show the word list
      std::cout << "\n Word List:\n";
      for (auto & word: words_vect) {
         std::cout << word << '\n';
      }
      cout << "Word " << k + 1 << " out of a total of " << dict_size() << "  words to be placed" << "\n";
      //Here the number of words to be placed is equal to num or num+1? Since the loop starts at 0 ?
      if (words_vect.size() != num) {
         complete_grid = false;

      } else if (words_vect.size() == num) {
         complete_grid = true;
      }
   } while (!complete_grid);

   showGrid();
   // Show the word list
   std::cout << "\n Word List:\n";
   for (auto & word: words_vect) {
      std::cout << word << '\n';
   }

}
Last edited on
oneidacharisse (81)
Right now I'm trying to fill the grid in a function. But the program never reaches the end of the loop. What's wrong with my reasoning ?

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
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
 
#include <iostream>

#include <string>

#include <algorithm>

#include <bits/stdc++.h>

#include <stdlib.h>

#include <sstream>

#include <ctime>

#include <vector>

using namespace std;

//Vectors for recording word coordinates
std::vector < double > coord_col;
std::vector < double > coord_row;
//Vectors for recording words
std::vector < std::string > words_vect;

constexpr char empty = '.';
constexpr int GridSize = 26;
char grid[GridSize][GridSize];

//Random number generating function
int random(int from, int to) {
   return rand() % (to - from + 1) + from;
}

//Function searching for letters common to two words
std::string find_intersection(std::string first, std::string second) {
   std::sort(first.begin(), first.end());
   std::sort(second.begin(), second.end());
   int length = std::min(first.length(), second.length());
   std::string result(length, ' ');
   std::set_intersection(first.begin(), first.end(), second.begin(), second.end(),
      result.begin());
   return result;
}

//Function placing words 
void Place(int col, int row, int id_word, int dr, int dc, std::string & word) {
   words_vect.push_back(word);
   coord_col.push_back(col);
   coord_row.push_back(row);
   unsigned taille = word.length();
   for (unsigned int j = 0; j < taille; j++) {
      grid[col][row] = word[j];
      col += dc;
      row += dr;
   }
}
//function that assigns a score to the place chosen for the word
bool can_place(int col, int row, int id_word, int dr, int dc, std::string & word) {
   int score = 0;
   unsigned taille = word.length();

   if (col < 0 || col + dc * taille >= GridSize || row < 0 || row + dr * taille >= GridSize) return false;
   for (unsigned int j = 0; j < taille; j++) {
      char word_letter = word[j];

      if (grid[col][row] == empty) {
         score = score + 1;
      } else if (grid[col][row] != word_letter) {
         return false;
      }
      row += dr;
      col += dc;
   }

   if (score < taille) {
      return true;
   } else {
      return false;
   }
}
//function that returns the size of the dictionary (number of words in the sentence or text)
int dict_size() {
   std::vector < std::string > words_count;
   bool to_add = false;

   std::ifstream file("comment.txt");
   for (std::string word; file >> word;) {

      if (std::find(words_count.begin(), words_count.end(), word) != words_count.end()) {
         to_add = false;
      } else {
         to_add = true;

      }
      if (to_add) {
         words_count.push_back(word);
      }

   }

   unsigned int vect_size = words_count.size();
   return vect_size;
}

//function that reads the file and extracts words from the sentence or text and returns a random word
std::string randomword(int id_word) {
   bool to_add = false;
   static std::vector < std::string > words;
   std::ifstream file("comment.txt");
   for (std::string word; file >> word;) {
      std::transform(word.begin(), word.end(), word.begin(), [](unsigned char c) {
         return std::tolower(c);
      });
      if (std::find(words.begin(), words.end(), word) != words.end()) {
         to_add = false;
      } else {
         to_add = true;

      }
      if (to_add) {
         words.push_back(word);
      }

   }
   //If it is the first word to be placed (id_word = 0) then look for the longest word of the word vector to be 
   //placed to maximize the chances of finding a letter of intersection later!
   if (id_word == 0) {
      std::sort(words.begin(), words.end(), [](const std::string & s1,
         const std::string & s2) {
         return s1.size() < s2.size();
      });
      int test = words.size() - 1;
      return words[test];

   } else if (id_word > 0) {
      // When you get here, the dictionary file has been read into the words vector.
      int randomline = random(0, words.size() - 1);
      return words[randomline];
   }

}

void showGrid() {
   //grid view
   for (unsigned int i = 0; i < GridSize; i++) {
      for (int j = 0; j < GridSize; j++) {
         std::cout << grid[i][j];
         std::cout << " ";
      }

      std::cout << "\n";
   }
}

int Align(float value, float size) {
   int pos = (size / 2) - value / 2;
   return pos;
}
//Function to fill the grid
bool fill_grid() {

   srand(time(0));
  int x[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
  int y[] = { -1,  0, 1, -1, 1, -1,  0, 1 };
   bool score;

   //number of words to place
   int num = dict_size();

   //position of the intersection letter
   int cur_word_pos_inter;
   int prec_word_pos_inter;

   std::string prec_word;
   std::string current_word;
   int prec_intersec;
   int cur_intersec;
   int index_direction;
   std::string intersec;
   std::string random_word;
   bool unplaced;
   int id_word;

   int k = 0;
   std::string word1 = randomword(k);
   unsigned len_word1 = word1.length();
   int pos_word1 = Align(len_word1, GridSize);
   Place(pos_word1, (GridSize / 2), 0, 0, 1, word1);

   k = k + 1;

   // Loop to try to place random words
   do {

      //as long as the chosen word is already placed, we look for a new word.	
      do {
         random_word = randomword(k);

         if (std::find(words_vect.begin(), words_vect.end(), random_word) != words_vect.end()) {
            unplaced = false;
         } else {

            unplaced = true;
         }

      } while (!unplaced);

      //if the chosen word is not already placed, it becomes the current word to be placed.
      current_word = random_word;

      for (unsigned int m = 0; m < words_vect.size(); m++) {
         id_word = m;
         prec_word = words_vect[id_word];

         intersec = find_intersection(prec_word, current_word);

         score = false;

         for (unsigned int j = 0; !score && j < intersec.length(); j++) {

            //temporary position of the selected intersection letter
            cur_intersec = current_word.find_last_of(intersec[j]);
            prec_intersec = prec_word.find_last_of(intersec[j]);
            //if the score of the position is equal to the size of the word 

            for (unsigned int i = 0; !score && i < 8; i++) {
               score = can_place(coord_col[id_word] + cur_intersec, coord_row[id_word] - prec_intersec, id_word, x[i], y[i], current_word);

               if (score) {
                  cur_word_pos_inter = cur_intersec;
                  prec_word_pos_inter = prec_intersec;
                  index_direction = i;

               }
            }

         }
      }
   } while (!score);

   Place(coord_col[id_word] + cur_word_pos_inter, coord_row[id_word] - prec_word_pos_inter, id_word, x[index_direction], y[index_direction], current_word);
   showGrid();

   std::cout << words_vect.size() << "\n";
   //Here the number of words to be placed is equal to num or num+1? Since the loop starts at 0 ?
   if (words_vect.size() < k) {
      return false;

   } else if (words_vect.size() == k) {
      return true;
   }
}
int main(int argc, char * argv[]) {

   memset(grid, '.', sizeof(grid));

   bool complete_grid;

   // As long as the function to fill the grid returns false, recall the fill function.
   do {
      complete_grid = fill_grid();
   } while (!complete_grid);

   showGrid();
   // Show the word list
   std::cout << "\n Word List:\n";
   for (auto & word: words_vect) {
      std::cout << word << '\n';
   }

}
Last edited on
dhayden (5798)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
   int k = 0;
   ...
   Place(pos_word1, (GridSize / 2), 0, 0, 1, word1);

   k = k + 1;
   ...
   Place(coord_col[id_word] + cur_word_pos_inter, coord_row[id_word] - prec_wor\
d_pos_inter, id_word, x[index_direction], y[index_direction], current_word);
   showGrid();
   ...
   if (words_vect.size() < k) {
      return false;

   } else if (words_vect.size() == k) {
      return true;
   }
}

Each call to Place() adds a string to words_vect. So by the time you check words_vect.size() in the first call, it's 2 and k is 1, so you fall out of the function without returning anything! The caller checks whatever happens to be leftover in the memory location where the unset return value was supposed to go.
oneidacharisse (81)
I'm really sorry, but I can't do it. You need words_vect.size() to be equal to num which is equal to the size of the dictionary: dict_size() ? If I replace K by num, why doesn't the program work? For this part of the code : 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
  int k = 1;
   ...//Here I don't use the variable k is the index of the word is 0 anyway.
  //And it has to be in the main program that I put the 0 word.
   Place(pos_word1, (GridSize / 2), 0, 0, 1, word1);
  

   ...
   Place(coord_col[id_word] + cur_word_pos_inter, coord_row[id_word] - prec_wor\
d_pos_inter, id_word, x[index_direction], y[index_direction], current_word);
//So this should be placed after the place() call?
   k = k + 1;

   showGrid();
   ... //If the number of words placed is less than the size of the dictionary the function returns false 
     //and if the number of words placed is equal to the size of the dictionary it returns true. 
   if (words_vect.size() < num) {
      return false;

   } else if (words_vect.size() == num) {
      return true;
   }
}
Last edited on
oneidacharisse (81)
I do this : 

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
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
 
#include <iostream>

#include <string>

#include <algorithm>

#include <bits/stdc++.h>

#include <stdlib.h>

#include <sstream>

#include <ctime>

#include <vector>

using namespace std;

//Vectors for recording word coordinates
std::vector < double > coord_col;
std::vector < double > coord_row;
//Vectors for recording words
std::vector < std::string > words_vect;

constexpr char empty = '.';
constexpr int GridSize = 26;
char grid[GridSize][GridSize];

//Random number generating function
int random(int from, int to) {
   return rand() % (to - from + 1) + from;
}

//Function searching for letters common to two words
std::string find_intersection(std::string first, std::string second) {
   std::sort(first.begin(), first.end());
   std::sort(second.begin(), second.end());
   int length = std::min(first.length(), second.length());
   std::string result(length, ' ');
   std::set_intersection(first.begin(), first.end(), second.begin(), second.end(),
      result.begin());
   return result;
}

//Function placing words 
void Place(int col, int row, int id_word, int dr, int dc, std::string & word) {
   words_vect.push_back(word);
   coord_col.push_back(col);
   coord_row.push_back(row);
   unsigned taille = word.length();
   for (unsigned int j = 0; j < taille; j++) {
      grid[col][row] = word[j];
      col += dc;
      row += dr;
   }
}
//function that assigns a score to the place chosen for the word
bool can_place(int col, int row, int id_word, int dr, int dc, std::string & word) {
   int score = 0;
   unsigned taille = word.length();

   if (col < 0 || col + dc * taille >= GridSize || row < 0 || row + dr * taille >= GridSize) return false;
   for (unsigned int j = 0; j < taille; j++) {
      char word_letter = word[j];

      if (grid[col][row] == empty) {
         score = score + 1;
      } else if (grid[col][row] != word_letter) {
         return false;
      }
      row += dr;
      col += dc;
   }

   if (score < taille) {
      return true;
   } else {
      return false;
   }
}
//function that returns the size of the dictionary (number of words in the sentence or text)
int dict_size() {
   std::vector < std::string > words_count;
   bool to_add = false;

   std::ifstream file("comment.txt");
   for (std::string word; file >> word;) {

      if (std::find(words_count.begin(), words_count.end(), word) != words_count.end()) {
         to_add = false;
      } else {
         to_add = true;

      }
      if (to_add) {
         words_count.push_back(word);
      }

   }

   unsigned int vect_size = words_count.size();
   return vect_size;
}

//function that reads the file and extracts words from the sentence or text and returns a random word
std::string randomword(int id_word) {
   bool to_add = false;
   static std::vector < std::string > words;
   std::ifstream file("comment.txt");
   for (std::string word; file >> word;) {
      std::transform(word.begin(), word.end(), word.begin(), [](unsigned char c) {
         return std::tolower(c);
      });
      if (std::find(words.begin(), words.end(), word) != words.end()) {
         to_add = false;
      } else {
         to_add = true;

      }
      if (to_add) {
         words.push_back(word);
      }

   }
   //If it is the first word to be placed (id_word = 0) then look for the longest word of the word vector to be 
   //placed to maximize the chances of finding a letter of intersection later!
   if (id_word == 0) {
      std::sort(words.begin(), words.end(), [](const std::string & s1,
         const std::string & s2) {
         return s1.size() < s2.size();
      });
      int test = words.size() - 1;
      return words[test];

   } else if (id_word > 0) {
      // When you get here, the dictionary file has been read into the words vector.
      int randomline = random(0, words.size() - 1);
      return words[randomline];
   }

}

void showGrid() {
   //grid view
   for (unsigned int i = 0; i < GridSize; i++) {
      for (int j = 0; j < GridSize; j++) {
         std::cout << grid[i][j];
         std::cout << " ";
      }

      std::cout << "\n";
   }
}

int Align(float value, float size) {
   int pos = (size / 2) - value / 2;
   return pos;
}
//Function to fill the grid
bool fill_grid() {

   srand(time(0));
  int x[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
  int y[] = { -1,  0, 1, -1, 1, -1,  0, 1 };
   bool score;

   //number of words to place
   int num = dict_size();

   //position of the intersection letter
   int cur_word_pos_inter;
   int prec_word_pos_inter;

   std::string prec_word;
   std::string current_word;
   int prec_intersec;
   int cur_intersec;
   int index_direction;
   std::string intersec;
   std::string random_word;
   bool unplaced;
   int id_word;

   int k =1;


  

   // Loop to try to place random words
   do {

      //as long as the chosen word is already placed, we look for a new word.	
      do {
         random_word = randomword(k);

         if (std::find(words_vect.begin(), words_vect.end(), random_word) != words_vect.end()) {
            unplaced = false;
         } else {

            unplaced = true;
         }

      } while (!unplaced);

      //if the chosen word is not already placed, it becomes the current word to be placed.
      current_word = random_word;

      for (unsigned int m = 0; m < words_vect.size(); m++) {
         id_word = m;
         prec_word = words_vect[id_word];

         intersec = find_intersection(prec_word, current_word);

         score = false;

         for (unsigned int j = 0; !score && j < intersec.length(); j++) {

            //temporary position of the selected intersection letter
            cur_intersec = current_word.find_last_of(intersec[j]);
            prec_intersec = prec_word.find_last_of(intersec[j]);
            //if the score of the position is equal to the size of the word 

            for (unsigned int i = 0; !score && i < 8; i++) {
               score = can_place(coord_col[id_word] + cur_intersec, coord_row[id_word] - prec_intersec, id_word, x[i], y[i], current_word);

               if (score) {
                  cur_word_pos_inter = cur_intersec;
                  prec_word_pos_inter = prec_intersec;
                  index_direction = i;
                  //if the score is true then we can place the word, so I can add 1 to k.
                   k = k + 1;

               }
            }

         }
      }
   } while (!score);

   Place(coord_col[id_word] + cur_word_pos_inter, coord_row[id_word] - prec_word_pos_inter, id_word, x[index_direction], y[index_direction], current_word);
   showGrid();

   std::cout << words_vect.size() <<" / "<<num<< "\n";
   //If the number of words placed is less than the size of the dictionary the function returns false 
     //and if the number of words placed is equal to the size of the dictionary it returns true. 
   if (words_vect.size() != num) {
      return false;
      
   } else if (words_vect.size() == num) {
      return true;
   }
}
int main(int argc, char * argv[]) {

   memset(grid, '.', sizeof(grid));

   bool complete_grid;

   //word placement 0
   std::string word1 = randomword(0);
   unsigned len_word1 = word1.length();
   int pos_word1 = Align(len_word1, GridSize);
   Place(pos_word1, (GridSize / 2), 0, 0, 1, word1);
   // As long as the function to fill the grid returns false, recall the fill function.
   do {
      complete_grid = fill_grid();
   } while (!complete_grid);

   showGrid();
   // Show the word list
   std::cout << "\n Word List:\n";
   for (auto & word: words_vect) {
      std::cout << word << '\n';
   }

}
Last edited on
dhayden (5798)
It's the same problem as before. If you can't place any of the remaining words in comment.txt then it will loop forever.
Pages: 1... 3456