Instantly share code, notes, and snippets.

# pragdave/00-question.md Secret

Last active July 16, 2022 23:35
Star You must be signed in to star a gist
«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...

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
 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

### 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)

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
value
end

defp update_and_get({value, _, _, :no_update}), do: value
end```

### reneweteling commented Oct 13, 2019

So after reading i guess ive forgotton to kill the agent, but it does work :)

```defmodule Fib do
def start do
{:ok, pid} = Agent.start_link(fn -> %{0 => 0, 1 => 1} end)
pid
end

def fib(n) do
start()
|> fib(n)
end

def fib(pid, n) do
Agent.get(pid, fn state -> state[n] end)
|> return_or_calculate(pid, n)
end

def return_or_calculate(result, _pid, _n) do
result
end

def return_or_calculate(nil, pid, n) do
calculated = fib(pid, n - 1) + fib(pid, n - 2)

Agent.update(pid, fn state ->
Map.put(state, n, calculated)
end)

calculated
end
end```

### reneweteling commented Oct 14, 2019

@pragdave so that would be in in the:

```Agent.update(pid, fn state ->
Map.put(state, n, calculated)
end)```

It should probably be `Agent.get_and_update` to make it sequential? Like you mentioned it did not affect the result so I didn't notice it.

And I must say, I'm enjoying myself immensely with the course, its funny, insightful and great to do. It has taken me quite some time to start, I was intrigued by the language by your talk in Amsterdam, and now finally started working with Elixir, it's great. Thanks for the course! Can't wait to continue tonight 👍

### koskoci commented Nov 8, 2019 • edited

My solution just calculates the nth Fibonacci number without providing caching functionality.

```defmodule Fib do
defp init() do
{ :ok, pid } = Agent.start_link(fn -> %{ 0 => 0, 1 => 1 } end)
pid
end

def calc(n) do
pid = init()

Enum.each(2..n, fn x ->
Agent.update(pid, fn state ->
Map.put(state, x, state[x-2] + state[x-1])
end)
end)

state = Agent.get(pid, fn x-> x end)
state[n]
end
end```

### waldfee commented Nov 24, 2019

My initial version:

```defmodule Fib do
alias Fib.Cache

def fib(n) do
{:ok, agent_pid} = Cache.init()
fib(n, agent_pid)
end

defp fib(n, agent_pid) do
fib_value = Cache.get(agent_pid, n)
fib(n, agent_pid, fib_value)
end

defp fib(n, agent_pid, _fib_value = nil) do
fib_value = fib(n - 1, agent_pid) + fib(n - 2, agent_pid)
Cache.put(agent_pid, {n, fib_value})
fib_value
end

defp fib(_n, _agent_pid, fib_value) do
fib_value
end
end```
```defmodule Fib.Cache do
use Agent

def init() do
Agent.start_link(fn -> %{0 => 0, 1 => 1} end)
end

def stop(agent_pid) do
Agent.stop(agent_pid)
end

def put(agent_pid, {number, fib_value}) do
Agent.update(agent_pid, fn map -> Map.put(map, number, fib_value) end)
end

def get(agent_pid, number) do
Agent.get(agent_pid, fn map -> Map.get(map, number) end)
end
end```

### carloscasalar commented Feb 1, 2020

I know I should extract cache functions to another module but this is roughly my solution:

```defmodule FibonacciWithCache do
def fib(0), do: 0

def fib(1), do: 1

def fib(n) do
cache_pid = init_cache()
value = fib(cache_pid, n)
clean_cache(cache_pid)
value
end

defp fib(cache_pid, 0) do
get_from_cache(cache_pid, 0)
end

defp fib(cache_pid, 1) do
get_from_cache(cache_pid, 1)
end

defp fib(cache_pid, n) do
calculate_fib_storing_in_cache(cache_pid, n, get_from_cache(cache_pid, n))
end

defp calculate_fib_storing_in_cache(cache_pid, n, nil) do
value = fib(cache_pid, n - 1) + fib(cache_pid, n - 2)
update_cache_and_get_value(cache_pid, n, value)
end

defp calculate_fib_storing_in_cache(_cache_pid, _n, value), do: value

defp init_cache do
{:ok, cache_pid} = Agent.start_link(fn -> %{0 => 0, 1 => 1} end)
cache_pid
end

defp clean_cache(cache_pid) do
Agent.stop(cache_pid)
end

defp update_cache_and_get_value(cache_pid, n, value) do
Agent.get_and_update(cache_pid, fn cache_value ->
{value, Map.merge(cache_value, %{n => value})}
end)
end

defp get_from_cache(cache_pid, n) do
Agent.get(cache_pid, fn cache_value -> cache_value[n] end)
end
end```

### herminiotorres commented Apr 8, 2020

#### My solution for a Fibonacci with Agent:

`fibonacci_cached.exs:`

```defmodule FibonacciCached do
def start() do
Agent.start_link(fn -> %{0 => 0, 1 => 1} end)
end

def get(agent, key) do
state = Agent.get(agent, fn state -> state end)
Map.get(state, key)
end

Agent.update(agent, fn state -> Map.put(state, key, value) end)
end

def print(agent) do
Agent.get(agent, fn state -> state end)
end
end```

`fibonacci.exs:`

```defmodule Fibonacci do
def start() do
FibonacciCached.start()
end

def print(agent) do
FibonacciCached.print(agent)
end

def calculate(_agent, 0), do: 0
def calculate(_agent, 1), do: 1

def calculate(agent, key) do
case FibonacciCached.get(agent, key) do
nil ->
value = calculate(agent, key-1) + calculate(agent, key-2)
value
cached_value ->
cached_value
end
end
end```

`call IEx:`

```\$ iex
iex> c "fibonacci_cached.exs"
[FibonacciCached]
iex> c "fibonacci.exs"
[Fibonacci]
iex> {:ok, agent} = Fibonacci.start()
{:ok, #PID<0.125.0>}
iex> Fibonacci.calculate(agent, 10)
55
iex> Fibonacci.print(agent)
%{
0 => 0,
1 => 1,
2 => 1,
3 => 2,
4 => 3,
5 => 5,
6 => 8,
7 => 13,
8 => 21,
9 => 34,
10 => 55
}
```

### lgprall commented May 29, 2020 • edited

This is kind of a simple solution. First thing I came up with; I need to look over some of the other solutions to see what I missed.

[NB] Guess I missed the point about having a separate module for the cache...

```defmodule Fib do

def find(0), do: 0
def find(1), do: 1
def find(2), do: 1

def find(count)  do

{:ok, pid } = Agent.start_link(fn -> %{ 0 => 0, 1 => 1} end)
for _n <- 1..div(count, 2), do: update(pid)
Agent.get(pid, fn map -> map end)
|> pick(count)

end

def pick(map,count) when rem(count,2) == 0, do: map

def pick(map,_), do: map

def update(pid) do
Agent.update(pid, fn map -> %{map | 0 => (map + map)} end)
Agent.update(pid, fn map -> %{map | 1 => (map + map)} end)
end
end```

iex(7)> Fib.find 100
354224848179261915075
iex(8)> Fib.find 1000
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
iex(9)> Fib.find 10000
336447648764317832666216120051075433103021484606800639065647699746800814421666623681555955136337340255820... . . .
642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875
iex(110)>

### tejpochiraju commented Nov 16, 2020 • edited

My first solution used an externally exposed PID. After stealing the `run(body)` portion of @pragdave's solution that hides the PID, here's where I arrived:

`fibonacci.ex`:

``````defmodule Fibonacci do
def fib(pid, n) do
state = Agent.get(pid, fn state -> state end)
cond do
state[n] -> state[n]
true ->
result = fib(pid, n-1) + fib(pid, n-2)
Agent.update(pid, fn state -> Map.put(state, n, result) end)
result
end
end

def cached_fib(n) do
FibCache.run(fn pid -> fib(pid, n) end)
end

end
``````

`cache.ex`:

``````defmodule FibCache do
def run(body) do
{:ok, pid} = Agent.start_link(fn -> %{0 => 0, 1 => 1} end)
result = body.(pid)
Agent.stop(pid)
result
end
end
``````

I find this a lot more readable, albeit with the use of `cond`.

### wuziq commented Mar 16, 2021

Could you explain why there's a race race condition with Agent.update() vs none with Agent.get_and_update()?

That's right. It's kinda a big deal, though. Being a language that encourages concurrency, that kind of nontransactional update can cause problems more easily than in most. Thanks for the kind words. Dave

On Mon, Oct 14, 2019 at 2:17 AM Rene Weteling @.***> wrote: @pragdave https://github.com/pragdave so that would be in in the: Agent.update(pid, fn state -> Map.put(state, n, calculated) end) It should probably be Agent.get_and_update to make it sequential? Like you mentioned it did not affect the result so I didn't notice it. And I must say, I'm enjoying myself immensely with the course, its funny, insightful and great to do. It has taken me quite some time to start, I was intrigued by the language by your talk in Amsterdam, and now finally started working with Elixir, it's great. Thanks for the course! Can't wait to continue tonight 👍 — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://gist.github.com/f8c7684b69d235269139bad0a2419273?email_source=notifications&email_token=AAACTGA6OKOIGC7ACTBJMSTQOQMJ3A5CNFSM4HQCVAUKYY3PNVWWK3TUL52HS4DFVNDWS43UINXW23LFNZ2KUY3PNVWWK3TUL5UWJTQAF2NXG#gistcomment-3054451, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAACTGAT5H2BPKCFUCL3RO3QOQMJ3ANCNFSM4HQCVAUA .

### jeffdevr commented Sep 18, 2021

Using || can remove all the explicit testing against nil, and it's very convenient having your update function return the new value.

``````defmodule Cache do

def start(initial_map = %{}) do
{:ok, pid } = Agent.start_link(fn -> initial_map end)
pid
end

def put(pid, key, value) do
Agent.update(pid, &Map.put(&1, key, value))
value
end

def get(pid, key) do
Agent.get(pid, &Map.get(&1, key))
end

end

defmodule FibCache do

def fib(n) do
Cache.start(%{ 0 => 0, 1 => 1 })
|> fib_iter(n)
end

defp fib_iter(cache, n) do
Cache.get(cache, n) ||
Cache.put(cache, n, fib_iter(cache, n-1) + fib_iter(cache, n-2))
end

end
``````