Solve a Hidato puzzle: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) (→{{header|Perl 6}}: Syntax fix, "0" is true now. (didn't actually affect this particular problem)) |
(Added Go) |
||
Line 1,352: | Line 1,352: | ||
17 7 6 3 |
17 7 6 3 |
||
5 4 |
5 4 |
||
</pre> |
|||
=={{header|Go}}== |
|||
{{trans|Java}} |
|||
<lang go>package main |
|||
import ( |
|||
"fmt" |
|||
"sort" |
|||
"strconv" |
|||
"strings" |
|||
) |
|||
var board [][]int |
|||
var start, given []int |
|||
func setup(input []string) { |
|||
/* This task is not about input validation, so |
|||
we're going to trust the input to be valid */ |
|||
puzzle := make([][]string, len(input)) |
|||
for i := 0; i < len(input); i++ { |
|||
puzzle[i] = strings.Fields(input[i]) |
|||
} |
|||
nCols := len(puzzle[0]) |
|||
nRows := len(puzzle) |
|||
list := make([]int, nRows*nCols) |
|||
board = make([][]int, nRows+2) |
|||
for i := 0; i < nRows+2; i++ { |
|||
board[i] = make([]int, nCols+2) |
|||
for j := 0; j < nCols+2; j++ { |
|||
board[i][j] = -1 |
|||
} |
|||
} |
|||
for r := 0; r < nRows; r++ { |
|||
row := puzzle[r] |
|||
for c := 0; c < nCols; c++ { |
|||
switch cell := row[c]; cell { |
|||
case "_": |
|||
board[r+1][c+1] = 0 |
|||
case ".": |
|||
break |
|||
default: |
|||
val, _ := strconv.Atoi(cell) |
|||
board[r+1][c+1] = val |
|||
list = append(list, val) |
|||
if val == 1 { |
|||
start = append(start, r+1, c+1) |
|||
} |
|||
} |
|||
} |
|||
} |
|||
sort.Ints(list) |
|||
given = make([]int, len(list)) |
|||
for i := 0; i < len(given); i++ { |
|||
given[i] = list[i] |
|||
} |
|||
} |
|||
func solve(r, c, n, next int) bool { |
|||
if n > given[len(given)-1] { |
|||
return true |
|||
} |
|||
back := board[r][c] |
|||
if back != 0 && back != n { |
|||
return false |
|||
} |
|||
if back == 0 && given[next] == n { |
|||
return false |
|||
} |
|||
if back == n { |
|||
next++ |
|||
} |
|||
board[r][c] = n |
|||
for i := -1; i < 2; i++ { |
|||
for j := -1; j < 2; j++ { |
|||
if solve(r+i, c+j, n+1, next) { |
|||
return true |
|||
} |
|||
} |
|||
} |
|||
board[r][c] = back |
|||
return false |
|||
} |
|||
func printBoard() { |
|||
for _, row := range board { |
|||
for _, c := range row { |
|||
switch { |
|||
case c == -1: |
|||
fmt.Print(" . ") |
|||
case c > 0: |
|||
fmt.Printf("%2d ", c) |
|||
default: |
|||
fmt.Print("__ ") |
|||
} |
|||
} |
|||
fmt.Println() |
|||
} |
|||
} |
|||
func main() { |
|||
input := []string{ |
|||
"_ 33 35 _ _ . . .", |
|||
"_ _ 24 22 _ . . .", |
|||
"_ _ _ 21 _ _ . .", |
|||
"_ 26 _ 13 40 11 . .", |
|||
"27 _ _ _ 9 _ 1 .", |
|||
". . _ _ 18 _ _ .", |
|||
". . . . _ 7 _ _", |
|||
". . . . . . 5 _", |
|||
} |
|||
setup(input) |
|||
printBoard() |
|||
fmt.Println("\nFound:") |
|||
solve(start[0], start[1], 1, 0) |
|||
printBoard() |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
. . . . . . . . . . |
|||
. __ 33 35 __ __ . . . . |
|||
. __ __ 24 22 __ . . . . |
|||
. __ __ __ 21 __ __ . . . |
|||
. __ 26 __ 13 40 11 . . . |
|||
. 27 __ __ __ 9 __ 1 . . |
|||
. . . __ __ 18 __ __ . . |
|||
. . . . . __ 7 __ __ . |
|||
. . . . . . . 5 __ . |
|||
. . . . . . . . . . |
|||
Found: |
|||
. . . . . . . . . . |
|||
. 32 33 35 36 37 . . . . |
|||
. 31 34 24 22 38 . . . . |
|||
. 30 25 23 21 12 39 . . . |
|||
. 29 26 20 13 40 11 . . . |
|||
. 27 28 14 19 9 10 1 . . |
|||
. . . 15 16 18 8 2 . . |
|||
. . . . . 17 7 6 3 . |
|||
. . . . . . . 5 4 . |
|||
. . . . . . . . . . |
|||
</pre> |
</pre> |
||