Solve a Hidato puzzle: Difference between revisions

Content added Content deleted

Inline

@@ Line 2,653: / Line 2,653: @@
 =={{header|Nim}}==
-<lang nim>import strutils, algorithm
+<lang nim>import strutils, algorithm, sequtils, strformat
+type Hidato = object
-var board: array[0..19, array[0..19, int]]
-var given, start: seq[int] = @[]
+       board: seq[seq[int]]
+       given: seq[int]
-var rows, cols: int = 0
+       start: (int, int)
-proc setup(s: string) =
-    var lines = s.splitLines()
-    cols = lines[0].split().len()
-    rows = lines.len()
+proc initHidato(s: string): Hidato =
-    for i in 0 .. rows + 1:
+  var lines = s.splitLines()
-        for j in 0 .. cols + 1:
+  let cols = lines[0].splitWhitespace().len()
-           board[i][j] = -1
+  let rows = lines.len()
+  result.board = newSeqWith(rows + 2, newSeq[int](cols + 2))  # Make room for borders.
-    for r, row in pairs(lines):
-        for c, cell in pairs(row.split()):
-            case cell
-            of "__" :
-                board[r + 1][c + 1] = 0
-                continue
-            of "." : continue
-            else :
-               var val = parseInt(cell)
-               board[r + 1][c + 1] = val
-               given.add(val)
-               if (val == 1):
-                   start.add(r + 1)
-                   start.add(c + 1)
-    given.sort(cmp[int], Ascending)
-proc solve(r, c, n: int, next: int = 0): bool =
-    if n > given[high(given)]:
-       return true
-    if board[r][c] < 0:
-        return false
-    if (board[r][c] > 0 and board[r][c] != n):
-        return false
-    if (board[r][c] == 0 and given[next] == n):
-        return false
-    var back = board[r][c]
+  for i in 0 .. result.board.high:
-    board[r][c] = n
+    for j in 0 .. result.board[0].high:
-    for i in -1 .. 1:
+      result.board[i][j] = -1
-        for j in -1 .. 1:
-            if back == n:
-                if (solve(r + i, c + j, n + 1, next + 1)):  return true
-            else:
-                if (solve(r + i, c + j, n + 1, next)): return true
-    board[r][c] = back
-    result = false
+  for r, row in lines:
+    for c, cell in row.splitWhitespace().pairs():
-proc printBoard() =
-    for r in  0 .. rows + 1:
+      case cell
+      of "__" :
-        for cellid,c in pairs(board[r]):
-            if cellid > cols + 1: break
+        result.board[r + 1][c + 1] = 0
-            if c == -1:
+        continue
-                write(stdout, " . ")
+      of "." :
-            elif c == 0:
+        continue
+      else :
-                write(stdout, "__ ")
-            else:
+        let val = parseInt(cell)
+        result.board[r + 1][c + 1] = val
-                write(stdout, "$# " % align($c,2))
-        writeLine(stdout, "")
+        result.given.add(val)
+        if val == 1:
-var hi: string = """__ 33 35 __ __  .  .  .
+          result.start = (r + 1, c + 1)
+  result.given.sort()
+proc solve(hidato: var Hidato; r, c, n: int; next = 0): bool =
+  if n > hidato.given[^1]:
+    return true
+  if hidato.board[r][c] < 0:
+    return false
+  if hidato.board[r][c] > 0 and hidato.board[r][c] != n:
+    return false
+  if hidato.board[r][c] == 0 and hidato.given[next] == n:
+    return false
+  let back = hidato.board[r][c]
+  hidato.board[r][c] = n
+  for i in -1 .. 1:
+    for j in -1 .. 1:
+      if back == n:
+        if hidato.solve(r + i, c + j, n + 1, next + 1): return true
+      else:
+        if hidato.solve(r + i, c + j, n + 1, next): return true
+  hidato.board[r][c] = back
+  result = false
+proc print(hidato: Hidato) =
+  for row in hidato.board:
+    for val in row:
+      stdout.write if val == -1: " . " elif val == 0: "__ " else: &"{val:2} "
+    writeLine(stdout, "")
+var hi = """
+__ 33 35 __ __  .  .  .
 __ __ 24 22 __  .  .  .
 __ __ __ 21 __ __  .  .
@@ Line 2,726: / Line 2,725: @@
 .  .  .  . __  7 __ __
 .  .  .  .  .  .  5 __"""
+var hidato = initHidato(hi)
-setup(hi)
+hidato.print()
-printBoard()
 echo("")
 echo("Found:")
-discard solve(start[0], start[1], 1)
+discard hidato.solve(hidato.start[0], hidato.start[1], 1)
-printBoard()</lang>
+hidato.print()</lang>
 {{out}}
 <pre> .  .  .  .  .  .  .  .  .  .