I want to convert this Word Search algo from Python to Nim.
Hit several errors. Need help!
I have commented those sections that hit error.
Python:
#-------------------------------------------------------------------------------
# Name: WordSearch-2.py
# Purpose: Find word in a grid of letters in any directions.
#-------------------------------------------------------------------------------
# Function to find word in grid of letters.
# Not a perfect algo, it miss "Thailand" and
# the solution doesn't follow the order of the clues.
def solve(puzzle, clues):
puzzle = puzzle.replace(' ','')
length = puzzle.index('\n')+1
# Make a list of tuples containing each letter and its row and column.
letters = [(letter, divmod(index, length))
for index, letter in enumerate(puzzle)]
# Reorder the list to represent each reading direction,
# and add them all to a dictionary.
lines = {}
offsets = {'down':0, 'left down':-1, 'right down':1}
for direction, offset in offsets.items():
lines[direction] = []
for i in range(length):
for j in range(i, len(letters), length + offset):
lines[direction].append(letters[j])
#print(f"lines[dir]={lines[direction]}, letters[j]={letters[j]}")
lines[direction].append('\n')
lines['right'] = letters
lines['left'] = [i for i in reversed(letters)]
lines['up'] = [i for i in reversed(lines['down'])]
lines['left up'] = [i for i in reversed(lines['right down'])]
lines['right up'] = [i for i in reversed(lines['left down'])]
# Make strings from the letters, find the words in them and retrieve
# their original locations.
nc = 0
for direction, tup in lines.items():
string = ''.join([i[0] for i in tup])
for word in clues:
if word.upper() in string:
nc = nc + 1
location = tup[string.index(word.upper())][1]
print(f"{word.upper()}: row[{location[0]+1:02}] col[{chr(ord('a')+location[1])}] {direction}")
if (nc%5) == 0 and nc<len(clues):
print("-"*35)
# Function to print the grid of letters with row numbers & column letters.
def print_grid(puzzle):
print()
g = puzzle.replace(" ","")
w = g.find("\n")+1
for r, row in enumerate(g.split('\n'), start=1):
# Print top column letters heading.
if r == 1:
print(" ", end='')
print("".join("%s " % chr(ord('a')+m) for m in range(len(row))))
print(" +", end='')
print("-"*(2*len(row)+1), end='')
print("+")
# Print row numbers heading.
print("%02d|" % r, end=' ')
for c, l in enumerate(row, start=1):
print("%s" % l, end=' ')
print("|%02d" % r)
# Print bottom column letters heading.
print(" +", end='')
print("-"*(2*len(row)+1), end='')
print("+")
print(" ", end='')
print("".join("%s " % chr(ord('a')+m) for m in range(len(row))))
# Function to find word in grid of letters.
# A better algo, that is able to find start & end of word;
# the solution is in order of the clues, and didn't missed "Thailand".
def find_word(puzzle, word):
print("%s:" % word.upper())
g = puzzle.replace(" ","")
w = g.find("\n")+1
L = len(word)
res = []
for i in range(len(g)):
for j in (-w-1, -w, -w+1, -1, 1, w-1, w, w+1):
for x in (i, i+(L-1)*j):
if g[i::j][:L] == word.upper():
res.append((x//w+1, x%w+1))
print(" --> ".join("Row[%02d] Col[%s]" % (t[0], chr(ord('a')+t[1]-1)) for t in res))
if __name__ == '__main__':
# Define the puzzle.
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"""
clues = ["Belgium", "Greece", "Canada", "Japan", "England",
"Italy", "France", "Panama", "India", "Mexico",
"Norway", "Spain", "China", "Thailand", "Sweden",
"Ghana", "Russia", "Finland", "Nigeria", "America"]
# Init g_highlight.
g_highlight = [False for l in (puzzle.replace(" ",""))]
# Print the grid.
print_grid(puzzle)
# Find the words.
print("")
print("="*40)
solve(puzzle, clues)
print("="*40)
# Another algo to find words.
print("")
print("="*40)
nw = 0
for word in clues:
nw = nw + 1
find_word(puzzle, word)
if (nw%5) == 0 and nw<len(clues):
print("-"*35)
else:
if nw!=len(clues):
print()
print("="*40)
print()
Nim:
#-------------------------------------------------------------------------------
# Name: WordSearch.nim
# Purpose: Find word in a grid of letters in any directions.
#-------------------------------------------------------------------------------
import strutils, std/strformat, std/enumerate, std/sugar, std/tables
# Implement print("="*20) for nim-lang.
let zero = ""
proc `+`(a, b: string): string =
a & b
proc `*`[T](a: T, b: int): T =
result = zero
for i in 0 .. b-1:
result = result + a # calls `+` from above proc `+`.
# Implement divmod for nim-lang.
proc divmod(a, b: int): (int, int) =
let res = a div b # integer division
let rem = a mod b # integer modulo operation
return (res, rem)
# 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:
write(stdout, " ")
for m in 0 ..< len(row):
write(stdout, fmt"{chr(ord('a')+m)} ")
echo()
write(stdout, " +")
write(stdout, "-"*(2*len(row)+1))
echo("+")
# Print row numbers heading.
write(stdout, fmt"{i:02}| ")
for m in row:
write(stdout, 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.
write(stdout, " +")
write(stdout, "-"*(2*len(lastRow)+1))
echo("+")
write(stdout, " ")
for m in 0 ..< len(lastRow):
write(stdout, fmt"{chr(ord('a')+m)} ")
echo()
# Procedure to find word in grid of letters.
proc solve_puzzle(puzzle: string; clues: seq) =
let newGrid = puzzle.replace(" ","")
let length = newGrid.find('\n')+1
##echo(fmt"length = {length}")
# Make a list of tuples containing each letter and its row and column.
let letters = collect(newSeq):
for index, letter in enumerate(newGrid): (letter, divmod(index, length))
##echo(fmt"letters = {letters}")
# Reorder the list to represent each reading direction,
# and add them all to a dictionary.
var lines = initTable[string, seq]()
let offsets = {"down": 0, "left down": -1, "right down": 1}.toTable
##echo(fmt"offsets = {offsets}")
# Test printing the dictionary/table 'offsets' items.
for dirn, offset in offsets.pairs():
echo(fmt"dirn = {dirn}, offset = {offset}")
#[
#!!! Hit error here !!!
for direction, offset in offsets.pairs():
lines[direction] = @[] # Empty seq.
for i in 0 ..< length:
for j in countup(i, len(letters), length+offset):
lines[direction].add(letters[j]) ## nim(84, 33) Error: type mismatch: got <seq[string], (char, (int, int))> but expected one of: proc add[T](x: var seq[T]; y: openArray[T])
lines[direction].add('\n')
lines["right"] = letters
lines["left"] = collect(newSeq):
for i in reversed(letters): i
lines["up"] = collect(newSeq):
for i in reversed(lines["down"]): i
lines["left up"] = collect(newSeq):
for i in reversed(lines["right down"]): i
lines["right up"] = collect(newSeq):
for i in reversed(lines["left down"]): i
# Make strings from the letters, find the words in them and retrieve
# their original locations.
var nc = 0
var myStr = ""
for direction, tup in lines.items():
myStr = collect(newSeq):
for i in tup: join("", i[0])
for word in clues:
if word.upper() in myStr:
nc = nc + 1
var location = tup[myStr.index(word.upper())][1]
echo(fmt"{word.upper()}: row[{location[0]+1:02}] col[{chr(ord('a')+location[1])}] {direction}")
if (nc%5) == 0 and nc<len(clues):
echo("-"*35)
#]#
# Function to find word in grid of letters.
proc solve_puzzle(puzzle: string; word: string) =
echo(fmt"{word}:")
let newGrid = puzzle.replace(" ","")
let w = newGrid.find("\n")+1
let L = len(word)
#[
#!!! Hit error here !!!
var res = @[] # nim(120, 15) Error: cannot infer the type of the sequence
for i in 0 ..< len(g):
for j in (-w-1, -w, -w+1, -1, 1, w-1, w, w+1):
for x in i ..< i+(L-1)*j:
if g[i::j][:L] == word.upper(): # nim(124, 25) Error: expected: ']', but got: '::'
res.append((x//w+1, x%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("="*40)
solve_puzzle(puzzle, clues)
echo("="*40)
Your Nim implementation is probably going to look something like this:
#-------------------------------------------------------------------------------
# Name: WordSearch.nim
# Purpose: Find word in a grid of letters in any directions.
#-------------------------------------------------------------------------------
import std/[strutils, strformat, enumerate, sugar, tables, algorithm]
# Implement divmod for nim-lang.
proc divmod(a, b: int): (int, int) =
let
res = a div b # integer division
rem = a mod b # integer modulo operation
(res, rem)
# 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()
# Procedure to find word in grid of letters.
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
# Test printing the dictionary/table 'offsets' items.
for dirn, offset in offsets.pairs():
echo fmt"dirn = {dirn}, offset = {offset}"
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
# Function to find word in grid of letters.
proc solve_puzzle(puzzle: string; word: string) =
echo(fmt"{word}:")
let newGrid = puzzle.replace(" ","")
let w = newGrid.find("\n")+1
let L = word.len
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 newGrid[i..j][0..L] == word.toUpper(): # nim(124, 25) Error: expected: ']', but got: '::'
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
A couple of things to note:
Thanks very much, @PMunch!
I've learnt a lot.
But for the 2nd algo, in the Python slice g[i::j][:L] is to loop from index i to end with step j. Not i to j => g[i:j].
Python has this [start:end:step] slice.
Hence, I don't know how to convert this in nim.
#-------------------------------------------------------------------------------
# Name: WordSearch.nim
# Purpose: Find word in a grid of letters in any directions.
#-------------------------------------------------------------------------------
import std/[strutils, strformat, enumerate, sugar, tables, algorithm]
# Implement divmod for nim-lang.
proc divmod(a, b: int): (int, int) =
let
res = a div b # integer division
rem = a mod b # integer modulo operation
(res, rem)
# 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
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 newGrid[i..j][0..L] == word.toUpper():
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: int = 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()
I renamed the 2nd algo procedure to find_word().
Running this, I hit this runtime error:
======================================== Belgium: /usercode/in.nim(141) in /usercode/in.nim(103) find_word /playground/nim/lib/system.nim(2566) [] /playground/nim/lib/system/fatal.nim(53) sysFatal Error: unhandled exception: index 2 not in 0 .. 1 [IndexDefect]
But for the 2nd algo, in the Python slice g[i::j][:L] is to loop from index i to end with step j. Not i to j => g[i:j]. Python has this [start:end:step] slice.
That kind of slicing syntax is implemented in arraymancer:
https://mratsim.github.io/Arraymancer/tuto.slicing.html
(for arraymancer Tensors).
It should be possible to extract the macro logic for it and use it for sequences in theory, but that wouldn't be non trivial.
It should be possible to extract the macro logic for it and use it for sequences in theory, but that would be non trivial.
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
It doesn't apply in this case, because you're only using divmod on positive numbers, but at the risk of confusion I want to point out that python divmod,div, and mod behave differently from Nim for negative numbers, so that can be a gotcha when porting python.
If negative numbers are involved you need to use floorDiv and floorMod from math. So a python-compatible divmod would be:
from math import floorMod,floorDiv
proc divmod(a, b: int): (int, int) =
let
res = a.floorDiv b # integer division
rem = a.floorMod b # integer modulo operation
(res, rem)
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()
Here is with an "unsate" slice version that doesn't use experimental features. It compiles but results are different. I added one string formatting but I think another one is missing
#-------------------------------------------------------------------------------
# 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: ptr UncheckedArray[T] # "lent UncheckedArray[T]" requires devel
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.} =
v.data[v.offset + idx*v.stride]
func `[]=`*[T](v: var View[T], idx: int, val: T) {.inline.} =
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[ptr 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
func `==`[T](a, b: View[T]): bool =
if a.len != b.len:
return false
var curA = a.offset
var curB = b.offset
for i in 0 ..< a.len:
if a.data[curA] != b.data[curB]:
return false
curA += a.stride
curB += b.stride
return true
#-------------------------------------------------------------------------------
# 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 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 viewGrid.slice(i, viewGrid.len-1,j).slice(0, L-1, 1) == word.toUpper().toView(): # 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()