Exercism v3 launches on Sept 1st 2021. Learn more! 🚀🚀🚀
Avatar of rootulp

rootulp's solution

to Run Length Encoding in the TypeScript Track

Published at Mar 10 2019 · 0 comments
Instructions
Test suite
Solution

Note:

This exercise has changed since this solution 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.

Setup

Go through the setup instructions for TypeScript to install the necessary dependencies:

http://exercism.io/languages/typescript

Requirements

Install assignment dependencies:

$ yarn install

Making the test suite pass

Execute the tests with:

$ yarn test

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.

run-length-encoding.test.ts

import RunLengthEncoding from './run-length-encoding'

describe('run-length encode a string', () => {
    it('empty string', () => {
        const expected = ''
        expect(RunLengthEncoding.encode('')).toEqual(expected)
    })

    it('single characters only are encoded without count', () => {
        const expected = 'XYZ'
        expect(RunLengthEncoding.encode('XYZ')).toEqual(expected)
    })

    it('string with no single characters', () => {
        const expected = '2A3B4C'
        expect(RunLengthEncoding.encode('AABBBCCCC')).toEqual(expected)
    })

    it('single characters mixed with repeated characters', () => {
        const expected = '12WB12W3B24WB'
        expect(RunLengthEncoding.encode('WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB')).toEqual(expected)
    })

    it('multiple whitespace mixed in string', () => {
        const expected = '2 hs2q q2w2 '
        expect(RunLengthEncoding.encode('  hsqq qww  ')).toEqual(expected)
    })

    it('lowercase characters', () => {
        const expected = '2a3b4c'
        expect(RunLengthEncoding.encode('aabbbcccc')).toEqual(expected)
    })
})

describe('run-length decode a string', () => {
    it('empty string', () => {
        const expected = ''
        expect(RunLengthEncoding.decode('')).toEqual(expected)
    })

    it('single characters only', () => {
        const expected = 'XYZ'
        expect(RunLengthEncoding.decode('XYZ')).toEqual(expected)
    })

    it('string with no single characters', () => {
        const expected = 'AABBBCCCC'
        expect(RunLengthEncoding.decode('2A3B4C')).toEqual(expected)
    })

    it('single characters with repeated characters', () => {
        const expected = 'WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB'
        expect(RunLengthEncoding.decode('12WB12W3B24WB')).toEqual(expected)
    })

    it('multiple whitespace mixed in string', () => {
        const expected = '  hsqq qww  '
        expect(RunLengthEncoding.decode('2 hs2q q2w2 ')).toEqual(expected)
    })

    it('lower case string', () => {
        const expected = 'aabbbcccc'
        expect(RunLengthEncoding.decode('2a3b4c')).toEqual(expected)
    })
})

describe('encode and then decode', () => {
    it('encode followed by decode gives original string', () => {
        expect(RunLengthEncoding.decode(RunLengthEncoding.encode('zzz ZZ  zZ'))).toEqual('zzz ZZ  zZ')
    })
})
import {last, isUndefined, startsWith, concat, slice, repeat} from "lodash"

export default class RunLengthEncoding {
    static encode(data: string): string {
        const chunks: string[] = RunLengthEncoding.splitIntoChunks(data)
        return chunks.map(RunLengthEncoding.encodeChunk).join('')
    }

    static decode(encodedData: string): string {
        const encodedChunks: string[] = RunLengthEncoding.splitIntoEncodedChunks(encodedData)
        return encodedChunks.map(RunLengthEncoding.decodeChunk).join('')
    }

    static splitIntoChunks(data: string): string[] {
        return data.split("").reduce((chunks: string[], currentCharacter: string) => {
            const lastChunkOfConsecutiveCharacters: string | undefined = last(chunks)

            if (!isUndefined(lastChunkOfConsecutiveCharacters) && startsWith(lastChunkOfConsecutiveCharacters, currentCharacter)) {
                return concat(slice(chunks, 0, -1), last(chunks) + currentCharacter)
            } else {
                return concat(chunks, currentCharacter)
            }
        }, [])
    }

    static splitIntoEncodedChunks(encodedData: string): string[] {
        const digitsFollowedByData = new RegExp(/(\d*\D{1})/g)
        const encodedChunk = encodedData.match(digitsFollowedByData)
        return encodedChunk ? encodedChunk : []
    }

    static decodeChunk(encodedChunk: string): string {
        if (encodedChunk.length === 1) {
            return encodedChunk
        } else {
            const numOccurences = parseInt(encodedChunk.slice(0, -1), 10)
            const data = encodedChunk.slice(-1)
            return repeat(data, numOccurences)
        }
    }

    static encodeChunk(chunk: string): string {
        if (chunk.length === 1) {
            return chunk
        } else {
            return `${chunk.length}${chunk.charAt(0)}`
        }
    }
}

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?