Run Length Encoding

Welcome to the second installment of Elixir Quiz. This week we will be tackling a data compression algorigthm, Run Length Encoding.

About Run Length Encoding

Run length encoding is a compression algorithm that takes runs of sequential items in a series of data points, replacing that run with a single instance of the data point and the number of elements in that run.

This compression algorithm can be fairly efficient for some types of data. For example bitmap images can be greatly reduced by using this method, however it would be a poor choice for English language text, since it’s uncommon for a charater to be repeated more than twice. This would be extremely inefficient as most words would double in length, such as horse, which becomes h1o1r1s1e1.

Historically, RLE has been used to encode bitmap images in Windows 3.x. It was not a commonly used format, however it was used as the format of the startup screen. The algorithm is also used by fax machines, since the data they send is largely whitespace with small amounts of text on the page.

The problem

Create a program that takes a single string as input, and returns the run length encoded value.

Given a string of uppercase characters in the range A-Z, replace runs of sequential characters with a single instance of that value preceded by the number of items in the run.

For example, if would take the sequence JJJTTWPPMMMMYYYYYYYYYVVVVVV the output would look like:

3J2T1W2P4M9Y6V

In this instance, we’ve compressed a 27 character string down to 14 characters

How do I enter?

The Run Length Encoding quiz runs from Saturday August 16th 2014 until Friday August 22nd, 2014.

To enter, just complete the problem and post the code to our subreddit. For short solutions, you can put the code directly into your comment in the quiz thread.

For larger solutions, please host your code elsewhere and link to it.

GitHub gists can be useful for hosting your solutions, but anywhere is fine.

Example solutions

After the quiz period ends on August 22nd, I will update this section and talk about some interesting solutions that were posted to our subreddit

FizzBuzz

Welcome to the first ever Elixir Quiz problem. This week we will be tackling the classic interview question, FizzBuzz.

About FizzBuzz

I first heard about this problem several years ago while reading a blog post on Coding Horror. Since then I, as well as many other programmers I am sure, have used the problem to start learning new languages, as code kata, and as interview questions.

The problem is often chosen as an interview question as it is quite simple to implement, either as hand written psudocode or executable code. This makes it a good choice to filter out candidates who have little to no programming experience.

Since some of us will be using Elixir Quiz to take our first steps into the Elixir language, it makes sense to start with something simple and well understood.

The problem

The FizzBuzz problem is fairly straight forward.

Print the numbers from 1 to 100, replacing multiples of 3 with the word Fizz and multiples of 5 with the word Buzz. For numbers that are divisible by 3 and 5, replace the number with the word FizzBuzz.

So for example, 1 to 15 would look like:

1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz

How do I enter?

The FizzBuzz quiz runs from Saturday August 9th 2014 until Friday August 15th, 2014.

To enter, just complete the problem and post the code to our subreddit. For short solutions, you can put the code directly into your comment in the quiz thread.

For larger solutions, please host your code elsewhere and link to it.

GitHub gists can be useful for hosting your solutions, but anywhere is fine.

Example solutions

We got 3 solutions for this problem.

• im_pragdave
• @jlind
• @bennyhallett

Two of the solutions involved pattern matching; Defining a function with 4 separate guard clauses to determine what string should be returned when a number is divisible by 15, 5, 3, or none of those.

def transform(value) when rem(value, 15) == 0, do: "FizzBuzz"
def transform(value) when rem(value, 3) == 0, do: "Fizz"
def transform(value) when rem(value, 5) == 0, do: "Buzz"
def transform(value), do: value

With the transform/1 function defined, both solutions took a range of numbers and mapped it to this function.

def up_to(n) do
  1..n
  |> Enum.to_list
  |> Enum.map(&transform/1)
  |> Enum.join " "
end

The other solution took a different approach, using two cycling Streams, zipping them, and transforming the result into the correct value using Stream.with_index/1.

defmodule FizzBuzz do

  @doc """
  Print the FizzBuzz sequence from 1 to `n`

  ## Example

      iex> FixxBuzz.up_to 20
      1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 Fizz Buzz 16 17 Fizz 19 Buzz
  """

  def up_to(n) do
    fizzbuzz_stream |> Enum.take(n) |> Enum.join |> IO.puts
  end

  @doc """
  Return a stream of FizzBuzz values
  """
  def fizzbuzz_stream do
    threes = Stream.cycle [ nil, nil, "Fizz " ]
    fives  = Stream.cycle [ nil, nil, nil, nil, "Buzz " ]
    Stream.zip(threes, fives) |> Stream.with_index |> Stream.map(&speak/1)
  end

  defp speak({{nil,  nil},  n}), do: "#{n+1} "
  defp speak({{fizz, buzz}, _}), do: "#{fizz}#{buzz}"

end