Skip to content

Instantly share code, notes, and snippets.

@dineshba
Last active April 18, 2016 10:06
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save dineshba/a74121a855ec05e158f36cb89c76314d to your computer and use it in GitHub Desktop.
Save dineshba/a74121a855ec05e158f36cb89c76314d to your computer and use it in GitHub Desktop.
Run Length Encoding to understand pattern matching and recursion in Elixir
#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