小町算

main.go

package main

import (
	"errors"
	"fmt"
	"math"
	"sort"
	"strconv"
)

// https://play.golang.org/p/ljft9xhOEn
// NextPermutation generates the next permutation of the
// sortable collection x in lexical order.  It returns false
// if the permutations are exhausted.
//
// Knuth, Donald (2011), "Section 7.2.1.2: Generating All Permutations",
// The Art of Computer Programming, volume 4A.
func NextPermutation(x sort.Interface) bool {
	n := x.Len() - 1
	if n < 1 {
		return false
	}
	j := n - 1
	for ; !x.Less(j, j+1); j-- {
		if j == 0 {
			return false
		}
	}
	l := n
	for !x.Less(j, l) {
		l--
	}
	x.Swap(j, l)
	for k, l := j+1, n; k < l; {
		x.Swap(k, l)
		k++
		l--
	}
	return true
}

type Permutation struct {
	x sort.Interface
	first bool
}

func NewPermutation(x sort.Interface) *Permutation {
	return &Permutation{
		x:     x,
		first: false,
	}
}

func (p *Permutation) Next() bool {
	if !p.first {
		p.first = true
		return true
	}
	return NextPermutation(p.x)
}

const (
	Plus = '+'
	Minus = '-'
	Times = '*'
	Divides = '/'
	Power = '^'
	Concat = '|'
)

var (
	nums = []rune{'1', '2', '3', '4', '5', '6', '7', '8', '9'}
	ops = []rune{Plus, Minus, Times, Divides, Power, Concat}
)

func power(a, b int) int {
	ret := 1
	for i := 0; i < b; i++ {
		ret *= a
	}
	return ret
}

func allMultiSets(ops []rune, pow int) [][]rune {
	ret := make([][]rune, 0, power(len(ops), pow))
	type recFunc func(depth int, cur []rune, f recFunc)
	f := func(depth int, cur []rune, f recFunc) {
		if depth == pow {
			v := make([]rune, len(cur))
			copy(v, cur)
			ret = append(ret, v)
			return
		}
		for _, op := range ops {
			cur = append(cur, op)
			f(depth+1, cur, f)
			cur = cur[:len(cur)-1]
		}
	}
	f(0, make([]rune, 0, pow), f)
	return ret
}

func isValidPostOrder(v []int) bool {
	stackSize := 0
	for _, vv := range v {
		if vv == 0 {
			// num
			stackSize++
		} else {
			// op
			stackSize--
			if stackSize <= 0 {
				return false
			}
		}
	}
	return true
}

var (
	errCannotDivide = errors.New("cannot divide")
	errUnexpectedChar = errors.New("unexpected char")
)

type (
	PostOrder []rune
	Tree struct {
		ch rune
		left *Tree
		right *Tree
	}
)

func (p PostOrder) calc() (int, error) {
	stack := make([]int, 0)
	for _, ch := range p {
		if '0' <= ch && ch <= '9' {
			// number
			stack = append(stack, int(ch - '0'))
		} else {
			// op
			a, b := stack[len(stack)-2], stack[len(stack)-1]
			stack = stack[:len(stack)-2]
			var next int
			switch ch {
			case Plus:
				next = a + b
			case Minus:
				next = a - b
			case Times:
				next = a * b
			case Divides:
				if b == 0 || a % b != 0 {
					return 0, errCannotDivide
				}
				next = a / b
			case Power:
				next = int(math.Pow(float64(a), float64(b)))
			case Concat:
				var err error
				next, err = strconv.Atoi(strconv.Itoa(a) + strconv.Itoa(b))
				if err != nil {
					return 0, err
				}
			default:
				return 0, errUnexpectedChar
			}
			stack = append(stack, next)
		}
	}
	return stack[0], nil
}

func (p PostOrder) toTree() *Tree {
	stack := make([]*Tree, 0)
	for _, ch := range p {
		if '0' <= ch && ch <= '9' {
			stack = append(stack, &Tree{
				ch:    ch,
				left:  nil,
				right: nil,
			})
		} else {
			a, b := stack[len(stack)-2], stack[len(stack)-1]
			stack = stack[:len(stack)-2]
			stack = append(stack, &Tree{
				ch:    ch,
				left:  a,
				right: b,
			})
		}
	}
	return stack[0]
}

func (t *Tree) inOrder() string {
	if t.left == nil && t.right == nil {
		return string(t.ch)
	} else if t.left == nil {
		return string(t.ch) + t.left.inOrder()
	} else if t.right == nil {
		return string(t.ch) + t.right.inOrder()
	} else {
		return "(" + t.left.inOrder() + string(t.ch) + t.right.inOrder() + ")"
	}
}

func main() {
	x := []int{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1}

	postOrders := make([][]int, 0)
	p := NewPermutation(sort.IntSlice(x))
	for p.Next() {
		if isValidPostOrder(x) {
			v := make([]int, 17)
			copy(v, x)
			postOrders = append(postOrders, v)
		}
	}
	fmt.Println("valid post orders", len(postOrders))

	opMultiSets := allMultiSets(ops, 8)
	fmt.Println("op multi sets (len(ops)^8)", len(opMultiSets))

	var id int64
	for _, postOrder := range postOrders {
		toTest := make(PostOrder, 17)
		opIndices := make([]int, 0, 8)
		nextNumIdx := 0
		for i := 0; i < 17; i++ {
			if postOrder[i] == 0 {
				toTest[i] = nums[nextNumIdx]
				nextNumIdx++
			} else {
				opIndices = append(opIndices, i)
			}
		}

		for _, operators := range opMultiSets {
			for i, opIdx := range opIndices {
				toTest[opIdx] = operators[i]
			}

			id++
			ans, err := toTest.calc()
			if err != nil {
				continue
			}
			if ans == 10958 {
				fmt.Printf("%v. %v = %v\n", id, toTest.toTree().inOrder(), ans)
			}
		}
	}
}