Word search: Difference between revisions
(J draft) |
(J: somewhat document and clean up the code) |
||
Line 68: | Line 68: | ||
fill=. 'ROSETTACODE' |
fill=. 'ROSETTACODE' |
||
grid=. ,10 10$' ' |
grid=. ,10 10$' ' |
||
test=. ,<:_30 _30{.20 20 {.>:i.10 10 |
|||
inds=. ,i.10 10 |
inds=. ,i.10 10 |
||
patience=. |
patience=. 40 |
||
key=. i.0 0 |
key=. i.0 0 |
||
while. 0<cap=. (+/' '=grid)-#fill do. |
while. 0<cap=. (+/' '=grid)-#fill do. |
||
Line 88: | Line 87: | ||
key=.i.0 0 |
key=.i.0 0 |
||
grid=. ,10 10$' ' |
grid=. ,10 10$' ' |
||
patience=. |
patience=. 40 |
||
end. |
end. |
||
end. |
end. |
||
Line 94: | Line 93: | ||
(10 10$fill (I.grid=' ')} grid),' ',/:~key |
(10 10$fill (I.grid=' ')} grid),' ',/:~key |
||
)</lang> |
)</lang> |
||
Notes: |
|||
While the result is square, we flatten our intermediate results to simplify the code. |
|||
<code>dirs</code> are index offsets within the flattened grid for each of the eight cardinal directions. |
|||
<code>lims</code> is, for each cardinal direction, and for each grid position, how long of a word can fit. |
|||
<code>dnms</code> are names for each of the cardinal directions. |
|||
<code>words</codes> are the viable words from unixdict, and <code>fill</code> 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). |
|||
<code>grid</code> is our working copy of the text of the word search puzzle. |
|||
<code>inds</code> are the indices into grid - we will use these as the starting positions when we place the words. |
|||
<code>patience</code> is a guard variable, to avoid problems with infinite loops if we arbitrarily place words in a non-viable fashion. |
|||
<code>key</code> lists the words we are placing, and where we placed them. |
|||
Once we have these, we go into a loop where: |
|||
<code>word</code> is picked arbitrarily from the viable words from unixdict. |
|||
<code>dir</code> is picked arbitrarily from one of our eight cardinal directions. |
|||
<code>offs</code> 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). |
|||
<code>cool</code> 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. |
|||
<code>sel</code> 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 place it, update the key and continue. |
|||
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. |
|||
Example run: |
Example run: |
||
<lang J> genpuz'' |
<lang J> genpuz'' |
||
eiRharobed |
|||
gOraSejoan |
|||
omeotdrEsc |
|||
lleoniTcbu |
|||
fTpyfhoApr |
|||
lsCielmayd |
|||
eOcDdrinot |
|||
pelacisumE |
|||
macdougall |
|||
ioceanllum |
|||
curd 3 10 south |
|||
deborah 1 10 west |
|||
flea 5 1 ne |
|||
hide 5 6 north |
|||
impel 10 1 north |
|||
iron 1 2 se |
|||
joan 2 7 east |
|||
loge 4 1 north |
|||
macdougall 9 1 east |
|||
meyers 3 2 se |
|||
mull 10 10 west |
|||
musicale 8 9 west |
|||
ocean 10 2 east |
|||
orifice 2 8 sw |
|||
pbs 5 9 north |
|||
scold 3 9 sw |
|||
spot 6 2 ne |
|||
toni 7 10 west |
|||
yam 6 9 west </lang> |
|||
=={{header|Java}}== |
=={{header|Java}}== |
Revision as of 04:08, 26 March 2016
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 are not allowed to zigzag, or wrap around. They may overlap but not be completely embedded in another word.
The 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.
Print the resulting grid and the solutions.
For instance:
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)
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=. 40 key=. i.0 0 while. 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 grid=. word off} grid patience=. patience+1 key=. key,(10{.word),(3":1+10 10#:{.off),' ',dir{::dnms else. NB. grr... if. 0 > patience=. patience-1 do. key=.i.0 0 grid=. ,10 10$' ' patience=. 40 end. end. end. (10 10$fill (I.grid=' ')} grid),' ',/:~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</codes> 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.
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 place it, update the key and continue.
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.
Example run:
<lang J> genpuz
eiRharobed
gOraSejoan
omeotdrEsc
lleoniTcbu
fTpyfhoApr
lsCielmayd
eOcDdrinot
pelacisumE
macdougall
ioceanllum
curd 3 10 south
deborah 1 10 west
flea 5 1 ne
hide 5 6 north
impel 10 1 north
iron 1 2 se
joan 2 7 east
loge 4 1 north
macdougall 9 1 east
meyers 3 2 se
mull 10 10 west
musicale 8 9 west
ocean 10 2 east
orifice 2 8 sw
pbs 5 9 north
scold 3 9 sw
spot 6 2 ne
toni 7 10 west
yam 6 9 west </lang>
Java
<lang java>import java.io.*;
import static java.lang.String.format;
import java.util.*;
public class WordSearch {
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 Random rand = new Random();
static List<char[]> words = new ArrayList<>();
static char[][] grid;
static List<String> solutions;
public static void main(String[] args) {
readWords("unixdict.txt");
createWordSearch();
printResult();
}
static void readWords(String filename) {
try (Scanner sc = new Scanner(new FileReader(filename))) {
while (sc.hasNext()) {
String s = sc.next().trim().toLowerCase();
if (s.matches("^[a-z]{3,}$"))
words.add(s.toCharArray());
}
} catch (FileNotFoundException e) {
System.out.println(e);
}
}
static int placeMessage(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[pos / nCols][pos % nCols] = msg.charAt(i);
}
}
return messageLen;
}
static void createWordSearch() {
int numAttempts = 0;
outer:
while (++numAttempts < 100) {
Collections.shuffle(words);
grid = new char[nRows][nCols];
solutions = new ArrayList<>();
int messageLen = placeMessage("Rosetta Code");
int numCellsToFill = gridSize - messageLen;
int cellsFilled = 0;
for (char[] word : words) {
cellsFilled += tryPlaceWord(word);
if (cellsFilled == numCellsToFill) {
break outer;
}
}
}
System.out.println("Attempts: " + numAttempts);
}
static int tryPlaceWord(char[] 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(word, dir, pos);
if (lettersPlaced > 0)
return lettersPlaced;
}
}
return 0;
}
static int tryLocation(char[] 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[rr][cc] != 0 && grid[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[rr][cc] == word[i])
overlaps++;
else
grid[rr][cc] = word[i];
if (i < len - 1) {
cc += dirs[dir][0];
rr += dirs[dir][1];
}
}
int lettersPlaced = len - overlaps;
if (lettersPlaced > 0) {
String w = new String(word);
solutions.add(format("%-10s (%d,%d)(%d,%d)", w, c, r, cc, rr));
}
return lettersPlaced;
}
static void printResult() {
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[r][c]);
}
System.out.println("\n");
int size = solutions.size();
for (int i = 0; i < size - 1; i += 2)
System.out.printf("%s %s%n", solutions.get(i), solutions.get(i + 1));
if (size % 2 == 1)
System.out.println(solutions.get(size - 1));
}
}</lang>
Attempts: 2
0 1 2 3 4 5 6 7 8 9
0 n r o t a t e R e p
1 e e s i o p O t v l
2 g a w t S t t E e a
3 a r a f r a s e r T
4 l i a s l s a h y c
5 l l T p u n c A m a
6 o a s b e r C h a p
7 c i u r o t c a n O
8 p r a p D a e e g a
9 b t a e e E b e i v
suburb (5,4)(0,9) fraser (3,3)(8,3)
collagen (0,7)(0,0) trial (1,9)(1,5)
everyman (8,0)(8,7) rotate (1,0)(6,0)
poise (5,1)(1,1) vie (9,9)(7,9)
actor (7,7)(3,7) porch (3,8)(7,4)
splat (2,6)(6,2) agee (9,8)(6,8)
arena (2,8)(6,4) sail (3,4)(0,4)
tail (3,2)(0,5) alp (9,2)(9,0)
cap (9,4)(9,6) each (4,9)(7,6)
rae (1,3)(1,1) ben (6,9)(8,7)
eat (3,9)(1,9) sat (5,4)(5,2)
twa (3,2)(1,2) platte (3,5)(8,0)
sip (2,6)(0,8)