woodcutter.go

package main

import (
	"fmt"
	"unsafe"
)

type plank struct {
	size int
	cuts []int
}

type plankHash struct {
	size int
	cuts [51]int
}

// Cache contains the minimum cost to cut a plank
var cache = make(map[plankHash]int)

func (p plank) hash() plankHash {
	hash := plankHash{
		size: p.size,
	}

	copy(hash.cuts[:], p.cuts)

	return hash
}

func (p plank) minCost() int {
	if len(p.cuts) == 0 {
		return 0
	} else if len(p.cuts) == 1 {
		return p.size
	}

	result, found := cache[p.hash()]
	if found {
		return result
	}

	min := 1000000

	for i := range p.cuts {
		result = p.makeCut(i)
		if result < min {
			min = result
		}
	}

	cache[p.hash()] = min

	return min
}

func (p plank) makeCut(index int) int {
	leftPlank := plank{
		size: p.cuts[index],
		cuts: p.cuts[:index],
	}

	rightPlank := plank{
		size: p.size - p.cuts[index],
		cuts: calculateCuts(p.cuts[index+1:], p.cuts[index]),
	}

	total := leftPlank.minCost() + rightPlank.minCost() + p.size
	return total
}

func calculateCuts(cuts []int, shift int) []int {
	newCuts := make([]int, len(cuts))
	for k, v := range cuts {
		newCuts[k] = v - shift
	}

	return newCuts
}

func main() {
	start := plank{
		size: 1000,
		cuts: []int{
			6, 13, 17, 55, 75, 90, 105, 126, 127, 177, 203, 233, 244,
			248, 256, 296, 306, 363, 411, 418, 430, 462, 466, 470, 475, 481,
			486, 494, 509, 533, 555, 597, 605, 608, 625, 629, 659, 668, 761,
			775, 814, 815, 823, 833, 842, 845, 850, 898, 906, 946,
		},
	}

	fmt.Println(start.minCost())
	fmt.Println("cache size:", len(cache))
	fmt.Println("cache in bytes:", int(unsafe.Sizeof(plankHash{}))*len(cache))
}