GCJ/2008/2/D/utils.go

package main

func minInt(nums ...int) int {
	min := nums[0]
	for i := 1; i < len(nums); i++ {
		if nums[i] < min {
			min = nums[i]
		}
	}
	return min
}

func nextPerm(nums []int) bool {
	n := len(nums)
	if n < 2 {
		return false
	}
	i := n - 2
	for ; 0 <= i && nums[i+1] <= nums[i]; i-- {
	}
	if i == -1 {
		return false
	}
	j := i + 1
	for ; j+1 < n && nums[i] < nums[j+1]; j++ {
	}
	nums[i], nums[j] = nums[j], nums[i]
	for l, r := i+1, n-1; l < r; l, r = l+1, r-1 {
		nums[l], nums[r] = nums[r], nums[l]
	}
	return true
}

func countGroup(s string, perm []int) int {
	n, k := len(s), len(perm)
	prevByte := s[perm[0]]
	cnt := 1
	for offset := 0; offset < n; offset += k {
		i := 0
		if offset == 0 {
			i = 1
		}
		for ; i < k; i++ {
			if s[offset+perm[i]] != prevByte {
				cnt++
			}
			prevByte = s[offset+perm[i]]
		}
	}
	return cnt
}

func slowSolution(s string, k int) (min int) {
	perm := make([]int, k)
	for i := range perm {
		perm[i] = i
	}
	min = countGroup(s, perm)
	for nextPerm(perm) {
		groupCnt := countGroup(s, perm)
		if groupCnt < min {
			min = groupCnt
		}
	}
	return
}