Skip to content

Latest commit

 

History

History
218 lines (171 loc) · 5.09 KB

pascals_triangle.livemd

File metadata and controls

218 lines (171 loc) · 5.09 KB

Pascal's Triangle

Mix.install([
  {:jason, "~> 1.4"},
  {:kino, "~> 0.9", override: true},
  {:youtube, github: "brooklinjazz/youtube"},
  {:hidden_cell, github: "brooklinjazz/hidden_cell"}
])

Navigation

Pascal's Triangle

In this exercise, you're going to generate Pascal's Triangle for a certain number of rows.

In Pascal's Triangle, each number is the sum of the two integers above it.

flowchart
a[1]
b1[1]
b2[1]
c1[1]
c2[2]
c3[1]
d1[1]
d2[3]
d3[3]
d4[1]
e1[1]
e2[4]
e3[6]
e4[4]
e5[1]

a --> b1
a --> b2

b1 --> c1
b1 --> c2

b2 --> c2
b2 --> c3

c1 --> d1
c1 --> d2

c2 --> d2
c2 --> d3

c3 --> d3
c3 --> d4

d1 --> e1
d1 --> e2

d2 --> e2
d2 --> e3

d3 --> e3
d3 --> e4

d4 --> e4
d4 --> e5
Loading

We can also represent Pascal's triangle as a list of lists.

[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

In the Elixir cell below, finish the of/1 function in the Pascal module which will return Pascal's triangle in a list for n number of rows.

Pascal.of(1)
[
  [1]
]

Pascal.of(2)
[
  [1],
  [1, 1],
]

Pascal.of(5)
[
  [1],
  [1, 1],
  [1, 2, 1],
  [1, 3, 3, 1],
  [1, 4, 6, 4, 1]
]
Example Solution

The following solution works, but is not very performant because it has to recalculate every previous row.

defmodule Pascal do
  def row(1), do: [1]
  def row(2), do: [1, 1]
  def row(n), do: [1 | Enum.chunk(row(n - 1), 2, 1) |> Enum.map(fn [a, b] -> a + b end)] ++ [1]

  def of(n) do
    Enum.map(1..n, &row/1)
  end
end

By building up the solution and referring to the previous value, we can avoid recalculating each row.

defmodule Pascal do
  def of(1), do: [[1]]
  def of(2), do: [[1], [1, 1]]

  def of(n) do
    Enum.reduce(3..n, [[1, 1], [1]], fn each, [prev | _] = acc ->
      row = [1 | Enum.chunk(prev, 2, 1) |> Enum.map(fn [a, b] -> a + b end)] ++ [1]
      [row | acc]
    end)
    |> Enum.reverse()
  end
end
defmodule Pascal do
  @doc ~S"""
  Generates a Pascal's Triangle of `n` rows.

  ## Examples

      iex> Pascal.of(1)
      [[1]]

      iex> Pascal.of(5)
      [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
  """
  def of(n) do
  end
end

Commit Your Progress

DockYard Academy now recommends you use the latest Release rather than forking or cloning our repository.

Run git status to ensure there are no undesirable changes. Then run the following in your command line from the curriculum folder to commit your progress.

$ git add .
$ git commit -m "finish Pascal's Triangle exercise"
$ git push

We're proud to offer our open-source curriculum free of charge for anyone to learn from at their own pace.

We also offer a paid course where you can learn from an instructor alongside a cohort of your peers. We will accept applications for the June-August 2023 cohort soon.

Navigation