Can someone give me some hint/guide how to start this Elixir homework (I have to write a function)

Questions / Help
1

Hi guys, I started to learn Elixir at University and I need to write a function (sit!) for homework. I have been struggling with this for days now.

The description of the task:

How many ways can ‘k’ people sit down in ‘n>2’ rows, but moving from the front to the back every row has ‘d’ less people.

Specifications:

@type variant :: { h :: integer, d :: integer }
@type seatings :: { n :: integer, vs :: [ variant ] }

@spec sit!( k :: integer ) :: r :: { m :: integer, ss :: [ seatings ] }

k: number of the people
m: maximum variation of the seating
ss: list of {n, vs} pairs
n: number of rows of the seating
h: the shortest row (back row/first row)
d: the difference between every neighboring rows

Here is an example:

10 - >
XXXX
XXX
XX
X

iex> Khf1.sit! 10
{1, [{4, [{1, 1}]}]}

In this case k=10, m=1 because there is only one variation, n=4 because there is 4 rows, h=1 because the shortest row is 1, d=1 because the difference between rows is 1.

I need to solve this problem with recursion and the output must look like the specification.

More examples:

iex> Khf1.sit! 101
{0, []}
iex> Khf1.sit! 15
{5, [{3, [{1, 4}, {2, 3}, {3, 2}, {4, 1}]}, {5, [{1, 1}]}]}
iex> Khf1.sit! 14
{1, [{4, [{2, 1}]}]}
iex> Khf1.sit! 10
{1, [{4, [{1, 1}]}]}
iex> Khf1.sit! 9
{2, [{3, [{1, 2}, {2, 1}]}]}
iex> Khf1.sit! 5
{0, []}

If someone could give me some tips how to do this that would be very helpful.
Thank you.

2

I’m learning Elixir too and when I look at your exercise, I had some ideas and wrote it down:

  • Firstly, I find what is max rows could be? So I assume that the max rows is when the different between 2 rows is 1 => So I can get the possible max rows.
  • Then I check with each row + people to find out its variants
    I tested and it could pass your requirements.
    Please refer to my code version, it might not good enough (the ranges I use in for is not the best) but I hope it could help you get some ideas.
    I’m looking forward to see your better version of this exercise.
defmodule Khf1 do
  def sit!(n) do
    max_row = :math.sqrt(n*2) |> floor()
    res =
      for row <- 3..max_row, into: [], do: sit_in_rows(n, row)

    res = res |> Enum.filter(&(&1 != nil))
    variants = Enum.reduce(res, 0, fn {v, _}, acc -> acc + v end )

    {variants, res}
  end


  def sit_in_rows(n, row) do
    max_d = floor(n/row)      # max differences between 2 rows
    res =
      for f <- 1..(n-row), d <- 1..max_d, satisfy?(f, d, n, row), into: [], do: {f, d}

    res = res |> Enum.filter(&(&1 != nil))
    variants = Enum.count(res)
    if variants != 0, do: {variants, res}, else: nil
  end

  def satisfy?(first, diff, n, row) do
    last = first + diff*(row - 1)
    sum = (first + last) * row/2

    sum == n
  end
end
1 Like
3

If the question is “how many permuatations of seating arrangements are there?”
then the solution is:

  1. calculate number of seats, call it k (do this as a recursive function, it will accept “number of rows” and “diff d between number of seats per row” as its 2 arguments)
  2. Get the number of people, call it n
  3. calculate the “k-permutations of n” (see here: Permutation - Wikipedia), like this:
n! / (n - k)!

In elixir, it would look like this:

factorial(n) / factorial(n - k)

The recursion happens when you write a “factorial” function, to calculate n! and (n - k)!. That function will be nicest as a recursive function.

Here’s my take on this problem.

defmodule SeatingProblem do
  @doc """
  Gets the factorial of a non-negative number.

  Here's how factorials work:
  factorial(5) = 5! = 5 * 4! = 5 * 4 * 3! = ... = 5 * 4 * 3 * 2 * 1
  """
  def factorial(n) when n < 0 do
    raise("Factorials don't work with negative numbers")
  end

  def factorial(0), do: 1
  def factorial(1), do: 1

  def factorial(n) when is_integer(n) do
    n * factorial(n - 1)
  end

  @doc """
  https://en.wikipedia.org/wiki/Permutation
  """
  def k_permutations_of_n(k, n) do
    div(factorial(n), factorial(n - k))
  end

  @doc """
  Why is this safe? Because we cannot get the factorial of a negative number.
  The number of ways of seating 35 people in 200 seats
  is the same as
  the number of ways of assigning 35 seats to 200 people.
  """
  def safe_k_permutations_of_n(k, n) do
    if n > k do
      k_permutations_of_n(k, n)
    else
      k_permutations_of_n(n, k)
    end
  end

  @doc """
  This is just to visualize what the rows of seats look like. Each "x" is a seat.
  """
  def visualize_seats(number_of_rows, row_seat_increment, initial_row_seat_count) do
    1..number_of_rows
    |> Enum.map(fn row_index ->
      seat_count = initial_row_seat_count + row_seat_increment * (row_index - 1)

      1..seat_count
      |> Enum.map(fn _ -> "x" end)
      |> Enum.join()
      |> IO.puts()
    end)
  end

  @doc """
  Gets the total number of seats
  """
  def number_of_seats(number_of_rows, row_seat_increment, initial_row_seat_count) do
    last_row_seat_count = initial_row_seat_count + row_seat_increment * (number_of_rows - 1)
    div((last_row_seat_count + initial_row_seat_count) * number_of_rows, 2)
  end

  @doc """
  Gets number of different permutations
  """
  def permutations(number_of_people, number_of_rows, row_seat_increment, initial_row_seat_count) do
    IO.puts("There are #{number_of_people} people.")
    seats_count = number_of_seats(number_of_rows, row_seat_increment, initial_row_seat_count)
    IO.puts("There are #{seats_count} seats in total.")
    IO.puts("Here's how the seats are arranged:")
    visualize_seats(number_of_rows, row_seat_increment, initial_row_seat_count)
    result = safe_k_permutations_of_n(seats_count, number_of_people)

    IO.puts(
      "Assuming the order of people matters, there are #{result} different ways of seating these people."
    )
  end
end

number_of_people = 10
number_of_rows = 4
row_seat_increment = 1
initial_row_seat_count = 1

SeatingProblem.permutations(
  number_of_people,
  number_of_rows,
  row_seat_increment,
  initial_row_seat_count
)

You can really push this.
See how many ways there are of seating 200 people in 5 rows incrementing 3 seats at a time.

6 Likes
4

You’ve got an Elixir course in your university? That’s awesome! Elixir becoming mainstream?… :wink:

5 Likes
5

Thank you for your solution! Now I am starting to understand Elixir more.

1 Like
6

Here is my email: bence.makula97@gmail.com
Could you contact me? I would happily receive some tips or educational material to have better knowledge in Elixir.

1 Like
7

Yeah! I’m sure we could help each other :grinning_face_with_smiling_eyes: