Word search: Difference between revisions
m (rephrase) |
(→{{header|CSharp}}: added C#) |
||
Line 253:
coot (8, 7) (8, 4) anne (1, 4) (1, 7)
reid (3, 3) (0, 0) sse (2, 9) (0, 9)
</pre>
=={{header|C sharp}}==
{{trans|Java}}
<lang csharp>using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
namespace Wordseach
{
static class Program
{
readonly static int[,] dirs = {{1, 0}, {0, 1}, {1, 1}, {1, -1}, {-1, 0},
{0, -1}, {-1, -1}, {-1, 1}};
class Grid
{
public char[,] Cells = new char[nRows, nCols];
public List<string> Solutions = new List<string>();
public int NumAttempts;
}
readonly static int nRows = 10;
readonly static int nCols = 10;
readonly static int gridSize = nRows * nCols;
readonly static int minWords = 25;
readonly static Random rand = new Random();
static void Main(string[] args)
{
PrintResult(CreateWordSearch(ReadWords("unixdict.txt")));
}
private static List<string> ReadWords(string filename)
{
int maxLen = Math.Max(nRows, nCols);
return System.IO.File.ReadAllLines(filename)
.Select(s => s.Trim().ToLower())
.Where(s => Regex.IsMatch(s, "^[a-z]{3," + maxLen + "}$"))
.ToList();
}
private static Grid CreateWordSearch(List<string> words)
{
int numAttempts = 0;
while (++numAttempts < 100)
{
words.Shuffle();
var grid = new Grid();
int messageLen = PlaceMessage(grid, "Rosetta Code");
int target = gridSize - messageLen;
int cellsFilled = 0;
foreach (var word in words)
{
cellsFilled += TryPlaceWord(grid, word);
if (cellsFilled == target)
{
if (grid.Solutions.Count >= minWords)
{
grid.NumAttempts = numAttempts;
return grid;
}
else break; // grid is full but we didn't pack enough words, start over
}
}
}
return null;
}
private static int TryPlaceWord(Grid grid, string word)
{
int randDir = rand.Next(dirs.GetLength(0));
int randPos = rand.Next(gridSize);
for (int dir = 0; dir < dirs.GetLength(0); dir++)
{
dir = (dir + randDir) % dirs.GetLength(0);
for (int pos = 0; pos < gridSize; pos++)
{
pos = (pos + randPos) % gridSize;
int lettersPlaced = TryLocation(grid, word, dir, pos);
if (lettersPlaced > 0)
return lettersPlaced;
}
}
return 0;
}
private static int TryLocation(Grid grid, string word, int dir, int pos)
{
int r = pos / nCols;
int c = pos % nCols;
int len = word.Length;
// check bounds
if ((dirs[dir, 0] == 1 && (len + c) > nCols)
|| (dirs[dir, 0] == -1 && (len - 1) > c)
|| (dirs[dir, 1] == 1 && (len + r) > nRows)
|| (dirs[dir, 1] == -1 && (len - 1) > r))
return 0;
int rr, cc, i, overlaps = 0;
// check cells
for (i = 0, rr = r, cc = c; i < len; i++)
{
if (grid.Cells[rr, cc] != 0 && grid.Cells[rr, cc] != word[i])
{
return 0;
}
cc += dirs[dir, 0];
rr += dirs[dir, 1];
}
// place
for (i = 0, rr = r, cc = c; i < len; i++)
{
if (grid.Cells[rr, cc] == word[i])
overlaps++;
else
grid.Cells[rr, cc] = word[i];
if (i < len - 1)
{
cc += dirs[dir, 0];
rr += dirs[dir, 1];
}
}
int lettersPlaced = len - overlaps;
if (lettersPlaced > 0)
{
grid.Solutions.Add($"{word,-10} ({c},{r})({cc},{rr})");
}
return lettersPlaced;
}
private static int PlaceMessage(Grid grid, string msg)
{
msg = Regex.Replace(msg.ToUpper(), "[^A-Z]", "");
int messageLen = msg.Length;
if (messageLen > 0 && messageLen < gridSize)
{
int gapSize = gridSize / messageLen;
for (int i = 0; i < messageLen; i++)
{
int pos = i * gapSize + rand.Next(gapSize);
grid.Cells[pos / nCols, pos % nCols] = msg[i];
}
return messageLen;
}
return 0;
}
public static void Shuffle<T>(this IList<T> list)
{
int n = list.Count;
while (n > 1)
{
n--;
int k = rand.Next(n + 1);
T value = list[k];
list[k] = list[n];
list[n] = value;
}
}
private static void PrintResult(Grid grid)
{
if (grid == null || grid.NumAttempts == 0)
{
Console.WriteLine("No grid to display");
return;
}
int size = grid.Solutions.Count;
Console.WriteLine("Attempts: " + grid.NumAttempts);
Console.WriteLine("Number of words: " + size);
Console.WriteLine("\n 0 1 2 3 4 5 6 7 8 9");
Console.Write("");
for (int r = 0; r < nRows; r++)
{
Console.Write("\n{0} ", r);
for (int c = 0; c < nCols; c++)
Console.Write(" {0} ", grid.Cells[r, c]);
}
Console.WriteLine("\n");
for (int i = 0; i < size - 1; i += 2)
{
Console.WriteLine("{0} {1}", grid.Solutions[i],
grid.Solutions[i + 1]);
}
if (size % 2 == 1)
Console.WriteLine(grid.Solutions[size - 1]);
Console.ReadLine();
}
}
}</lang>
<pre>
Attempts: 1
Number of words: 28
0 1 2 3 4 5 6 7 8 9
0 i m n e p o R p i d
1 s u r O e l d n i b
2 n e S b a n d y a E
3 a s d i t h y t T b
4 m u a r n s a u d r
5 s m h T o s o i h o
6 d A c r t C p c r t
7 a y p e p a n O c h
8 e o D o r u x g s a
9 l b E w l a k n o h
rapid (4,8)(8,4) bindle (9,1)(4,1)
bandy (3,2)(7,2) leadsman (0,9)(0,2)
accost (9,8)(4,3) museum (1,5)(1,0)
taste (7,3)(3,7) broth (9,3)(9,7)
rosy (3,6)(6,3) honk (9,9)(6,9)
chad (2,6)(2,3) lunch (4,9)(8,5)
open (5,0)(2,0) gsa (7,8)(9,8)
dip (9,0)(7,0) ansi (0,3)(0,0)
pol (2,7)(0,9) boy (1,9)(1,7)
woe (3,9)(3,7) tax (4,6)(6,8)
rib (3,4)(3,2) not (4,4)(4,6)
hair (5,3)(8,6) bat (9,1)(7,3)
nyu (5,2)(7,4) ape (5,7)(3,7)
era (3,7)(5,9) ere (1,2)(3,0)
</pre>
|
Revision as of 12:10, 8 September 2017
A word search puzzle typically consists of a grid of letters in which words are hidden.
There are many varieties of word search puzzles. For the task at hand we will use a rectangular grid in which the words may be placed horizontally, vertically, or diagonally. The words may also be spelled backwards.
The words may overlap but are not allowed to zigzag, or wrap around.
- Task
Create a 10 by 10 word search and fill it using words from the unixdict. Use only words that are longer than 2, and contain no non-alphabetic characters.
The cells not used by the hidden words should contain the message: Rosetta Code, read from left to right, top to bottom. These letters should be somewhat evenly distributed over the grid, not clumped together. The message should be in upper case, the hidden words in lower case. All cells should either contain letters from the hidden words or from the message.
Pack a minimum of 25 words into the grid.
Print the resulting grid and the solutions.
- Example
0 1 2 3 4 5 6 7 8 9 0 n a y r y R e l m f 1 y O r e t s g n a g 2 t n e d i S k y h E 3 n o t n c p c w t T 4 a l s u u n T m a x 5 r o k p a r i s h h 6 a A c f p a e a c C 7 u b u t t t O l u n 8 g y h w a D h p m u 9 m i r p E h o g a n parish (3,5)(8,5) gangster (9,1)(2,1) paucity (4,6)(4,0) guaranty (0,8)(0,1) prim (3,9)(0,9) huckster (2,8)(2,1) plasm (7,8)(7,4) fancy (3,6)(7,2) hogan (5,9)(9,9) nolo (1,2)(1,5) under (3,4)(3,0) chatham (8,6)(8,0) ate (4,8)(6,6) nun (9,7)(9,9) butt (1,7)(4,7) hawk (9,5)(6,2) why (3,8)(1,8) ryan (3,0)(0,0) fay (9,0)(7,2) much (8,8)(8,5) tar (5,7)(5,5) elm (6,0)(8,0) max (7,4)(9,4) pup (5,3)(3,5) mph (8,8)(6,8)
C++
<lang cpp>
- include <iomanip>
- include <ctime>
- include <iostream>
- include <vector>
- include <string>
- include <algorithm>
- include <fstream>
const int WID = 10, HEI = 10, MIN_WORD_LEN = 3, MIN_WORD_CNT = 25;
class Cell { public:
Cell() : val( 0 ), cntOverlap( 0 ) {} char val; int cntOverlap;
}; class Word { public:
Word( std::string s, int cs, int rs, int ce, int re, int dc, int dr ) : word( s ), cols( cs ), rows( rs ), cole( ce ), rowe( re ), dx( dc ), dy( dr ) {} bool operator ==( const std::string& s ) { return 0 == word.compare( s ); } std::string word; int cols, rows, cole, rowe, dx, dy;
}; class words { public:
void create( std::string& file ) { std::ifstream f( file.c_str(), std::ios_base::in ); std::string word; while( f >> word ) { if( word.length() < MIN_WORD_LEN || word.length() > WID || word.length() > HEI ) continue; if( word.find_first_not_of( "abcdefghijklmnopqrstuvwxyz" ) != word.npos ) continue; dictionary.push_back( word ); } f.close(); std::random_shuffle( dictionary.begin(), dictionary.end() ); buildPuzzle(); }
void printOut() { std::cout << "\t"; for( int x = 0; x < WID; x++ ) std::cout << x << " "; std::cout << "\n\n"; for( int y = 0; y < HEI; y++ ) { std::cout << y << "\t"; for( int x = 0; x < WID; x++ ) std::cout << puzzle[x][y].val << " "; std::cout << "\n"; } size_t wid1 = 0, wid2 = 0; for( size_t x = 0; x < used.size(); x++ ) { if( x & 1 ) { if( used[x].word.length() > wid1 ) wid1 = used[x].word.length(); } else { if( used[x].word.length() > wid2 ) wid2 = used[x].word.length(); } } std::cout << "\n"; std::vector<Word>::iterator w = used.begin(); while( w != used.end() ) { std::cout << std::right << std::setw( wid1 ) << ( *w ).word << " (" << ( *w ).cols << ", " << ( *w ).rows << ") (" << ( *w ).cole << ", " << ( *w ).rowe << ")\t"; w++; if( w == used.end() ) break; std::cout << std::setw( wid2 ) << ( *w ).word << " (" << ( *w ).cols << ", " << ( *w ).rows << ") (" << ( *w ).cole << ", " << ( *w ).rowe << ")\n"; w++; } std::cout << "\n\n"; }
private:
void addMsg() { std::string msg = "ROSETTACODE"; int stp = 9, p = rand() % stp; for( size_t x = 0; x < msg.length(); x++ ) { puzzle[p % WID][p / HEI].val = msg.at( x ); p += rand() % stp + 4; } } int getEmptySpaces() { int es = 0; for( int y = 0; y < HEI; y++ ) { for( int x = 0; x < WID; x++ ) { if( !puzzle[x][y].val ) es++; } } return es; } bool check( std::string word, int c, int r, int dc, int dr ) { for( size_t a = 0; a < word.length(); a++ ) { if( c < 0 || r < 0 || c >= WID || r >= HEI ) return false; if( puzzle[c][r].val && puzzle[c][r].val != word.at( a ) ) return false; c += dc; r += dr; } return true; } bool setWord( std::string word, int c, int r, int dc, int dr ) { if( !check( word, c, r, dc, dr ) ) return false; int sx = c, sy = r; for( size_t a = 0; a < word.length(); a++ ) { if( !puzzle[c][r].val ) puzzle[c][r].val = word.at( a ); else puzzle[c][r].cntOverlap++; c += dc; r += dr; } used.push_back( Word( word, sx, sy, c - dc, r - dr, dc, dr ) ); return true; } bool add2Puzzle( std::string word ) { int x = rand() % WID, y = rand() % HEI, z = rand() % 8; for( int d = z; d < z + 8; d++ ) { switch( d % 8 ) { case 0: if( setWord( word, x, y, 1, 0 ) ) return true; break; case 1: if( setWord( word, x, y, -1, -1 ) ) return true; break; case 2: if( setWord( word, x, y, 0, 1 ) ) return true; break; case 3: if( setWord( word, x, y, 1, -1 ) ) return true; break; case 4: if( setWord( word, x, y, -1, 0 ) ) return true; break; case 5: if( setWord( word, x, y, -1, 1 ) ) return true; break; case 6: if( setWord( word, x, y, 0, -1 ) ) return true; break; case 7: if( setWord( word, x, y, 1, 1 ) ) return true; break; } } return false; } void clearWord() { if( used.size() ) { Word lastW = used.back(); used.pop_back();
for( size_t a = 0; a < lastW.word.length(); a++ ) { if( puzzle[lastW.cols][lastW.rows].cntOverlap == 0 ) { puzzle[lastW.cols][lastW.rows].val = 0; } if( puzzle[lastW.cols][lastW.rows].cntOverlap > 0 ) { puzzle[lastW.cols][lastW.rows].cntOverlap--; } lastW.cols += lastW.dx; lastW.rows += lastW.dy; } } } void buildPuzzle() { addMsg(); int es = 0, cnt = 0; size_t idx = 0; do { for( std::vector<std::string>::iterator w = dictionary.begin(); w != dictionary.end(); w++ ) { if( std::find( used.begin(), used.end(), *w ) != used.end() ) continue; if( add2Puzzle( *w ) ) { es = getEmptySpaces(); if( !es && used.size() >= MIN_WORD_CNT ) return; } } clearWord(); std::random_shuffle( dictionary.begin(), dictionary.end() );
} while( ++cnt < 100 ); } std::vector<Word> used; std::vector<std::string> dictionary; Cell puzzle[WID][HEI];
}; int main( int argc, char* argv[] ) {
unsigned s = unsigned( time( 0 ) ); srand( s ); words w; w.create( std::string( "unixdict.txt" ) ); w.printOut(); return 0;
} </lang>
- Output:
0 1 2 3 4 5 6 7 8 9 0 d b R f t a u n p w 1 O i l o b h a m a o 2 S r e e r p E t r h 3 e c o r a T l i e T 4 f a m e w A e n t s 5 l n C h u y p g o l 6 o n p t O n s e o D 7 w e u b e f i a c b 8 E i n e m a d a m e 9 e s s k a p l a n e thereof (3, 6) (3, 0) seen (2, 9) (5, 6) pareto (8, 0) (8, 5) wolf (0, 7) (0, 4) crib (1, 3) (1, 0) tinge (7, 2) (7, 6) sienna (1, 9) (1, 4) war (4, 4) (4, 2) dispel (6, 8) (6, 3) kaplan (3, 9) (8, 9) tau (4, 0) (6, 0) lob (2, 1) (4, 1) how (9, 2) (9, 0) same (6, 6) (9, 9) men (4, 8) (2, 8) feb (5, 7) (3, 7) ham (5, 1) (7, 1) moe (2, 4) (2, 2) pan (5, 2) (7, 0) yuh (5, 5) (3, 5) pun (2, 6) (2, 8) load (9, 5) (6, 8) can (1, 3) (1, 5) madame (4, 8) (9, 8) gob (7, 5) (9, 7) rib (1, 2) (1, 0) nee (5, 6) (3, 8) set (9, 4) (7, 2) alp (7, 9) (5, 9) wolfe (0, 7) (0, 3) the (3, 6) (3, 4) low (0, 5) (0, 7) tea (3, 6) (5, 8) era (8, 3) (8, 1) nne (1, 5) (1, 7) amen (5, 8) (2, 8) coot (8, 7) (8, 4) anne (1, 4) (1, 7) reid (3, 3) (0, 0) sse (2, 9) (0, 9)
C#
<lang csharp>using System; using System.Collections.Generic; using System.Linq; using System.Text.RegularExpressions;
namespace Wordseach {
static class Program { readonly static int[,] dirs = {{1, 0}, {0, 1}, {1, 1}, {1, -1}, {-1, 0}, {0, -1}, {-1, -1}, {-1, 1}};
class Grid { public char[,] Cells = new char[nRows, nCols]; public List<string> Solutions = new List<string>(); public int NumAttempts; }
readonly static int nRows = 10; readonly static int nCols = 10; readonly static int gridSize = nRows * nCols; readonly static int minWords = 25;
readonly static Random rand = new Random();
static void Main(string[] args) { PrintResult(CreateWordSearch(ReadWords("unixdict.txt"))); }
private static List<string> ReadWords(string filename) { int maxLen = Math.Max(nRows, nCols);
return System.IO.File.ReadAllLines(filename) .Select(s => s.Trim().ToLower()) .Where(s => Regex.IsMatch(s, "^[a-z]{3," + maxLen + "}$")) .ToList(); }
private static Grid CreateWordSearch(List<string> words) { int numAttempts = 0;
while (++numAttempts < 100) { words.Shuffle();
var grid = new Grid(); int messageLen = PlaceMessage(grid, "Rosetta Code"); int target = gridSize - messageLen;
int cellsFilled = 0; foreach (var word in words) { cellsFilled += TryPlaceWord(grid, word); if (cellsFilled == target) { if (grid.Solutions.Count >= minWords) { grid.NumAttempts = numAttempts; return grid; } else break; // grid is full but we didn't pack enough words, start over } } } return null; }
private static int TryPlaceWord(Grid grid, string word) { int randDir = rand.Next(dirs.GetLength(0)); int randPos = rand.Next(gridSize);
for (int dir = 0; dir < dirs.GetLength(0); dir++) { dir = (dir + randDir) % dirs.GetLength(0);
for (int pos = 0; pos < gridSize; pos++) { pos = (pos + randPos) % gridSize;
int lettersPlaced = TryLocation(grid, word, dir, pos); if (lettersPlaced > 0) return lettersPlaced; } } return 0; }
private static int TryLocation(Grid grid, string word, int dir, int pos) { int r = pos / nCols; int c = pos % nCols; int len = word.Length;
// check bounds if ((dirs[dir, 0] == 1 && (len + c) > nCols) || (dirs[dir, 0] == -1 && (len - 1) > c) || (dirs[dir, 1] == 1 && (len + r) > nRows) || (dirs[dir, 1] == -1 && (len - 1) > r)) return 0;
int rr, cc, i, overlaps = 0;
// check cells for (i = 0, rr = r, cc = c; i < len; i++) { if (grid.Cells[rr, cc] != 0 && grid.Cells[rr, cc] != word[i]) { return 0; }
cc += dirs[dir, 0]; rr += dirs[dir, 1]; }
// place for (i = 0, rr = r, cc = c; i < len; i++) { if (grid.Cells[rr, cc] == word[i]) overlaps++; else grid.Cells[rr, cc] = word[i];
if (i < len - 1) { cc += dirs[dir, 0]; rr += dirs[dir, 1]; } }
int lettersPlaced = len - overlaps; if (lettersPlaced > 0) { grid.Solutions.Add($"{word,-10} ({c},{r})({cc},{rr})"); }
return lettersPlaced; }
private static int PlaceMessage(Grid grid, string msg) { msg = Regex.Replace(msg.ToUpper(), "[^A-Z]", "");
int messageLen = msg.Length; if (messageLen > 0 && messageLen < gridSize) { int gapSize = gridSize / messageLen;
for (int i = 0; i < messageLen; i++) { int pos = i * gapSize + rand.Next(gapSize); grid.Cells[pos / nCols, pos % nCols] = msg[i]; } return messageLen; } return 0; }
public static void Shuffle<T>(this IList<T> list) { int n = list.Count; while (n > 1) { n--; int k = rand.Next(n + 1); T value = list[k]; list[k] = list[n]; list[n] = value; } }
private static void PrintResult(Grid grid) { if (grid == null || grid.NumAttempts == 0) { Console.WriteLine("No grid to display"); return; } int size = grid.Solutions.Count;
Console.WriteLine("Attempts: " + grid.NumAttempts); Console.WriteLine("Number of words: " + size);
Console.WriteLine("\n 0 1 2 3 4 5 6 7 8 9"); Console.Write(""); for (int r = 0; r < nRows; r++) { Console.Write("\n{0} ", r); for (int c = 0; c < nCols; c++) Console.Write(" {0} ", grid.Cells[r, c]); }
Console.WriteLine("\n");
for (int i = 0; i < size - 1; i += 2) { Console.WriteLine("{0} {1}", grid.Solutions[i], grid.Solutions[i + 1]); } if (size % 2 == 1) Console.WriteLine(grid.Solutions[size - 1]);
Console.ReadLine(); } }
}</lang>
Attempts: 1 Number of words: 28 0 1 2 3 4 5 6 7 8 9 0 i m n e p o R p i d 1 s u r O e l d n i b 2 n e S b a n d y a E 3 a s d i t h y t T b 4 m u a r n s a u d r 5 s m h T o s o i h o 6 d A c r t C p c r t 7 a y p e p a n O c h 8 e o D o r u x g s a 9 l b E w l a k n o h rapid (4,8)(8,4) bindle (9,1)(4,1) bandy (3,2)(7,2) leadsman (0,9)(0,2) accost (9,8)(4,3) museum (1,5)(1,0) taste (7,3)(3,7) broth (9,3)(9,7) rosy (3,6)(6,3) honk (9,9)(6,9) chad (2,6)(2,3) lunch (4,9)(8,5) open (5,0)(2,0) gsa (7,8)(9,8) dip (9,0)(7,0) ansi (0,3)(0,0) pol (2,7)(0,9) boy (1,9)(1,7) woe (3,9)(3,7) tax (4,6)(6,8) rib (3,4)(3,2) not (4,4)(4,6) hair (5,3)(8,6) bat (9,1)(7,3) nyu (5,2)(7,4) ape (5,7)(3,7) era (3,7)(5,9) ere (1,2)(3,0)
J
Implementation:
<lang J>require'web/gethttp'
unixdict=:verb define
if. _1 -: fread 'unixdict.txt' do. (gethttp 'http://www.puzzlers.org/pub/wordlists/unixdict.txt') fwrite 'unixdict.txt' end. fread 'unixdict.txt'
)
words=:verb define
(#~ 1 - 0&e.@e.&'abcdefghijklmnopqrstuvwxyz'@>) (#~ [: (2&< * 10&>:) #@>) <;._2 unixdict
)
dirs=: 10#.0 0-.~>,{,~<i:1 lims=: _10+,"2 +/&>/"1 (0~:i:4)#>,{,~<<"1]1 10 1 +i."0]10*i:_1 dnms=: ;:'nw north ne west east sw south se'
genpuz=:verb define
words=. words fill=. 'ROSETTACODE' grid=. ,10 10$' ' inds=. ,i.10 10 patience=. -:#words key=. i.0 0 inuse=. i.0 2 while. (26>#key)+.0<cap=. (+/' '=grid)-#fill do. word=. >({~ ?@#) words dir=. ?@#dirs offs=. (inds#~(#word)<:inds{dir{lims)+/(i.#word)*/dir{dirs cool=. ' '=offs{grid sel=. */"1 cool+.(offs{grid)="1 word offs=. (sel*cap>:+/"1 cool)#offs if. (#offs) do. off=. ({~ ?@#) offs loc=. ({.off),dir if. -. loc e. inuse do. inuse=. inuse,loc grid=. word off} grid patience=. patience+1 key=. /:~ key,' ',(10{.word),(3":1+10 10#:{.off),' ',dir{::dnms end. else. NB. grr... if. 0 > patience=. patience-1 do. inuse=.i.0 2 key=.i.0 0 grid=. ,10 10$' ' patience=. -:#words end. end. end. puz=. (_23{.":i.10),' ',1j1#"1(":i.10 1),.' ',.10 10$fill (I.grid=' ')} grid puz,' ',1 1}._1 _1}.":((</.~ <.) i.@# * 3%#)key
)</lang>
Notes:
While the result is square, we flatten our intermediate results to simplify the code.
dirs
are index offsets within the flattened grid for each of the eight cardinal directions.
lims
is, for each cardinal direction, and for each grid position, how long of a word can fit.
dnms
are names for each of the cardinal directions.
words
are the viable words from unixdict, and fill
is what we're going to leave in the puzzle for spaces not occupied by any of those words (and this could be made into a parameter).
grid
is our working copy of the text of the word search puzzle.
inds
are the indices into grid - we will use these as the starting positions when we place the words.
patience
is a guard variable, to avoid problems with infinite loops if we arbitrarily place words in a non-viable fashion.
key
lists the words we are placing, and where we placed them.
inuse
marks location+directions which already have a word (to prevent short words such as sal from being placed as prefixes of longer words such as sale).
Once we have these, we go into a loop where:
word
is picked arbitrarily from the viable words from unixdict.
dir
is picked arbitrarily from one of our eight cardinal directions.
offs
are places where we might place the word (initially limited only by geometry, but we then constrain this based on what's already been placed).
cool
marks where our word can be placed in unoccupied spaces (and also will be used later to count how many new spaces will be occupied by the word we pick.
sel
marks where our word can be placed such that it does not conflict with existing words.
If this leaves us with any way to place the word, we pick one of them as off
and combine the starting location with dir in loc
to see if a word has already been placed there and if we're good, we place the word and update our key. (It's extremely rare that loc matches an inuse location, so just ignoring that word works just fine).
Otherwise, we check if we're getting impatient (in which case we scrap the entire thing and start over).
Once we're done, we reshape our grid so it's square and attach the key. Here, puz
is the grid formatted for display (with a space between each column, and a numeric key for each row and column).
Example run:
<lang J> genpuz
0 1 2 3 4 5 6 7 8 9
0 y R p y r f O a p S 1 l o l s i f c c e a 2 l n v z i e n r n l 3 o p z s t e E i n l 4 h l s a v e r d a o 5 e a t a g r e e d y 6 m e m a g T f T A C 7 a y e r s p f z a p 8 O e c n a w o l l a 9 e s o p o r p c D E
acetate 1 8 sw │ gam 7 5 west │ pol 1 3 sw acrid 1 8 south│ holly 5 1 north│ propose 10 7 west agreed 6 4 east │ massif 7 1 ne │ rsvp 1 5 sw allowance 9 10 west │ neva 3 7 sw │ sao 8 5 south alloy 2 10 south│ offer 9 7 north│ save 5 3 east arm 9 5 nw │ only 4 1 ne │ sop 10 2 east ayers 8 1 east │ pap 10 4 ne │ tee 4 5 se cop 10 8 nw │ paz 8 10 west │ wan 9 6 west fizzle 1 6 sw │ penna 1 9 south│
</lang>
Java
<lang java>import java.io.*; import static java.lang.String.format; import java.util.*;
public class WordSearch {
static class Grid { int numAttempts; char[][] cells = new char[nRows][nCols]; List<String> solutions = new ArrayList<>(); }
final static int[][] dirs = {{1, 0}, {0, 1}, {1, 1}, {1, -1}, {-1, 0}, {0, -1}, {-1, -1}, {-1, 1}};
final static int nRows = 10; final static int nCols = 10; final static int gridSize = nRows * nCols; final static int minWords = 25;
final static Random rand = new Random();
public static void main(String[] args) { printResult(createWordSearch(readWords("unixdict.txt"))); }
static List<String> readWords(String filename) { int maxLen = Math.max(nRows, nCols);
List<String> words = new ArrayList<>(); try (Scanner sc = new Scanner(new FileReader(filename))) { while (sc.hasNext()) { String s = sc.next().trim().toLowerCase(); if (s.matches("^[a-z]{3," + maxLen + "}$")) words.add(s); } } catch (FileNotFoundException e) { System.out.println(e); } return words; }
static Grid createWordSearch(List<String> words) { Grid grid = null; int numAttempts = 0;
outer: while (++numAttempts < 100) { Collections.shuffle(words);
grid = new Grid(); int messageLen = placeMessage(grid, "Rosetta Code"); int target = gridSize - messageLen;
int cellsFilled = 0; for (String word : words) { cellsFilled += tryPlaceWord(grid, word); if (cellsFilled == target) { if (grid.solutions.size() >= minWords) { grid.numAttempts = numAttempts; break outer; } else break; // grid is full but we didn't pack enough words, start over } } }
return grid; }
static int placeMessage(Grid grid, String msg) { msg = msg.toUpperCase().replaceAll("[^A-Z]", "");
int messageLen = msg.length(); if (messageLen > 0 && messageLen < gridSize) { int gapSize = gridSize / messageLen;
for (int i = 0; i < messageLen; i++) { int pos = i * gapSize + rand.nextInt(gapSize); grid.cells[pos / nCols][pos % nCols] = msg.charAt(i); } return messageLen; } return 0; }
static int tryPlaceWord(Grid grid, String word) { int randDir = rand.nextInt(dirs.length); int randPos = rand.nextInt(gridSize);
for (int dir = 0; dir < dirs.length; dir++) { dir = (dir + randDir) % dirs.length;
for (int pos = 0; pos < gridSize; pos++) { pos = (pos + randPos) % gridSize;
int lettersPlaced = tryLocation(grid, word, dir, pos); if (lettersPlaced > 0) return lettersPlaced; } } return 0; }
static int tryLocation(Grid grid, String word, int dir, int pos) {
int r = pos / nCols; int c = pos % nCols; int len = word.length();
// check bounds if ((dirs[dir][0] == 1 && (len + c) > nCols) || (dirs[dir][0] == -1 && (len - 1) > c) || (dirs[dir][1] == 1 && (len + r) > nRows) || (dirs[dir][1] == -1 && (len - 1) > r)) return 0;
int rr, cc, i, overlaps = 0;
// check cells for (i = 0, rr = r, cc = c; i < len; i++) { if (grid.cells[rr][cc] != 0 && grid.cells[rr][cc] != word.charAt(i)) return 0; cc += dirs[dir][0]; rr += dirs[dir][1]; }
// place for (i = 0, rr = r, cc = c; i < len; i++) { if (grid.cells[rr][cc] == word.charAt(i)) overlaps++; else grid.cells[rr][cc] = word.charAt(i);
if (i < len - 1) { cc += dirs[dir][0]; rr += dirs[dir][1]; } }
int lettersPlaced = len - overlaps; if (lettersPlaced > 0) { grid.solutions.add(format("%-10s (%d,%d)(%d,%d)", word, c, r, cc, rr)); }
return lettersPlaced; }
static void printResult(Grid grid) { if (grid == null || grid.numAttempts == 0) { System.out.println("No grid to display"); return; } int size = grid.solutions.size();
System.out.println("Attempts: " + grid.numAttempts); System.out.println("Number of words: " + size);
System.out.println("\n 0 1 2 3 4 5 6 7 8 9"); System.out.print(""); for (int r = 0; r < nRows; r++) { System.out.printf("%n%d ", r); for (int c = 0; c < nCols; c++) System.out.printf(" %c ", grid.cells[r][c]); }
System.out.println("\n");
for (int i = 0; i < size - 1; i += 2) { System.out.printf("%s %s%n", grid.solutions.get(i), grid.solutions.get(i + 1)); } if (size % 2 == 1) System.out.println(grid.solutions.get(size - 1)); }
}</lang>
Attempts: 2 Number of words: 27 0 1 2 3 4 5 6 7 8 9 0 R p d i o r o t r a 1 O a o e s b l o c S 2 m s t l f e t l a y 3 E t e i y o t s T i 4 e y l b t g r s p l 5 r l T i A h o e e l 6 o e l h t j c n s C 7 z l o u a a O t a t 8 u k r g c n D z i l 9 o t r a v e l E v w rototill (8,0)(1,7) polygonal (1,0)(9,8) fill (4,2)(1,5) goer (3,8)(0,5) travel (1,9)(6,9) deforest (2,0)(9,7) toroid (7,0)(2,0) truth (1,9)(5,5) estes (8,5)(4,1) ipecac (9,3)(4,8) ouzo (0,9)(0,6) pasty (1,0)(1,4) dote (2,0)(2,3) lay (7,2)(9,2) witch (9,9)(5,5) han (3,6)(5,8) bloc (5,1)(8,1) ill (9,3)(9,5) slot (7,3)(7,0) art (9,0)(7,0) ore (0,6)(0,4) bye (3,4)(5,2) elk (1,6)(1,8) jan (5,6)(5,8) liz (9,8)(7,8) dam (2,0)(0,2) via (8,9)(8,7)
Phix
<lang Phix>-- -- demo\rosetta\wordsearch.exw -- =========================== -- string message = "ROSETTACODE" sequence words, solution="", placed
constant grid = split(""" X 0 1 2 3 4 5 6 7 8 9 X 0 X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 X 9 X X X X X X X X X X X X X""",'\n')
constant DX = {-1, 0,+1,+1,+1, 0,-1,-1},
DY = {-3,-3,-3, 0,+3,+3,+3, 0}
procedure wordsearch(sequence grid, integer rqd, integer left, sequence done)
sequence rw = shuffle(tagset(length(words))), rd = shuffle(tagset(8)), rs = shuffle(tagset(100)) for i=1 to length(rs) do integer sx = floor((rs[i]-1)/10)+2, sy = remainder(rs[i]-1,10)*3+4 for w=1 to length(rw) do string word = words[rw[w]] if not find(word,done[1]) then for d=1 to length(rd) do integer {dx,dy} = {DX[rd[d]],DY[rd[d]]}, {nx,ny} = {sx,sy}, chcount = length(word) sequence newgrid = grid for c=1 to length(word) do integer ch = grid[nx][ny] if ch!=' ' then if ch!=word[c] then chcount = -1 exit end if chcount -= 1 end if newgrid[nx][ny] = word[c] nx += dx ny += dy end for if chcount!=-1 then sequence posinfo = {sx-2,(sy-4)/3,nx-dx-2,(ny-dy-4)/3}, newdone = {append(done[1],word),append(done[2],posinfo)} if rqd<=1 and left-chcount=length(message) then {solution, placed} = {newgrid, newdone} return elsif left-chcount>length(message) then wordsearch(newgrid,rqd-1,left-chcount,newdone) if length(solution) then return end if end if end if end for end if end for end for
end procedure
function valid_word(string word)
if length(word)<3 then return false end if for i=1 to length(word) do integer ch = word[i] if ch<'a' or ch>'z' then return false end if end for return true
end function
integer fn = open("..\\unixdict.txt","r") words = get_text(fn,GT_LF_STRIPPED) close(fn) for i=length(words) to 1 by -1 do
if not valid_word(words[i]) then words[i] = words[$] words = words[1..$-1] end if
end for printf(1,"%d words loaded\n",length(words))
wordsearch(grid,25,100,{{},{}}) for x=2 to 11 do
for y=4 to 31 by 3 do if solution[x][y]=' ' then solution[x][y] = message[1] message = message[2..$] end if end for
end for if length(message) then ?9/0 end if puts(1,substitute(join(solution,'\n'),"X"," ")) printf(1,"\n%d words\n",length(placed[1])) for i=1 to length(placed[1]) do
printf(1,"%10s %10s ",{placed[1][i],sprint(placed[2][i])}) if mod(i,3)=0 then puts(1,"\n") end if
end for</lang>
- Output:
24822 words loaded 0 1 2 3 4 5 6 7 8 9 0 R y g e r m a n y O 1 d r a g a v e S o E 2 c a t n w e w T l T 3 r t s e p h a o k A 4 a u e v p e d t k C 5 g l c a o l k O a e 6 n a t r h l c h o u 7 a s m p a c a d i a 8 v n r a d s j o i l 9 D y i p i E s a s h 42 words salutary {7,1,0,1} idaho {9,4,5,4} jackdaw {8,6,2,6} darn {8,4,8,1} avenge {5,3,0,3} van {8,0,6,0} war {2,4,0,4} crag {2,0,5,0} drag {1,0,1,3} gam {5,0,7,2} stag {3,2,0,2} crass {5,2,9,6} apr {8,3,6,3} staph {7,1,3,5} germany {0,2,0,8} laos {6,5,9,8} chou {6,6,6,9} hell {3,5,6,5} wee {2,4,4,2} acadia {7,4,7,9} yolk {0,8,3,8} pap {7,3,9,3} pry {7,3,9,1} usn {4,1,2,3} agave {1,2,1,6} nat {6,0,6,2} pee {3,4,1,6} sash {9,6,9,9} eel {3,3,5,1} hid {9,9,7,7} yip {9,1,9,3} wok {2,6,4,8} raw {0,4,2,4} rave {6,3,3,3} oak {6,8,4,8} oil {8,7,8,9} lao {6,5,8,7} pest {3,4,3,1} doe {7,7,5,9} pet {4,4,2,2} arc {4,0,2,0} tau {4,7,6,9}
zkl
Repeat words allowed. Rather brute force as I didn't realize that the message has to fit exactly. <lang zkl>fcn buildVectors(R,C){ //-->up to 8 vectors of wild card strings
var [const] dirs=T(T(1,0), T(0,1), T(1,1), T(1,-1), T(-1,0),T(0,-1), T(-1,-1), T(-1,1)); vs,v:=List(),List(); foreach dr,dc in (dirs){ v.clear(); r,c:=R,C; while( (0<=r<10) and (0<=c<10) ){ v.append(grid[r][c]); r+=dr; c+=dc; } vs.append(T(v.concat(), // eg "???e??????" would match "cohen" or "mineral" dr,dc)); } vs.filter(fcn(v){ v[0].len()>2 }).shuffle()
} fcn findFit(vs,words){ //-->(n, word) ie (nth vector,word), empty vs not seen
do(1000){ foreach n,v in (vs.enumerate()){ do(10){ // lots of ties word:=words[(0).random(nwds)]; if(word.matches(v[0][0,word.len()])) return(word,n); // "??" !match "abc" }}} False
} fcn pasteWord(r,c, dr,dc, word) // jam word into grid along vector
{ foreach char in (word){ grid[r][c]=char; r+=dr; c+=dc; } }
fcn printGrid{
println("\n 0 1 2 3 4 5 6 7 8 9"); foreach n,line in (grid.enumerate()){ println(n," ",line.concat(" ")) }
} fcn stuff(msg){ MSG:=msg.toUpper() : Utils.Helpers.cycle(_);
foreach r,c in (10,10){ if(grid[r][c]=="?") grid[r][c]=MSG.next() } MSG._n==msg.len() // use all of, not more, not less, of msg?
}</lang> <lang zkl>msg:="RosettaCode";
validWord:=RegExp("[A-Za-z]+\n$").matches; File("unixdict.txt").read(*) // dictionary file to blob, copied from web
// blob to list of valid words .filter('wrap(w){ (3<w.len()<=10) and validWord(w) }) // "word\n" .howza(11).pump(List,"toLower") // convert blob to list of words, removing \n : words:=(_);
reg fitted; do{
var nwds=words.len(), grid=(10).pump(List(),(10).pump(List(),"?".copy).copy); fitted=List(); do(100){ r,c:=(0).random(10), (0).random(10); if(grid[r][c]=="?"){
vs,wn:=buildVectors(r,c), findFit(vs,words); if(wn){ w,n:=wn; pasteWord(r,c,vs[n][1,*].xplode(),w); fitted.append(T(r,c,w)); }
}} print(".");
}while(fitted.len()<25 or not stuff(msg));
printGrid(); println(fitted.len()," words fitted"); fitted.pump(Console.println, T(Void.Read,3,False),
fcn{ vm.arglist.pump(String, fcn([(r,c,w)]){ "%-19s".fmt("[%d,%d]: %s ".fmt(r,c,w)) }) }
); fitted.apply(fcn(w){ w[2].len() }).sum(0).println();</lang>
- Output:
.................................. 0 1 2 3 4 5 6 7 8 9 0 s t b n i b s d R O 1 k y s u p i d a g w 2 i S a a r n E f a a 3 s T d w o n k l b m 4 u T s e t b c o h u 5 m e d e y A e p c p 6 y r e l x e b g a C 7 h o a g d i l l o n 8 t c f p O g u n r D 9 k b o l s h o i b E 26 words fitted [6,5]: eyed [7,4]: dillon [9,1]: bolshoi [6,1]: rap [9,8]: broach [4,6]: claw [0,2]: burn [3,3]: way [8,5]: gun [2,7]: fad [6,7]: gpo [6,6]: beck [8,0]: thymus [4,5]: boast [1,6]: dip [2,5]: nib [3,8]: bag [4,2]: sex [8,1]: core [0,3]: nibs [7,3]: gee [5,2]: deaf [4,4]: twa [5,9]: puma [0,0]: ski [6,3]: lack 102