FormParens

formParens.go

package kata

import (
    "strings"
    "strconv"
)

//
// First possible value (odd number):
// 
// - If n == 2: (()) ~ 0011
// - If n == 3: ((())) ~ 000111
// - If n == 4: (((()))) ~ 00001111
// - ...
//
// Last possible value (not included): 011_ ~ ())_
//
func FormParens(n int) []string {
    if n == 1 { return []string{"()"} }

    var result []string

    maxLength := n*2
    first := (1 << n) - 1
    last := 3 << (maxLength - 3)

    for i := first; i < last; i = i+2 { // Just odd numbers
        candidate := strings.Map(toParentheses, toBinary(i, maxLength))
        if validExpression(candidate) {
            result = append(result, candidate)
        }
    }
    return result
}

func toParentheses(bit rune) rune {
    if bit == '0' {
        return '('
    }
    return ')'
}

func toBinary(value, length int) string {
    result := strconv.FormatInt(int64(value), 2)
    return strings.Repeat("0", length - len(result)) + result
}

func validExpression(expr string) bool {
    open := 0
    closed := 0
    for i := 0; i < len(expr); i++ {
        if expr[i] == '(' {
            open ++
        } else {
            closed ++
        }
        if closed > open {
            return false
        }
    }
    return (open == closed)
}