Skip to content

Instantly share code, notes, and snippets.

@bfcoder
Created March 1, 2017 16:41
Show Gist options
  • Save bfcoder/8481d378efdee4b2a9c4c4a0f866344d to your computer and use it in GitHub Desktop.
Save bfcoder/8481d378efdee4b2a9c4c4a0f866344d to your computer and use it in GitHub Desktop.

Run Length Encoding

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"

If the string contains any whitespace, it should be passed through unchanged:

"aabc dddef"  ->  "2abc 3def"

For simplicity, you can assume that the unencoded string will only contain the letters A through Z (either lower or uppercase) and whitespace.


For installation and learning resources, refer to the exercism help page.

For running the tests provided, you will need the Minitest gem. Open a terminal window and run the following command to install minitest:

gem install minitest

If you would like color output, you can require 'minitest/pride' in the test file, or note the alternative instruction, below, for running the test file.

In order to run the test, you can run the test file from the exercise directory. For example, if the test suite is called hello_world_test.rb, you can run the following command:

ruby hello_world_test.rb

To include color from the command line:

ruby -r minitest/pride hello_world_test.rb

The test files may have the execution bit set so you may also be able to run it like this:

./hello_world_test.rb

Source

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

Submitting Incomplete Problems

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

require "strscan"
class RunLengthEncoding
def self.encode(input)
reference = input.squeeze
input_scanner = StringScanner.new input
reference_scanner = StringScanner.new reference
output = ""
loop do
break if reference_scanner.eos?
ref = reference_scanner.getch
length = input_scanner.scan(/#{ref}+/).length
output << "#{length > 1 ? length : ''}#{ref}"
end
output
end
def self.decode(input)
scanner = StringScanner.new input
output = ""
loop do
break if scanner.eos?
scanned = scanner.scan_until(/[^0-9]/)
if scanned.length > 1
scanned.to_i.times { output << scanner.matched }
else
output << scanner.matched
end
end
output
end
end
module BookKeeping
VERSION = 2
end
#!/usr/bin/env ruby
# encoding: utf-8
gem "minitest", ">= 5.0.0"
require "minitest/autorun"
require_relative "run_length_encoding"
require "byebug"
# Test data version:
# deb225e Implement canonical dataset for scrabble-score problem (#255)
class RunLengthEncodingTest < Minitest::Test
def test_encode_simple
input = "AABBBCCCC"
output = "2A3B4C"
assert_equal output, RunLengthEncoding.encode(input)
end
def test_decode_simple
input = "2A3B4C"
output = "AABBBCCCC"
assert_equal output, RunLengthEncoding.decode(input)
end
def test_encode_with_single_values
input = "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB"
output = "12WB12W3B24WB"
assert_equal output, RunLengthEncoding.encode(input)
end
def test_decode_with_single_values
input = "12WB12W3B24WB"
output = "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB"
assert_equal output, RunLengthEncoding.decode(input)
end
def test_decode_encode_combination
input = "zzz ZZ zZ"
output = "zzz ZZ zZ"
assert_equal output,
RunLengthEncoding.decode(RunLengthEncoding.encode(input))
end
def test_encode_unicode
input = "⏰⚽⚽⚽⭐⭐⏰"
output = "⏰3⚽2⭐⏰"
assert_equal output, RunLengthEncoding.encode(input)
end
def test_decode_unicode
input = "⏰3⚽2⭐⏰"
output = "⏰⚽⚽⚽⭐⭐⏰"
assert_equal output, RunLengthEncoding.decode(input)
end
# Problems in exercism evolve over time, as we find better ways to ask
# questions.
# The version number refers to the version of the problem you solved,
# not your solution.
#
# Define a constant named VERSION inside of the top level BookKeeping
# module.
# In your file, it will look like this:
#
# module BookKeeping
# VERSION = 1 # Where the version number matches the one in the test.
# end
#
# If you are curious, read more about constants on RubyDoc:
# http://ruby-doc.org/docs/ruby-doc-bundle/UsersGuide/rg/constants.html
def test_bookkeeping
assert_equal 2, BookKeeping::VERSION
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment