Solve a Hopido 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 442: | Line 442: | ||
23 20 15 |
23 20 15 |
||
1 |
1 |
||
</pre> |
|||
=={{header|Go}}== |
|||
{{trans|Java}} |
|||
<lang go>package main |
|||
import ( |
|||
"fmt" |
|||
"sort" |
|||
) |
|||
var board = []string{ |
|||
".00.00.", |
|||
"0000000", |
|||
"0000000", |
|||
".00000.", |
|||
"..000..", |
|||
"...0...", |
|||
} |
|||
var moves = [][2]int{ |
|||
{-3, 0}, {0, 3}, {3, 0}, {0, -3}, |
|||
{2, 2}, {2, -2}, {-2, 2}, {-2, -2}, |
|||
} |
|||
var grid [][]int |
|||
var totalToFill = 0 |
|||
func solve(r, c, count int) bool { |
|||
if count > totalToFill { |
|||
return true |
|||
} |
|||
nbrs := neighbors(r, c) |
|||
if len(nbrs) == 0 && count != totalToFill { |
|||
return false |
|||
} |
|||
sort.Slice(nbrs, func(i, j int) bool { |
|||
return nbrs[i][2] < nbrs[j][2] |
|||
}) |
|||
for _, nb := range nbrs { |
|||
r = nb[0] |
|||
c = nb[1] |
|||
grid[r][c] = count |
|||
if solve(r, c, count+1) { |
|||
return true |
|||
} |
|||
grid[r][c] = 0 |
|||
} |
|||
return false |
|||
} |
|||
func neighbors(r, c int) (nbrs [][3]int) { |
|||
for _, m := range moves { |
|||
x := m[0] |
|||
y := m[1] |
|||
if grid[r+y][c+x] == 0 { |
|||
num := countNeighbors(r+y, c+x) - 1 |
|||
nbrs = append(nbrs, [3]int{r + y, c + x, num}) |
|||
} |
|||
} |
|||
return |
|||
} |
|||
func countNeighbors(r, c int) int { |
|||
num := 0 |
|||
for _, m := range moves { |
|||
if grid[r+m[1]][c+m[0]] == 0 { |
|||
num++ |
|||
} |
|||
} |
|||
return num |
|||
} |
|||
func printResult() { |
|||
for _, row := range grid { |
|||
for _, i := range row { |
|||
if i == -1 { |
|||
fmt.Print(" ") |
|||
} else { |
|||
fmt.Printf("%2d ", i) |
|||
} |
|||
} |
|||
fmt.Println() |
|||
} |
|||
} |
|||
func main() { |
|||
nRows := len(board) + 6 |
|||
nCols := len(board[0]) + 6 |
|||
grid = make([][]int, nRows) |
|||
for r := 0; r < nRows; r++ { |
|||
grid[r] = make([]int, nCols) |
|||
for c := 0; c < nCols; c++ { |
|||
grid[r][c] = -1 |
|||
} |
|||
for c := 3; c < nCols-3; c++ { |
|||
if r >= 3 && r < nRows-3 { |
|||
if board[r-3][c-3] == '0' { |
|||
grid[r][c] = 0 |
|||
totalToFill++ |
|||
} |
|||
} |
|||
} |
|||
} |
|||
pos, r, c := -1, 0, 0 |
|||
for { |
|||
for { |
|||
pos++ |
|||
r = pos / nCols |
|||
c = pos % nCols |
|||
if grid[r][c] != -1 { |
|||
break |
|||
} |
|||
} |
|||
grid[r][c] = 1 |
|||
if solve(r, c, 2) { |
|||
break |
|||
} |
|||
grid[r][c] = 0 |
|||
if pos >= nRows*nCols { |
|||
break |
|||
} |
|||
} |
|||
printResult() |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
1 22 14 21 |
|||
18 10 7 17 11 8 16 |
|||
5 24 27 4 23 26 13 |
|||
2 19 9 15 20 |
|||
6 25 12 |
|||
3 |
|||
</pre> |
</pre> |
||