Explosive Sum https://www.codewars.com/kata/52ec24228a515e620b0005ef

main.go

package main

import (
	"fmt"
	"time"
	"strings"
)

var logOn = false

func cloneInts(a []int, b ...int) []int {
	r := make([]int, len(a), len(a)+len(b))
	copy(r, a)
	return append(r, b...)
}

func log(pad int, args ...interface{}) {
	if !logOn {
		return
	}
	tmp := []interface{}{}
	if pad > 0 {
		tmp = append(tmp, strings.Repeat("  ", pad))
	}
	fmt.Println(append(tmp, args...)...)
}

func split(arr []int) []int {
	ret := cloneInts(arr, 1)
	ret[0]--
	log(0, "split", arr, "->", ret)
	return ret
}

func testm(arr []int, idx int) []int {
	a := arr[idx]
	if arr[idx-1] < a {
		for i := idx + 1; i < len(arr); i++ {
			b := arr[i]
			if (a - b) > 1 {
				arr[i] = b + 1
				arr[idx] = a - 1
				return testm(arr, idx+1)
			}
		}
		return nil
	}
	return arr
}

func move(arr []int, pad int) []int {
	if (len(arr) <= 1) || (arr[0] <= 2) {
		return nil
	}
	f := arr[0]
	l := len(arr)
	for i := 1; i < l; i++ {
		a := arr[i]
		if (f - a) > 1 {
			r := cloneInts(arr)
			r[0] = f - 1
			r[i] = a + 1
			if r := testm(r, 1); r == nil {
				return nil
			}
			log(pad, "movd", r)
			return r
		}
	}
	return nil
}

func calc(arr []int, pad int) int {
	k := 1
	log(pad, "calc", arr)
	if arr[0] <= 2 {
		return k
	}
	pad++
	for i := len(arr) - 2; i >= 0; i-- {
		if mv := move(arr[i:], pad); mv != nil {
			k += calc(mv, pad)
		}

	}
	return k
}

func elapsed(what string) func() {
    start := time.Now()
    return func() {
        fmt.Printf("%s took %v\n", what, time.Since(start))
    }
}

func sum(n int) int {
        defer elapsed("run")()  
	k := 1
	ar := []int{n}
	log(0, "in:", ar)
	for ar[0] > 1 {
		ar = split(ar)
		k += calc(ar, 1)
		log(0, "k=", k)
	}
	return k
}

var test = [...]int{
	/*0..9*/ 1, 1, 2, 3, 5, 7, 11, 15, 22, 30,
	/*10..19*/ 42, 56, 77, 101, 135, 176, 231, 297, 385, 490,
	/*20..29*/ 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565,
	/*30..39*/ 5604, 6842, 8349, 10143, 12310, 14883, 17977, 21637, 26015, 31185,
	/*40..49*/ 37338, 44583, 53174, 63261, 75175, 89134, 105558, 124754, 147273, 173525}

func main() {
	//	fmt.Println(1 + calc([]int{7, 1, 1, 1, 1}, 0, 0))

	//	tmp := []int{3, 3, 3, 1}
	//	move(tmp, tmp, 0)
	for i, v := range test {
		k := sum(i)
		fmt.Println(i, ">", k)
		if k != v {
			logOn = true
			fmt.Println("fail", i, sum(i))
			break
		}

	}
	fmt.Println("done!")

}

/*
https://www.codewars.com/kata/52ec24228a515e620b0005ef/train/javascript


How many ways can you make the sum of a number?
From wikipedia: https://en.wikipedia.org/wiki/Partition_(number_theory)#

In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. If order matters, the sum becomes a composition. For example, 4 can be partitioned in five distinct ways:

4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1



0		1
1		1
2		2
3		3
4		5
5		7
6		11
7		15
8		22
9		30
10		42
11		56
12		77
13		101
14		135
15		176
16		231
17		297
18		385
19		490
20		627
21		792
22		1002
23		1255
24		1575
25		1958
26		2436
27		3010
28		3718
29		4565
30		5604
31		6842
32		8349
33		10143
34		12310
35		14883
36		17977
37		21637
38		26015
39		31185
40		37338
41		44583
42		53174
43		63261
44		75175
45		89134
46		105558
47		124754
48		147273
49		173525

*/