Word search: Difference between revisions
Rename Perl 6 -> Raku, alphabetize, minor clean-up
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
|||
Line 45:
mph (8,8)(6,8)</pre>
<br><br>
=={{header|C sharp}}==
Line 499 ⟶ 289:
nyu (5,2)(7,4) ape (5,7)(3,7)
era (3,7)(5,9) ere (1,2)(3,0)
</pre>
=={{header|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>
{{out}}
<pre>
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)
</pre>
Line 1,291:
liz (9,8)(7,8) dam (2,0)(0,2)
via (8,9)(8,7)</pre>
=={{header|Julia}}==
Line 1,629 ⟶ 1,628:
act (2,0)(0,2)
</pre>
=={{header|Perl}}==
<lang perl>#!/usr/bin/perl
Line 1,757:
tum (0,1)->(2,3) yells (4,5)->(8,9)
</pre>
=={{header|Phix}}==
Line 2,061 ⟶ 1,897:
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}
</pre>
=={{header|Python}}==
{{trans|Java}}
{{works with|Python|3.x}}
<lang python>
import re
from random import shuffle, randint
dirs = [[1, 0], [0, 1], [1, 1], [1, -1], [-1, 0], [0, -1], [-1, -1], [-1, 1]]
n_rows = 10
n_cols = 10
grid_size = n_rows * n_cols
min_words = 25
class Grid:
def __init__(self):
self.num_attempts = 0
self.cells = [['' for _ in range(n_cols)] for _ in range(n_rows)]
self.solutions = []
def read_words(filename):
max_len = max(n_rows, n_cols)
words = []
with open(filename, "r") as file:
for line in file:
s = line.strip().lower()
if re.match(r'^[a-z]{3,' + re.escape(str(max_len)) + r'}$', s) is not None:
words.append(s)
return words
def place_message(grid, msg):
msg = re.sub(r'[^A-Z]', "", msg.upper())
message_len = len(msg)
if 0 < message_len < grid_size:
gap_size = grid_size // message_len
for i in range(0, message_len):
pos = i * gap_size + randint(0, gap_size)
grid.cells[pos // n_cols][pos % n_cols] = msg[i]
return message_len
return 0
def try_location(grid, word, direction, pos):
r = pos // n_cols
c = pos % n_cols
length = len(word)
# check bounds
if (dirs[direction][0] == 1 and (length + c) > n_cols) or \
(dirs[direction][0] == -1 and (length - 1) > c) or \
(dirs[direction][1] == 1 and (length + r) > n_rows) or \
(dirs[direction][1] == -1 and (length - 1) > r):
return 0
rr = r
cc = c
i = 0
overlaps = 0
# check cells
while i < length:
if grid.cells[rr][cc] != '' and grid.cells[rr][cc] != word[i]:
return 0
cc += dirs[direction][0]
rr += dirs[direction][1]
i += 1
rr = r
cc = c
i = 0
# place
while i < length:
if grid.cells[rr][cc] == word[i]:
overlaps += 1
else:
grid.cells[rr][cc] = word[i]
if i < length - 1:
cc += dirs[direction][0]
rr += dirs[direction][1]
i += 1
letters_placed = length - overlaps
if letters_placed > 0:
grid.solutions.append("{0:<10} ({1},{2})({3},{4})".format(word, c, r, cc, rr))
return letters_placed
def try_place_word(grid, word):
rand_dir = randint(0, len(dirs))
rand_pos = randint(0, grid_size)
for direction in range(0, len(dirs)):
direction = (direction + rand_dir) % len(dirs)
for pos in range(0, grid_size):
pos = (pos + rand_pos) % grid_size
letters_placed = try_location(grid, word, direction, pos)
if letters_placed > 0:
return letters_placed
return 0
def create_word_search(words):
grid = None
num_attempts = 0
while num_attempts < 100:
num_attempts += 1
shuffle(words)
grid = Grid()
message_len = place_message(grid, "Rosetta Code")
target = grid_size - message_len
cells_filled = 0
for word in words:
cells_filled += try_place_word(grid, word)
if cells_filled == target:
if len(grid.solutions) >= min_words:
grid.num_attempts = num_attempts
return grid
else:
break # grid is full but we didn't pack enough words, start over
return grid
def print_result(grid):
if grid is None or grid.num_attempts == 0:
print("No grid to display")
return
size = len(grid.solutions)
print("Attempts: {0}".format(grid.num_attempts))
print("Number of words: {0}".format(size))
print("\n 0 1 2 3 4 5 6 7 8 9\n")
for r in range(0, n_rows):
print("{0} ".format(r), end='')
for c in range(0, n_cols):
print(" %c " % grid.cells[r][c], end='')
print()
print()
for i in range(0, size - 1, 2):
print("{0} {1}".format(grid.solutions[i], grid.solutions[i+1]))
if size % 2 == 1:
print(grid.solutions[size - 1])
if __name__ == "__main__":
print_result(create_word_search(read_words("unixdict.txt")))
</lang>
{{out}}
<pre>
Attempts: 1
Number of words: 25
0 1 2 3 4 5 6 7 8 9
0 f b R u e r u l t h
1 o n o t v O e r o p
2 a S a b a x o b E m
3 l e d s h w T p e u
4 w p v a n s u c k i
5 o T u r A t u t s r
6 n s o p u m y d i t
7 t h C j a c o b i O
8 t i r e h n i m D p
9 y n o l o c E s a c
exhaust (6,1)(0,7) hornwort (1,7)(8,0)
btu (3,2)(3,0) jacobi (3,7)(8,7)
foal (0,0)(0,3) triumph (9,6)(9,0)
inherit (6,8)(0,8) mecum (9,2)(5,6)
colony (5,9)(0,9) curve (5,7)(1,3)
wont (0,4)(0,7) lure (7,0)(4,0)
hob (9,0)(7,2) tidy (9,6)(6,6)
suck (5,4)(8,4) san (3,3)(1,1)
sac (7,9)(9,9) put (7,3)(5,5)
led (0,3)(2,3) stu (8,5)(6,5)
have (4,3)(4,0) min (7,8)(5,8)
bob (1,0)(3,2) pup (3,6)(1,4)
dip (7,6)(9,8)
</pre>
Line 2,685 ⟶ 2,723:
way (18,17 ←) wham (11,5 ↓) </pre>
=={{header|
(formerly Perl 6)
{{works with|Rakudo|2020.01}}
<lang perl6>my $rows = 10;
my $cols = 10;
my $message = q:to/END/;
.....R....
......O...
.......S..
........E.
T........T
.A........
..C.......
...O......
....D.....
my %dir =
'→' => (1,0),
'↘' => (1,1),
'↓' => (0,1),
'↙' => (-1,1),
'←' => (-1,0),
'↖' => (-1,-1),
'↑' => (0,-1),
'↗' => (1,-1)
;
my @ws = $message.comb(/<print>/);
my $path = './unixdict.txt'; # or wherever
my @words = $path.IO.slurp.words.grep( { $_ !~~ /<-[a..z]>/ and 2 < .chars < 11 } ).pick(*);
my %index;
my %used;
while @ws.first( * eq '.') {
# find an unfilled cell
my $i = @ws.grep( * eq '.', :k ).pick;
# translate the index to x / y coordinates
# find a word that fits
my $word = find($x, $y);
# Meh, reached an impasse, easier to just throw it all
# away and start over rather than trying to backtrack.
restart, next unless $word;
%used{"$word"}++;
# Keeps trying to place an already used word, choices
# must be limited, start over
restart, next if %used{$word} > 15;
# Already used this word, try again
next if %index{$word.key};
# Add word to used word index
%index ,= $word;
# place the word
place($x, $y, $word);
}
display();
sub display {
put flat " ", 'ABCDEFGHIJ'.comb;
.put for (^10).map: { ($_).fmt(" %2d"), @ws[$_ * $cols .. ($_ + 1) * $cols - 1] }
my $max = 1 + %index.keys.max( *.chars ).chars;
for %index.sort {
printf "%{$max}s %4s %s ", .key, .value.key, .value.value;
print "\n" if $++ % 2;
}
say "\n"
}
sub restart {
@ws = $message.comb(/<print>/);
%index = ();
%used = ();
}
sub place ($x is copy, $y is copy, $w) {
my $dir = %dir{$w.value.value};
@ws[$y * $rows + $x] = @word.shift;
while @word {
($x, $y) »+=« $dir;
@ws[$y * $rows + $x] = @word.shift;
}
}
sub find ($x, $y) {
my @trials = %dir.keys.map: -> $dir {
last if 0 > $r|$c;
my $l = @ws[$r * $rows + $c];
last if $l ~~ /<:Lu>/;
$space ~= $l;
}
next if $space.chars < 3;
[$space.trans( '.' => ' ' ),
("{'ABCDEFGHIJ'.comb[$x]} {$y}" => $dir)]
};
for @words.pick(*) -> $word {
for @trials -> $space {
next if $word.chars > $space[0].chars;
return ($word => $space[1]) if compare($space[0].comb, $word.comb)
}
}
sub compare (@s, @w) {
for ^@w {
next if @s[$_] eq
return False if @s[$_] ne @w[$_]
}
True
}</lang>
{{out|Sample output}}
<pre> A B C D E F G H I J
0 b y e e a R s w u k
1 r g e n p f O s e s
2 d i n l e i i S t i
3 r e b i l a c e E f
4 T g t a d a g n l T
5 d A a t d o w a i d
6 g i C n a n a l r c
7 a o g O p a l p r f
8 p g n p D d a i o a
9 c r u s h E s p t d
Words used:
aaa G 8 ↖ afield E 0 ↘
alley F 4 ↖ bye A 0 →
caliber G 3 ← crush A 9 →
dan F 8 ↑ dig A 5 ↘
epic D 0 ↘ fad J 7 ↓
fisk J 3 ↑ gap A 6 ↓
geigy B 4 ↑ get G 4 ↗
gnp B 8 → goa C 7 ←
lane H 6 ↑ law G 7 ↑
nag D 6 ↖ nne D 1 ↙
odin F 5 ↖ orr I 8 ↑
paddle E 7 ↑ picnic E 1 ↘
pip H 9 ↑ rib A 1 ↘
sir G
tail D 5 ↑ ted C 4 ↖
tor I
wei H 0 ↘
=={{header|Visual Basic .NET}}==
Line 3,227 ⟶ 3,144:
cilia (0,0)(4,4) sims (9,9)(6,9)
marsha (7,9)(7,4)</pre>
=={{header|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>
{{out}}
<pre>
..................................
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
</pre>
| |||