Avatar of mstranger

mstranger's solution

to Run Length Encoding in the Go Track

Published at Apr 19 2019 · 0 comments
Instructions
Test suite
Solution

Implement run-length encoding and decoding.

Run-length encoding (RLE) is a simple form of data compression, where runs (consecutive data elements) are replaced by just one data value and count.

For example we can represent the original 53 characters with only 13.

"WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB"  ->  "12WB12W3B24WB"

RLE allows the original data to be perfectly reconstructed from the compressed data, which makes it a lossless data compression.

"AABCCCDEEEE"  ->  "2AB3CD4E"  ->  "AABCCCDEEEE"

For simplicity, you can assume that the unencoded string will only contain the letters A through Z (either lower or upper case) and whitespace. This way data to be encoded will never contain any numbers and numbers inside data to be decoded always represent the count for the following character.

Running the tests

To run the tests run the command go test from within the exercise directory.

If the test suite contains benchmarks, you can run these with the --bench and --benchmem flags:

go test -v --bench . --benchmem

Keep in mind that each reviewer will run benchmarks on a different machine, with different specs, so the results from these benchmark tests may vary.

Further information

For more detailed information about the Go track, including how to get help if you're having trouble, please visit the exercism.io Go language page.

Source

Wikipedia https://en.wikipedia.org/wiki/Run-length_encoding

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

cases_test.go

package encode

// Source: exercism/problem-specifications
// Commit: 1b7900e run-length-encoding: apply "input" policy
// Problem Specifications Version: 1.1.0

// run-length encode a string
var encodeTests = []struct {
	input       string
	expected    string
	description string
}{
	{"", "", "empty string"},
	{"XYZ", "XYZ", "single characters only are encoded without count"},
	{"AABBBCCCC", "2A3B4C", "string with no single characters"},
	{"WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB", "12WB12W3B24WB", "single characters mixed with repeated characters"},
	{"  hsqq qww  ", "2 hs2q q2w2 ", "multiple whitespace mixed in string"},
	{"aabbbcccc", "2a3b4c", "lowercase characters"},
}

// run-length decode a string
var decodeTests = []struct {
	input       string
	expected    string
	description string
}{
	{"", "", "empty string"},
	{"XYZ", "XYZ", "single characters only"},
	{"2A3B4C", "AABBBCCCC", "string with no single characters"},
	{"12WB12W3B24WB", "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB", "single characters with repeated characters"},
	{"2 hs2q q2w2 ", "  hsqq qww  ", "multiple whitespace mixed in string"},
	{"2a3b4c", "aabbbcccc", "lower case string"},
}

// encode and then decode
var encodeDecodeTests = []struct {
	input       string
	expected    string
	description string
}{
	{"zzz ZZ  zZ", "zzz ZZ  zZ", "encode followed by decode gives original string"},
}

run_length_encoding_test.go

package encode

import "testing"

func TestRunLengthEncode(t *testing.T) {
	for _, test := range encodeTests {
		if actual := RunLengthEncode(test.input); actual != test.expected {
			t.Errorf("FAIL %s - RunLengthEncode(%s) = %q, expected %q.",
				test.description, test.input, actual, test.expected)
		}
		t.Logf("PASS RunLengthEncode - %s", test.description)
	}
}
func TestRunLengthDecode(t *testing.T) {
	for _, test := range decodeTests {
		if actual := RunLengthDecode(test.input); actual != test.expected {
			t.Errorf("FAIL %s - RunLengthDecode(%s) = %q, expected %q.",
				test.description, test.input, actual, test.expected)
		}
		t.Logf("PASS RunLengthDecode - %s", test.description)
	}
}
func TestRunLengthEncodeDecode(t *testing.T) {
	for _, test := range encodeDecodeTests {
		if actual := RunLengthDecode(RunLengthEncode(test.input)); actual != test.expected {
			t.Errorf("FAIL %s - RunLengthDecode(RunLengthEncode(%s)) = %q, expected %q.",
				test.description, test.input, actual, test.expected)
		}
		t.Logf("PASS %s", test.description)
	}
}
package encode

import (
	"strconv"
	"strings"
	"unicode"
)

// RunLengthEncode replaces consecutive data elements by just one data
// value and count ("wwwbba" -> "3w2ba")
func RunLengthEncode(input string) string {
	var output string
	var i, j int

	for ; i < len(input); i += j {
		// find count number
		for j = 0; i+j < len(input) && input[i] == input[i+j]; j++ {
		}

		chunck := input[i : i+j]

		if len(chunck) > 1 {
			s := strconv.Itoa(len(chunck)) + chunck[0:1]
			output += s
		} else {
			output += chunck
		}
	}

	return output
}

// RunLengthDecode replaces count and value by consecutive data elements
// ("3w2ba" -> "wwwbba")
func RunLengthDecode(input string) string {
	var output string
	var j int

	for i := 0; i < len(input); {
		if unicode.IsNumber(rune(input[i])) {
			// find numuber chunck
			for j = 0; i+j < len(input)-1 && unicode.IsNumber(rune(input[j+i])); j++ {
			}

			// convert to int and ignore all errors
			n, _ := strconv.Atoi(input[i : i+j])

			// because 3ba and b should be skipped
			i += j + 1
			output += strings.Repeat(string(input[i-1]), n)
		} else {
			output += input[i : i+1]
			i++
		}
	}

	return output
}

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?