crossword puzzle

Pages: 123456
oneidacharisse (81)
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
 
int main(int argc, char *argv[])
{
	srand(time(0));
	memset(grid, '.', sizeof(grid));
	bool place_v = false;
	bool place_h = false;
	int n;
	//number of words to place
	int rand0 = random(5, 10);
	int num = rand0;

	//position of the horizontal and vertical intersection letter
	int x_word2_intersection_h;
	int x_word1_intersection_h;
	int x_word2_intersection_v;
	int x_word1_intersection_v;
	std::string prec_word;
	std::string current_word;
	int temp_intersec_2;
	int temp_intersec_1;
	//score for horizontal and vertical positioning
	int score_h = 0;
	int score_v = 0;

	//random word retrieval and addition to vector
	for (unsigned int i = 0; i < num; i++)
	{
		//depending on the size of the dictionary
		int rand1 = random(100, 20000);
		std::string word1 = randomword(rand1);
		words_vect.push_back(word1);
	}

	std::string word1 = words_vect[0];
	int pos_word1 = 8;
	PlaceVertical(pos_word1, pos_word1, 0, words_vect[0]);

	for (unsigned int k = 1; k < words_vect.size(); k++)
	{
		back:
			// start of testing
			prec_word = words_vect[k - 1];
		current_word = words_vect[k];
		std::string intersec = find_intersection(words_vect[k - 1], words_vect[k]);

		if (intersec.empty())
		{
			std::cout << " Replacing current word " << words_vect[k] << "\n";
			replace_word(current_word);
			goto back;
		}
		else
		{
			//for each intersecting letter of the word in the vector 
			for (unsigned int j = 0; j < intersec.length(); j++)
			{
			 	//temporary position of the selected intersection letter

				if (k % 2 != 0)
				{
					temp_intersec_2 = current_word.find_last_of(intersec[j]);
					temp_intersec_1 = prec_word.find_last_of(intersec[j]);
					score_h = can_place_h(coord_x[k - 1] + temp_intersec_2, coord_y[k - 1] - temp_intersec_1, k, current_word);
					//if the horizontal score of the position is equal to the size of the word 
					if (score_h == current_word.length() && k % 2 != 0)
					{

						place_h = true;
						std::cout << " Testing word " << k << "/" << num << "\n";
						std::cout << " Current score " << score_h << "/" << current_word.length() << "\n";
						std::cout << " Current word1 " << prec_word << " Current word2 " << current_word << "\n";
						std::cout << "-----" << "\n";
						x_word2_intersection_h = temp_intersec_2;
						x_word1_intersection_h = temp_intersec_1;
						goto placing_word;
					}
					else if (score_h != current_word.length() && k % 2 != 0)
					{
						place_h = false;
						std::cout << " Replacing current word " << words_vect[k] << "\n";
						replace_word(words_vect[k]);
						goto back;
					}
				}
				if (k % 2 == 0)
				{
					temp_intersec_2 = current_word.find_last_of(intersec[j]);
					temp_intersec_1 = prec_word.find_last_of(intersec[j]);
					score_v = can_place_v(coord_x[k - 1] - temp_intersec_1, coord_y[k - 1] + temp_intersec_2, k, current_word);

					//if the vertical score of the position is equal to the size of the word 
					if (score_v == current_word.length() && k % 2 == 0)
					{

						place_v = true;
						std::cout << " Testing word " << k << "/" << num << "\n";
						std::cout << " Current score " << score_v << "/" << current_word.length() << "\n";
						std::cout << " Current word1 " << prec_word << " Current word2 " << current_word << "\n";
						std::cout << "-----" << "\n";
						x_word2_intersection_v = temp_intersec_2;
						x_word1_intersection_v = temp_intersec_1;
						goto placing_word;
					}
					else if (score_v != current_word.length() && k % 2 == 0)
					{
						place_v = false;
						std::cout << " Replacing current word " << words_vect[k] << "\n";
						replace_word(words_vect[k]);
						goto back;
					}
				}
			}
		}

		placing_word: if (k % 2 != 0)
		{
			if (place_h == true)
			{
				PlaceHorizontal(coord_x[k - 1] + x_word2_intersection_h, coord_y[k - 1] - x_word1_intersection_h, k, current_word);
			}
			else
			{
				std::cout << "Placing word : " << current_word << " horizontally is impossible ! " << "\n";
				return 1;
			}
		}
		else
		{
			if (place_v == true)
			{
				PlaceVertical(coord_x[k - 1] - x_word1_intersection_v, coord_y[k - 1] + x_word2_intersection_v, k, current_word);
			}
			else
			{
				std::cout << "Placing word : " << current_word << " vertically is impossible ! " << "\n";
				return 1;
			}
		}
	}

	showGrid();

	words_vect.clear();
}
oneidacharisse (81)
I think the program stops because I can't replace the word when it can't be placed correctly. I think I'm making a mistake here. The replacement function is void. Wouldn't it be better to make a string array rather than a vector (for words) ?
Last edited on
dhayden (5798)
You aren't checking the range correctly.

First, you can tell if the entire word will fit within the grid with a little math before you enter the for loop. For example, in can_place_v(), you check if the starting row is too small or of the ending row is too big. There's no need to check the rows of each letter:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
int can_place_v(int x, int y, int id_word, std::string &word)
{
        int score = 0;
        unsigned taille = word.length();

        if (x < 0 || x+taille >= GridSize || y < 0 || y >= GridSize) return 0;

        for (unsigned int j = 0; j < taille; j++)
        {
                char word_letter = word[j];
                if (grid[x + j][y] == empty || grid[x + j][y] == word_letter)
                {
                        score = score + 1;
                }
                else
                {
                        score = score - 4;
                }
        }
        return score;
}


can_check_h is similar.

Once I make these changes it seems to run correctly. But there are still plenty of improvements that can be made to this code. If you're interested, I'd be happy to guide you through them.

Dave
oneidacharisse (81)
Re! ah yes indeed. And to guide me, if you want, but sometimes I don't understand certain concepts! You have to go slowly. lol

Jonathan
dhayden (5798)
Great. Let's start with can_place_v() and can_place_h(). The functions compute a numeric score, but you only check if the result is the length of the word. In other words, you really only care if it fits, or doesn't.

So it would be better to return a bool value. Bool is a build-in type (like int, long or double) but it takes on just two values: true and false. Here is a version of can_place_v() that returns a bool:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
//function that assigns a score to the place chosen for the word
bool can_place_v(int x, int y, int id_word, std::string &word)
{
        unsigned taille = word.length();

        if (x < 0 || x+taille >= GridSize || y < 0 || y >= GridSize) return false;

        for (unsigned int j = 0; j < taille; j++)
        {
                char word_letter = word[j];
                if (grid[x + j][y] != empty && grid[x + j][y] != word_letter)
                {
                    return false; // it doesn't fit
                }
        }

        // You get through the whole loop without detecting a conflict then it fits.
        return true;
}


Then you have to change the declaration of score_h & score_v, along with how they're used:
bool score_h = false;
bool score_v = false;
...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
                                        score_h = can_place_h(coord_x[k - 1] + temp_intersec_2, coord_y[k - 1] - temp_inter\
sec_1, k, current_word);
                                        //if the horizontal score of the position is equal to the size of the word
                                        if (score_h && k % 2 != 0)
                                        {

                                                place_h = true;
                                                std::cout << " Testing word " << k << "/" << num << "\n";
                                                std::cout << " Current score " << score_h << "/" << current_word.length() <\
< "\n";
                                                std::cout << " Current word1 " << prec_word << " Current word2 " << current\
_word << "\n";
                                                std::cout << "-----" << "\n";
                                                x_word2_intersection_h = temp_intersec_2;
                                                x_word1_intersection_h = temp_intersec_1;
                                                goto placing_word;
                                        }
                                        else if (!score_h && k % 2 != 0)


and similarly for score_v.

Can you make those changes and get it working?


oneidacharisse (81)
Okay, I'll try. I was going to post my last correction, but it's good to move on.
oneidacharisse (81)
I don't come with your function but I have created a function (not_empty) to avoid that the place chosen for the word is totally empty. Sometimes the program blocks, and if a word doesn't cross it's the 0 word of the vector.
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
 
#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
void PlaceHorizontal(int col, int row, int id_word, std::string &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)
{
	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 to avoid a completely empty slot
bool not_empty_v(int col, int row, int id_word, std::string &word)
{
	int score = 0;
	unsigned taille = word.length();
	if (col < 0 || col + taille >= GridSize || row < 0 || row >= GridSize) return false;
	for (unsigned int j = 0; j < taille; j++)
	{
		if (grid[col + j][row] == empty)
		{
			score = score + 1;
		}
		else
		{
			score = score - 4;
		}
	}

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

bool not_empty_h(int col, int row, int id_word, std::string &word)
{
	int score = 0;
	unsigned taille = word.length();
	if (col < 0 || col >= GridSize || row < 0 || row + taille >= GridSize) return 0;
	for (unsigned int j = 0; j < taille; j++)
	{
		if (grid[col][row + j] == empty)
		{
			score = score + 1;
		}
		else
		{
			score = score - 4;
		}
	}

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

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

	if (col < 0 || col + taille >= GridSize || row < 0 || row >= GridSize) return 0;

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

	return score;
}

int can_place_h(int col, int row, int id_word, std::string &word)
{
	int score = 0;
	unsigned taille = word.length();

	if (col < 0 || col >= GridSize || row < 0 || row + taille >= GridSize) return 0;

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

	return score;

}

//Function randomly retrieving words from the dictionary
std::string randomword(int randomline)
{
	std::string word1;
	std::string ifileName = "dictionary.txt";
	std::ifstream f(ifileName);

	if (!f)
		std::cerr << "File '" << ifileName << "' couldn't opened!\n";

	std::string s;

	for (int i = 1; i < randomline; i++)
	{
		std::getline(f, s);
		std::transform(s.begin(), s.end(), s.begin(), [](unsigned char c)
		{
			return std::tolower(c);
	});
		word1 = s;
	}

	return word1;
}

void replace_word(std::string &current_word)
{
	int rand3 = random(100, 20000);
	std::string replacement = randomword(rand3);
	std::replace(words_vect.begin(), words_vect.end(), current_word, replacement);

}

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;
	return pos;
}
Last edited on
oneidacharisse (81)
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
 
int main(int argc, char *argv[])
{
	srand(time(0));
	memset(grid, '.', sizeof(grid));
	bool place_v = false;
	bool place_h = false;
	int n;
	//number of words to place
	int rand0 = random(10, 15);
	int num = rand0;

	//position of the horizontal and vertical intersection letter
	int x_word2_intersection_h;
	int x_word1_intersection_h;
	int x_word2_intersection_v;
	int x_word1_intersection_v;
	std::string prec_word;
	std::string current_word;
	int temp_intersec_2;
	int temp_intersec_1;
	//score for horizontal and vertical positioning
	int score_h = 0;
	int score_v = 0;
	bool place_empty_score_h;
	bool place_empty_score_v;
	//random word retrieval and addition to vector
	for (unsigned int i = 0; i < num; i++)
	{
		//depending on the size of the dictionary
		int rand1 = random(100, 20000);
		std::string word1 = randomword(rand1);
		words_vect.push_back(word1);

	}

	std::string word1 = words_vect[0];
	unsigned len_word1 = word1.length();

	int pos_word1 = Align(len_word1, GridSize);
	PlaceVertical(pos_word1, (GridSize / 2), 0, words_vect[0]);

	for (unsigned int k = 1; k < words_vect.size(); k++)
	{
		back:
			// start of testing
			prec_word = words_vect[k - 1];
		current_word = words_vect[k];
		std::string intersec = find_intersection(words_vect[k - 1], words_vect[k]);

		if (intersec.empty())
		{
			std::cout << " Replacing current word " << words_vect[k] << "\n";
			replace_word(current_word);
			goto back;
		}
		else
		{
			//for each intersecting letter of the word in the vector 
			for (unsigned int j = 0; j < intersec.length(); j++)
			{
				//temporary position of the selected intersection letter

				if (k % 2 != 0)
				{
					temp_intersec_2 = current_word.find_last_of(intersec[j]);
					temp_intersec_1 = prec_word.find_last_of(intersec[j]);
					score_h = can_place_h(coord_col[k - 1] + temp_intersec_2, coord_row[k - 1] - temp_intersec_1, k, current_word);
					//if the horizontal score of the position is equal to the size of the word 
					place_empty_score_h = not_empty_h(coord_col[k - 1] + temp_intersec_2, coord_row[k - 1] - temp_intersec_1, k, current_word);

					if (place_empty_score_h && score_h == current_word.length() && k % 2 != 0)
					{
						place_h = true;
						std::cout << " Testing word " << k << "/" << num << "\n";
						std::cout << " Current score " << score_h << "/" << current_word.length() << "\n";
						std::cout << " Current word1 " << prec_word << " Current word2 " << current_word << "\n";
						std::cout << "-----" << "\n";
						x_word2_intersection_h = temp_intersec_2;
						x_word1_intersection_h = temp_intersec_1;
						goto placing_word;
					}
					else
					{
						place_h = false;

					}
				}

				if (k % 2 == 0)
				{
					temp_intersec_2 = current_word.find_last_of(intersec[j]);
					temp_intersec_1 = prec_word.find_last_of(intersec[j]);
					score_v = can_place_v(coord_col[k - 1] - temp_intersec_1, coord_row[k - 1] + temp_intersec_2, k, current_word);
					place_empty_score_v = not_empty_v(coord_col[k - 1] - temp_intersec_1, coord_row[k - 1] + temp_intersec_2, k, current_word);

					//if the vertical score of the position is equal to the size of the word 

					if (place_empty_score_v && score_v == current_word.length() && k % 2 == 0)
					{
						place_v = true;
						std::cout << " Testing word " << k << "/" << num << "\n";
						std::cout << " Current score " << score_v << "/" << current_word.length() << "\n";
						std::cout << " Current word1 " << prec_word << " Current word2 " << current_word << "\n";
						std::cout << "-----" << "\n";
						x_word2_intersection_v = temp_intersec_2;
						x_word1_intersection_v = temp_intersec_1;
						goto placing_word;
					}
					else
					{
						place_v = false;

					}
				}
			}
		}

		placing_word:

			if (place_h && k % 2 != 0)
			{
				PlaceHorizontal(coord_col[k - 1] + x_word2_intersection_h, coord_row[k - 1] - x_word1_intersection_h, k, current_word);
			}
		else if (!place_h && k % 2 != 0)
		{
			std::cout << " Replacing current word " << words_vect[k] << "\n";
			replace_word(words_vect[k]);
			goto back;
		}

		if (place_v && k % 2 == 0)
		{
			PlaceVertical(coord_col[k - 1] - x_word1_intersection_v, coord_row[k - 1] + x_word2_intersection_v, k, current_word);

		}
		else if (!place_v && k % 2 == 0)
		{
			std::cout << " Replacing current word " << words_vect[k] << "\n";
			replace_word(words_vect[k]);
			goto back;
		}
	}

	showGrid();

	words_vect.clear();
}
Last edited on
dhayden (5798)
not_empty() has the same problem as can_place_X(): it can go off the end of the grid array.

Why not combine all the logic into the can_place_X() functions? For example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
//function that assigns a score to the place chosen for the word
bool can_place_v(int x, int y, int id_word, std::string &word)
{
        unsigned taille = word.length();
        unsigned numEmpty=0;    // number of empty cells

        if (x < 0 || x+taille >= GridSize || y < 0 || y >= GridSize) return false;

        for (unsigned int j = 0; j < taille; j++)
        {
                char word_letter = word[j];
                if (grid[x + j][y] == empty) {
                    ++numEmpty;
                } else if (grid[x + j][y] != word_letter) {
                    return false; // it doesn't fit
                }
        }

        // You got through the whole loop without detecting a conflict. You can place it here
        // as long as the cells weren't all empty
        return (numEmpty != taille);
}


Our next step will be a big one, but will reduce the amount of code enormously. Instead of having separate code for horizontal and vertical, we're going to create two new variables that define the direction of the word and use one set of code. A really cool side effect of this is that we'll be able to add diagonal words and words that go up or left instead of down or right too.

Dave
oneidacharisse (81)
Ok, with the previous function I couldn't, that's why I did it differently. I'll test it. I have to do this before I can see further ;)
Last edited on
oneidacharisse (81)
I found my error on the code I posted yesterday, I corrected I check that in a way if the boxes were empty. So I did in both directions the code works normally and all the words are crossed. Now I will try to do with your function. I edited the post to avoid republishing code (see above).
oneidacharisse (81)
That's it. I think I've taken care of what you asked me to do. I encoded the not_empty function in the can_placeX functions. Tell me if that's what was expected I think the program is working correctly.

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
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
 
#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
void PlaceHorizontal(int col, int row, int id_word, std::string &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)
{
	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(int randomline)
{
	std::string word1;
	std::string ifileName = "dictionary.txt";
	std::ifstream f(ifileName);

	if (!f)
		std::cerr << "File '" << ifileName << "' couldn't opened!\n";

	std::string s;

	for (int i = 1; i < randomline; i++)
	{
		std::getline(f, s);
		std::transform(s.begin(), s.end(), s.begin(), [](unsigned char c)
		{
			return std::tolower(c);
	});
		word1 = s;
	}

	return word1;
}

void replace_word(std::string &current_word)
{
	int rand3 = random(100, 20000);
	std::string replacement = randomword(rand3);
	std::replace(words_vect.begin(), words_vect.end(), current_word, replacement);

}

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;
	return pos;
}

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

	//position of the horizontal and vertical intersection letter
	int x_word2_intersection_h;
	int x_word1_intersection_h;
	int x_word2_intersection_v;
	int x_word1_intersection_v;
	std::string prec_word;
	std::string current_word;
	int temp_intersec_2;
	int temp_intersec_1;
	//score for horizontal and vertical positioning
	bool score_h = false;
	bool score_v = false;

	//random word retrieval and addition to vector
	for (unsigned int i = 0; i < num; i++)
	{
		//depending on the size of the dictionary
		int rand1 = random(100, 20000);
		std::string word1 = randomword(rand1);
		words_vect.push_back(word1);
	}

	std::string word1 = words_vect[0];
	unsigned len_word1 = word1.length();

	int pos_word1 = Align(len_word1, GridSize);
	PlaceVertical(pos_word1, (GridSize / 2), 0, words_vect[0]);

	for (unsigned int k = 1; k < words_vect.size(); k++)
	{
		back:
			// start of testing
			prec_word = words_vect[k - 1];
		current_word = words_vect[k];
		std::string intersec = find_intersection(words_vect[k - 1], words_vect[k]);

		if (intersec.empty())
		{
			std::cout << " Replacing current word " << words_vect[k] << "\n";
			replace_word(current_word);
			goto back;
		}
		else
		{
			//for each intersecting letter of the word in the vector 
			for (unsigned int j = 0; j < intersec.length(); j++)
			{
			 	//temporary position of the selected intersection letter

				if (k % 2 != 0)
				{
					temp_intersec_2 = current_word.find_last_of(intersec[j]);
					temp_intersec_1 = prec_word.find_last_of(intersec[j]);
					score_h = can_place(coord_col[k - 1] + temp_intersec_2, coord_row[k - 1] - temp_intersec_1, k, current_word);
					//if the horizontal score of the position is equal to the size of the word 

					if (score_h && k % 2 != 0)
					{
						place_h = true;
						std::cout << " Testing word " << k << "/" << num << "\n";
						std::cout << " Current word1 " << prec_word << " Current word2 " << current_word << "\n";
						std::cout << "-----" << "\n";
						x_word2_intersection_h = temp_intersec_2;
						x_word1_intersection_h = temp_intersec_1;
						goto placing_word;
					}
					else
					{
						place_h = false;
					}
				}

				if (k % 2 == 0)
				{
					temp_intersec_2 = current_word.find_last_of(intersec[j]);
					temp_intersec_1 = prec_word.find_last_of(intersec[j]);
					score_v = can_place(coord_col[k - 1] - temp_intersec_1, coord_row[k - 1] + temp_intersec_2, k, current_word);

					//if the vertical score of the position is equal to the size of the word 

					if (score_v && k % 2 == 0)
					{
						place_v = true;
						std::cout << " Testing word " << k << "/" << num << "\n";
						std::cout << " Current word1 " << prec_word << " Current word2 " << current_word << "\n";
						std::cout << "-----" << "\n";
						x_word2_intersection_v = temp_intersec_2;
						x_word1_intersection_v = temp_intersec_1;
						goto placing_word;
					}
					else
					{
						place_v = false;
					}
				}
			}
		}

		placing_word:

			if (place_h && k % 2 != 0)
			{
				PlaceHorizontal(coord_col[k - 1] + x_word2_intersection_h, coord_row[k - 1] - x_word1_intersection_h, k, current_word);
			}
		else if (!place_h && k % 2 != 0)
		{
			std::cout << " Replacing current word " << words_vect[k] << "\n";
			replace_word(words_vect[k]);
			goto back;
		}

		if (place_v && k % 2 == 0)
		{
			PlaceVertical(coord_col[k - 1] - x_word1_intersection_v, coord_row[k - 1] + x_word2_intersection_v, k, current_word);
		}
		else if (!place_v && k % 2 == 0)
		{
			std::cout << " Replacing current word " << words_vect[k] << "\n";
			replace_word(words_vect[k]);
			goto back;
		}
	}

	showGrid();

	words_vect.clear();
}
Last edited on
oneidacharisse (81)
I also put the two can_placeX functions into one to lighten the code.
dhayden (5798)
I was having a lot of trouble keeping row and col straight. The way it prints, the first dimension is the row and the second is the column. I went through the code and made that consistent.

I changed Place() and can_place() to take two variables (dr and dc) to indicate which direction you're doing.

I added a bunch of debugging code, such as printing the grid after each word is placed.

I removed several redundant variables (xword_N_intersection_D) and renamed others: (temp_intersec_1 and temp_intersec_2 to cur_intersec and prev_intersec) to more clearly say what they represent.

Look this over and let me know if you have any questions. After this, let's get rid of all those goto's.

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
277
278
279
280
281
282
283
284
285
286
 
#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
void
Place(int row, int col,
      int dr, int dc,
      std::string & word)
{
    coord_col.push_back(col);
    coord_row.push_back(row);
    unsigned taille = word.length();
    for (unsigned int j = 0; j < taille; j++) {
	grid[row][col] = word[j];
	col += dc;
	row += dr;
    }
}


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

    std::cout << "Can " << word << " go at " << row << ',' << col << " -> " << dr << ',' << dc << '?';
    if (col < 0 || col + dc*taille >= GridSize ||
	row < 0 || row + dr*taille >= GridSize) {
	std::cout << " no\n";
	return false;
    }


    for (unsigned int j = 0; j < taille; j++) {
	char word_letter = word[j];
	if (grid[row][col] == empty) {
	    score = score + 1;
	} else if (grid[row][col] != word_letter) {
	    std::cout << " no\n";
	    return false;
	}
	row += dr;
	col += dc;
    }
    if (score < taille) {
	std::cout << " yes\n";
	return true;
    } else {
	std::cout << " no\n";
	return false;
    }
}

//Function randomly retrieving words from the dictionary
std::string randomword(int randomline)
{
    std::string word1;
    std::string ifileName = "dictionary.txt";
    std::ifstream f(ifileName);

    if (!f)
	std::cerr << "File '" << ifileName << "' couldn't opened!\n";

    std::string s;

    for (int i = 1; i < randomline; i++) {
	std::getline(f, s);
	std::transform(s.begin(), s.end(), s.begin(),[](unsigned char c) {
		       return std::tolower(c);}
	);
	word1 = s;
    }

    return word1;
}

void
replace_word(std::string & current_word)
{
    int rand3 = random(100, 20000);
    std::string replacement = randomword(rand3);
    std::replace(words_vect.begin(), words_vect.end(), current_word, replacement);

}

void
showGrid()
{
    //grid view

    std::cout << "  ";
    for (int col = 0; col < GridSize; col++) {
	std::cout << col % 10 << ' ';
    }
    std::cout << '\n';
    
    for (unsigned int row = 0; row < GridSize; row++) {
	std::cout << row%10 << ' ';
	for (int col = 0; col < GridSize; col++) {
	    std::cout << grid[row][col];
	    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 place_v = false;
    bool place_h = false;
    //number of words to place
    int rand0 = random(10, 15);
    int num = rand0;

    //position of the horizontal and vertical intersection letter
    std::string prec_word;
    std::string current_word;
    int cur_intersec;
    int prev_intersec;
    //score for horizontal and vertical positioning
    bool score_h = false;
    bool score_v = false;
    //random word retrieval and addition to vector
    for (unsigned int i = 0; i < num; i++) {
	//depending on the size of the dictionary
	int rand1 = random(100, 20000);
	std::string word1 = randomword(rand1);
	words_vect.push_back(word1);
    }

    std::string word1 = words_vect[0];
    unsigned len_word1 = word1.length();

    int pos_word1 = Align(len_word1, GridSize);
    Place(pos_word1, (GridSize / 2), 1, 0, words_vect[0]);

    for (unsigned int k = 1; k < words_vect.size(); k++) {
      back:
	// start of testing
	prec_word = words_vect[k - 1];
	current_word = words_vect[k];
	std::string intersec = find_intersection(words_vect[k - 1], words_vect[k]);

	if (intersec.empty()) {
	    std::cout << " Replacing current word " << words_vect[k]
		      << "because it doesn't intersect with " << words_vect[k-1] << "\n";
	    replace_word(current_word);
	    goto back;
	} else {
	    //for each intersecting letter of the word in the vector 
	    std::cout << "Last word started at " << coord_row[k-1] << ',' << coord_col[k-1] << '\n';
	    for (unsigned int j = 0; j < intersec.length(); j++) {
		//temporary position of the selected intersection letter

		if (k % 2 != 0) {
		    // Place it horizontally
		    cur_intersec = current_word.find_last_of(intersec[j]);
		    prev_intersec = prec_word.find_last_of(intersec[j]);
		    score_h =
			can_place(coord_row[k - 1] + prev_intersec,
				  coord_col[k - 1] - cur_intersec,
				  0, 1, current_word);
		    //if the horizontal score of the position is equal to the size of the word 

		    if (score_h && k % 2 != 0) {
			place_h = true;
			std::cout << " Testing word " << k << "/" << num << "\n";
			std::
			    cout << " Current word1 " << prec_word << " Current word2 " <<
			    current_word << "\n";
			std::cout << "-----" << "\n";
			goto placing_word;
		    } else {
			place_h = false;
		    }
		}

		if (k % 2 == 0) {
		    // Place it vertically
		    cur_intersec = current_word.find_last_of(intersec[j]);
		    prev_intersec = prec_word.find_last_of(intersec[j]);
		    score_v =
			can_place(coord_row[k - 1] - cur_intersec,
				  coord_col[k - 1] + prev_intersec,
				  1, 0, current_word);

		    //if the vertical score of the position is equal to the size of the word 

		    if (score_v && k % 2 == 0) {
			place_v = true;
			std::cout << " Testing word " << k << "/" << num << "\n";
			std::
			    cout << " Current word1 " << prec_word << " Current word2 " <<
			    current_word << "\n";
			std::cout << "-----" << "\n";
			goto placing_word;
		    } else {
			place_v = false;
		    }
		}
	    }
	}

      placing_word:

	if (place_h && k % 2 != 0) {
	    Place(coord_row[k - 1] + prev_intersec,
		  coord_col[k - 1] - cur_intersec,
		  0, 1, current_word);
	} else if (!place_h && k % 2 != 0) {
	    std::cout << " Replacing current word " << words_vect[k] << "\n";
	    replace_word(words_vect[k]);
	    goto back;
	}

	if (place_v && k % 2 == 0) {
	    Place(coord_row[k - 1] - cur_intersec,
		  coord_col[k - 1] + prev_intersec,
		  1, 0, current_word);
	} else if (!place_v && k % 2 == 0) {
	    std::cout << " Replacing current word " << words_vect[k] << "\n";
	    replace_word(words_vect[k]);
	    goto back;
	}
	showGrid();
    }


    words_vect.clear();
}

oneidacharisse (81)
Okay, I think I understand the code. If ever, I'll tell you!
dhayden (5798)
Let's look at the logic in main. After some setup, it's basically:
1
2
3
4
5
 
for each word to place {
    pick a random word
    if you can't place it then pick another one
    place the word
}


That suggests an inner loop:
1
2
3
4
5
6
7
 
for (each word to place) {
   do {
      pick a random word
      see if you can place it
   } while (you can't place it)
   place the word
}


To see if you can place it, you don't need special code to see if there's an intersection. Instead, just attempt the loop through the intersecting characters. It won't run since there's no intersection and thus it won't find a place to put the word.

You can also do away with replaceword(). Instead, only store the words in the words_vect after they've been placed.

I decided to change randomword() also. The new version reads the entire dictionary file the first time it's called. Then it picks a random word from the dictionary. The new code runs much faster.

Finally, I added code to print the list of words at the end.
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
 
#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 < int > coord_col;
std::vector < int > 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;
}

// Place the word at the location and direction given. Also update
// coord_col, coord_row, and words_vect
void
Place(int row, int col,
      int dr, int dc,
      std::string & word)
{
    coord_col.push_back(col);
    coord_row.push_back(row);
    words_vect.push_back(word);
    unsigned taille = word.length();
    for (unsigned int j = 0; j < taille; j++) {
	grid[row][col] = word[j];
	col += dc;
	row += dr;
    }
}


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

    std::cout << "Can " << word << " go at " << row << ',' << col << " -> " << dr << ',' << dc << '?';
    if (col < 0 || col + dc*taille >= GridSize ||
	row < 0 || row + dr*taille >= GridSize) {
	std::cout << " no\n";
	return false;
    }


    for (unsigned int j = 0; j < taille; j++) {
	char word_letter = word[j];
	if (grid[row][col] == empty) {
	    score = score + 1;
	} else if (grid[row][col] != word_letter) {
	    std::cout << " no\n";
	    return false;
	}
	row += dr;
	col += dc;
    }
    if (score < taille) {
	std::cout << " yes\n";
	return true;
    } else {
	std::cout << " no\n";
	return false;
    }
}

//Function randomly retrieving words from the dictionary
std::string randomword()
{
    static std::vector<std::string> dict;
    if (dict.size() == 0) {
	std::string ifileName = "dictionary.txt";
	std::ifstream f(ifileName);

	if (!f)
	    std::cerr << "File '" << ifileName << "' couldn't opened!\n";

	std::string s;
	while (f >> s) {
	    std::transform(s.begin(), s.end(), s.begin(),[](unsigned char c) {
							 return std::tolower(c);}
		);
	    dict.push_back(s);
	}
    }
    return dict[rand() % dict.size()];
}

void
showGrid()
{
    //grid view

    std::cout << "  ";
    for (int col = 0; col < GridSize; col++) {
	std::cout << col % 10 << ' ';
    }
    std::cout << '\n';
    
    for (unsigned int row = 0; row < GridSize; row++) {
	std::cout << row%10 << ' ';
	for (int col = 0; col < GridSize; col++) {
	    std::cout << grid[row][col];
	    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));
    //number of words to place
    int rand0 = random(10, 15);
    int num = rand0;

    //position of the horizontal and vertical intersection letter
    std::string current_word;
    int cur_intersec;
    int prev_intersec;

    // Place the first word vertically in the middle of the grid
    current_word = randomword();
    int pos_word1 = Align(current_word.length(), GridSize);
    Place(pos_word1, (GridSize / 2), 1, 0, current_word);

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

	// Loop to try to place random words
	do {
	    string prec_word = words_vect[k - 1];
	    current_word = randomword();
	    std::string intersec = find_intersection(prec_word, current_word);
		    
	    score = false;
	    std::cout << "Last word started at " << coord_row[k-1] << ',' << coord_col[k-1] << '\n';

	    // for each intersecting letter of the word in the vector 
	    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]);
		prev_intersec = prec_word.find_last_of(intersec[j]);
		if (k % 2 != 0) {
		    // Place it horizontally
		    score = can_place(coord_row[k - 1] + prev_intersec,
				      coord_col[k - 1] - cur_intersec,
				      0, 1, current_word);
		} else {
		    // Place it vertically
		    score = can_place(coord_row[k - 1] - cur_intersec,
				      coord_col[k - 1] + prev_intersec,
				      1, 0, current_word);
		}
	    }
	} while (!score);
	
	if (k % 2 != 0) {
	    Place(coord_row[k - 1] + prev_intersec,
		  coord_col[k - 1] - cur_intersec,
		  0, 1, current_word);
	} else {
	    Place(coord_row[k - 1] - cur_intersec,
		  coord_col[k - 1] + prev_intersec,
		  1, 0, current_word);
	}
	showGrid();
    }
    // Show the word list
    std::cout << "\n Word List:\n";
    for (auto &word : words_vect) {
	std::cout << word << '\n';
    }
}

oneidacharisse (81)
It's great that it's faster, but I must admit I don't understand how you do it when the word doesn't match? Without replacing it! You change the word randomly in the dictionary completely recorded in the vector?
Last edited on
dhayden (5798)
It's the loop from lines 171 to 197. Line 173 picks a random word from the dictionary. Lines 174-195 determine if it will fit. The test at the end of the do/while loop (line 197) checks to see if it fits. If score is false, then we couldn't fit it and we go around to pick another random word. Otherwise we drop down to lines 199-207 to actually place it.

I don't have to replace the word because I don't insert it into words_vect until I'm certain that it can be placed. In fact, you'll find that Place() contains the code to add the word to words_vect.
oneidacharisse (81)
Okay, I'll try to redo this on my version of the code to incorporate your ideas and make sure I understand. Cause if I don't, I'm going to be standing on the side of the road.
oneidacharisse (81)
Ok know that I'm not doing this to question your idea of the program but simply to understand by myself how to do it. I tried, following your idea (the one in the last code), to modify my code. But my program is slower than the previous version, could you tell me where my mistake is ? Then if you want I delete the post.

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
 
#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
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() {
  int randomline = random(20, 22000);
  std::string word1;
  std::string ifileName = "dictionary.txt";
  std::ifstream f(ifileName);

  if (!f)
    std::cerr << "File '" << ifileName << "' couldn't opened!\n";

  std::string s;

  for (int i = 1; i < randomline; i++) {
    std::getline(f, s);
    std::transform(s.begin(), s.end(), s.begin(), [](unsigned char c) {
      return std::tolower(c);
    });
    word1 = s;
  }

  return word1;
}

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));

  //number of words to place
  int rand0 = random(5, 15);
  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++) {
    bool score;
    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);

      if (intersec.empty()) {
        score = false;

      } else {
        for (unsigned int j = 0; 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);

          } 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
Pages: 123456