Instantly share code, notes, and snippets.

# pragdave/00-question.mdSecret Last active Jun 29, 2019

«tutor»:e4p~basic-processes~fib

If you're up for a challenge…

The classic Fibonacci implementation is

```def fib(0), 0
def fib(1), 1
def fib(n), fib(n-1) + fib(n-2)```

This has a worst case performance of \( O( 1.6^{n+1} ) \). For large \( n \), this is a big number (20 digits or so long for \( n = 100 \)). This means it is slow, and it burns through stack space at an alarming rate.

However, you can make the function perform in linear time by implementing a simple cache. An Elixir map is a good data structure for this. Initialize it with `%{ 0 => 0, 1 => 1 }`, and add new values to it as you discover them.

Write a module that implements the cache. It should use an agent, and that agent's state should be the map.

Then write a Fibonacci module that uses this cache.

Try calculating `fib(100)`. If it comes back without crashing your machine, and before the sun has expanded to consume the Earth, then your cache worked...

 defmodule Cache do @moduledoc """ We implement a simple key/value cache. State is stored in an Agent, in the form of a map. The function `lookup` tries to look the value up in the cache, and then calls `complete_if_not_found`. This takes two forms. If there was no value in the cache, it calls the function passed in by the client to supply it, updating the cache at the same time. Otherwise, it simply returns the cached value. """ @doc """ Start the cache, run the supplied function, then stop the cache. Eventually we'll be able to do better than this. """ def run(body) do { :ok, pid } = Agent.start_link(fn -> %{ 0 => 0, 1 => 1 } end) result = body.(pid) Agent.stop(pid) result end def lookup(cache, n, if_not_found) do Agent.get(cache, fn map -> map[n] end) |> complete_if_not_found(cache, n, if_not_found) end defp complete_if_not_found(nil, cache, n, if_not_found) do if_not_found.() |> set(cache, n) end defp complete_if_not_found(value, _cache, _n, _if_not_found) do value end defp set(val, cache, n) do Agent.get_and_update(cache, fn map -> { val, Map.put(map, n, val)} end) end end defmodule CachedFib do def fib(n) do Cache.run(fn cache -> cached_fib(n, cache) end) end defp cached_fib(n, cache) do Cache.lookup(cache, n, fn -> cached_fib(n-2, cache) + cached_fib(n-1, cache) end) end end

### rchavarria commented Jul 19, 2017

 Here is the code for my first iteration. Basically, I'm using the cache as a map, nothing fancy. More or less the code is like: ```defmodule FibonacciAgent.Cache do def start do Agent.start_link(fn -> %{ 0 => 0, 1 => 1 } end) end def get_fibs(agent) do Agent.get(agent, &(&1)) end def update_fibs(agent, fibs) do Agent.update(agent, fn _ -> fibs end) end end defmodule FibonacciAgent.Calculator do alias FibonacciAgent.Cache def fib(agent, n) do fibs = Cache.get_fibs(agent) compute_fib(agent, n, Map.get(fibs, n)) end defp compute_fib(agent, n, nil) do nth_fib = fib(agent, n - 1) + fib(agent, n - 2) fibs = Cache.get_fibs(agent) Cache.update_fibs(agent, Map.put(fibs, n, nth_fib)) nth_fib end defp compute_fib(agent, n, computed), do: computed end ``` It's similar in some points to the proposed solution. But I get some interesting ideas from the proposed solution: It didn't occurred to me to start and stop the agent, passing in a function with the code I want to run using the agent. The value extracted from the cache and passed to `complete_if_not_found` is the first parameter. That allows you to use the pipe operator, and the code gets cleaner that mine. Very nice. Same for `Cache.set`. @pragdave - Question: is there a reason to compute `n-2` first at `CachedFib.cached_fig`? ```defp cached_fib(n, cache) do Cache.lookup(cache, n, fn -> # is there a reason for `n-2` to come first? cached_fib(n-2, cache) + cached_fib(n-1, cache) end) end```

### fahrinh commented Jan 6, 2018 • edited

 Here are my solutions : `cache.exs` ```defmodule Cache do def start(init_cache) do Agent.start_link(fn -> init_cache end) end def put(pid, number, result) do Agent.update(pid, &(Map.put(&1, number, result))) end def get(pid, number) do Agent.get(pid, &(Map.get(&1, number))) end end``` `fib.exs` ```defmodule Fib do def init do Cache.start(%{0 => 0, 1 => 1}) end def fib(pid, n) do case Cache.get(pid, n) do nil -> result = fib(pid, n-1) + fib(pid, n-2) Cache.put(pid, n, result) result val -> val end end end``` How to run : ``````iex> c "cache.exs" iex> c "fib.exs" iex> {:ok, pid} = Fib.init iex> Fib.fib(pid, 100) ``````

### fahrinh commented Jan 6, 2018

 I like @pragdev 's solution. He don't expose `pid` on the api. But, I think we can treat `pid` as a reference to global cache so it can be passed around (like my solution) :D

### 9mm commented Jan 12, 2018

 I feel retarded for not getting this, not thinking in terms of if/else and early returns is so much more hard than i was expecting

### arcseldon commented Jan 26, 2018 • edited

 Here was my first solution - very similar to one above! ``````defmodule FibCache do def init() do Agent.start_link(fn -> %{0 => 0, 1 => 1} end) end def add(agent, k, v) do Agent.update(agent, &Map.put(&1, k, v)) end def get(agent, k) do Agent.get(agent, &Map.get(&1, k)) end def print(agent) do Agent.get(agent, fn (cache) -> IO.inspect cache; cache end) end end `````` ``````defmodule Fib do def init() do {:ok, cache} = FibCache.init() cache end def print(cache) do FibCache.print(cache) end def fib(cache, n) do case FibCache.get(cache, n) do nil -> res = fib(cache, n - 1) + fib(cache, n - 2) FibCache.add(cache, n, res) cached_value -> cached_value end end # def fib(0), do: 0 # def fib(1), do: 1 # def fib(n), do: fib(n - 1) + fib(n - 2) end `````` Usage: ``````iex [13:30 :: 58] > cache = Fib.init() #PID<0.390.0> iex [13:30 :: 59] > Fib.fib(cache, 20) 6765 iex [13:30 :: 60] > Fib.print(cache) %{ 0 => 0, 1 => 1, 2 => 1, 3 => 2, 4 => 3, 5 => 5, 6 => 8, 7 => 13, 8 => 21, 9 => 34, 10 => 55, 11 => 89, 12 => 144, 13 => 233, 14 => 377, 15 => 610, 16 => 987, 17 => 1597, 18 => 2584, 19 => 4181, 20 => 6765 } iex [13:30 :: 61] > Fib.fib(cache, 50) 12586269025 iex [13:30 :: 62] > Fib.fib(cache, 100) 354224848179261915075 ``````

### dovadi commented Feb 3, 2018

 I like @pragdave' s solution, the Agent/Cache is completely hidden from the user. However, he uses a custom made (and dare I say an also more complicated) cache. (The function name complete_if_not_found is somewhat confusing, the second and last implementation of complete_if_not_found is doing the opposite which is nothing because the value was found!) Why not use a 'standard Map cache', used in the Agent example in the getting started guide from elixir-lang.org ( see the example pf KV.Bucket ) and combine this with @fahrinh's Fib implementation? ```defmodule MapCache do use Agent def start_link() do Agent.start_link(fn -> %{} end) end def get(bucket, key) do Agent.get(bucket, &Map.get(&1, key)) end def put(bucket, key, value) do Agent.update(bucket, &Map.put(&1, key, value)) end end``` ```defmodule Fib do def calc(n) do {:ok, cache} = MapCache.start_link() result = calc(cache, n) Agent.stop(cache) result end defp calc(_cache, 0), do: 0 defp calc(_cache, 1), do: 1 defp calc(cache, n) do result = MapCache.get(cache, n) if is_nil(result) do result = calc(cache, n-1) + calc(cache, n-2) MapCache.put(cache, n, result) result else result end end end``` Usage: ``````iex [19:35 :: 1] > Fib.calc(50) 12586269025 iex [19:35 :: 2] > Fib.calc(100) 354224848179261915075 `````` PS: In this case I find the usage of a good old if statement more acceptable than an implementation like below: ```defmodule Fib do def calc(n) do {:ok, cache} = MapCache.start_link() result = calc(cache, n) Agent.stop(cache) result end defp calc(_cache, 0), do: 0 defp calc(_cache, 1), do: 1 defp calc(cache, n) do result = MapCache.get(cache, n) show_result(result, cache, n) end def show_result(nil, cache, n) do result = calc(cache, n-1) + calc(cache, n-2) MapCache.put(cache, n, result) result end def show_result(result, _cache, _n), do: result end```

### cleaton commented Feb 4, 2018 • edited

 Here's my first solution, since it's slightly different from others shared here. Some thoughts that came to my mind: while generic cache implementations are nice, it seems to make the fib solution more difficult to read (or am I biased?) as other's mentioned,I too did not consider Agent.stop like @pragdave used in his solution I hide cache state behind the public fib function, this makes it impossible to reuse cache between multiple fib(n) runs. @pragdave solution has the same issue is there a clean tail recursive version? ``````defmodule Fib do def fib(n) do {:ok, a} = Agent.start_link(fn -> %{0 => 0, 1 => 1} end) fib(a, n) end defp fib(agent, n) do fib(agent, n, Agent.get(agent, &Map.get(&1, n))) end defp fib(agent, n, nil) do v = fib(agent, n - 1) + fib(agent, n - 2) Agent.update(agent, &Map.put(&1, n, v)) v end defp fib(agent, n, value) do value end end ``````

### celyr commented Feb 12, 2018

 Using the Bucket example I find my implementatio pretty elegant: ``````defmodule Fibonacci do alias Fibonacci.Cache def calculate(n) do {:ok, cache} = Cache.start_link() Cache.put(cache, 0, 0) Cache.put(cache, 1, 1) cal(n, cache, Cache.get(cache, n)) end defp cal(n, cache, nil) do result = cal(n-1, cache, Cache.get(cache, n-1)) + cal(n-2, cache, Cache.get(cache, n-2)) Cache.put(cache, n, result) result end defp cal(_, _, result) do result end end `````` ``````defmodule Fibonacci.Cache do use Agent def start_link() do Agent.start_link(fn -> %{} end) end def get(bucket, key) do Agent.get(bucket, &Map.get(&1, key)) ## fn map -> Map.get(map, key) end) end def put(bucket, key, value) do Agent.update(bucket, &Map.put(&1, key, value)) end end `````` I also left a small comment to better understand the catch operator

### EssenceOfChaos commented Feb 18, 2018 • edited

 Here is a fib calculator of the same complexity with less code. ``````defmodule Fibonacci do def find(n), do: find(n, 0, 1) def find(1, _acc1, acc2), do: acc2 def find(n, acc1, acc2) do find(n - 1, acc2, acc1 + acc2) end end `````` iex> Fibonacci.find(100) 354224848179261915075 iex> Fibonacci.find(150) 9969216677189303386214405760200

### uttamk commented Apr 15, 2018

 Here is my implementation. `Fibonacci.Cache` is just a wrapper over a map/state. The public api for the `Fibonacci` module is just `Fibonacci.fib(n)`. Everything else is abstracted away in private functions. ``````defmodule Fibonacci do alias Fibonacci.Cache def fib(n) do {:ok, agent} = Cache.intialize(fn -> %{0 => 0, 1 => 1} end) value = fib(agent, n) Agent.stop(agent) value end defp fib(agent, 0) do Cache.get(agent, 0) end defp fib(agent, 1) do Cache.get(agent, 1) end defp fib(agent, n) do fib_n_minus_one = fib(agent, n - 1, Cache.has_key?(agent, n - 1)) fib_n_minus_two = fib(agent, n - 2, Cache.has_key?(agent, n - 2)) fib_n_minus_one + fib_n_minus_two end defp fib(agent, n, _is_in_cache = true) do Cache.get(agent, n) end defp fib(agent, n, _is_in_cache = false) do Cache.update(agent, n, fib(agent, n)) end end defmodule Fibonacci.Cache do def intialize(init_fn) do Agent.start_link(init_fn) end def get(agent, key) do Agent.get(agent, fn map -> Map.get(map, key) end) end def has_key?(agent, key) do Agent.get(agent, fn map -> Map.has_key?(map, key) end) end def update(agent, key, value) do Agent.update(agent, fn map -> Map.put(map, key, value) end) value end end `````` and tests too ``````defmodule FibonacciTest do use ExUnit.Case doctest Fibonacci test "return 0 for 0" do assert Fibonacci.fib(0) == 0 end test "return 1 for 1" do assert Fibonacci.fib(1) == 1 end test "return 1 for 2" do assert Fibonacci.fib(2) == 1 end test "return 2 for 3" do assert Fibonacci.fib(3) == 2 end test "return 55 for 10" do assert Fibonacci.fib(10) == 55 end test "return 55 for 100" do assert Fibonacci.fib(100) == 354_224_848_179_261_915_075 end end ``````

### teberl commented Jul 26, 2018

#### My final version

I changed my API after seeing @pragdave's solution with using a lambda in `Cache.run/1`.
By using the lambda i was able to easily remove the `pid` aka `cache` from the Fibonacci API, but still keep the calculation logic I had before.

THX @pragdave for the awesome course so far and also the other solutions which are very inspiring !

fibonacci.exs

```defmodule Fibonacci do
def fib(0), do: 0
def fib(1), do: 1
def fib(n) do
fib(n - 1) + fib(n - 2)
end

def cached_fib(n) do
Cache.start(fn cache -> calculation(cache, n) end)
end

defp calculation(cache, n) do
cached_fib = Cache.get(cache, n)
case cached_fib do
nil ->
result = calculation(cache, n - 1) + calculation(cache, n - 2)
_ ->
cached_fib
end
end
end

defmodule Cache do
def start(lambda) do
{:ok, pid} = Agent.start_link(fn -> %{0 => 0, 1 => 1} end)
result = lambda.(pid)
Agent.stop(pid)
result
end

def add(pid, key, value) do
Agent.get_and_update(pid, fn(map) -> {value, Map.put(map, key, value)} end)
end

def get(pid, n) do
result = Agent.get(pid, &(&1))
result[n]
end
end```

### barthr commented Sep 23, 2018

 ```defmodule Cache do def new() do Agent.start_link(fn -> %{0 => 0, 1 => 1} end) end def contains(agent, key) do Agent.get(agent, fn state -> Map.has_key?(state, key) end) end def get(agent, key) do Agent.get(agent, fn state -> Map.get(state, key) end) end def insert(agent, key, value) do Agent.update(agent, fn state -> Map.put(state, key, value) end) end end defmodule Fibonacci do def fib(n) do {:ok, cache} = Cache.new() fib_cache(cache, n) end defp fib_cache(cache, n) do case Cache.contains(cache, n) do false -> result = fib_cache(cache, n - 1) + fib_cache(cache, n - 2) Cache.insert(cache, n, result) result true -> Cache.get(cache, n) end end end```

### rahul-rege commented Oct 2, 2018

 I have done it without recursion but I do not know if that'd be a problem. Also, don't know if it makes sense to hold the full cache of all numbers if the problem statement asks for the nth Fibbonaci number. My below solution only holds latest two and calculates. `defmodule Cache do def start_value do %{:first => 0, :second => 1} end def init() do Agent.start_link(fn -> start_value end, name: :cache) end def init({:error, _}) do Cache.init end def init({:ok, _}) do end def get(key) do Agent.get(:cache, fn(keymap) -> keymap |> Map.get(key) end ) end def update(key, value) do Agent.update(:cache, fn(keymap) -> keymap |> Map.put(key, value) end) end def reset() do Agent.update(:cache, fn(keymap) -> start_value end) end end defmodule fibocached do def fibbonaci(0) do Cache.get(:first) end def fibbonaci(1) do Cache.get(:second) end def fibbonaci(n) do Cache.reset range = 2..n |> Enum.map(&step/1) Cache.get(:second) end def step(number) do first = Cache.get(:first) Cache.update(:first, Cache.get(:second)) Cache.update(:second, Cache.get(:second) + first) end def run(n) do Cache.init FiboCached.fibbonaci(n) end def print_cache do IO.puts("First is #{Cache.get(:first)} Second is #{Cache.get(:second)}") end end` Thanks @praddave for the awesome course ! Continuing with further modules with lots of enthusiasm..

### antoniosb commented Nov 4, 2018

 My humble version: I wanted to ensure that the cache process was stoped before returning, thus no creating zombie processes, is that right? ```defmodule FibCache do def start() do Agent.start_link(fn -> %{0 => 0, 1 => 1} end) end def get(cache) do Agent.get(cache, & &1) end def update(cache, k, v) do Agent.update(cache, fn cache -> Map.put(cache, k, v) end) end def get_and_update(cache, k, v) do Agent.get_and_update(cache, fn cache -> new_cache = Map.put(cache, k, v) {new_cache, new_cache} end) end def stop(cache) do Agent.stop(cache) end end defmodule Fibonacci do @moduledoc """ Calculates Fibonacci numbers using the FibCache cache. """ defp cached_fib(cache, n) do hit_cache = FibCache.get(cache)[n] cond do hit_cache != nil -> hit_cache hit_cache == nil -> FibCache.update(cache, n, cached_fib(cache, n - 1) + cached_fib(cache, n - 2)) FibCache.get(cache)[n] end end def fib(n) do {:ok, cache} = FibCache.start() result = cache |> cached_fib(n) FibCache.stop(cache) result end end ```

### artonragsdale commented May 28, 2019 • edited

 ```defmodule FibCache do def start() do Agent.start_link(fn -> %{0 => 0, 1 => 1} end) end def get_fib(pid, n) do state = Agent.get(pid, fn state -> state end) Map.get(state, n) end def update(pid, n, value) do Agent.update(pid, fn state -> Map.put(state, n, value) end) end end``` ```defmodule Fib do def start() do FibCache.start() end def fib(_pid, 0), do: 0 def fib(_pid, 1), do: 1 def fib(pid, n) do case FibCache.get_fib(pid, n) do nil -> answer = fib(pid, n - 1) + fib(pid, n - 2) FibCache.update(pid, n, answer) answer value -> value end end end``` ```iex> {:ok, pid} = Fib.start iex> Fib.fib(pid, 100)```

### Markentoine commented Jun 29, 2019

 A version (the Cache module is straightforward) ```defmodule FiboOpt.Compute do def fibo(n) do {:ok, cacheID} = Cache.start() result = find_result(cacheID, n) Agent.stop(cacheID) result end defp find_result(cacheID, n) do check_value(cacheID, n) |> compute_result(cacheID, n) |> update_and_get end defp check_value(pid, n), do: Cache.get(pid, n) defp compute_result(_value_not_exists = nil, pid, n) do value = find_result(pid, n - 2) + find_result(pid, n - 1) {value, pid, n, :update} end defp compute_result(value, pid, n), do: {value, pid, n, :no_update} defp update_and_get({value, pid, n, :update}) do Cache.add(pid, n, value) value end defp update_and_get({value, _, _, :no_update}), do: value end```
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.