Thanks all for the great responses! But I'm still not sure how to use the slice
function.
#-------------------------------------------------------------------------------
# Name: WordSearch.nim
# Purpose: Find word in a grid of letters in any directions.
#-------------------------------------------------------------------------------
import std/[strutils, strformat, enumerate, sugar, tables, algorithm]
from math import floorMod,floorDiv
# Implement Python compatible divmod for nim-lang.
proc divmod(a, b: int): (int, int) =
let
res = a.floorDiv b # integer division
rem = a.floorMod b # integer modulo operation
(res, rem)
#-------------------------------------------------------------------------------
{.experimental: "views".}
type
View*[T] = object
## A strided view over an (unowned) data buffer
len*: int
stride: int
offset: int
data: lent UncheckedArray[T]
func `[]`*[T](v: View[T], idx: int): lent T {.inline.} =
v.data[v.offset + idx*v.stride]
func `[]`*[T](v: var View[T], idx: int): var T {.inline.} =
# Experimental views indeed ...
cast[ptr UncheckedArray[T]](v.data)[v.offset + idx*v.stride]
func `[]=`*[T](v: var View[T], idx: int, val: T) {.inline.} =
# Experimental views indeed ...
cast[ptr UncheckedArray[T]](v.data)[v.offset + idx*v.stride] = val
func toView*[T](oa: openArray[T]): View[T] {.inline.} =
result.len = oa.len
result.stride = 1
result.offset = 0
result.data = cast[lent UncheckedArray[T]](oa[0].unsafeAddr)
iterator items*[T](v: View[T]): lent T =
var cur = v.offset
for _ in 0 ..< v.len:
yield v.data[cur]
cur += v.stride
func slice*(v: View, start, stop, step: int): View {.inline.} =
## Slice a view
## stop is inclusive
# General tensor slicing algorithm is
#
https://github.com/mratsim/Arraymancer/blob/71cf616/src/arraymancer/tensor/private/p_accessors_macros_read.nim#L26-L56
#
# for i, slice in slices:
# # Check if we start from the end
# let a = if slice.a_from_end: result.shape[i] - slice.a
# else: slice.a
#
# let b = if slice.b_from_end: result.shape[i] - slice.b
# else: slice.b
#
# # Compute offset:
# result.offset += a * result.strides[i]
# # Now change shape and strides
# result.strides[i] *= slice.step
# result.shape[i] = abs((b-a) div slice.step) + 1
#
# with slices being of size 1, as we have a monodimensional Tensor
# and the slice being a..<b with the reverse case: len-1 -> 0
#
# result is preinitialized with a copy of v (shape, stride, offset, data)
result.offset = v.offset + start * v.stride
result.stride = v.stride * step
result.len = abs((stop-start) div step) + 1
result.data = v.data
#-------------------------------------------------------------------------------
# Procedure to print the grid of letters with row numbers & column letters.
proc print_grid(puzzle: string) =
var lastRow: string
let newGrid = puzzle.replace(" ", "")
for i, row in enumerate(1, newGrid.split('\n')):
# Print top column letters heading.
if i == 1:
stdout.write " "
for m in 0 ..< len(row):
stdout.write fmt"{chr(ord('a')+m)} "
echo()
stdout.write " +"
stdout.write "-".repeat(2 * len(row) + 1)
echo "+"
# Print row numbers heading.
stdout.write fmt"{i:02}| "
for m in row:
stdout.write fmt"{m} "
echo(fmt"|{i:02}")
# row is out of scope after the for-loop in Nim.
# Need a var lastRow to store the last value.
lastRow = row
# Print bottom column letters heading.
stdout.write " +"
stdout.write "-".repeat(2 * len(lastRow) + 1)
echo "+"
stdout.write " "
for m in 0 ..< len(lastRow):
stdout.write fmt"{chr(ord('a')+m)} "
echo()
# Algo1: Procedure to find word in grid of letters using Table.
proc solve_puzzle(puzzle: string; clues: seq) =
let
newGrid = puzzle.replace(" ", "")
length = newGrid.find('\n') + 1
# Make a list of tuples containing each letter and its row and column.
letters = collect(newSeq):
for index, letter in enumerate(newGrid): (letter, divmod(index,
length))
# Reorder the list to represent each reading direction,
# and add them all to a dictionary.
var lines = initTable[string, typeof(letters)]()
let offsets = {"down": 0, "left down": -1, "right down": 1}.toTable
for direction, offset in offsets:
lines[direction] = @[] # Empty seq.
for i in 0 ..< length:
for j in countup(i, letters.high, length + offset):
lines[direction].add(letters[j])
lines[direction].add(('\n', (0, 0)))
lines["right"] = letters
lines["left"] = letters.reversed
lines["up"] = lines["down"].reversed
lines["left up"] = lines["right down"].reversed
lines["right up"] = lines["left down"].reversed
# Make strings from the letters, find the words in them and retrieve
# their original locations.
var nc = 0
for direction, tup in lines:
let myStr = block:
var x = ""
for line in tup: x &= line[0]
x
for word in clues:
if word.toUpper() in myStr:
nc = nc + 1
var location = tup[myStr.find(word.toUpper())][1]
echo fmt"{word.toUpper()}: row[{location[0] + 1:02}]
col[{chr(ord('a') + location[1])}] {direction}"
if (nc mod 5) == 0 and nc < clues.len:
echo "-".repeat 35
# Algo2: Function to find word in grid of letters using Array.
proc find_word(puzzle: string; word: string) =
echo(fmt"{word}:")
let newGrid = puzzle.replace(" ","")
let w = newGrid.find("\n")+1
let L = word.len
let lenGrid = len(newGrid)
let viewGrid = newGrid.toView() # nim(165, 25) template/generic
instantiation of `toView` from here.
# nim(43, 17) Error: expression cannot
be cast to lent UncheckedArray[char]
var res: seq[(int, int)]
for i in 0 ..< len(newGrid):
for j in @[-w-1, -w, -w+1, -1, 1, w-1, w, w+1]:
for x in i ..< i+(L-1)*j:
if slice(viewGrid,i,lenGrid,j)[0..L] == word.toUpper(): # Not
sure if this is correct.
res.add((x div (w + 1), (x mod w) + 1))
for t in res:
echo " --> ".join("Row[t[0]:02] Col[{chr(ord('a') + t[1] - 1)}]")
#===============================================================================
when is_main_module:
# Define the puzzle.
let puzzle = """I U W S S W E D E N F Q S M V R P B
B M I D F I N D I A H I S P W Y Y L
H T E N I G E R I A I O N V A M C P
Y Y H X R L E B E T G R J L O I A A
H N X A I U E Z F R A N C E A E N N
V R O T I C S N B E L G I U M N A A
N F R R Y L O S G I C V M N V E D M
W N X F W V A I I L T O Z I H A A A
G H A N A A M N X A A A F B K I N B
G R E E C E Y A D A D N L Z U D F Z
T P K P Q J A P A N T Q D Y D L V I
V K A M E R I C A D C H I N A B C X"""
let clues = @["Belgium", "Greece", "Canada", "Japan", "England",
"Italy", "France", "Panama", "India", "Mexico",
"Norway", "Spain", "China", "Thailand", "Sweden",
"Ghana", "Russia", "Finland", "Nigeria", "America"]
# Print the grid.
print_grid(puzzle)
# Find the words.
echo()
echo "=".repeat 40
solve_puzzle(puzzle, clues)
echo "=".repeat 40
# Another algo to find words.
echo()
echo "=".repeat 40
var nw = 0
for word in clues:
nw = nw + 1
find_word(puzzle, word)
if nw mod 5 == 0 and nw < len(clues):
echo "-".repeat 35
else:
if nw != len(clues):
echo()
echo "=".repeat 40
echo()
Run
