From 15bc82acf0e243017464f307b098bf8fa642991d Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Tue, 22 Nov 2022 18:26:18 +0100 Subject: solve run length encoding --- go/run-length-encoding/.exercism/config.json | 32 ++++++++ go/run-length-encoding/.exercism/metadata.json | 1 + go/run-length-encoding/HELP.md | 40 ++++++++++ go/run-length-encoding/README.md | 50 ++++++++++++ go/run-length-encoding/cases_test.go | 89 ++++++++++++++++++++++ go/run-length-encoding/go.mod | 3 + go/run-length-encoding/run_length_encoding.go | 60 +++++++++++++++ go/run-length-encoding/run_length_encoding_test.go | 53 +++++++++++++ 8 files changed, 328 insertions(+) create mode 100644 go/run-length-encoding/.exercism/config.json create mode 100644 go/run-length-encoding/.exercism/metadata.json create mode 100644 go/run-length-encoding/HELP.md create mode 100644 go/run-length-encoding/README.md create mode 100644 go/run-length-encoding/cases_test.go create mode 100644 go/run-length-encoding/go.mod create mode 100644 go/run-length-encoding/run_length_encoding.go create mode 100644 go/run-length-encoding/run_length_encoding_test.go diff --git a/go/run-length-encoding/.exercism/config.json b/go/run-length-encoding/.exercism/config.json new file mode 100644 index 0000000..9c9538f --- /dev/null +++ b/go/run-length-encoding/.exercism/config.json @@ -0,0 +1,32 @@ +{ + "blurb": "Implement run-length encoding and decoding.", + "authors": [ + "MatForsberg" + ], + "contributors": [ + "bitfield", + "ekingery", + "ferhatelmas", + "hilary", + "ilmanzo", + "leenipper", + "sebito91", + "eklatzer" + ], + "files": { + "solution": [ + "run_length_encoding.go" + ], + "test": [ + "run_length_encoding_test.go" + ], + "example": [ + ".meta/example.go" + ], + "editor": [ + "cases_test.go" + ] + }, + "source": "Wikipedia", + "source_url": "https://en.wikipedia.org/wiki/Run-length_encoding" +} diff --git a/go/run-length-encoding/.exercism/metadata.json b/go/run-length-encoding/.exercism/metadata.json new file mode 100644 index 0000000..dd34cf8 --- /dev/null +++ b/go/run-length-encoding/.exercism/metadata.json @@ -0,0 +1 @@ +{"track":"go","exercise":"run-length-encoding","id":"36e9ecb416fc40eaa771f9d3f44c8ef1","url":"https://exercism.org/tracks/go/exercises/run-length-encoding","handle":"dim13","is_requester":true,"auto_approve":false} \ No newline at end of file diff --git a/go/run-length-encoding/HELP.md b/go/run-length-encoding/HELP.md new file mode 100644 index 0000000..30de1a6 --- /dev/null +++ b/go/run-length-encoding/HELP.md @@ -0,0 +1,40 @@ +# Help + +## 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. + +## Submitting your solution + +You can submit your solution using the `exercism submit run_length_encoding.go` command. +This command will upload your solution to the Exercism website and print the solution page's URL. + +It's possible to submit an incomplete solution which allows you to: + +- See how others have completed the exercise +- Request help from a mentor + +## Need to get help? + +If you'd like help solving the exercise, check the following pages: + +- The [Go track's documentation](https://exercism.org/docs/tracks/go) +- [Exercism's programming category on the forum](https://forum.exercism.org/c/programming/5) +- The [Frequently Asked Questions](https://exercism.org/docs/using/faqs) + +Should those resources not suffice, you could submit your (incomplete) solution to request mentoring. + +To get help if you're having trouble, you can use one of the following resources: + +- [How to Write Go Code](https://golang.org/doc/code.html) +- [Effective Go](https://golang.org/doc/effective_go.html) +- [Go Resources](http://golang.org/help) +- [StackOverflow](http://stackoverflow.com/questions/tagged/go) \ No newline at end of file diff --git a/go/run-length-encoding/README.md b/go/run-length-encoding/README.md new file mode 100644 index 0000000..c48d31f --- /dev/null +++ b/go/run-length-encoding/README.md @@ -0,0 +1,50 @@ +# Run-Length Encoding + +Welcome to Run-Length Encoding on Exercism's Go Track. +If you need help running the tests or submitting your code, check out `HELP.md`. + +## Instructions + +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. + +```text +"WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB" -> "12WB12W3B24WB" +``` + +RLE allows the original data to be perfectly reconstructed from +the compressed data, which makes it a lossless data compression. + +```text +"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. + +## Source + +### Created by + +- @MatForsberg + +### Contributed to by + +- @bitfield +- @ekingery +- @ferhatelmas +- @hilary +- @ilmanzo +- @leenipper +- @sebito91 +- @eklatzer + +### Based on + +Wikipedia - https://en.wikipedia.org/wiki/Run-length_encoding \ No newline at end of file diff --git a/go/run-length-encoding/cases_test.go b/go/run-length-encoding/cases_test.go new file mode 100644 index 0000000..38266e9 --- /dev/null +++ b/go/run-length-encoding/cases_test.go @@ -0,0 +1,89 @@ +package encode + +// This is an auto-generated file. Do not change it manually. Run the generator to update the file. +// See https://github.com/exercism/go#synchronizing-tests-and-instructions +// Source: exercism/problem-specifications +// Commit: a757698 run-length-encoding: 'lower case' -> 'lowercase' (#1708) + +type testCase struct { + description string + input string + expected string +} + +// run-length encode a string +var encodeTests = []testCase{ + { + description: "empty string", + input: "", + expected: "", + }, + { + description: "single characters only are encoded without count", + input: "XYZ", + expected: "XYZ", + }, + { + description: "string with no single characters", + input: "AABBBCCCC", + expected: "2A3B4C", + }, + { + description: "single characters mixed with repeated characters", + input: "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB", + expected: "12WB12W3B24WB", + }, + { + description: "multiple whitespace mixed in string", + input: " hsqq qww ", + expected: "2 hs2q q2w2 ", + }, + { + description: "lowercase characters", + input: "aabbbcccc", + expected: "2a3b4c", + }, +} + +// run-length decode a string +var decodeTests = []testCase{ + { + description: "empty string", + input: "", + expected: "", + }, + { + description: "single characters only", + input: "XYZ", + expected: "XYZ", + }, + { + description: "string with no single characters", + input: "2A3B4C", + expected: "AABBBCCCC", + }, + { + description: "single characters with repeated characters", + input: "12WB12W3B24WB", + expected: "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB", + }, + { + description: "multiple whitespace mixed in string", + input: "2 hs2q q2w2 ", + expected: " hsqq qww ", + }, + { + description: "lowercase string", + input: "2a3b4c", + expected: "aabbbcccc", + }, +} + +// encode and then decode +var encodeDecodeTests = []testCase{ + { + description: "encode followed by decode gives original string", + input: "zzz ZZ zZ", + expected: "zzz ZZ zZ", + }, +} diff --git a/go/run-length-encoding/go.mod b/go/run-length-encoding/go.mod new file mode 100644 index 0000000..6689746 --- /dev/null +++ b/go/run-length-encoding/go.mod @@ -0,0 +1,3 @@ +module encode + +go 1.16 diff --git a/go/run-length-encoding/run_length_encoding.go b/go/run-length-encoding/run_length_encoding.go new file mode 100644 index 0000000..07fdcd9 --- /dev/null +++ b/go/run-length-encoding/run_length_encoding.go @@ -0,0 +1,60 @@ +package encode + +import ( + "fmt" + "strings" +) + +func encodeLength(s string) (n int) { + var last rune + for _, c := range s { + if last == 0 { + last = c + } + if c != last { + break + } + n++ + } + return n +} + +func RunLengthEncode(input string) string { + var s strings.Builder + for len(input) != 0 { + n := encodeLength(input) + if n == 1 { + fmt.Fprintf(&s, "%c", input[0]) + } else { + fmt.Fprintf(&s, "%d%c", n, input[0]) + } + input = input[n:] + } + return s.String() +} + +func decodeLength(s string) (number, count int) { + for _, c := range s { + if c >= '0' && c <= '9' { + number *= 10 + number += int(c) - '0' + count++ + } else { + break + } + } + if number == 0 { + number = 1 + } + return number, count +} + +func RunLengthDecode(input string) string { + var s strings.Builder + for len(input) > 0 { + n, c := decodeLength(input) + s.WriteString(strings.Repeat(string(input[c]), n)) + input = input[c+1:] + } + return s.String() +} diff --git a/go/run-length-encoding/run_length_encoding_test.go b/go/run-length-encoding/run_length_encoding_test.go new file mode 100644 index 0000000..2440d65 --- /dev/null +++ b/go/run-length-encoding/run_length_encoding_test.go @@ -0,0 +1,53 @@ +package encode + +import "testing" + +func TestRunLengthEncode(t *testing.T) { + for _, tc := range encodeTests { + t.Run(tc.description, func(t *testing.T) { + if actual := RunLengthEncode(tc.input); actual != tc.expected { + t.Errorf("RunLengthEncode(%q) = %q, want:%q", tc.input, actual, tc.expected) + } + }) + } +} +func TestRunLengthDecode(t *testing.T) { + for _, tc := range decodeTests { + t.Run(tc.description, func(t *testing.T) { + if actual := RunLengthDecode(tc.input); actual != tc.expected { + t.Errorf("RunLengthDecode(%q) = %q, want:%q", tc.input, actual, tc.expected) + } + }) + } +} +func TestRunLengthEncodeDecode(t *testing.T) { + for _, tc := range encodeDecodeTests { + t.Run(tc.description, func(t *testing.T) { + if actual := RunLengthDecode(RunLengthEncode(tc.input)); actual != tc.expected { + t.Errorf("RunLengthDecode(RunLengthEncode(%q)) = %q, want:%q", tc.input, actual, tc.expected) + } + }) + } +} + +func BenchmarkRunLengthEncode(b *testing.B) { + if testing.Short() { + b.Skip("skipping benchmark in short mode.") + } + for i := 0; i < b.N; i++ { + for _, test := range encodeTests { + RunLengthEncode(test.input) + } + } +} + +func BenchmarkRunLengthDecode(b *testing.B) { + if testing.Short() { + b.Skip("skipping benchmark in short mode.") + } + for i := 0; i < b.N; i++ { + for _, test := range decodeTests { + RunLengthDecode(test.input) + } + } +} -- cgit v1.2.3