improv.go

package main

import (
	"fmt"
	"math"
	"os"
	"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][]int
	charmoves = []byte("nesw")
)

func printMoves(moves uint64, depth int) {
	b := make([]byte, depth)
	for i := depth - 1; i >= 0; i-- {
		b[i] = charmoves[moves&3]
		moves >>= 2
	}
	fmt.Printf("%s\n", string(b))
}

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

type Record struct {
	Children []Key
	Count    int
}

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

var sentinel = Key(0)

func solve(chips int) map[Key]Record {
	// 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)))
	fmt.Println(min)
	max := int(math.Ceil(math.Sqrt(float64(chips) * 2)))
	fmt.Println(max)
	sub_solutions := map[Key]Record{}
	// preload the final case
	for depth := min; depth <= max; depth += 2 {
		key := key(0, goal, depth)
		sub_solutions[key] = Record{[]Key{sentinel}, 1}
	}
	goal_chip := intdata[goal]
	for target_chip := goal_chip; target_chip <= chips; target_chip++ {
		for depth := max; depth >= 0; depth-- {
			for pos := range data {
				pos_key := key(target_chip, pos, depth)
				children := []Key{}
				n := 0
				for _, neighbor := range neighs[pos] {
					neighbor_chip := target_chip - intdata[neighbor]
					if neighbor != start && neighbor != goal {
						neighbor_chip -= depth
					}
					neighbor_key := key(neighbor_chip, neighbor, depth+1)
					record, ok := sub_solutions[neighbor_key]
					if !ok {
						continue
					}
					n += record.Count
					children = append(children, neighbor_key)
				}
				if len(children) > 0 {
					sub_solutions[pos_key] = Record{children, n}
				}
			}
		}
	}
	return sub_solutions
}

func direction(cur, next Key) byte {
	switch next&0xffff - cur&0xffff {
	case 1:
		return 'e'
	case -1:
		return 'w'
	case width:
		return 's'
	default:
		return 'n'
	}
}

func count_paths(sub_solutions map[Key]Record, cur Key) int {
	return sub_solutions[cur].Count
}

func gen_paths(sub_solutions map[Key]Record, cur Key, path []byte) []string {
	if cur == sentinel {
		return []string{string(path)}
	}
	paths := []string{}
	for _, next := range sub_solutions[cur].Children {
		paths = append(paths, gen_paths(sub_solutions, next, append(path, direction(cur, next)))...)
	}
	return paths
}

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()
	sub_solutions := solve(start_chips)
	fmt.Fprintf(os.Stderr, "%f\n", float64(time.Since(now))/1000000000.0)
	start_key := key(start_chips, start, 0)
	fmt.Fprintf(os.Stderr, "%d\n", sub_solutions[start_key].Count)
	all := gen_paths(sub_solutions, start_key, nil)
	fmt.Fprintf(os.Stderr, "%f\n", float64(time.Since(now))/1000000000.0)
	fmt.Fprintf(os.Stderr, "%d\n", len(all))
}