Avatar of paulfioravanti

paulfioravanti's solution

to Run Length Encoding in the Elm Track

Published at Jul 14 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.

Elm Installation

Refer to the Installing Elm page for information about installing elm.

Writing the Code

The first time you start an exercise, you'll need to ensure you have the appropriate dependencies installed. Thankfully, Elm makes that easy for you and will install dependencies when you try to run tests or build the code.

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 is possible to submit an incomplete solution so you can see how others have completed the exercise.

Tests.elm

module Tests exposing (tests)

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


tests : Test
tests =
    describe "RunLengthEncoding"
        [ 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"))
            ]
        ]
module RunLengthEncoding exposing (decode, encode)

import Parser exposing ((|=), Parser, Step)


type alias Encoding =
    { count : Int
    , character : String
    }


encode : String -> String
encode string =
    let
        compress : Encoding -> String
        compress { count, character } =
            case count of
                1 ->
                    character

                _ ->
                    String.fromInt count ++ character
    in
    string
        |> String.split ""
        |> List.foldr tallyEncoding []
        |> List.map compress
        |> String.concat


decode : String -> String
decode string =
    let
        reconstruct : Encoding -> String
        reconstruct { count, character } =
            String.repeat count character
    in
    string
        |> Parser.run encodingsParser
        |> Result.withDefault []
        |> List.map reconstruct
        |> String.concat



-- PRIVATE


tallyEncoding : String -> List Encoding -> List Encoding
tallyEncoding character acc =
    let
        initEncoding : String -> Encoding
        initEncoding char =
            { count = 1, character = char }
    in
    case acc of
        [] ->
            [ initEncoding character ]

        head :: tail ->
            if character == head.character then
                { head | count = head.count + 1 } :: tail

            else
                initEncoding character :: acc


encodingsParser : Parser (List Encoding)
encodingsParser =
    let
        encodingsIterationParser :
            List Encoding
            -> Parser (Step (List Encoding) (List Encoding))
        encodingsIterationParser encodings =
            Parser.oneOf
                [ Parser.succeed
                    (\encoding -> Parser.Loop (encoding :: encodings))
                    |= encodingParser
                , Parser.succeed ()
                    |> Parser.map (\_ -> Parser.Done (List.reverse encodings))
                ]
    in
    Parser.loop [] encodingsIterationParser


encodingParser : Parser Encoding
encodingParser =
    let
        countParser : Parser Int
        countParser =
            Parser.oneOf
                [ Parser.succeed identity
                    |= Parser.int
                , Parser.succeed 1
                ]

        alphaOrSpaceParser : Parser String
        alphaOrSpaceParser =
            let
                isAlphaOrSpace char =
                    Char.isAlpha char || char == ' '
            in
            Parser.chompIf isAlphaOrSpace
                |> Parser.getChompedString
    in
    Parser.succeed Encoding
        |= countParser
        |= alphaOrSpaceParser

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?