knight_travails.go ported from http://rubyquiz.com/quiz27.html

knight_travails.go

package main 

import (
  "fmt"
  "math"
  "os"
  "reflect"
)

var p = fmt.Println

var LETTERS = [] string {"a","b","c","d","e","f","g","h"}
var DIGITS = [] uint8 {0,1,2,3,4,5,6,7}

//Helper methods
func Contains(slice interface{}, val interface{}) bool {
  sv := reflect.ValueOf(slice)

  for i := 0; i < sv.Len(); i++ {
    if reflect.DeepEqual(sv.Index(i).Interface(), val) {
      return true
    }
  }
  return false
}

//Helper class
type Tile struct {
  x,y uint8
}
func named(s string) Tile{
  tile := Tile{x:s[0]-"a"[0],y:s[1]-"0"[0]}
  if  !tile.valid() {
    fmt.Println("this tile is not valid",tile)
  }
  return tile
}

func (tile Tile) valid() bool {
  return Contains(DIGITS,tile.x) && Contains(DIGITS,tile.y) 
}
// func (tile Tile) String() string {
//     if tile.valid() {
//         return fmt.Sprintf("%s%s", LETTERS[tile.x],DIGITS[tile.y])     
//     }
//     fmt.Println("WARNING: this tile is not valid",tile.x,tile.y)
//     return ""
// }
func (tile Tile) adjacent(tile_ Tile) bool {
  var dx = math.Abs(float64(tile.x) - float64(tile_.x))
  var dy = math.Abs(float64(tile.y) - float64(tile_.y))
  return tile.valid() && tile_.valid() && (dx ==1 && dy ==2 || dx==2 && dy==1)
}



type Board struct {
    board [] Tile
}

func (b *Board) Pop() {
    if len(b.board) == 0 { return }
    b.board = b.board[:len(b.board)-1]
}
func (b *Board) Del(item Tile) {
  found := -1
  for i, el := range(b.board){
    if item.x==el.x && item.y ==el.y {
      found  = i
      break
    }
  }
  if found >0 {
    b.board = append(b.board[:found],b.board[found+1:len(b.board)]...)
    fmt.Println("found item at ", item,  found, len(b.board))

  }
}

func (b *Board) Add(tile... Tile) {
    b.board = append(b.board, tile...)
}

func (b *Board) String() string {
    return fmt.Sprintf("%v",b.board)
}
func (b *Board) find_all_adjacent(tile Tile) [] Tile {
  ret :=  make([]Tile, 0)
  for _, el := range(b.board){
    if tile.adjacent(el) {
      fmt.Println("Found adjacent: ", el)
      ret = append(ret, el)
    }
  }
  fmt.Println("Finding adjacent of tile ",tile, ret)
  return ret
}

func (b *Board) reject_all(black_list... Tile) {
  fmt.Println("starting rejecting all tile in ", black_list)
  list_tile_tobe_rejected :=  make([]Tile, 0)
  for _, el := range(b.board){
    if Contains(black_list,el) {
      list_tile_tobe_rejected = append(list_tile_tobe_rejected, el)
    }
  }
  if len(list_tile_tobe_rejected) > 0 {
    for _,el := range(list_tile_tobe_rejected) {
      fmt.Println("Reject: ", el)
      b.Del(el)
    }
  }

}


func knights_trip(start Tile, finish Tile, forbidden... Tile) [] Tile{
  // First, build big bucket o' tiles.
  board := &Board{} 
  for i:=0;i<64;i++ {
    board.Add(Tile{x:uint8(i%8),y:uint8(i/8)})
  }
//   Second, pull out forbidden tiles.
// TODO : Implement forbidden
  // # Third, prepare a hash, where layer 0 is just the start.
  // # Remove start from the board.
  x := 0
  flood := map[int][]Tile{x: {start}}
  board.Del(start)
  fmt.Println(flood)
  fmt.Println(board)
  // # Fourth, perform a "flood fill" step, finding all board tiles
  // # adjacent to the previous step.
  for len(flood[x]) > 0 && !Contains(flood[x], finish) {
    x +=1
    flood[x] =  make([]Tile, 0)
    for _, obj := range(flood[x-1]) {
      flood[x] = append(flood[x], board.find_all_adjacent(obj)...)
    }
  //   # Remove those found from the board.
    fmt.Println("Checking layer x= ",x)
    fmt.Println("Current adjacent: ", flood[x])
    board.reject_all(flood[x]...)
  }
  path :=  make([]Tile, 0)
  if len(flood[x]) > 0 {
//     # We found a way. Time to build the path. This is built
//     # backwards, so finish goes in first.    
     fmt.Println("found a way with . Here it is ", x)
     path = append(path,finish)
     for x >0  {
        x -=1
//       # Find in flood[x] a tile adjacent to the head of our
//       # path. Doesn't matter which one. Make it the new head
//       # of our path.
        jumps :=  make([]Tile, 0)
        for _, el := range(flood[x]){
          if el.adjacent(path[0]) {
            jumps = append(jumps, el)
          }
        }
        // Insert at top. copyright by Golang !!!!
        i:=0        
        // append a dummy node (tile)
        path = append(path, named("a9"))
        copy(path[i+1:], path[i:])
        path[i] = jumps[0]  
      } 
  }
  return path
}

func main() {
  fmt.Println(os.Args[1:])
  var args [2] Tile
  for i, arg := range os.Args[1:]{
    args[i] = named(arg)
  }
  for _, arg := range(args) {
    if !arg.valid() {
      fmt.Println("Invalid arg: ", arg)
      os.Exit(1)
    }
  }
  trip := knights_trip(args[0],args[1])
  if len(trip) < 1 {
    fmt.Println("No path found")
  }
  fmt.Println("Route: ", trip)
}