Word search: Difference between revisions

=={{header|Nim}}==

{{trans|D}}

<lang Nim>import random, sequtils, strformat, strutils

const

Dirs = [[1, 0], [ 0, 1], [ 1, 1],

[1, -1], [-1, 0],

[0, -1], [-1, -1], [-1, 1]]

NRows = 10

NCols = 10

GridSize = NRows * NCols

MinWords = 25

type Grid = ref object

numAttempts: Natural

cells: array[NRows, array[NCols, char]]

solutions: seq[string]

proc readWords(filename: string): seq[string] =

const MaxLen = max(NRows, NCols)

for word in filename.lines():

if word.len in 3..MaxLen:

if word.allCharsInSet(Letters):

result.add word.toLowerAscii

proc placeMessage(grid: var Grid; msg: string): int =

let msg = msg.map(toUpperAscii).filter(isUpperAscii).join()

if msg.len in 1..<GridSize:

let gapSize = GridSize div msg.len

for i in 0..msg.high:

let pos = i * gapSize + rand(gapSize - 1)

grid.cells[pos div NCols][pos mod NCols] = msg[i]

result = msg.len

proc tryLocation(grid: var Grid; word: string; dir, pos: Natural): int =

let row = pos div NCols

let col = pos mod NCols

let length = word.len

# Check bounds.

if (Dirs[dir][0] == 1 and (length + col) > NCols) or

(Dirs[dir][0] == -1 and (length - 1) > col) or

(Dirs[dir][1] == 1 and (length + row) > NRows) or

(Dirs[dir][1] == -1 and (length - 1) > row):

return 0

# Check cells.

var r = row

var c = col

for ch in word:

if grid.cells[r][c] != '\0' and grid.cells[r][c] != ch: return 0

c += Dirs[dir][0]

r += Dirs[dir][1]

# Place.

r = row

c = col

var overlaps = 0

for i, ch in word:

if grid.cells[r][c] == ch: inc overlaps

else: grid.cells[r][c] = ch

if i < word.high:

c += Dirs[dir][0]

r += Dirs[dir][1]

let lettersPlaced = length - overlaps

if lettersPlaced > 0:

grid.solutions.add &"{word:<10} ({col}, {row}) ({c}, {r})"

result = lettersPlaced

proc tryPlaceWord(grid: var Grid; word: string): int =

let randDir = rand(Dirs.high)

let randPos = rand(GridSize - 1)

for dir in 0..Dirs.high:

let dir = (dir + randDir) mod Dirs.len

for pos in 0..<GridSize:

let pos = (pos + randPos) mod GridSize

let lettersPlaced = grid.tryLocation(word, dir, pos)

if lettersPlaced > 0:

return lettersPlaced

proc initGrid(words: seq[string]): Grid =

var words = words

for numAttempts in 1..100:

words.shuffle()

new(result)

let messageLen = result.placeMessage("Rosetta Code")

let target = GridSize - messageLen

var cellsFilled = 0

for word in words:

cellsFilled += result.tryPlaceWord(word)

if cellsFilled == target:

if result.solutions.len >= MinWords:

result.numAttempts = numAttempts

return

# Grid is full but we didn't pack enough words: start over.

break

proc printResult(grid: Grid) =

if grid.isNil or grid.numAttempts == 0:

echo "No grid to display."

return

let size = grid.solutions.len

echo "Attempts: ", grid.numAttempts

echo "Number of words: ", size

echo "\n 0 1 2 3 4 5 6 7 8 9\n"

for r in 0..<NRows:

echo &"{r} ", grid.cells[r].join(" ")

echo()

for i in countup(0, size - 2, 2):

echo grid.solutions[i], " ", grid.solutions[i + 1]

if (size and 1) == 1:

echo grid.solutions[^1]

randomize()

let grid = initGrid("unixdict.txt".readWords())

grid.printResult()</lang>

{{out}}

<pre>Attempts: 2

Number of words: 29

0 1 2 3 4 5 6 7 8 9

0 s i a b l R d a t d

1 u x i i m e O l b e

2 n o v i r w S l u j

3 k n l a E b z i b T

4 a k n y o y e e T e

5 y g t l e A a d d l

6 e f u l f i l l C d

7 r e g a y o v O l d

8 f o h s l e w D i a

9 f o g y r E p i n s

derange (6, 0) (0, 6) fulfill (1, 6) (7, 6)

frey (0, 8) (0, 5) allied (7, 0) (7, 5)

sally (3, 8) (3, 4) anvil (0, 4) (4, 0)

saddle (9, 9) (9, 4) voyage (6, 7) (1, 7)

iii (3, 2) (1, 0) sunk (0, 0) (0, 3)

bub (8, 1) (8, 3) fogy (0, 9) (3, 9)

zeal (6, 3) (6, 6) milky (4, 1) (0, 5)

welsh (6, 8) (2, 8) knox (1, 4) (1, 1)

allay (9, 8) (5, 4) jed (9, 2) (9, 0)

snip (9, 9) (6, 9) bed (5, 3) (7, 5)

bmw (3, 0) (5, 2) gut (2, 7) (2, 5)

rev (4, 9) (6, 7) tad (8, 0) (6, 0)

via (2, 2) (2, 0) ogle (1, 8) (4, 5)

add (6, 5) (8, 5) lob (3, 5) (5, 3)

lin (8, 7) (8, 9)</pre>