crossword puzzle

Pages: 1234... 6
codingday (23)
I've modified the word placement functions. But I need to create a function that says if I place the word or not in the grid or complete the else {} of my loop if {}. I'd like to avoid using the structures if possible, no offense.

 
 
constexpr char empty = '.';


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
 
//Horizontal word placement function
int PlaceHorizontal(int x, int y, std::string &word)
{
	coord_x.push_back(x);
	coord_y.push_back(y);

	int taille = word.length();
	for (int j = 0; j != taille; j++)
	{
		char letter_in_grid = grid[x][y + j];
		if (letter_in_grid == empty || letter_in_grid == word[j])
		{
			grid[x][y + j] = word[j];
		}
		else { 
// here I have to be able to give feedback not to place the word and go back to the main program to change the word or position is that right?
                         }
	}
}

//Function placing words vertically
int PlaceVertical(int x, int y, std::string &word)
{
	coord_x.push_back(x);
	coord_y.push_back(y);
	int taille = word.length();
	for (int j = 0; j != taille; j++)
	{
		char letter_in_grid = grid[x + j][y];
		if (letter_in_grid == empty || letter_in_grid == word[j])
		{
			grid[x + j][y] = word[j];
		}
		else { 
// here I have to be able to give feedback not to place the word and go back to the main program to change the word or position is that right?
                         }
	}
}
Last edited on
nuderobmonkey (640)
Hello to replace this part of my code? or replacing the whole and recoding everything? Can you explain the idea to me, please?

My code is merely a suggestion that shows the Idea of counting matching letters. You need to customize the code to your needs.

The function works like the following:
It tests a word for all positions in the grid whether it can be placed. And as an additional constraint, there must match a distinct count of letters in the grid. So for the second and third words, you could set 'needed_matching_letters' to 1, for the fourth and fifth you could set it to 2 and so forth.
This should produce a tight grid with as many intersections as you want. Combine it with testing for random words.

And yes, if you want to use this idea, I guess you need to recode the most stuff of your own code.
Last edited on
codingday (23)
Okay, I'll try to rewrite the code by trying your idea.

;) keep calm and hard coding !
codingday (23)
Hello, could you help me to adapt this code to my code please I really don't know how to do it? That would be one way to overcome it.

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
 
#include <iostream>
#include <vector>
#include <algorithm>

// admissible_choice returns true when the point at (x,y) is inside the grid,
// and is also unpopulated.
bool admissible_choice(std::vector<std::vector<char> > grid, int x, int y) {
    return x >= 0
        && x < static_cast<int>(grid.front().size())
        && y >= 0
        && y < static_cast<int>(grid.size())
        && grid[y][x] == '.';
}

void print_grid(std::vector<std::vector<char> > const& grid) {
    for(const auto& line : grid) {
        for(auto ch : line) {
            std::cout << ch;
        }
        std::cout << '\n';
    }
    std::cout << '\n';
}

// backtracking performs a depth-first recursive search for valid word positions
void backtracking(std::vector<std::vector<char> > &grid, std::vector<char> const& word, int x, int y, int wi=0) {
    if(!admissible_choice(grid, x, y)) {
        return;
    }

    grid[y][x] = word[wi];

    if(++wi == word.size()) {
        print_grid(grid);
    } else {
        backtracking(grid, word, x+1, y, wi);
        backtracking(grid, word, x-1, y, wi);
        backtracking(grid, word, x, y+1, wi);
        backtracking(grid, word, x, y-1, wi);
    }
    grid[y][x] = '.';
}

// place_word initializes backtracking recursion, for every
// possible starting point for a word placed in a grid
void place_word(std::vector<std::vector<char> > &grid, std::vector<char> const& word) {
    const int width = static_cast<int>(grid.front().size());
    const int height = static_cast<int>(grid.size());
    for(int y=0; y<height; ++y) {
        for(int x=0; x<width; ++x) {
            backtracking(grid, word, x, y);
        }
    }
}

// ToVector converts a char string literal to a vector
template <std::size_t N>
std::vector<char> ToVector(const char (&str)[N]) {
    return std::vector<char>(&str[0], &str[N-1]);
}

// InitGrid returns a grid with the given dimensions in its unpopulated state
std::vector<std::vector<char> > InitGrid(std::size_t width, std::size_t height) {
    std::vector<std::vector<char> > grid(height);
    for(auto& line : grid) {
        line.assign(width, '.');
    }
    return grid;
}

int main() {
    auto word = ToVector("henri");
    
    auto grid = InitGrid(word.size(), word.size());

    place_word(grid, word);
}
dhayden (5798)
could you help me to adapt this code to my code
Are you sure you want to? This lets words snake around the grid. Here are a few lines of output of the program as it places "henri" on the grid:
he...
rn...
i....
.....
.....

he...
.n...
.ri..
.....
.....

he...
.n...
ir...
.....
.....

he...
.n...
.r...
.i...
.....

h....
enri.
.....
.....
.....

codingday (23)
Hello it's the backtracking that interests me in the code it's not what the code does. In the function admissible_choice I have to put either the vertical placement or the horizontal placement but in place_word?

I made a shorter version, I think it works pretty well with a random number of words and the best placement possible. There are still some bugs, but it works overall.
Last edited on
codingday (23)
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
 
#include <iostream>
#include <string>
#include <algorithm>
#include <bits/stdc++.h>
#include <stdlib.h>
#include <sstream>
#include <ctime>
#include <vector>
using namespace std;
std::vector<double> coord_x;
std::vector<double> coord_y;

std::vector<double> temporary_coord_x;
std::vector<double> temporary_coord_y;

std::vector<std::string > words;
//vector to know how the word is placed in the grid vertically or horizontally (v / h)
std::vector<std::string > place;
constexpr char empty = '.';
char grid[26][26] = {
		{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' }
};
//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
int PlaceHorizontal(int x, int y, int id_word, std::string &word)
{
	int x_word1_intersection;
	int x_word2_intersection;
	std::string intersec;
	std::string temp1 = word;
	std::string temp2;
	int taille = word.length();
	for (int j = 0; j <= taille; j++)
	{
		char letter_in_grid = grid[x][y + j];
		if (letter_in_grid == empty || letter_in_grid == word[j])
		{
			grid[x][y + j] = word[j];
			coord_x.push_back(x);
			coord_y.push_back(y);
			place.push_back("h");
		}
		else {}
	}
}

//Function placing words vertically
int PlaceVertical(int x, int y, int id_word, std::string &word)
{
	int taille = word.length();
	for (int j = 0; j <= taille; j++)
	{
		char letter_in_grid = grid[x + j][y];
		if (letter_in_grid == empty || letter_in_grid == word[j])
		{
			grid[x + j][y] = word[j];
			coord_x.push_back(x);
			coord_y.push_back(y);
			place.push_back("v");
		}
		else {}
	}
}
//function that assigns a score to the place chosen for the word
int can_place(int x, int y, int id_word, std::string &word)
{
	int score = 0;
	int taille = word.length();
	for (int j = 0; j != taille; j++)
	{
               //if the previous word is placed horizontally place the word vertically
		if (place[id_word - 1] == "h")
		{
			char letter_in_grid = grid[x + j][y];
			if (letter_in_grid == empty || letter_in_grid == word[j])
			{
				score = score + 1;
			}
			else
			{
				score = score - 1;
			}
		}
                //if the previous word is placed vertically place the word horizontally
		if (place[id_word - 1] == "v")
		{
			char letter_in_grid = grid[x][y + j];
			if (letter_in_grid == empty || letter_in_grid == word[j])
			{
				score = score + 1;
			}
			else
			{
				score = score - 1;
			}
		}
	}

	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;
}
Last edited on
codingday (23)
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
 
int main(int argc, char *argv[])
{
	string word1;
	string word2;
	string word3;
	int score;
	int x_replace;
	int y_replace;
	std::string temp1;
	std::string temp2;
	std::string temp3;
	int x_word1_intersection;
	int x_word2_intersection;
	int x_word23_intersection;
	int x_word32_intersection;

	srand(time(0));
	int x = 8;
	int y = 8;
	int indice1 = 0;
	int indice2 = 0;

	std::string intersec1;
	std::string intersec;
	std::string replace;
	int n;
	int rand0 = random(4, 40);
	n = rand0;

	int number;
	//random word retrieval and addition to vector 
	for (int i = 0; i < n; i++)
	{
		int rand1 = random(2000, 4000);
		word1 = randomword(rand1);
		words.push_back(word1);
	}

	//first word placement 
	PlaceVertical(x, y, 0, words[0]);
	intersec1 = "";

	for (int i = 1; i < words.size(); i++)
	{
		temp1 = words[i - 1];
		temp2 = words[i];
		word2 = words[i];
		//if there is no common letter between the two words running to look for a new word
		intersec = find_intersection(temp1, temp2);
		if (intersec.empty())
		{
			int rand2 = random(2000, 4000);
			replace = randomword(rand2);
			word2 = replace;
			std::replace(words.begin(), words.end(), temp2, replace);
			intersec = find_intersection(temp1, temp2);
		}

		if (i < 2)
		{
			indice2 = 0;
		}
		else
		{
			//if the letters common to the two previous words are the same as for the two current words change the common letter if possible
			if (intersec[0] == intersec1[0] && intersec.length() > 0)
			{
				if (indice2 + 1 <= intersec.length())
				{
					indice2 = indice2 + 1;
				}
			}
			else
			{
				indice2 = 0;
			}
		}

		x_word1_intersection = word1.find_last_of(intersec[indice2]);
		x_word2_intersection = word2.find_last_of(intersec[indice2]);
		//if the number i is even 
		if (i % 2 == 0)
		{
			score = can_place(coord_x[i - 1] + x_word2_intersection, coord_y[i - 1] - x_word1_intersection, i, word2);
			//if the score is equal to the size of the word place the word normally
			if (score == word2.length())
			{
				PlaceHorizontal(coord_x[i - 1] + x_word2_intersection, coord_y[i - 1] - x_word1_intersection, i, word2);
			}
			//Otherwise search each letter of the word test the position and record the position
			else
			{
				for (int k = 0; k <= word2.length(); k++)
				{
					for (int i = 0; i < 26; i++)
					{
						for (int j = 0; j < 26; j++)
						{
							if (grid[i][j] == word2[k])
							{

								temporary_coord_x.push_back(i);
								temporary_coord_y.push_back(j);
							}
						}
					}
				}
				//note all previously saved positions - if the score is equal to the size of the word place the word
				for (int l = 0; l != temporary_coord_x.size(); l++)
				{
					score = can_place(temporary_coord_x[l] + x_word2_intersection, temporary_coord_y[l], i, word2);
					if (score == word2.length())
					{
						x_replace = temporary_coord_x[l];
						y_replace = temporary_coord_y[l];
					}
				}
				PlaceHorizontal(x_replace + x_word2_intersection, y_replace, i, word2);
				temporary_coord_x.clear();
				temporary_coord_y.clear();
			}
		}
		//if the number i is odd 
		if (i % 2 != 0)
		{
			score = can_place(coord_x[i - 1] - x_word1_intersection, coord_y[i - 1] + x_word2_intersection, i, word2);
			//if the score is equal to the size of the word place the word normally 
			if (score == word2.length())
			{
				PlaceVertical(coord_x[i - 1] - x_word1_intersection, coord_y[i - 1] + x_word2_intersection, i, word2);
			}
			//Otherwise search each letter of the word test the position and record the position
			else
			{
				for (int k = 0; k <= word2.length(); k++)
				{
					for (int i = 0; i < 26; i++)
					{
						for (int j = 0; j < 26; j++)
						{
							if (grid[i][j] == word2[k])
							{
								temporary_coord_x.push_back(i);
								temporary_coord_y.push_back(j);
							}
						}
					}
				}
                                //note all previously saved positions - if the score is equal to the size of the word place the word
				for (int l = 0; l != temporary_coord_x.size(); l++)
				{
					score = can_place(temporary_coord_x[l], temporary_coord_y[l] + x_word2_intersection, i, word2);
					if (score == word2.length())
					{
						x_replace = temporary_coord_x[l];
						y_replace = temporary_coord_y[l];
					}
				}
				PlaceVertical(x_replace, y_replace + x_word2_intersection, i, word2);
				temporary_coord_x.clear();
				temporary_coord_y.clear();
			}
		}
	}

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

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

	words.clear();

}
Last edited on
codingday (23)
Hello, I've corrected some mistakes, but I don't know how to manage distances when the common word can't cross another one.
codingday (23)
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
 
#include <iostream>
#include <string>
#include <algorithm>
#include <bits/stdc++.h>
#include <stdlib.h>
#include <sstream>
#include <ctime>
#include <vector>
using namespace std;
std::vector<double> coord_x;
std::vector<double> coord_y;

std::vector<double> temporary_coord_x;
std::vector<double> temporary_coord_y;

std::vector<std::string > words;
//vector to know how the word is placed in the grid vertically or horizontally (v / h)
std::vector<std::string > place;
constexpr char empty = '.';
char grid[26][26] = {
		{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' }
};
//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
int PlaceHorizontal(int x, int y, int id_word, std::string &word)
{
	int x_word1_intersection;
	int x_word2_intersection;
	std::string intersec;
	std::string temp1 = word;
	std::string temp2;
	int taille = word.length();
	for (int j = 0; j <= taille; j++)
	{
		char letter_in_grid = grid[x][y + j];
		if (letter_in_grid == empty || letter_in_grid == word[j])
		{
			grid[x][y + j] = word[j];
			coord_x.push_back(x);
			coord_y.push_back(y);
			place.push_back("h");
		}
		else {}
	}
}

//Function placing words vertically
int PlaceVertical(int x, int y, int id_word, std::string &word)
{
	int taille = word.length();
	for (int j = 0; j <= taille; j++)
	{
		char letter_in_grid = grid[x + j][y];
		if (letter_in_grid == empty || letter_in_grid == word[j])
		{
			grid[x + j][y] = word[j];
			coord_x.push_back(x);
			coord_y.push_back(y);
			place.push_back("v");
		}
		else {}
	}
}
//function that assigns a score to the place chosen for the word
int can_place(int x, int y, int id_word, std::string &word)
{
	int score = 0;
	int taille = word.length();
	for (int j = 0; j != taille; j++)
	{
		//if the previous word is placed horizontally place the word vertically
		if (place[id_word - 1] == "h")
		{
			char letter_in_grid_v = grid[x + j][y];
			if (letter_in_grid_v == empty || letter_in_grid_v == word[j])
			{
				score = score + 1;
			}
			else
			{
				score = score - 1;
			}
		}
		//if the previous word is placed vertically place the word horizontally
		if (place[id_word - 1] == "v")
		{
			char letter_in_grid_h = grid[x][y + j];
			if (letter_in_grid_h == empty || letter_in_grid_h == word[j])
			{
				score = score + 1;
			}
			else
			{
				score = score - 3;
			}
		}
	}

	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;
}
Last edited on
codingday (23)
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
 
int main(int argc, char *argv[])
{
	string word1;
	string word2;
	string word3;
	int score;
	int x_replace;
	int y_replace;
	std::string temp1;
	std::string temp2;
	std::string temp3;
	int x_word1_intersection;
	int x_word2_intersection;
	int x_word23_intersection;
	int x_word32_intersection;

	srand(time(0));
	int x = 8;
	int y = 8;
	int indice1 = 0;
	int indice2 = 0;

	std::string intersec;
	std::string replace;

	//number of words to be placed in the grid
	int n;
	int rand0 = random(15, 40);
	n = rand0;

	int number;
	//random word retrieval and addition to vector
	for (int i = 0; i < n; i++)
	{
		//depending on the size of the dictionary
		int rand1 = random(2000, 4000);
		word1 = randomword(rand1);
		words.push_back(word1);
	}

	//first word placement
	PlaceVertical(x, y, 0, words[0]);

	for (int i = 1; i < words.size(); i++)
	{
		temp1 = words[i - 1];
		temp2 = words[i];
		word2 = words[i];

		//if there is no common letter between the two words running to look for a new word
		intersec = find_intersection(temp1, temp2);
		while (intersec.empty())
		{
			int rand2 = random(2000, 4000);
			replace = randomword(rand2);
			word2 = replace;
			std::replace(words.begin(), words.end(), temp2, replace);
			intersec = find_intersection(temp1, temp2);
		}

		int rand3 = random(0, intersec.length());
		x_word1_intersection = word1.find_last_of(intersec[rand3]);
		x_word2_intersection = word2.find_last_of(intersec[rand3]);
		//if the number i is even
		if (i % 2 == 0)
		{
			score = can_place(coord_x[i - 1] + x_word2_intersection, coord_y[i - 1] - x_word1_intersection, i, word2);
			//if the score is equal to the size of the word place the word normally
			if (score == word2.length())
			{
				PlaceHorizontal(coord_x[i - 1] + x_word2_intersection, coord_y[i - 1] - x_word1_intersection, i, word2);
			}

			//Otherwise search each letter of the word test the position and record the position
			else
			{
				for (int k = 0; k <= word2.length(); k++)
				{
					for (int i = 0; i < 26; i++)
					{
						for (int j = 0; j < 26; j++)
						{
							if (grid[i][j] == empty || grid[i][j] == word2[k])
							{
								temporary_coord_x.push_back(i);
								temporary_coord_y.push_back(j);
							}
						}
					}
				}
				//note all previously saved positions - if the score is equal to the size of the word place the word
				for (int l = 0; l != temporary_coord_x.size(); l++)
				{
					score = can_place(temporary_coord_x[l] + x_word2_intersection, temporary_coord_y[l], i, word2);
					if (score == word2.length())
					{
						x_replace = temporary_coord_x[l];
						y_replace = temporary_coord_y[l];
					}
					else {}
				}

				PlaceHorizontal(x_replace + x_word2_intersection, y_replace, i, word2);
				temporary_coord_x.clear();
				temporary_coord_y.clear();
			}
		}
		//if the number i is odd
		if (i % 2 != 0)
		{
			score = can_place(coord_x[i - 1] - x_word1_intersection, coord_y[i - 1] + x_word2_intersection, i, word2);
			//if the score is equal to the size of the word place the word normally
			if (score == word2.length())
			{
				PlaceVertical(coord_x[i - 1] - x_word1_intersection, coord_y[i - 1] + x_word2_intersection, i, word2);
			}
			//Otherwise search each letter of the word test the position and record the position
			else
			{
				for (int k = 0; k <= word2.length(); k++)
				{
					for (int i = 0; i < 26; i++)
					{
						for (int j = 0; j < 26; j++)
						{
							if (grid[i][j] == empty || grid[i][j] == word2[k])
							{
								temporary_coord_x.push_back(i);
								temporary_coord_y.push_back(j);
							}
						}
					}
				}
				//note all previously saved positions - if the score is equal to the size of the word place the word
				for (int l = 0; l != temporary_coord_x.size(); l++)
				{
					score = can_place(temporary_coord_x[l], temporary_coord_y[l] + x_word2_intersection, i, word2);
					if (score == word2.length())
					{
						x_replace = temporary_coord_x[l];
						y_replace = temporary_coord_y[l];
					}
					else {}
				}

				PlaceVertical(x_replace, y_replace + x_word2_intersection, i, word2);
				temporary_coord_x.clear();
				temporary_coord_y.clear();
			}
		}
	}

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

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

	words.clear();

}

Last edited on
codingday (23)
For this loop:
1
2
3
4
5
6
 
score = can_place(temporary_coord_x[l], temporary_coord_y[l] + x_word2_intersection, i, word2);
if (score == word2.length())
{
	x_replace = temporary_coord_x[l];
	y_replace = temporary_coord_y[l];
}

I would need a then to replace the word and redo the process of placing the word. But I'm stuck I can't go back there?
Last edited on
nuderobmonkey (640)
If you want to redo a replacement, you have to check if there are intersections with crossing words. This could be achieved by checking the upper and lower positions of a letter of the word (at a horizontally placed word). If there is a letter, you need to skip the deletion for that letter.
Last edited on
codingday (23)
There was a loop comparing the two intersecting letters from the old version that I removed. I edited and corrected without posting the code again (see above). And I changed the notation : the function removes more points when it's a bad placement than it adds points when the placement is good. For what you just wrote I understand but I can't without having to redo the whole word placement process, which would make my code twice as long. I'm trying to optimize as I go along.
Last edited on
codingday (23)
Just like that ?

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
 
#include <iostream>
#include <string>
#include <algorithm>
#include <bits/stdc++.h>
#include <stdlib.h>
#include <sstream>
#include <ctime>
#include <vector>
using namespace std;
std::vector<double> coord_x;
std::vector<double> coord_y;

//Vectors for recording word coordinates
std::vector<double> temporary_coord_x;
std::vector<double> temporary_coord_y;

std::vector<std::string > words;
//vector to know how the word is placed in the grid vertically or horizontally (v / h)
std::vector<std::string > place;
constexpr char empty = '.';
char grid[26][26] = {
		{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' }
};
//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
int PlaceHorizontal(int x, int y, int id_word, std::string &word)
{
	int x_word1_intersection;
	int x_word2_intersection;
	std::string intersec;
	std::string temp1 = word;
	std::string temp2;
	int taille = word.length();
	for (int j = 0; j < taille; j++)
	{
		char letter_in_grid = grid[x][y + j];
		if (letter_in_grid == empty || letter_in_grid == word[j])
		{
			grid[x][y + j] = word[j];
			coord_x.push_back(x);
			coord_y.push_back(y);
			place.push_back("h");
		}
		else {}
	}
}

//Function placing words vertically
int PlaceVertical(int x, int y, int id_word, std::string &word)
{
	int taille = word.length();
	for (int j = 0; j < taille; j++)
	{
		char letter_in_grid = grid[x + j][y];
		if (letter_in_grid == empty || letter_in_grid == word[j])
		{
			grid[x + j][y] = word[j];
			coord_x.push_back(x);
			coord_y.push_back(y);
			place.push_back("v");
		}
		else {}
	}
}

//function that assigns a score to the place chosen for the word
int can_place(int x, int y, int id_word, std::string &word)
{
	int score = 0;
	int taille = word.length();
	for (int j = 0; j < taille; j++)
	{
		//if the previous word is placed horizontally place the word vertically
		if (place[id_word - 1] == "h")
		{
			char letter_in_grid_v = grid[x + j][y];
			if (letter_in_grid_v == empty || letter_in_grid_v == word[j])
			{
				score = score + 1;
			}
			else
			{
				score = score - 3;
			}
		}

		//if the previous word is placed vertically place the word horizontally
		if (place[id_word - 1] == "v")
		{
			char letter_in_grid_h = grid[x][y + j];
			if (letter_in_grid_h == empty || letter_in_grid_h == word[j])
			{
				score = score + 1;
			}
			else
			{
				score = score - 3;
			}
		}
	}

	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;
}
Last edited on
codingday (23)
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
 
int main(int argc, char *argv[])
{
	string word1;
	string word2;
	string word3;
	int score;
	int x_replace;
	int y_replace;
	std::string temp1;
	std::string temp2;
	std::string temp3;
	int x_word1_intersection;
	int x_word2_intersection;

	srand(time(0));
	int x = 8;
	int y = 8;
	int indice1 = 0;
	int indice2 = 0;

	std::string intersec;
	std::string intersec1;	//I think it's unused.
	std::string replace;

	//number of words to be placed in the grid
	int n;
	int rand0 = random(10, 40);
	n = rand0;

	int number;
	//random word retrieval and addition to vector
	for (int i = 0; i < n; i++)
	{
		//depending on the size of the dictionary
		int rand1 = random(100, 20000);
		word1 = randomword(rand1);
		words.push_back(word1);
	}

	//first word placement
	PlaceVertical(x, y, 0, words[0]);

	for (int i = 1; i < words.size(); i++)
	{
		temp1 = words[i - 1];
		temp2 = words[i];
		word2 = words[i];

		intersec = find_intersection(temp1, temp2);
		while (intersec.empty())
		{
			int rand2 = random(100, 20000);
			replace = randomword(rand2);
			word2 = replace;
			std::replace(words.begin(), words.end(), temp2, replace);
			intersec = find_intersection(temp1, temp2);
		}
		//for all intersecting letters, test the position
		for (int j = 0; j < intersec.length(); j++)
		{
			int temp_intersec_1 = word1.find_last_of(intersec[j]);
			int temp_intersec_2 = word2.find_last_of(intersec[j]);
			score = can_place(coord_x[i - 1] + temp_intersec_2, coord_y[i - 1] - temp_intersec_1, i, word2);
			if (score == word2.length())
			{
				x_word1_intersection = word1.find_last_of(intersec[j]);
				x_word2_intersection = word2.find_last_of(intersec[j]);
			}
		}
		//if the number i is odd
		if (i % 2 != 0)
		{
			score = can_place(coord_x[i - 1] + x_word2_intersection, coord_y[i - 1] - x_word1_intersection, i, word2);
			//if the score is equal to the size of the word place the word normally
			if (score == word2.length())
			{
				PlaceHorizontal(coord_x[i - 1] + x_word2_intersection, coord_y[i - 1] - x_word1_intersection, i, word2);
			}

			//Otherwise search each letter of the word test the position and record the position
			else
			{
				for (int k = 0; k < word2.length(); k++)
				{
					for (int i = 0; i < 26; i++)
					{
						for (int j = 0; j < 26; j++)
						{
							if (grid[i][j] == empty || grid[i][j] == word2[k])
							{
								temporary_coord_x.push_back(i);
								temporary_coord_y.push_back(j);
								x_word2_intersection = word2.find_last_of(word2[k]);
							}
						}
					}
				}

				//note all previously saved positions - if the score is equal to the size of the word place the word
				for (int l = 0; l < temporary_coord_x.size(); l++)
				{
					score = can_place(temporary_coord_x[l] + x_word2_intersection, temporary_coord_y[l], i, word2);
					if (score == word2.length())
					{
						x_replace = temporary_coord_x[l];
						y_replace = temporary_coord_y[l];
					}
					else {}
				}
				//word placement
				PlaceHorizontal(x_replace + x_word2_intersection, y_replace, i, word2);
				temporary_coord_x.clear();
				temporary_coord_y.clear();
			}
		}
		//if the number i is even
		if (i % 2 == 0)
		{
			score = can_place(coord_x[i - 1] - x_word1_intersection, coord_y[i - 1] + x_word2_intersection, i, word2);
			//if the score is equal to the size of the word place the word normally
			if (score == word2.length())
			{
				PlaceVertical(coord_x[i - 1] - x_word1_intersection, coord_y[i - 1] + x_word2_intersection, i, word2);
			}

			//Otherwise search each letter of the word test the position and record the position
			else
			{
				for (int k = 0; k < word2.length(); k++)
				{
					for (int i = 0; i < 26; i++)
					{
						for (int j = 0; j < 26; j++)
						{
							if (grid[i][j] == empty || grid[i][j] == word2[k])
							{
								temporary_coord_x.push_back(i);
								temporary_coord_y.push_back(j);
								x_word2_intersection = word2.find_last_of(word2[k]);
							}
						}
					}
				}

				//note all previously saved positions - if the score is equal to the size of the word place the word
				for (int l = 0; l < temporary_coord_x.size(); l++)
				{
					score = can_place(temporary_coord_x[l], temporary_coord_y[l] + x_word2_intersection, i, word2);
					if (score == word2.length())
					{
						x_replace = temporary_coord_x[l];
						y_replace = temporary_coord_y[l];
					}
					else {}
				}
				//word placement
				PlaceVertical(x_replace, y_replace + x_word2_intersection, i, word2);
				temporary_coord_x.clear();
				temporary_coord_y.clear();
			}
		}
	}

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

		std::cout << "\n";
	}
	//cleaning the vector containing the words to prevent certain words
	//from remaining in memory the next time the program is executed
	words.clear();

}
Last edited on
codingday (23)
Hello, I think I brought my idea to the end, there are still some placement errors but overall the program works well. I didn't use a c++ class for beginners can use my code. I learned the code at home by my own means, and I apologize for rough draft style. I wanted to make this code because I couldn't find any code accessible to beginners to start creating C++ crosswords on the internet. And because my project is to use the crossword puzzle grid system to do compression and encryption.
Last edited on
closed account S3CpLyTq (3)
Hello, you're missing a loop if the chosen place is not correct. At line 108 place = false and so after ? It's the same draft style but it's in the same look. 

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;
std::vector<double> coord_x;
std::vector<double> coord_y;

//Vectors for recording word coordinates
std::vector<double> temporary_coord_x;
std::vector<double> temporary_coord_y;
std::vector<std::string > words_vect;
std::vector<std::string > intersection;

//vector to know how the word is placed in the grid vertically or horizontally (v / h)
std::vector<std::string > place;
constexpr char empty = '.';
char grid[26][26] = {
		{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
	{
		'.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' }
};
//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;
}
bool can_go_down(int x, int y, char letter)
{
	
    if ( y < 0 && grid[x][y+1] == '.' || y < 0 && grid[x][y+1] == letter)
        return true;
    else
        return false;
}
bool can_go_right(int x, int y, char letter)
{
    if ( x < 0 && grid[x+1][y] == '.' || x < 0 && grid[x+1][y] == letter)
        return true;
    else
        return false;
}
//Horizontal word placement function
int PlaceHorizontal(int x, int y, int id_word, std::string &word)
{
	int taille = word.length();
	for (int j = 0; j < taille; j++)
	{
		char letter_in_grid = grid[x][y + j];
		if (letter_in_grid == empty || letter_in_grid == word[j])
		{
			grid[x][y + j] = word[j];
			coord_x.push_back(x);
			coord_y.push_back(y);

		}
		else {}
	}
}
//Function placing words vertically
int PlaceVertical(int x, int y, int id_word, std::string &word)
{
	int taille = word.length();
	for (int j = 0; j < taille; j++)
	{
		char letter_in_grid = grid[x + j][y];
		if (letter_in_grid == empty || letter_in_grid == word[j])
		{
			grid[x + j][y] = word[j];
			coord_x.push_back(x);
			coord_y.push_back(y);

		}
		else {}
	}
}

//function that assigns a score to the place chosen for the word
int can_place_v(int x, int y, int id_word, std::string &word)
{
	int score = 0;
	int taille = word.length();
	for (int j = 0; j < taille; j++)
	{
		//if the previous word is placed vertically place the word horizontally
		char word_letter = word[j];
		bool test_down = can_go_down(x, y + j, word[j]);
		if (test_down == true)
		{
			if (grid[x][y + j] == empty || grid[x][y + j] == word_letter)
			{
				score = score + 1;
			}
		}
		else
		{
			score = score - 1;
		}
	}

	return score;

}

int can_place_h(int x, int y, int id_word, std::string &word)
{
	int score = 0;
	int taille = word.length();
	for (int j = 0; j < taille; j++)
	{
		//if the previous word is placed horizontally place the word vertically

		char word_letter = word[j];
		bool test_right = can_go_down(x + j, y, word[j]);
		if (test_right == true)
		{
			if (grid[x + j][y] == empty || grid[x + j][y] == word_letter)
			{
				score = score + 1;
			}
		}
		else
		{
			score = score - 1;
		}
	}

	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;
}
Last edited on
closed account S3CpLyTq (3)
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
 
int main(int argc, char *argv[])
{
	int score;
	srand(time(0));
	bool place = false;
	int n;
	int rand0 = random(20, 40);
	int num = rand0;
	int x_word2_intersection;
	int x_word1_intersection;
	int number;
	std::string temp1;
	std::string temp2;
	int word_index;
	std::string prec_word;
	std::string current_word;
	//random word retrieval and addition to vector

	//depending on the size of the dictionary

	for (int i = 0; i < num; i++)
	{
		int rand1 = random(100, 20000);
		std: string word1 = randomword(rand1);
		words_vect.push_back(word1);
	}

	//	back:
	std::string word1 = words_vect[0];
	int pos_word1 = 26 - word1.length();
	PlaceVertical(pos_word1, pos_word1, 0, words_vect[0]);

	for (int k = 1; k < words_vect.size(); k++)
	{
		back: current_word = words_vect[k];
		prec_word = words_vect[k - 1];
		temp1 = words_vect[k - 1];
		temp2 = words_vect[k];

		std::string intersec = find_intersection(temp1, temp2);
		//---

		while (intersec.empty())
		{
			int rand3 = random(100, 20000);
			std::string replacement = randomword(rand3);

			vector<string>::iterator it;
			for (it = words_vect.begin(); it != words_vect.end(); ++it)
			{
				if (*it == current_word)
				{
					words_vect.erase(it);
					words_vect.insert(it, replacement);
					prec_word = replacement;
					temp1 = replacement;
					cout << "Replacing : " << current_word << " by " << temp1 << "\n";
					goto back;
				}
			}

			std::string intersec = find_intersection(temp1, temp2);

		}

		for (int j = 0; j < intersec.length(); j++)
		{
			int temp_intersec_2 = current_word.find_last_of(intersec[j]);
			int temp_intersec_1 = prec_word.find_last_of(intersec[j]);
			if (k % 2 != 0)
			{
				score = 0;
				score = can_place_h(coord_x[k - 1] + temp_intersec_2, coord_y[k - 1] - temp_intersec_1, k, current_word);
			}
			else
			{
				score = 0;
				score = can_place_v(coord_x[k - 1] - temp_intersec_1, coord_y[k - 1] + temp_intersec_2, k, current_word);

			}

			if (score == current_word.length())
			{
				place = true;
				x_word2_intersection = temp_intersec_2;
				x_word1_intersection = temp_intersec_1;

				std::cout << " Testing word " << k << "/" << num << "\n";
				std::cout << " Current score " << score << "/" << current_word.length() << "\n";
				std::cout << " Current word1 " << prec_word << " Current word2 " << current_word << "\n";
				std::cout << "-----" << "\n";
				goto placing_word;

			}
			else

			{
				std::cout << " Testing word " << k << "/" << num << "\n";
				std::cout << " Current score " << score << "/" << current_word.length() << "\n";
				std::cout << " Current word1 " << prec_word << " Current word2 " << current_word << "\n";
				std::cout << "-----" << "\n";
				place = false;

			}
		}

		placing_word: if (place == true)
		{
			if (k % 2 != 0)
			{
				PlaceHorizontal(coord_x[k - 1] + x_word2_intersection, coord_y[k - 1] - x_word1_intersection, k, current_word);

			}
			else
			{
				PlaceVertical(coord_x[k - 1] - x_word1_intersection, coord_y[k - 1] + x_word2_intersection, k, current_word);

			}
		}
		else
		{
			int rand2 = random(100, 20000);
			std::string replacement = randomword(rand2);

			vector<string>::iterator it;
			for (it = words_vect.begin(); it != words_vect.end(); ++it)
			{
				if (*it == current_word)
				{
					words_vect.erase(it);
					words_vect.insert(it, replacement);
					prec_word = replacement;
					temp1 = replacement;
					cout << "Replacing : " << current_word << " by " << prec_word << "\n";

				}
			}
		}
	}

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

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

	words_vect.clear();

}
closed account S3CpLyTq (3)
The program generates an error from time to time, but it tests the words and replaces them if positioning is not possible. It remains to improve your idea with this participation. Don't give up.
Pages: 1234... 6