schönbrunn.go

package main

import "fmt"

type Coord struct {
	Row int
	Col int
}

type Cell struct {
	Coord
	Value   int
	Visited bool
}

func (cell *Cell) String() string {
	var sign string
	if cell.Visited {
		sign = "*"
	}
	return fmt.Sprintf("(%d%s @ {%d, %d})", cell.Value, sign, cell.Row, cell.Col)
}

type Puzzle [][]Cell

func NewPuzzle(input [][]int) Puzzle {
	cells := make([][]Cell, len(input))
	for i, row := range input {
		for j, _ := range row {
			cell := Cell{
				Value: row[j],
				Coord: Coord{Row: i, Col: j},
			}

			cells[i] = append(cells[i], cell)
		}
	}
	return Puzzle(cells)
}

func (puzzle Puzzle) CellAt(coords Coord) *Cell {
	return &puzzle[coords.Row][coords.Col]
}

func (puzzle Puzzle) UnvisitedNeighborsForCell(cell *Cell) []*Cell {
	var neighbors []*Cell
	cellValue := abs(cell.Value)

	maybeCoords := []Coord{
		Coord{Row: cell.Coord.Row - cellValue, Col: cell.Coord.Col},
		Coord{Row: cell.Coord.Row + cellValue, Col: cell.Coord.Col},
		Coord{Row: cell.Coord.Row, Col: cell.Coord.Col - cellValue},
		Coord{Row: cell.Coord.Row, Col: cell.Coord.Col + cellValue},
	}

	for _, coords := range maybeCoords {
		if coords.Row < 0 || coords.Row >= len(puzzle) {
			continue
		}
		if coords.Col < 0 || coords.Col >= len(puzzle[coords.Row]) {
			continue
		}
		if puzzle.CellAt(coords).Visited {
			continue
		}

		neighbors = append(neighbors, puzzle.CellAt(coords))
	}

	return neighbors
}

func (puzzle *Puzzle) FindPath(from, to *Cell) (bool, []*Cell) {
	path := []*Cell{from}
	from.Visited = true // mark as visited

	if from == to { // found the target
		return true, path
	}

	nextCells := puzzle.UnvisitedNeighborsForCell(from)
	for _, nextCell := range nextCells {
		nextCell.Visited = true
		found, restOfPath := puzzle.FindPath(nextCell, to)

		if found {
			path = append(path, restOfPath...)
			return true, path
		}

		if restOfPath == nil { // backtrack
			nextCell.Visited = false // reset visited flag
		} else {
			path = append(path, restOfPath...)
		}

		path = path[:len(path)-1]
	}

	return false, path
}

func main() {
	puzzle := NewPuzzle([][]int{
		{2, -2, 4, -1, 3},
		{-3, 3, 1, 3, -2},
		{1, -2, 0, -2, -3},
		{-3, 2, -3, 2, -4},
		{4, -2, 1, -3, 2},
	})
	beginning := puzzle.CellAt(Coord{4, 2})
	ending := puzzle.CellAt(Coord{2, 2})
	_, path := puzzle.FindPath(beginning, ending)

	printSolution(path)
}

func printSolution(solution []*Cell) {
	for _, cell := range solution {
		fmt.Printf("%v -> ", cell)
	}
	fmt.Println()
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}