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 adecimal(base10) number, inbinary(base2)
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.
- Video available here: https://youtu.be/344o8gRWEVY
- Also streaming on Twitch: https://www.twitch.tv/percygrunwald
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:
- Convert the number into a decimal representation
- 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:
digitslist should not be emptybase_aandbase_bshould both be an integer and greater than1(the lowest possible base is2)- all items in
digitsshould be0 <= 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