fastest.go

package main

import (
	"fmt"
	"math"
	"math/bits"
	"os"
	"sync"
	"time"
	"unsafe"
)

const (
	height      = 12
	width       = 12
	start_chips = 444
	data        = "081788529595" +
		"851156944521" +
		"723529269394" +
		"925989577596" +
		"246714266258" +
		"281538497523" +
		"293567249425" +
		"631782336793" +
		"257427855358" +
		"529836149563" +
		"469854976468" +
		"277199737225"
	start = 0
	goal  = len(data) - 1
	e     = 0
	s     = 1
	w     = 2
	n     = 3
)

var (
	solutions = 0
	intdata   [144]int
	neighs    [144][]int
	// charmoves = []byte("nesw")
	charmoves = []byte("eswn")
)

func neighbors(position int) []int {
	x := position % width
	y := position / width
	n := []int{}
	if x < width-1 {
		n = append(n, position+1)
	}
	if y < height-1 {
		n = append(n, position+width)
	}
	if x > 0 {
		n = append(n, position-1)
	}
	if y > 0 {
		n = append(n, position-width)
	}
	return n
}

type Key int64

func (k Key) String() string {
	pos := int(k & 0xffff)
	chips := int(k >> 32)
	return fmt.Sprintf("%d %d %d", pos%width, pos/width, chips)
}

// inline
func key(goal_chip, pos int) Key {
	return Key(goal_chip<<32 + pos)
}

type Path uint64

func (p Path) String() string {
	end := 22 + bits.OnesCount64(uint64(p)&0xaaaaaaaaaaaaaaaa)*2
	bytes := make([]byte, 32)
	x := unsafe.Pointer(&bytes[0])
	pi := (*[4]uint64)(x)
	for i := 3; i >= 0; i-- {
		pi[i] = intmoves[p&0xffff]
		p >>= 16
	}
	return string(bytes[:end])
}

type Paths []Path

func solve(chips int) [][]string {
	// min depth is linear distance between start and goal
	min := int(math.Abs(float64(start%width-goal%width)) + math.Abs(float64(start/width-goal/width)))
	max := int(math.Ceil(math.Sqrt(float64(chips) * 2)))
	// figure better split
	split := max / 2
	fmt.Println(min, max, split)
	goal_key := key(0, goal)
	wg1 := sync.WaitGroup{}
	backwards := map[Key]Paths{}
	backwards[goal_key] = Paths{0}
	wg1.Add(1)
	go func() {
		defer wg1.Done()
		for depth := max - 1; depth >= split; depth-- {
			backwards = step(backwards, depth, false)
			if (depth-min)%2 == 0 {
				backwards[goal_key] = Paths{0}
			}
			// fmt.Println(depth, len(current))
			// fmt.Println(backwards)
		}
	}()
	fmt.Fprintf(os.Stderr, "Backs Started %f\n", float64(time.Since(now))/1000000000.0)
	start_key := key(chips, start)
	forwards := map[Key]Paths{}
	forwards[start_key] = Paths{0}
	for depth := 0; depth < split-1; depth++ {
		current := step(forwards, depth, true)
		forwards = current
		// fmt.Println(depth, len(current))
		// fmt.Println(forwards)
	}
	fmt.Fprintf(os.Stderr, "Forwards Complete %f\n", float64(time.Since(now))/1000000000.0)
	wg1.Wait()
	fmt.Fprintf(os.Stderr, "Backs Complete %f\n", float64(time.Since(now))/1000000000.0)
	chunkSize := 100
	num := (len(forwards) / chunkSize) + 1
	results := make([][]string, num)
	keys := make([][]Key, num)
	wg2 := sync.WaitGroup{}
	i := 0
	j := 0
	keys[0] = make([]Key, 0, chunkSize)
	for k := range forwards {
		i++
		keys[j] = append(keys[j], k)
		if i == chunkSize {
			i = 0
			j++
			keys[j] = make([]Key, 0, chunkSize)
		}
	}
	for i := 0; i < num; i++ {
		wg2.Add(1)
		go func(i int) {
			defer wg2.Done()
			results[i] = step_product(keys[i], backwards, forwards, split-1)
		}(i)
	}
	wg2.Wait()
	fmt.Fprintf(os.Stderr, "Products Complete %f\n", float64(time.Since(now))/1000000000.0)
	return results
}

func step_product(keys []Key, backwards map[Key]Paths, forwards map[Key]Paths, depth int) []string {
	paths := []string{}
	for _, last_key := range keys {
		f := forwards[last_key]
		last_pos := int(last_key & 0xffff)
		last_chip := int(last_key >> 32)
		for _, pos := range neighs[last_pos] {
			current_chip := last_chip
			current_chip -= intdata[pos]
			if pos != start && pos != goal {
				current_chip -= depth
			}
			pos_key := key(current_chip, pos)
			b, ok := backwards[pos_key]
			if !ok {
				continue
			}
			for _, p1 := range f {
				for _, p2 := range b {
					// combine the paths
					m := direction(last_pos, pos)
					m <<= 62 - depth*2
					paths = append(paths, (p1 + m + p2).String())
				}
			}
		}
	}
	return paths
}

func step(last map[Key]Paths, depth int, fwd bool) map[Key]Paths {
	current := map[Key]Paths{}
	for last_key, record := range last {
		last_pos := int(last_key & 0xffff)
		last_chip := int(last_key >> 32)
		if fwd {
			if last_chip < 260 {
				continue
			}
		} else {
			if last_chip > 290 {
				continue
			}
		}
		for _, pos := range neighs[last_pos] {
			current_chip := last_chip
			if fwd {
				current_chip -= intdata[pos]
				if pos != start && pos != goal {
					current_chip -= depth
				}
			} else {
				current_chip += intdata[last_pos]
				if last_pos != start && last_pos != goal {
					current_chip += depth
				}
			}
			pos_key := key(current_chip, pos)
			current_record, ok := current[pos_key]
			if !ok {
				current_record = Paths{}
			}
			for _, p := range record {
				var m Path
				if fwd {
					m = direction(last_pos, pos)
				} else {
					m = direction(pos, last_pos)
				}
				m <<= 62 - depth*2
				current_record = append(current_record, p+m)
			}
			current[pos_key] = current_record
		}
	}
	return current
}

func direction(from, to int) Path {
	switch to - from {
	case 1:
		return e
	case -1:
		return w
	case width:
		return s
	default:
		return n
	}
}

var intmoves = [65536]uint64{}

func genIntMoves() {
	// generate combinations of 8 charmoves
	i := 0
	for _, c1 := range charmoves {
		for _, c2 := range charmoves {
			for _, c3 := range charmoves {
				for _, c4 := range charmoves {
					for _, c5 := range charmoves {
						for _, c6 := range charmoves {
							for _, c7 := range charmoves {
								for _, c8 := range charmoves {
									intmoves[i] = uint64(c8)<<56 + uint64(c7)<<48 + uint64(c6)<<40 + uint64(c5)<<32 + uint64(c4)<<24 + uint64(c3)<<16 + uint64(c2)<<8 + uint64(c1)
									i++
								}
							}
						}
					}
				}
			}
		}
	}
}

var now time.Time

func main() {
	var i int
	for i = 0; i < len(data); i++ {
		intdata[i] = int(data[i] - '0')
		neighs[i] = neighbors(i)
	}
	now = time.Now()
	genIntMoves()
	paths := solve(start_chips)
	fmt.Println(paths[0][:10])
	n := 0
	for _, p := range paths {
		n += len(p)
	}
	fmt.Fprintf(os.Stderr, "total: %d\n", n)
}

string.go

package main

import (
	"fmt"
	"math"
	"os"
	"sync"
	"time"
)

const (
	height      = 12
	width       = 12
	start_chips = 444
	data        = "081788529595" +
		"851156944521" +
		"723529269394" +
		"925989577596" +
		"246714266258" +
		"281538497523" +
		"293567249425" +
		"631782336793" +
		"257427855358" +
		"529836149563" +
		"469854976468" +
		"277199737225"
	start = 0
	goal  = len(data) - 1
	n     = 0
	e     = 1
	s     = 2
	w     = 3
)

var (
	solutions = 0
	intdata   [144]int
	neighs    [144][]Neighbor
	charmoves = []byte("nesw")
)

type Neighbor struct {
	p int
	f Path
	r Path
}

func neighbors(position int) []Neighbor {
	x := position % width
	y := position / width
	n := []Neighbor{}
	if x < width-1 {
		n = append(n, Neighbor{position + 1, "e", "w"})
	}
	if y < height-1 {
		n = append(n, Neighbor{position + width, "s", "n"})
	}
	if x > 0 {
		n = append(n, Neighbor{position - 1, "w", "e"})
	}
	if y > 0 {
		n = append(n, Neighbor{position - width, "n", "s"})
	}
	return n
}

type Key int64

func (k Key) String() string {
	pos := int(k & 0xffff)
	chips := int(k >> 32)
	return fmt.Sprintf("%d %d %d", pos%width, pos/width, chips)
}

// inline
func key(goal_chip, pos int) Key {
	return Key(goal_chip<<32 + pos)
}

type Path string

type Paths []Path

func solve(chips int) [][]Path {
	// min depth is linear distance between start and goal
	min := int(math.Abs(float64(start%width-goal%width)) + math.Abs(float64(start/width-goal/width)))
	max := int(math.Ceil(math.Sqrt(float64(chips) * 2)))
	// figure better split
	split := max / 2
	fmt.Println(min, max, split)
	goal_key := key(0, goal)
	depths := []int{}
	for depth := min; depth <= max; depth += 2 {
		depths = append(depths, depth)
	}
	wg1 := sync.WaitGroup{}
	backwards := map[Key]Paths{}
	backwards[goal_key] = Paths{""}
	wg1.Add(1)
	go func() {
		defer wg1.Done()
		for depth := max - 1; depth >= split; depth-- {
			backwards = step(backwards, depth, false)
			if (depth-min)%2 == 0 {
				backwards[goal_key] = Paths{""}
			}
			// fmt.Println(depth, len(current))
			// fmt.Println(backwards)
		}
	}()
	fmt.Fprintf(os.Stderr, "Backs Started %f\n", float64(time.Since(now))/1000000000.0)
	start_key := key(chips, start)
	forwards := map[Key]Paths{}
	forwards[start_key] = Paths{""}
	for depth := 0; depth < split-1; depth++ {
		forwards = step(forwards, depth, true)
		// fmt.Println(depth, len(current))
		// fmt.Println(forwards)
	}
	fmt.Fprintf(os.Stderr, "Forwards Complete %f\n", float64(time.Since(now))/1000000000.0)
	wg1.Wait()
	fmt.Fprintf(os.Stderr, "Backs Complete %f\n", float64(time.Since(now))/1000000000.0)
	fmt.Println(len(forwards))
	chunkSize := 50
	num := (len(forwards) / chunkSize) + 1
	keys := make([][]Key, num)
	results := make([][]Path, num)
	wg2 := sync.WaitGroup{}
	i := 0
	j := 0
	keys[0] = make([]Key, 0, chunkSize)
	for k := range forwards {
		i++
		keys[j] = append(keys[j], k)
		if i == chunkSize {
			i = 0
			j++
			keys[j] = make([]Key, 0, chunkSize)
		}
	}
	for i := 0; i < num; i++ {
		wg2.Add(1)
		go func(i int) {
			defer wg2.Done()
			results[i] = step_product(keys[i], backwards, forwards, split-1)
		}(i)
	}
	wg2.Wait()
	fmt.Fprintf(os.Stderr, "Products Complete %f\n", float64(time.Since(now))/1000000000.0)
	return results
}

func step_product(keys []Key, backwards map[Key]Paths, forwards map[Key]Paths, depth int) []Path {
	paths := []Path{}
	for _, last_key := range keys {
		f := forwards[last_key]
		last_pos := int(last_key & 0xffff)
		last_chip := int(last_key >> 32)
		for _, n := range neighs[last_pos] {
			pos := n.p
			current_chip := last_chip
			current_chip -= intdata[pos]
			if pos != start && pos != goal {
				current_chip -= depth
			}
			pos_key := key(current_chip, pos)
			b, ok := backwards[pos_key]
			if !ok {
				continue
			}
			for _, p1 := range f {
				for _, p2 := range b {
					// combine the paths
					paths = append(paths, p1+n.f+p2)
				}
			}
		}
	}
	return paths
}

func step(last map[Key]Paths, depth int, fwd bool) map[Key]Paths {
	current := map[Key]Paths{}
	for last_key, record := range last {
		last_pos := int(last_key & 0xffff)
		last_chip := int(last_key >> 32)
		if fwd {
			if last_chip < 260 {
				continue
			}
		} else {
			if last_chip > 290 {
				continue
			}
		}
		for _, n := range neighs[last_pos] {
			pos := n.p
			current_chip := last_chip
			if fwd {
				current_chip -= intdata[pos]
				if pos != start && pos != goal {
					current_chip -= depth
				}
			} else {
				current_chip += intdata[last_pos]
				if last_pos != start && last_pos != goal {
					current_chip += depth
				}
			}
			pos_key := key(current_chip, pos)
			current_record, ok := current[pos_key]
			if !ok {
				current_record = Paths{}
			}
			for _, p := range record {
				var m Path
				if fwd {
					m = p + n.f
				} else {
					m = n.r + p
				}
				current_record = append(current_record, m)
			}
			current[pos_key] = current_record
		}
	}
	return current
}

var now time.Time

func main() {
	var i int
	for i = 0; i < len(data); i++ {
		intdata[i] = int(data[i] - '0')
		neighs[i] = neighbors(i)
	}
	now = time.Now()
	paths := solve(start_chips)
	fmt.Println(paths[0][:10])
	n := 0
	for _, p := range paths {
		n += len(p)
	}
	fmt.Fprintf(os.Stderr, "total: %d\n", n)
}