Home Posts Tags Post Search Tag Search

Post 27

Hacker Rank 03 - Pascals Triangle

Published on: 2025-05-19 Tags: elixir, Blog, Hacker Rank
For this challenge I needed to print out the Pascals Triangle for a given size. The triangle is written as such:

1
1 1
1 2 1
1 3 3 1
...

As you might be able to see the triangle is constructed such that the next line is the sum of 2 of the given entries of the previous line with 1 appended and prepended. 

1 3 3 1 is 
1 <> 1 + 2, 2 + 1 <> 1

So in this case if you can find a way to go through each pairing of the previous line you can get the values for the inside. So lets start there.

Enum.chuck_every is great for this. [https://hexdocs.pm/elixir/1.12/Enum.html#chunk_every/4]

This this you can determine the amount of items that you want in the list and the step so that you can go forward by that amount.

So 
Enum.chunk_every([1, 2, 3, 4, 5, 6], 2, 1)
[[1,2], [2,3], [3,4], [4,5], [5,6], [6]]

This is perfect for our needs (although just this won't get us the entire row, and we need a way to deal with the last element that isn't needed (easy fix there, just add :discard)

Enum.chunk_every([1, 2, 3, 4, 5, 6], 2, 1, :discard)
[[1,2], [2,3], [3,4], [4,5], [5,6]]

Okay so let's put this into action.

    def pascal(0), do: [1]
    def pascal(1), do: [1, 1]
    
    def pascal(x) do
        Enum.chunk_every(pascal(x - 1), 2, 1, :discard)
        |> Enum.map(fn [x , y] -> 
            x + y
        end)
    end

Ok let's go over this

Enum.chunk_every gets us the set of 2 elements that we want to sum,
We then pass it to the Enum.map so that we can keep each element separate and just hold there sum.

We also needed to deal with the base case as we want to recursively deal with each row.

Now we need to append and prepend 1 to either side. I changed the function life so:

    def pascal(x) do
        inside = Enum.chunk_every(pascal(x - 1), 2, 1, :discard)
        |> Enum.map(fn [x , y] -> 
            x + y
        end)
        [1] ++ inside ++ [1]
    end

Now we need to put each row into a list so that we can have the entire triangle for the given input.

I added a simple function that will go through the pascal for the given size:

    def tree(x) do
        Enum.map(0..x - 1, fn index -> 
            pascal(index)
        end)
    end

This simply will ask for every row for a given size and map it to the list.

Okay so now we have the triangle but it's not in the format that Hacker Rank wants. We want the elements separated by a space not a series of lists. That is where Enum.join() comes in [https://hexdocs.pm/elixir/1.12/Enum.html#join/2]:

With this function you can join and items with a specific joiner (in this case " ")

    def print_tree(nested_list) do
        Enum.each(nested_list, fn row ->  
            IO.puts(Enum.join(row, " "))
        end)
    end

So I take every row in the nested_list and join each row item into a single string and then put them into the IO stream. 

This can still be made to work even faster as each row is created from scratch but as this is a very simple set of addition it won't take long to get to any size we want.