24.go

package main

import (
	"fmt"
	"strconv"
)

func MakeTwentyFour(nums []int) (expr string, found bool) {
	// in reality, as long as len(nums) >= 1, this function just works.
	// Just to be conformed with the problem I'm trying to solve here.
	_assertEqual(4, len(nums))

	var fnums []float64
	var exprs []string

	for _, num := range nums {
		fnums = append(fnums, float64(num))
		exprs = append(exprs, strconv.Itoa(num))
	}

	found, expr = solve(fnums, exprs)
	return
}

func solve(nums []float64, exprs []string) (found bool, solution string) {
	_assertEqual(true, len(nums) >= 1)
	_assertEqual(len(nums), len(exprs))

	if len(nums) == 1 {
		return nums[0] == 24, exprs[0]
	}

	// iterate through all possible pairs of numbers from nums.
	for i := 0; i < len(nums); i++ {
		for j := 0; j < len(nums); j++ {
			if i == j {
				continue
			}

			nextExprs := make([]string, 0, len(exprs)-1)
			nextNums := make([]float64, 0, len(nums)-1)
			for k := 0; k < len(nums); k++ {
				if k == i || k == j {
					continue
				}
				nextExprs = append(nextExprs, exprs[k])
				nextNums = append(nextNums, nums[k])
			}

			for _, op := range []byte{'+', '-', '*', '/'} {
				var num float64
				switch op {
				case '+':
					num = nums[i] + nums[j]
				case '-':
					num = nums[i] - nums[j]
				case '*':
					num = nums[i] * nums[j]
				case '/':
					num = nums[i] / nums[j]
				}
				nextNums = append(nextNums, num)
				nextExprs = append(nextExprs,
					fmt.Sprintf("(%s%c%s)", exprs[i], op, exprs[j]))

				if found, solution = solve(nextNums, nextExprs); found {
					return
				}
				nextNums = nextNums[:len(nextNums)-1]
				nextExprs = nextExprs[:len(nextExprs)-1]
			}
		}
	}
	return false, ""
}

func _assertEqual(expected, actual interface{}) {
	if expected != actual {
		panic("assertion failed")
	}
}

func main() {
	cases := [][]int{
		{1, 1, 1, 1},
		{2, 2, 2, 2},
		{3, 3, 3, 3},
		{4, 4, 4, 4},
		{5, 5, 5, 5},
		{6, 6, 6, 6},
		{3, 3, 7, 7},
		{1, 2, 3, 4},
		{2, 3, 4, 5},
		{3, 4, 5, 6},
		{4, 5, 6, 7},
		{5, 6, 7, 8},
		{6, 7, 8, 9},
		{7, 8, 9, 10},
		{3, 8, 4, 5},
		{3, 3, 7, 9},
		{13, 3, 13, 1},
		{11, 3, 7, 2},
	}

	for _, nums := range cases {
		expr, found := MakeTwentyFour(nums)
		if !found {
			fmt.Printf("%v: not found\n", nums)
		} else {
			fmt.Printf("%v: %s\n", nums, expr)
		}
	}
	// [1 1 1 1]: not found
	// [2 2 2 2]: not found
	// [3 3 3 3]: ((3*(3*3))-3)
	// [4 4 4 4]: ((4+4)+(4*4))
	// [5 5 5 5]: ((5*5)-(5/5))
	// [6 6 6 6]: ((6+6)+(6+6))
	// [3 3 7 7]: (7*(3+(3/7)))
	// [1 2 3 4]: (4*(3+(1+2)))
	// [2 3 4 5]: (4*(5-(2-3)))
	// [3 4 5 6]: (6*(5+(3-4)))
	// [4 5 6 7]: (4*(7+(5-6)))
	// [5 6 7 8]: ((5+7)*(8-6))
	// [6 7 8 9]: ((6*8)/(9-7))
	// [7 8 9 10]: ((8*9)/(10-7))
	// [3 8 4 5]: (4*((3+8)-5))
	// [3 3 7 9]: ((3-7)*(3-9))
	// [13 3 13 1]: ((13-3)+(13+1))
	// [11 3 7 2]: ((11*3)-(7+2))
}