#### 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.

- 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:

`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
```