Word search

Word search is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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)

Java

Works with: Java version 7

<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)