Word search: Difference between revisions
(→{{headerJava}}: added Java) |
(J draft) |
||
Line 42: | Line 42: | ||
mph (8,8)(6,8)</pre> |
mph (8,8)(6,8)</pre> |
||
=={{header|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$' ' |
|||
test=. ,<:_30 _30{.20 20 {.>:i.10 10 |
|||
inds=. ,i.10 10 |
|||
patience=. 10 |
|||
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=. 20 |
|||
end. |
|||
end. |
|||
end. |
|||
(10 10$fill (I.grid=' ')} grid),' ',/:~key |
|||
)</lang> |
|||
Example run: |
|||
<lang J> genpuz'' |
|||
etwarpesmR |
|||
feoOakplsS |
|||
anEtoaanim |
|||
hTrpixTuva |
|||
cownkuAhac |
|||
loCOaaqstk |
|||
cmiamifsae |
|||
biggsDdroy |
|||
neetxisaim |
|||
Epalettenm |
|||
atavism 7 9 north |
|||
biggs 8 1 east |
|||
chafe 5 1 north |
|||
cowpoke 7 1 ne |
|||
lax 2 8 sw |
|||
mackey 3 10 south |
|||
miami 7 2 east |
|||
mirfak 10 10 nw |
|||
mosquito 9 10 nw |
|||
nadia 10 9 nw |
|||
net 3 2 north |
|||
palette 10 2 east |
|||
patrol 1 6 sw |
|||
shun 6 8 north |
|||
sixteen 9 7 west |
|||
spain 1 8 sw |
|||
warp 1 3 east </lang> |
|||
=={{header|Java}}== |
=={{header|Java}}== |
Revision as of 03:50, 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$' ' test=. ,<:_30 _30{.20 20 {.>:i.10 10 inds=. ,i.10 10 patience=. 10 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=. 20 end. end. end. (10 10$fill (I.grid=' ')} grid),' ',/:~key
)</lang>
Example run:
<lang J> genpuz etwarpesmR feoOakplsS anEtoaanim hTrpixTuva cownkuAhac loCOaaqstk cmiamifsae biggsDdroy neetxisaim Epalettenm
atavism 7 9 north biggs 8 1 east chafe 5 1 north cowpoke 7 1 ne lax 2 8 sw mackey 3 10 south miami 7 2 east mirfak 10 10 nw mosquito 9 10 nw nadia 10 9 nw net 3 2 north palette 10 2 east patrol 1 6 sw shun 6 8 north sixteen 9 7 west spain 1 8 sw warp 1 3 east </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)