Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 261
Good morning! Here's your coding interview problem for today.

This problem was asked by Amazon.

Huffman coding is a method of encoding characters based on their frequency. Each letter is assigned a variable-length binary string, such as 0101 or 111110, where shorter lengths correspond to more common letters. To accomplish this, a binary tree is built such that the path from the root to any leaf uniquely maps to a character. When traversing the path, descending to a left child corresponds to a 0 in the prefix, while descending right corresponds to 1.

Here is an example tree (note that only the leaf nodes have letters):
```
        *
      /   \
    *       *
   / \     / \
  *   a   t   *
 /             \
c               s
```
With this encoding, cats would be represented as `0000110111`.

Given a dictionary of character frequencies, build a Huffman tree, and use it to determine a mapping between characters and their encoded binary strings.

Pull request:
Day261
Resolves #534.

Patch:
diff --git a/README.md b/README.md
index 68457b0..57cc65e 100644
--- a/README.md
+++ b/README.md
@@ -272,6 +272,7 @@ problems from
 * [Day 258](https://github.com/vaskoz/dailycodingproblem-go/issues/530)
 * [Day 259](https://github.com/vaskoz/dailycodingproblem-go/issues/531)
 * [Day 260](https://github.com/vaskoz/dailycodingproblem-go/issues/533)
+* [Day 261](https://github.com/vaskoz/dailycodingproblem-go/issues/534)
 * [Day 263](https://github.com/vaskoz/dailycodingproblem-go/issues/539)
 * [Day 266](https://github.com/vaskoz/dailycodingproblem-go/issues/542)
 * [Day 267](https://github.com/vaskoz/dailycodingproblem-go/issues/543)
diff --git a/day261/problem.go b/day261/problem.go
new file mode 100644
index 0000000..1a096be
--- /dev/null
+++ b/day261/problem.go
@@ -0,0 +1,121 @@
+package day261
+
+import (
+	"container/heap"
+	"errors"
+	"strings"
+)
+
+var errTranslate = errors.New("could not be translated")
+
+// ErrTranslate is returned if there is a problem with compressing or decompressing.
+func ErrTranslate() error {
+	return errTranslate
+}
+
+// Huffman is a huffman tree that can encode/decode.
+type Huffman interface {
+	Encode(string) (string, error)
+	Decode(string) (string, error)
+}
+
+type huffman struct {
+	Freq        int
+	Leaf        bool
+	R           rune
+	Left, Right *huffman
+}
+
+func dfsBuildCodeMap(h *huffman, codeMap map[rune]string, path string) map[rune]string {
+	if h.Leaf {
+		codeMap[h.R] = path
+		return codeMap
+	}
+	codeMap = dfsBuildCodeMap(h.Left, codeMap, path+"0")
+	codeMap = dfsBuildCodeMap(h.Right, codeMap, path+"1")
+	return codeMap
+}
+
+func buildCodeMap(h *huffman) map[rune]string {
+	return dfsBuildCodeMap(h, make(map[rune]string), "")
+}
+
+func (h *huffman) Encode(s string) (string, error) {
+	var sb strings.Builder
+	codeMap := buildCodeMap(h)
+	for _, r := range s {
+		prefix, found := codeMap[r]
+		if !found {
+			return s, errTranslate
+		}
+		sb.WriteString(prefix)
+	}
+	return sb.String(), nil
+}
+
+func (h *huffman) Decode(s string) (string, error) {
+	var sb strings.Builder
+	root := h
+	for _, r := range s {
+		switch r {
+		case '0':
+			if root.Leaf {
+				sb.WriteRune(root.R)
+				root = h
+			}
+			root = root.Left
+
+		case '1':
+			if root.Leaf {
+				sb.WriteRune(root.R)
+				root = h
+			}
+			root = root.Right
+		}
+	}
+	if root.Leaf {
+		sb.WriteRune(root.R)
+		return sb.String(), nil
+	}
+	return s, errTranslate
+}
+
+type minHeap []*huffman
+
+func (mh minHeap) Len() int { return len(mh) }
+
+func (mh minHeap) Less(i, j int) bool {
+	return mh[i].Freq < mh[j].Freq
+}
+
+func (mh minHeap) Swap(i, j int) {
+	mh[i], mh[j] = mh[j], mh[i]
+}
+
+func (mh *minHeap) Push(x interface{}) {
+	item := x.(*huffman)
+	*mh = append(*mh, item)
+}
+
+func (mh *minHeap) Pop() interface{} {
+	old := *mh
+	n := len(old)
+	item := old[n-1]
+	*mh = old[0 : n-1]
+	return item
+}
+
+// NewHuffman returns a new Huffman tree.
+func NewHuffman(freq map[rune]int) Huffman {
+	mh := make(minHeap, 0, len(freq))
+	for r, count := range freq {
+		heap.Push(&mh, &huffman{Freq: count, R: r, Leaf: true})
+	}
+	for mh.Len() > 1 {
+		one := heap.Pop(&mh).(*huffman)
+		two := heap.Pop(&mh).(*huffman)
+		parent := &huffman{Freq: one.Freq + two.Freq, Left: one, Right: two}
+		mh.Push(parent)
+	}
+	return mh.Pop().(*huffman)
+}


Test patch:
diff --git a/day261/problem_test.go b/day261/problem_test.go
new file mode 100644
index 0000000..1409542
--- /dev/null
+++ b/day261/problem_test.go
@@ -0,0 +1,73 @@
+package day261
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	freq       map[rune]int
+	decoded    []string
+	decodedErr []error
+	encoded    []string
+	encodedErr []error
+}{
+	{
+		freq: map[rune]int{
+			'c': 1,
+			's': 2,
+			'a': 10,
+			't': 11,
+		},
+		decoded:    []string{"cats"},
+		decodedErr: []error{nil},
+		encoded:    []string{"110100111"},
+		encodedErr: []error{nil},
+	},
+	{
+		freq: map[rune]int{
+			'c': 1,
+			's': 2,
+			'a': 10,
+			't': 11,
+		},
+		decoded:    []string{"dogs"},
+		decodedErr: []error{ErrTranslate()},
+		encoded:    []string{"dogs"},
+		encodedErr: []error{ErrTranslate()},
+	},
+}
+
+func TestHuffmanEncode(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		h := NewHuffman(tc.freq)
+		for i := range tc.decoded {
+			if encode, err := h.Encode(tc.decoded[i]); err != tc.encodedErr[i] || encode != tc.encoded[i] {
+				t.Errorf("Given %v, expected (%v,%v), got (%v,%v)", tc.decoded[i], tc.encoded[i], tc.encodedErr[i], encode, err)
+			}
+		}
+	}
+}
+
+func TestHuffmanDecode(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		h := NewHuffman(tc.freq)
+		for i := range tc.encoded {
+			if decode, err := h.Decode(tc.encoded[i]); err != tc.decodedErr[i] || decode != tc.decoded[i] {
+				t.Errorf("Given %v, expected (%v,%v), got (%v,%v)", tc.encoded[i], tc.decoded[i], tc.decodedErr[i], decode, err)
+			}
+		}
+	}
+}
+
+func BenchmarkHuffman(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			h := NewHuffman(tc.freq)
+			for i := range tc.decoded {
+				h.Encode(tc.decoded[i]) // nolint
+				h.Decode(tc.encoded[i]) // nolint
+			}
+		}
+	}
+}