codewars/go/kyu4/strings_mix/k.go

package kata

import (
	"fmt"
	"sort"
	"strings"
	"unicode"
)

type count map[rune]int

func (c count) String() (s string) {
	var sl []string
	for r := 'a'; r <= 'z'; r++ {
		n, ok := c[r]
		if ok {
			sl = append(sl, fmt.Sprintf("%c: %d", r, n))
		}
	}
	s = "[" + strings.Join(sl, ", ") + "]"
	return s
}

func (c count) ascending() []string {
	res := make([]string, len(c))
	i := 0
	for r, n := range c {
		res[i] = string(rune(n)) + string(r)
		i++
	}
	sort.Strings(res)
	return res
}

func newCount() count {
	c := make(count, 26)
	for r := 'a'; r <= 'z'; r++ {
		c[r] = 0
	}
	return c
}


func (c count) ingest(s string) {
	// Count letters.
	for _, r := range s {
		if unicode.IsLower(r) {
			c[r]++
		}
	}

	// Remove non-repeated letters and order.
	for r := 'a'; r <= 'z'; r++ {
		occurrences := c[r]
		if occurrences <= 1 {
			delete(c, r)
			continue
		}
	}
}

type hitList map[int]count

func (h hitList) descendingKeys() []int {
	keys:= make([]int, len(h))
	i := 0
	for k := range h {
		keys[i] = k
		i++
	}
	sort.Sort(sort.Reverse(sort.IntSlice(keys)))
	return keys
}

func (h hitList) String() string {
	var sl []string
	for n, c := range h {
		sl = append(sl, fmt.Sprintf("%d: %s", n, c))
	}
	res := "[" + strings.Join(sl, ", ") + "]"
	return res
}

// Cull removes from each count entries not at least equal to the one in the other count.
func cull(c1, c2 count) (r1, r2 count) {
	r1, r2 = count{}, count{}
	for r, n1 := range c1 {
		n2, ok := c2[r]
		if !ok || n1 >= n2 {
			r1[r] = n1
		}
	}
	for r, n2 := range c2 {
		n1, ok := c1[r]
		if !ok || n2 >= n1 {
			r2[r] = n2
		}
	}
	return
}

// Invert build an inverse count, assuming already culled counts.
func invert(c1, c2 count) hitList {
	union := hitList{}
	for r, n := range c1 {
		if _, ok := union[n]; !ok {
			union[n] = count{}
		}
		// On the first string, every letter is missing, so just initialize.
		union[n][r] = '1'
	}
	for r, n := range c2 {
		if _, ok := union[n]; !ok {
			union[n] = count{}
		}
		// On any subsequent string, letters may exist or not, so be careful.
		_, ok  := union[n][r]
		if !ok {
			union[n][r] = '2'
		} else {
			union[n][r] = '='
		}
	}
	return union
}

func Mix(s1, s2 string) string {
	c1, c2 := newCount(), newCount()
	c1.ingest(s1)
	c2.ingest(s2)
	c1, c2 = cull(c1, c2)
	union := invert(c1, c2)
	var sl []string
	for _, n := range union.descendingKeys() {
		for _, hits := range union[n].ascending() {
			source, r := hits[0], hits[1]
			sl = append(sl, fmt.Sprintf("%c:%s", source, strings.Repeat(string(r), n)))
		}
	}
	s := strings.Join(sl, "/")
	return s
}