crossword puzzle

[oneidacharisse]

Hello, if it is not possible to be sure to place all the words of the sentence or text contained in the file, I would like to make a large number of tests and save the best possible grid with this line :

uninitialized_copy_n(*grid, Size*Size, *grid2);

can you please help me with that?

#include <iostream>
#include <string>
#include <algorithm>
#include <bits/stdc++.h>
#include <stdlib.h>
#include <sstream>
#include <ctime>
#include <vector>
#include <memory>
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;
const size_t Size = 26;

char grid[Size][Size];

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

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

//Function placing words 
void Place(int col, int row, int id_word, int dr, int dc, std::string &word)
{
	words_vect.push_back(word);
	coord_col.push_back(col);
	coord_row.push_back(row);

	unsigned taille = word.length();
	for (unsigned int j = 0; j < taille; j++)
	{
		grid[col][row] = word[j];
		col += dc;
		row += dr;
	}
}

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

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

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

		row += dr;
		col += dc;
	}

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

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

	std::ifstream file("comment.txt");
	for (std::string word; file >> word;)
	{
		if (std::find(words_count.begin(), words_count.end(), word) != words_count.end())
		{
			to_add = false;
		}
		else
		{
			to_add = true;
		}

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

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

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

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

	//If it is the first word to be placed (id_word = 0) then look for the longest word of the word vector to be 
	//placed to maximize the chances of finding a letter of intersection later!
	if (id_word < 1)
	{
		std::sort(words.begin(), words.end(), [](const std::string &s1, const std::string &s2)
		{
			return s1.size() < s2.size();
	});
		int test = words.size() - 1;
		return words[test];
	}
	else if (id_word > 1)
	{
		// When you get here, the dictionary file has been read into the words vector.
		int randomline = random(0, words.size() - 1);
		return words[randomline];
	}
}

//grid view 
template < typename T, size_t ROWS, size_t COLS>
	void print(T(&grid)[ROWS][COLS])
	{
		for (size_t r = 0; r < ROWS; ++r)
		{
			for (size_t c = 0; c < COLS; ++c)
				cout << grid[r][c] << ' ';
			cout << '\n';
		}
	}

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

//Function to fill the grid
void fill_grid()
{
	srand(time(0));
	int x[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
	int y[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
	bool score;

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

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

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

	int k = 1;

	// Loop to try to place random words
	do {
		//as long as the chosen word is already placed, we look for a new word.	
		do { 	k = k + 1;
			random_word = randomword(k);

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

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

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

			intersec = find_intersection(prec_word, current_word);

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

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

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

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

}

int main(int argc, char *argv[])
{
	std::vector<double> notation;
	char grid2[Size][Size];
	uninitialized_fill_n(*grid, Size *Size, '.');
	int score = 0;
	int note;

	//start of a 100 test loop
	for (unsigned int j = 1; j < 20; j++)
	{
		//grid filling

		std::string word1 = randomword(0);
		unsigned len_word1 = word1.length();
		int pos_word1 = Align(len_word1, GridSize);
		Place(pos_word1, (GridSize / 2), 0, 0, 1, word1);
		fill_grid();
		note = words_vect.size();
		notation.push_back(note);
		for (int k: notation)
		{
			if (note > k)
			{
				score = score + 4;
			}
			else
			{
				score = score - 2;
			}
		}
		if (score > notation.size())
		{

			uninitialized_copy_n(*grid, Size *Size, *grid2);
			print(grid2);
		}
	}
}

Edited to change the last loop but the program still does not end correctly. My if condition on the score doesn't play its role! I have another possibility to copy the grid but I haven't tried it yet.

[oneidacharisse]

Another version with a different random that I found while doing my research for this topic:
http://www.cplusplus.com/forum/general/271499/

#include <iostream>
#include <string>
#include <algorithm>
#include <bits/stdc++.h>
#include <stdlib.h>
#include <sstream>
#include <ctime>
#include <chrono>
#include <random>
#include <functional>
#include <cstdint>
#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];

static std::mt19937 rng;

static void seed(uint32_t seed)
{
	rng.seed(static_cast<std::mt19937::result_type > (seed));
}

static void seed()
{
	uint32_t t = static_cast<uint32_t> (time(nullptr));
	std::hash<uint32_t> hasher;
	size_t hashed = hasher(t);
	seed(static_cast<uint32_t> (hashed));
}

//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()
{
	// 22000 words in the dictionary. "static" means doesn't get destroyed each time the function returns
	static std::vector<std::string > words;
	std::string s;

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

		if (!f)
		{
			std::cerr << "File '" << ifileName << "' couldn't opened!\n";
			exit(1);	// fatal error
		}

		for (int i = 0; i <= 22000; i++)
		{
			std::getline(f, s);
			std::transform(s.begin(), s.end(), s.begin(), [](unsigned char c)
			{
				return std::tolower(c);
	});
			words.push_back(s);	// save the word
		}
	}

	// When you get here, the dictionary file has been read into the words vector.

	std::uniform_int_distribution < > dis(20, 22000);
	int randomline = dis(rng);

	return words[randomline];	// return that word from the dictionary
}

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

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

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

int main(int argc, char *argv[])
{
	seed();
	memset(grid, '.', sizeof(grid));
	bool score;
	bool unplaced;
	//number of words to place

	std::uniform_int_distribution < > dis(20, 30);
	int rand0 = dis(rng);

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

	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++)
	{
		// Loop to try to place random words
		do {
			//as long as the chosen word is already placed, we look for a new word.	
			do {
				random_word = randomword();

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

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

			prec_word = words_vect[k - 1];

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

			for (unsigned int j = 0; !score && j < intersec.length(); j++)
			{
				//temporary position of the selected intersection letter
				cur_intersec = current_word.find_last_of(intersec[j]);
				prec_intersec = prec_word.find_last_of(intersec[j]);
				//if the horizontal score of the position is equal to the size of the word 
				if (k % 2 != 0)
				{
					score = can_place(coord_col[k - 1] + cur_intersec, coord_row[k - 1] - prec_intersec, k, current_word);
					if (score)
					{
						cur_word_pos_inter = cur_intersec;
						prec_word_pos_inter = prec_intersec;
					}
				}
				else if (k % 2 == 0)
				{
					score = can_place(coord_col[k - 1] - prec_intersec, coord_row[k - 1] + cur_intersec, k, current_word);
					if (score)
					{
						cur_word_pos_inter = cur_intersec;
						prec_word_pos_inter = prec_intersec;
					}
				}
			}
		} while (!score);

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

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

[oneidacharisse]

I created a workspace for this project:
https://hyom.slack.com/files/U01601BUX0X/F01681SUTF0/test_random_crossword17_without_double.cpp

https://hyom.slack.com/archives/D016EVB128K/p1593680181000100