Exercism v3 launches on Sept 1st 2021. Learn more! ๐Ÿš€๐Ÿš€๐Ÿš€
Avatar of rootulp

rootulp's solution

to Run Length Encoding in the Elm Track

Published at Jul 13 2018 · 0 comments
Instructions
Test suite
Solution

Note:

This solution was written on an old version of Exercism. The tests below might not correspond to the solution code, and the exercise may have changed since this code was written.

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.

Elm Installation

Refer to the Exercism help page for Elm installation and learning resources.

Writing the Code

The first time you start an exercise, you'll need to ensure you have the appropriate dependencies installed.

$ elm-package install --yes

Execute the tests with:

$ elm-test

Automatically run tests again when you save changes:

$ elm-test --watch

As you work your way through the test suite, be sure to remove the skip <| calls from each test until you get them all passing!

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.

Tests.elm

module Tests exposing (..)

import Expect
import RunLengthEncoding exposing (decode, encode, version)
import Test exposing (..)


tests : Test
tests =
    describe "RunLengthEncoding"
        [ test "the solution is for the correct version of the test" <|
            \() -> Expect.equal 2 version
        , describe "run-length encode a string"
            [ test "empty string" <|
                \() -> Expect.equal "" (encode "")
            , skip <|
                test "single characters only are encoded without count" <|
                    \() -> Expect.equal "XYZ" (encode "XYZ")
            , skip <|
                test "string with no single characters" <|
                    \() -> Expect.equal "2A3B4C" (encode "AABBBCCCC")
            , skip <|
                test "single characters mixed with repeated characters" <|
                    \() ->
                        Expect.equal "12WB12W3B24WB"
                            (encode "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB")
            , skip <|
                test "multiple whitespace mixed in string" <|
                    \() -> Expect.equal "2 hs2q q2w2 " (encode "  hsqq qww  ")
            , skip <|
                test "lowercase characters" <|
                    \() -> Expect.equal "2a3b4c" (encode "aabbbcccc")
            ]
        , describe "run-length decode a string"
            [ skip <|
                test "empty string" <|
                    \() -> Expect.equal "" (decode "")
            , skip <|
                test "single characters only" <|
                    \() -> Expect.equal "XYZ" (decode "XYZ")
            , skip <|
                test "string with no single characters" <|
                    \() -> Expect.equal "AABBBCCCC" (decode "2A3B4C")
            , skip <|
                test "single characters with repeated characters" <|
                    \() ->
                        Expect.equal "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB"
                            (decode "12WB12W3B24WB")
            , skip <|
                test "multiple whitespace mixed in string" <|
                    \() -> Expect.equal "  hsqq qww  " (decode "2 hs2q q2w2 ")
            , skip <|
                test "lower case string" <|
                    \() -> Expect.equal "" (decode "")
            , skip <|
                test "with a x10 value" <|
                    \() ->
                        Expect.equal "WWWWWWWWWW"
                            (decode "10W")
            ]
        , describe "encode and then decode"
            [ skip <|
                test "encode followed by decode gives original string" <|
                    \() ->
                        Expect.equal "zzz ZZ  zZ"
                            (decode (encode "zzz ZZ  zZ"))
            ]
        ]

elm-package.json

{
    "version": "3.0.0",
    "summary": "Exercism problems in Elm.",
    "repository": "https://github.com/exercism/elm.git",
    "license": "BSD3",
    "source-directories": [
        ".",
        ".."
    ],
    "exposed-modules": [],
    "dependencies": {
        "elm-lang/core": "5.0.0 <= v < 6.0.0",
        "elm-community/elm-test": "4.0.0 <= v < 5.0.0"
    },
    "elm-version": "0.18.0 <= v < 0.19.0"
}
module RunLengthEncoding exposing (..)
import Maybe
import Char
import Tuple

encode: String -> String
encode data =
  data
    |> String.toList
    |> List.foldr splitRuns []
    |> List.map encodeRun
    |> String.join ""

decode: String -> String
decode data =
  data
    |> String.toList
    |> List.foldr splitRuns []
    |> List.map decodeRun
    |> String.join ""

splitRuns: (Char -> List String -> List String)
splitRuns value runs =
  if runBoundary value runs then
    startNewRun value runs
  else
    addValueToExistingRun value runs

runBoundary: Char -> List String -> Bool
runBoundary value runs =
  not (Char.isDigit value || -- during decode
  valueInPreviousRun value runs) -- during encode

startNewRun: Char -> List String -> List String
startNewRun value runs =
  String.fromChar value :: runs

valueInPreviousRun: Char -> List String -> Bool
valueInPreviousRun value runs =
  previousRun runs
   |> String.contains (String.fromChar value)

addValueToExistingRun: Char -> List String -> List String
addValueToExistingRun value runs =
  appendValueToPreviousRun value runs :: restOfRuns runs

appendValueToPreviousRun: Char -> List String -> String
appendValueToPreviousRun value runs =
  runs
    |> previousRun
    |> String.cons value

encodeRun: String -> String
encodeRun run =
    run
      |> String.left 1
      |> String.append (calculateRunLength run)

decodeRun: String -> String
decodeRun run =
  run
    |> splitIntoLengthAndValue
    |> expand

splitIntoLengthAndValue: String -> (Int, String)
splitIntoLengthAndValue run =
  run
    |> String.toList
    |> List.partition Char.isDigit
    |> Tuple.mapFirst convertRunLength
    |> Tuple.mapSecond String.fromList

expand: (Int, String) -> String
expand (length, value) =
  String.repeat length value

convertRunLength: List Char -> Int
convertRunLength runLength =
  runLength
    |> String.fromList
    |> String.toInt
    |> Result.withDefault 1

calculateRunLength: String -> String
calculateRunLength run =
  let runLength = String.length run in
    if runLength == 1 then "" else toString runLength

previousRun: List String -> String
previousRun runs =
  runs
    |> List.head
    |> Maybe.withDefault ""

restOfRuns: List String -> List String
restOfRuns runs =
  runs
    |> List.tail
    |> Maybe.withDefault []

version : Int
version =
  2

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?