Last active
April 18, 2016 10:06
-
-
Save dineshba/a74121a855ec05e158f36cb89c76314d to your computer and use it in GitHub Desktop.
Run Length Encoding to understand pattern matching and recursion in Elixir
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#Hi | |
#Lets try to solve the Run Length encoding problem. (Refer Run length encoding here https://en.wikipedia.org/wiki/Run-length_encoding) | |
#[1,1,2,3,3,3,4] => (Run Length Encoder)RLE => [{1,2},2,{3,3},4] | |
#For sake of simplicity, will try to solve like this [1,1,2,3,3,3,4] => RLE => [{1,2},{2, 1},{3,3},{4, 1}] and will optimize it finally. | |
#Lets try to solve incrementally | |
#[] => RLE => [] | |
defmodule RunLengthEncoder do | |
def encode([]), do: [] | |
end | |
#[2] => RLE => [{2, 1}] | |
defmodule RunLengthEncoder do | |
def encode([]), do: [] | |
def encode([h|t]), do: [{h , 1}] | |
end | |
#[1, 1] => RLE => [{1, 2}] | |
defmodule RunLengthEncoder do | |
def encode([]), do: [] | |
def encode([h|t]), do: count(h, t, 1) | |
#Note: In the below line first argument (h) and second argument's head should match to call this function | |
defp count(h, [h|t], counter), do: count(h, t, counter + 1) | |
defp count(h, [], counter), do: [{h, counter}] | |
end | |
#[1, 1, 2] => RLE => [{1, 2}, {2, 1}] | |
defmodule RunLengthEncoder do | |
def encode([]), do: [] | |
def encode([h|t]), do: count(h, t, 1) | |
defp count(h, [h|t], counter), do: count(h, t, counter + 1) | |
defp count(h, [h1|t], counter), do: [{h, counter} | encode([h1 | t])] | |
defp count(h, [], counter), do: [{h, counter}] | |
end | |
#[1, 1, 2] => RLE => [{1, 2}, {2, 1}] | |
defmodule RunLengthEncoder do | |
def encode([]), do: [] | |
def encode([h|t]), do: count(h, t, 1) | |
defp count(h, [h|t], counter), do: count(h, t, counter + 1) | |
defp count(h, [h1|t], 1), do: [h | encode([h1 | t])] | |
defp count(h, [h1|t], counter), do: [{h, counter} | encode([h1 | t])] | |
defp count(h, [], 1), do: [h] | |
defp count(h, [], counter), do: [{h, counter}] | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment