# Run as: iex --dot-iex <path/to/>dp24a-fp4gy-megoldas.exs

# Title: DP24a - 4. FP gyakorlat, 2024-10-08

# ── Elágazó rekurzió ──

# ### Számítások elágazó rekurzióval

# #### Fibonacci-számok elágazó és lineáris rekurzióval

defmodule FibTree do
  @spec fib(n :: integer()) :: f :: integer()
  # Az n-edik Fibonacci-szám f
  def fib(0), do: 0
  def fib(1), do: 1
  def fib(n), do: fib(n - 2) + fib(n - 1)
end

IO.puts(FibTree.fib(0) == 0)
IO.puts(FibTree.fib(1) == 1)
IO.puts(FibTree.fib(2) == 1)
IO.puts(FibTree.fib(5) == 5)
IO.puts(FibTree.fib(7) == 13)
IO.puts(FibTree.fib(43))

defmodule FibLin do
  @spec fib(n :: integer()) :: f :: integer()
  # Az n-edik Fibonacci-szám f
  def fib(n), do: fib(n, 0, 1)

  @spec fib(n :: integer(), n_2 :: integer(), n_1 :: integer()) :: f :: integer()
  # Az n-edik Fibonacci-szám ???
  defp fib(0, n_2, _), do: n_2
  defp fib(n, n_2, n_1), do: fib(n - 1, n_1, n_2 + n_1)
end

IO.puts(FibLin.fib(0) == 0)
IO.puts(FibLin.fib(1) == 1)
IO.puts(FibLin.fib(2) == 1)
IO.puts(FibLin.fib(5) == 5)
IO.puts(FibLin.fib(7) == 13)
IO.puts(FibLin.fib(43))
# IO.puts(FibLin.fib(193))

# #### Pénzváltások száma

defmodule CountOfChanges do
  @spec count_of_changes(amount :: integer()) :: count :: integer()
  # Az amount összeg összes lehetséges felváltásának száma count
  def count_of_changes(amount), do: count_of_changes(amount, 6)

  @spec count_of_changes(amount :: integer(), index :: integer()) :: count :: integer()
  # Az amount összeg összes lehetséges felváltásának száma a coin_id-nél nem nagyobb
  # indexű érmékkel count
  defp count_of_changes(amount, _) when amount < 0, do: 0
  defp count_of_changes(0, _), do: 1
  defp count_of_changes(_amount, 0), do: 0

  defp count_of_changes(amount, coin_id) do
    count_of_changes(amount, coin_id - 1) +
      count_of_changes(amount - coins(coin_id), coin_id)
  end

  @spec coins(n :: integer()) :: c :: integer()
  # Az n kulcsú címlet c
  defp coins(6), do: 200
  defp coins(5), do: 100
  defp coins(4), do: 50
  defp coins(3), do: 20
  defp coins(2), do: 10
  defp coins(1), do: 5
end

IO.puts(CountOfChanges.count_of_changes(5) === 1)
IO.puts(CountOfChanges.count_of_changes(10) === 2)
IO.puts(CountOfChanges.count_of_changes(100) === 50)
IO.puts(CountOfChanges.count_of_changes(1000) === 98411)

# ### Bináris fák feldolgozása elágazó rekurzióval

defmodule T do
  @type tree() :: :leaf | {any(), tree(), tree()}
  @type inttree() :: :leaf | {integer(), inttree(), inttree()}
  def t1() do
    {4, {3, :leaf, :leaf}, {6, {5, :leaf, :leaf}, {7, :leaf, :leaf}}}
  end

  def t2() do
    {:a, {:b, {:v, :leaf, :leaf}, :leaf},
     {:c, :leaf,
      {:d, {:w, {:x, :leaf, :leaf}, :leaf}, {:f, {:x, :leaf, :leaf}, {:y, :leaf, :leaf}}}}}
  end
end

IO.puts("t1 = " <> inspect(T.t1()))
IO.puts("t2 = " <> inspect(T.t2()))

# #### Bináris egészfa minden címkéjének megnövelése 1-gyel

defmodule IncTree do
  @spec fa_noveltje(f0 :: T.inttree()) :: f :: T.inttree()
  # Az f fa minden címkéje eggyel nagyobb az f0 fa azonos helyen lévő címkéjénél
  def fa_noveltje(:leaf), do: :leaf
  def fa_noveltje({c, bfa, jfa}), do: {c + 1, fa_noveltje(bfa), fa_noveltje(jfa)}
end

IncTree.fa_noveltje(T.t1()) === {5, {4, :leaf, :leaf}, {7, {6, :leaf, :leaf}, {8, :leaf, :leaf}}}

# #### Bináris fa tükörképe

defmodule Mirtree do
  @spec fa_tukorkepe(f0 :: T.tree()) :: f :: T.tree()
  # f az f0 fa tükörképe
  def fa_tukorkepe(:leaf), do: :leaf
  def fa_tukorkepe({c, bfa, jfa}), do: {c, fa_tukorkepe(jfa), fa_tukorkepe(bfa)}
end

Mirtree.fa_tukorkepe(T.t1()) === {4, {6, {7, :leaf, :leaf}, {5, :leaf, :leaf}}, {3, :leaf, :leaf}}

# #### Bináris fa inorder, preorder és postorder bejárása

defmodule TravTree do
  @spec inorder(f :: T.tree()) :: ls :: [any()]
  # ls az f fa elemeinek a fa inorder bejárásával létrejövő listája
  def inorder(:leaf), do: []
  def inorder({c, bfa, jfa}), do: inorder(bfa) ++ [c | inorder(jfa)]
  @spec preorder(f :: T.tree()) :: ls :: [any()]
  # ls az f fa elemeinek a fa preorder bejárásával létrejövő listája
  def preorder(:leaf), do: []
  def preorder({c, bfa, jfa}), do: [c | preorder(bfa) ++ preorder(jfa)]
  @spec postorder(f :: T.tree()) :: ls :: [any()]
  # ls az f fa elemeinek a fa postorder bejárásával létrejövő listája
  def postorder(:leaf), do: []
  def postorder({c, bfa, jfa}), do: postorder(bfa) ++ postorder(jfa) ++ [c]
end

(TravTree.inorder(T.t1()) === [3, 4, 5, 6, 7]) |> IO.inspect()
(TravTree.preorder(T.t1()) === [4, 3, 6, 5, 7]) |> IO.inspect()
(TravTree.postorder(T.t1()) === [3, 5, 7, 6, 4]) |> IO.inspect()

# #### Címke előfordulása (rendezetlen) bináris fában

defmodule Contains do
  @spec tartalmaz(f :: T.tree(), c :: any()) :: b :: boolean()
  # b igaz, ha c az f fa valamely címkéje
  def tartalmaz(:leaf, _), do: false
  def tartalmaz({c, _, _}, c), do: true
  def tartalmaz({_, bfa, jfa}, c), do: tartalmaz(bfa, c) or tartalmaz(jfa, c)
end

(Contains.tartalmaz(T.t1(), :x) === false) |> IO.inspect()
(Contains.tartalmaz(T.t2(), :x) === true) |> IO.inspect()

# #### Címke összes előfordulásának száma bináris fában

defmodule Occurs do
  @spec elofordul(f :: T.tree(), c :: any()) :: n :: integer()
  # A c címke az f fában n-szer fordul elő
  def elofordul(:leaf, _), do: 0

  def elofordul({r, bfa, jfa}, c) do
    if r === c, do: 1, else: 0 + elofordul(bfa, c) + elofordul(jfa, c)
  end
end

(Occurs.elofordul(T.t1(), :x) === 0) |> IO.inspect()
(Occurs.elofordul(T.t2(), :x) === 2) |> IO.inspect()

# #### Címkék felsorolása

defmodule Labels do
  @spec cimkek(f :: T.tree()) :: ls :: [any()]
  # ls az f fa címkéinek listája inorder sorrendben
  def cimkek(fa), do: cimkek(fa, [])

  @spec cimkek(f :: T.tree(), zs :: [any()]) :: ls :: [any()]
  # ls az f fa címkéinek listája inorder sorrendben a zs elé fűzve
  defp cimkek(:leaf, zs), do: zs
  defp cimkek({r, bfa, jfa}, zs), do: cimkek(bfa, [r | cimkek(jfa, zs)])
end

(Labels.cimkek(T.t1()) === [3, 4, 5, 6, 7]) |> IO.inspect()
(Labels.cimkek(T.t2()) === [:v, :b, :a, :c, :x, :w, :d, :x, :f, :y]) |> IO.inspect()

# #### Bal és jobb szélső címkék visszaadása

defmodule MostLeftRight do
  @spec fa_balerteke(f :: T.tree()) :: {:ok, c :: any()} | :error
  # Egy nemüres f fa bal oldali szélső címkéje c (minden
  # felmenőjére is igaz, hogy bal oldali gyermek)
  # Ha nincs bal oldali szélső érték, az :error atomot adja vissza
  def fa_balerteke(:leaf), do: :error
  def fa_balerteke({c, :leaf, _}), do: {:ok, c}
  def fa_balerteke({_, bfa, _}), do: fa_balerteke(bfa)

  @spec fa_jobberteke(f :: T.tree()) :: {:ok, c :: any()} | :error
  # Egy nemüres f fa jobb oldali szélső címkéje c (minden
  # felmenőjére is igaz, hogy jobb oldali gyermek)
  # Ha nincs jobb oldali szélső érték, az :error atomot adja vissza
  def fa_jobberteke(:leaf), do: :error
  def fa_jobberteke({c, _, :leaf}), do: {:ok, c}
  def fa_jobberteke({_, _, jfa}), do: fa_jobberteke(jfa)
end

(MostLeftRight.fa_balerteke(T.t1()) === {:ok, 3}) |> IO.inspect()
(MostLeftRight.fa_balerteke(:leaf) === :error) |> IO.inspect()
(MostLeftRight.fa_jobberteke(T.t1()) === {:ok, 7}) |> IO.inspect()
(MostLeftRight.fa_jobberteke(:leaf) === :error) |> IO.inspect()

# #### Bináris fa rendezettsége

defmodule Ordered do
  @spec rendezett(f :: T.tree()) :: b :: boolean()
  # b igaz, ha az f fa rendezett
  def rendezett(:leaf), do: true

  def rendezett({c, bfa, jfa}) do
    case MostLeftRight.fa_jobberteke(bfa) do
      :error -> true
      {:ok, j} -> j < c
    end and
      rendezett(bfa) and
      case MostLeftRight.fa_balerteke(jfa) do
        :error -> true
        {:ok, b} -> c < b
      end and
      rendezett(jfa)
  end
end

(Ordered.rendezett(T.t1()) === true) |> IO.inspect()
(Ordered.rendezett(T.t2()) === false) |> IO.inspect()

defmodule Ordered2 do
  @spec rendezett(f :: T.tree()) :: b :: boolean()
  # b igaz, ha az f fa rendezett
  def rendezett(f) do
    Labels.cimkek(f) |> sorted?()
  end

  defp sorted?([x1 | [x2 | _xs] = xxs]) when x1 < x2, do: sorted?(xxs)
  defp sorted?([_x1, _x2 | _xs]), do: false
  defp sorted?(_), do: true
end

(Ordered2.rendezett(T.t1()) === true) |> IO.inspect()
(Ordered2.rendezett(T.t2()) === false) |> IO.inspect()

# #### Bináris fa összes címkéjének útvonala

defmodule Route do
  @type route() :: [any()]
  @spec utak(f :: T.tree()) :: cimkezett_utak :: [{c :: any(), cu :: route()}]
  # A cimkezett_utak lista az f fa minden csomópontjához egy {c,cu} párt
  # társít, ahol c az adott csomópont címkéje, cu pedig az adott
  # csomóponthoz vezető útvonal
  def utak(fa), do: utak(fa, [])

  @spec utak(f :: T.tree(), eddigi_ut :: route()) ::
          cimkezett_utak :: [{c :: any(), cu :: route()}]
  # A cimkezett_utak lista az f fa minden csomópontjához egy {c,cu} párt
  # társít, ahol c az adott csomópont címkéje, cu pedig az adott
  # csomóponthoz vezető útvonal az eddigi_ut eddigi útvonal elé fűzve
  def utak(:leaf, _), do: []

  def utak({c, bfa, jfa}, eddigi) do
    # eddigi1 = eddigi ++ [c] # Költséges művelet: O(n2)!
    # Kevésbé: O(2n)
    eddigi1 = Enum.reverse([c | Enum.reverse(eddigi)])
    [{c, eddigi} | utak(bfa, eddigi1)] ++ utak(jfa, eddigi1)
  end
end

(Route.utak(T.t1()) === [{4, []}, {3, [4]}, {6, [4]}, {5, [4, 6]}, {7, [4, 6]}]) |> IO.inspect()

(Route.utak(T.t2()) === [
   {:a, []},
   {:b, [:a]},
   {:v, [:a, :b]},
   {:c, [:a]},
   {:d, [:a, :c]},
   {:w, [:a, :c, :d]},
   {:x, [:a, :c, :d, :w]},
   {:f, [:a, :c, :d]},
   {:x, [:a, :c, :d, :f]},
   {:y, [:a, :c, :d, :f]}
 ])
|> IO.inspect()

# #### Adott címke összes előfordulása bináris fában útvonallal

defmodule Occurrences do
  @spec cutak(f :: T.tree(), c :: any()) :: utak :: [{c :: any(), cu :: Route.route()}]
  # utak azon csomópontok útvonalainak listája f-ben, amelyek címkéje c
  def cutak(fa, c), do: for({c0, _} = cu <- Route.utak(fa), c0 === c, do: cu)
end

(Occurrences.cutak(T.t1(), :x) === []) |> IO.inspect()

(Occurrences.cutak(T.t2(), :x) === [{:x, [:a, :c, :d, :w]}, {:x, [:a, :c, :d, :f]}])
|> IO.inspect()

defmodule Occurrences2 do
  @spec cutak(f :: T.tree(), c :: any()) :: utak :: [{c :: any(), cu :: Route.route()}]
  # utak azon csomópontok útvonalainak listája f-ben, amelyek címkéje c
  def cutak(fa, c), do: cutak(fa, c, [])

  @spec cutak(f :: T.tree(), c :: any(), eddigi :: Route.route()) ::
          cimkezett_utak :: [{c :: any(), u :: Route.route()}]
  # A cimkezett_utak lista az f fa minden c címkéjű csomópontjához egy {c,u}
  # párt társít, ahol c az adott csomópont címkéje, u pedig az adott
  # csomóponthoz vezető útvonal az eddigi eddigi útvonal elé fűzve
  def cutak(:leaf, _, _), do: []

  def cutak({r, bfa, jfa}, c, eddigi) do
    eddigi1 = eddigi ++ [r]
    cutak = cutak(bfa, c, eddigi1) ++ cutak(jfa, c, eddigi1)
    if r === c, do: [{c, eddigi} | cutak], else: cutak
  end
end

(Occurrences2.cutak(T.t1(), :x) === []) |> IO.inspect()

(Occurrences2.cutak(T.t2(), :x) === [{:x, [:a, :c, :d, :w]}, {:x, [:a, :c, :d, :f]}])
|> IO.inspect()

# ── Binárisok kezelése ──

defmodule Varlen do
  import Bitwise
  @spec decode(bin :: binary()) :: int :: integer()
  # bin decimális értéke int
  def decode(bin) do
    decode(bin, 0)
  end

  defp decode(<<0::1, bytes::7>>, result) do
    (result <<< 7) + bytes
  end

  defp decode(<<1::1, bytes::7, rest::binary>>, result) do
    decode(rest, (result <<< 7) + bytes)
  end
end

IO.puts(Varlen.decode(<<0x01>>) === 1)
IO.puts(Varlen.decode(<<0x7F>>) === 127)
IO.puts(Varlen.decode(<<0xFF, 0x7F>>) === 16383)
IO.puts(Varlen.decode(<<0x81, 0x80, 0x01>>) === 16385)