OEIS A300665 (Go)

count_paths.go

// Number of n-step paths made by a chess king, starting from the corner of an infinite chessboard, and never revisiting a cell.
// OEIS A300665
// Ricardo Bittencourt, March 13 2018

package main

import "fmt"

type Grid struct {
  grid []bool
  n int
  ci, cj int
  left int
}

func newGrid(n int) Grid {
  return Grid{make([]bool, n * n), n, 0, 0, n}
}

var di = [8]int{-1,  0,  1, -1, 1, -1, 0, 1}
var dj = [8]int{-1, -1, -1,  0, 0,  1, 1, 1}

func (g *Grid) print() {
  for j := 0; j < g.n; j++ {
    for i := 0; i < g.n; i++ {
      if g.grid[j * g.n + i] {
        fmt.Printf("*")
      } else {
        fmt.Printf(".")
      }
    }
    fmt.Printf("\n");
  }
  fmt.Printf("\n");
}

func (g *Grid) search(cj, ci, left int) uint64 {
  if left == 1 {
    return 1
  }
  g.grid[cj * g.n + ci] = true
  var total uint64 = 0
  for k := 0; k < 8; k++ {
    ii := ci + di[k]
    jj := cj + dj[k]
    if ii < 0 || jj < 0 || g.grid[jj * g.n + ii] {
      continue;
    }
    total += g.search(jj, ii, left - 1)
  }
  g.grid[cj * g.n + ci] = false
  return total
}

func (g *Grid) search_split(cj, ci, left, limit int, out chan<- Grid) {
  g.grid[cj * g.n + ci] = true
  defer func() { g.grid[cj * g.n + ci] = false }()
  if left == 1 || left <= limit {
    newgrid := make([]bool, g.n * g.n)
    copy(newgrid, g.grid)
    out <- Grid{newgrid, g.n, ci, cj, left}
    return
  }
  for k := 0; k < 8; k++ {
    ii := ci + di[k]
    jj := cj + dj[k]
    if ii < 0 || jj < 0 || g.grid[jj * g.n + ii] {
      continue;
    }
    g.search_split(jj, ii, left - 1, limit, out)
  }
}

func (g *Grid) search_limit(cj, ci, left int, out chan<- Grid) {
  if ci > cj {
    return
  }
  if ci == cj && ci == g.n - 1 {
    return
  }
  g.grid[cj * g.n + ci] = true
  defer func(){ g.grid[cj * g.n + ci] = false }()
  if ci < cj || left == 1 {
    newgrid := make([]bool, g.n * g.n)
    copy(newgrid, g.grid)
    out <- Grid{newgrid, g.n, ci, cj, left}
    return
  }
  for k := 0; k < 8; k++ {
    ii := ci + di[k]
    jj := cj + dj[k]
    if ii < 0 || jj < 0 || g.grid[jj * g.n + ii] {
      continue;
    }
    g.search_limit(jj, ii, left - 1, out)
  }
}

func (g *Grid) count() uint64 {
  return g.search(g.cj, g.ci, g.left)
}

func (g *Grid) bootstrap(out chan<- Grid) {
  g.search_limit(g.cj, g.ci, g.n, out)
  close(out)
}

func (g *Grid) split(first <-chan Grid, second chan<- Grid) {
  for g := range first {
    g.search_split(g.cj, g.ci, g.left, g.left - 4, second)
  }
  close(second)
}

func add(g Grid, adder chan<- uint64) {
  adder <- g.count()
}

func kernel(in <-chan Grid) uint64 {
  adder := make(chan uint64)
  x := 0
  for g := range in {
    go add(g, adder)
    x++
  }
  var total uint64 = 0
  for i := 0; i < x; i++ {
    total += <-adder
  }
  return 2 * total + 1
}

func main() {
  var n int
  fmt.Scanf("%d", &n)
  fmt.Printf("n=%d\n", n)
  first := make(chan Grid)
  second := make(chan Grid)
  grid := newGrid(n)
  go grid.bootstrap(first)
  go grid.split(first, second)
  fmt.Printf("val=%v\n", kernel(second))
}