1. Home
  2. Elixir + Phoenix Tutorials & Courses
  3. All Your Base Problem - Exercism Elixir Solution & Tutorial

All Your Base Problem - Exercism Elixir Solution & Tutorial

Percy Grunwald's Profile Picture

Written by Percy Grunwald

— Last Updated January 8, 2024

Table of Contents

This problem required us to implement a function to express a number in another base. For instance:

Express the number 42, which is a decimal (base 10) number, in binary (base 2)

42 (base 10) expressed in base 2 is 101010. The resulting function call:

iex> AllYourBase.convert([4, 2], 10, 2)
[1, 0, 1, 0, 1, 0]

101010 (base 2) expressed in base 10 is 42. The resulting function call:

iex> AllYourBase.convert([1, 0, 1, 0, 1, 0], 2, 10)
[4, 2]

The function should also be able to convert between numbers in any arbitrary bases. For example, we should be able to express 42 (base 10) in hexadecimal (base 16) and trinary (base 3) and also convert between any bases:

iex> AllYourBase.convert([4, 2], 10, 16)
[2, 10]

iex> AllYourBase.convert([4, 2], 10, 3)
[1, 1, 2, 0]

iex> AllYourBase.convert([2, 10], 16, 3)
[1, 1, 2, 0]

iex> AllYourBase.convert([1, 1, 2, 0], 3, 16)
[2, 10]

iex> AllYourBase.convert([2, 10], 16, 10)
[4, 2]

iex> AllYourBase.convert([1, 1, 2, 0], 3, 10)
[4, 2]

This was a pretty challenging problem, and my live stream of the solution is about 2 hours long. Keep reading to see how I approached and solved the problem!

Live solution video

This is my daily live stream video solution to this problem.

Explanation of the solution

First step: split the problem into 2 parts

My first step in approaching this problem was to split it into 2 parts:

  1. Convert the number into a decimal representation
  2. Express the decimal number in some arbitrary base as a list

As a data flow, this is what I was picturing in my head:

# convert [4, 2] base 10 into base 2
[4, 2] => 42 => [1, 0, 1, 0, 1, 0]

# convert [1, 0, 1, 0, 1, 0] base 2 into base 10
[1, 0, 1, 0, 1, 0] => 42 => [4, 2]

I want this intermediate step because my brain works in decimal and all the integer math operations work on decimal numbers.

Breaking it up into 2 steps also makes our code easier to comprehend, since we can write nicely named functions for each step that express exactly what’s happening.

Function to convert a list of numbers and base to a decimal number

This function is actually pretty close to what we implemented in the solution to the previous Roman Numerals problem. Basically we want to express this idea in function form:

[4, 2] base 10 
=> (4 * 10^1) + (2 * 10^0)
=> 42

[1, 0, 1, 0, 1, 0] base 2 
=> (1 * 2^5) + (0 * 2^4) + (1 * 2^3) + (0 * 2^2) + (1 * 2^1) + (0 * 2^0) 
=> 42

This was my solution in Elixir code:

defp convert_to_decimal(digits, base) do
  digits
  |> Enum.with_index(1)
  |> Enum.map(fn {digit, index} ->
    factor = pow(base, length(digits) - index)

    digit * factor
  end)
  |> Enum.sum()
end

defp pow(number, power) do
  :math.pow(number, power) |> :erlang.floor()
end

The flow of data can be represented like this:

[4, 2]
=> [{4,1}, {2, 2}]
=> [40, 2]
=> 42

The pow/2 function is just a little helper that makes doing powers cleaner given that we know we’re working with integers. Erlang’s :math.pow/2 returns a float.

Function to convert a decimal number into a list of numbers in an arbitrary base

This recursive function does most of the work for this problem. It converts an arbitrary decimal int into a list of numbers in base. It needs to be a recursive function because we need to reference the previous power and have access to the list of numbers that we’ve built up.

defp convert_to_base(int, base, acc) when is_integer(int) and int > 0 do
  {acc_list, previous_power} = acc

  power =
    if is_nil(previous_power) do
      get_highest_power(int, base)
    else
      previous_power - 1
    end

  highest_factor = pow(base, power)
  int_quotient = div(int, highest_factor)
  int_remainder = rem(int, highest_factor)

  cond do
    power == 0 ->
      acc_list ++ [int_quotient]

    power == 1 ->
      acc_list ++ [int_quotient, int_remainder]

    true ->
      convert_to_base(int_remainder, base, {acc_list ++ [int_quotient], power})
  end
end

I’ll go through some examples of the logic of the functions to make it clearer.

The iterations will look like this for converting 42 into base 10 representation:

# iteration 1
int = 42, base = 10, acc = {[], nil}

power = 1 (highest power of `10` required is 10^1, because no previous_power supplied)
highest_factor = 10^1 = 10
int_quotient = 42 / 10 = 4
int_remainder = 42 % 10 = 2

cond chooses path for `power == 1`
  return acc_list ++ [int_quotient, int_remainder] 
  = [] ++ [4, 2] = [4, 2]

We don’t need to do any further iterations if the maximum power is 1, since we know that the next iteration for power 0 will be the same for any base (anything to the power of 0 is 1).

Let’s see an example where multiple iterations will be needed (convert 9 to binary):

# iteration 1
int = 9, base = 2, acc = {[], nil}

power = 3 (highest power of `2` required is 2^3 == 8, because no previous_power is supplied)
highest_factor = 2^3 = 8
int_quotient = 9 / 8 = 1
int_remainder = 9 % 8 = 1

cond chooses default path because power is not 0 or 1
  recursively call convert_to_base with the remainder of the function
  convert_to_base(int_remainder, base, {acc_list ++ [int_quotient], power})
    = convert_to_base(1, 2, {[] ++ [1], 3})

# iteration 2
int = 1, base = 2, acc = {[1], 3}

power = 3 - 1 = 2 (because previous_power is supplied in acc)
highest_factor = 2^2 = 4
int_quotient = 1 / 4 = 0
int_remainder = 1 % 4 = 1

cond chooses default path because power is not 0 or 1
  recursively call convert_to_base with the remainder of the function
  convert_to_base(int_remainder, base, {acc_list ++ [int_quotient], power})
    = convert_to_base(1, 2, {[1] ++ [0], 2})

# iteration 3
int = 1, base = 2, acc = {[1, 0], 2}

power = 2 - 1 = 1 (because previous_power is supplied in acc)
highest_factor = 2^1 = 2
int_quotient = 1 / 2 = 0
int_remainder = 1 % 2 = 1

cond chooses path for `power == 1`
  return acc_list ++ [int_quotient, int_remainder] 
  = [1, 0] ++ [0, 1] = [1, 0, 0, 1]

Function to get the highest power necessary to express a decimal number in an arbitrary base

The function above makes use of a helper function to get the highest power necessary to express a decimal number in a base. For example, if we want to express 42 in base 10, the highest power we need is 1 (10^1 == 10), which is to say we only need tens and ones to express 42 in base 10. The reason the highest power is not 2 is because 10^2 == 100, which is higher than 42.

I implemented this as a recursive function as well, starting from a power of 0 and going up until we go over the decimal number target.

defp get_highest_power(int, base, power \\ 0) do
  factor = pow(base, power)

  cond do
    int == factor ->
      power

    int > factor ->
      get_highest_power(int, base, power + 1)

    true ->
      power - 1
  end
end

For 42, the iterations look like this:

# iteration 1
int = 42, base = 10, power = 0

factor = 10^0 = 1

cond chooses path for int > factor
  recursive call to get_highest_power(42, 10, 0 + 1)

# iteration 2
int = 42, base = 10, power = 1

factor = 10^1 = 10

cond chooses path for int > factor
  recursive call to get_highest_power(42, 10, 1 + 1)

# iteration 3
int = 42, base = 10, power = 2

factor = 10^2 = 100

cond chooses default path because factor is greater than int
  (the reason we subtract 1 from the power is because we know
  that if the factor is greater than the int, we can make the int
  from the powers below)

  return power - 1 = 1

Here are some more examples to demonstrate:

int = 42, base = 10 => 1 => because 10^2 (100) is greater than 42

int = 1000, base = 10 => 3 => because 10^3 is exactly equal to 1000

int = 42, base = 2 => 5 => because 2^6 (64) is greater than 42

Function to validate the input to the main convert/3 function

The validation function makes sure that the inputs to the main convert/3 function are valid:

  • digits list should not be empty
  • base_a and base_b should both be an integer and greater than 1 (the lowest possible base is 2)
  • all items in digits should be 0 <= item < base_a
defp is_valid?(digits, base_a, base_b) do
  all_digits_between_zero_and_base_a? =
    Enum.all?(digits, fn digit ->
      0 <= digit and digit < base_a
    end)

  length(digits) > 0 and is_integer(base_a) and base_a > 1 and is_integer(base_b) and base_b > 1 and
    all_digits_between_zero_and_base_a?
end

Main function that ties everything together

Since we have factored our functionality into smaller helper functions, our main convert/3 function just needs to validate the input and then pipe the list through the conversion helpers:

@doc """
Given a number in base a, represented as a sequence of digits, converts it to base b,
or returns nil if either of the bases are less than 2
"""
@spec convert(list, integer, integer) :: list
def convert(digits, base_a, base_b) do
  if is_valid?(digits, base_a, base_b) do
    digits
    |> convert_to_decimal(base_a)
    |> convert_to_base(base_b)
  else
    nil
  end
end

Full solution in text form

Here’s the full solution in text form, in case you want to look over the final product:

defmodule AllYourBase do
  @doc """
  Given a number in base a, represented as a sequence of digits, converts it to base b,
  or returns nil if either of the bases are less than 2
  """
  @spec convert(list, integer, integer) :: list
  def convert(digits, base_a, base_b) do
    if is_valid?(digits, base_a, base_b) do
      digits
      |> convert_to_decimal(base_a)
      |> convert_to_base(base_b)
    else
      nil
    end
  end

  defp is_valid?(digits, base_a, base_b) do
    all_digits_between_zero_and_base_a? =
      Enum.all?(digits, fn digit ->
        0 <= digit and digit < base_a
      end)

    length(digits) > 0 and is_integer(base_a) and base_a > 1 and is_integer(base_b) and base_b > 1 and
      all_digits_between_zero_and_base_a?
  end

  defp convert_to_decimal(digits, base) do
    digits
    |> Enum.with_index(1)
    |> Enum.map(fn {digit, index} ->
      factor = pow(base, length(digits) - index)

      digit * factor
    end)
    |> Enum.sum()
  end

  defp convert_to_base(int, base), do: convert_to_base(int, base, {[], nil})

  defp convert_to_base(0, _base, _acc), do: [0]

  defp convert_to_base(int, base, acc) when is_integer(int) and int > 0 do
    {acc_list, previous_power} = acc

    power =
      if is_nil(previous_power) do
        get_highest_power(int, base)
      else
        previous_power - 1
      end

    highest_factor = pow(base, power)
    int_quotient = div(int, highest_factor)
    int_remainder = rem(int, highest_factor)

    cond do
      power == 0 ->
        acc_list ++ [int_quotient]

      power == 1 ->
        acc_list ++ [int_quotient, int_remainder]

      true ->
        convert_to_base(int_remainder, base, {acc_list ++ [int_quotient], power})
    end
  end

  defp convert_to_base(_int, _base, _acc), do: nil

  defp get_highest_power(int, base, power \\ 0) do
    factor = pow(base, power)

    cond do
      int == factor ->
        power

      int > factor ->
        get_highest_power(int, base, power + 1)

      true ->
        power - 1
    end
  end

  defp pow(number, power) do
    :math.pow(number, power) |> :erlang.floor()
  end
end

Comment & Share