Math Code Challange

Written for BSIT 330: Discrete Mathematics (Westcliff University), on April 25, 2021
Reviwed on September 22, 2024

As a common practice, developers are requested to complete code challenges to assess their knowledge of a specific language or prove a certain level of experience in logical conundrums. Usually, such tests ask the programmer to receive a specific input and provide an output based on a series of criteria. Sometimes, the expected solution has to be elegant, be aware of edge cases, and work relatively fast given heavier inputs. However, there are cases that the best solution could be found using a comprehensive understanding of mathematics or other subjects. That is undoubtedly the case of the challenge that is going to be presented in this paper.

The Challenge

Finding the total number of possible combinations is a relatively common code challenge. In this one, the developer will receive a number as an input, like the number 4, for instance, and count on how many ways it can be reached using a sum of only the numbers 1, 2, and 3. The conditions are: it is allowed to use any amount of each of these numbers (1 + 1 + 1 + 1 is a valid answer), numbers in different positions are counted separately (2 + 1 + 1 and 1 + 1 + 2 are two different answers), and the result is expected to be as fast as possible.

To illustrate, Table 1 shows all the possibilities given that the input number is 4. Therefore, the expected response of such an algorithm would be 7.

Table 1: The result of all the possibilities given the number 4 as the input.

`1 + 1 + 1 + 1`	`2 + 1 + 1`	`3 + 1`
	`1 + 2 + 1`	`1 + 3`
	`1 + 1 + 2`	`2 + 2`

The Code Solution

When not considering the performance as an essential criterium, the solution is quite simple. It all falls into a recursion problem. Götschi, Sanders, and Galpin (2003) explain recursion as "a process that is capable of triggering new instantiations of itself, with control passing forward to successive instantiations and back from terminated ones" (p. 346). Although recursion can be a significant challenge and is often tested in these code challenges, it always presents a problem in performance. However, the presented problem can easily be solved using this approach, as presented in the following code.

Code 1: A Ruby code that solves the challenge using recursion on the left and the result on the right for the number 4 as input.

# Stores the end result
result = 0

# The recursive function
def iterate(expected, accum = [])
  # The total of the current accumulated result
  total = accum.sum

  # If total is equal to the expected number,
  # add to the result and do not proceed
  if total == expected
    result += 1
    
    # Show the individual result
    puts accum.join(' + ')
  
  # Do not proceed if the total is larger than
  # the expected result
  elsif total > expected
    return
  end
  
  # From 1 to 3, run it again adding to the accumulator
  1.upto(3) { |num| iterate(expected, accum + [num]) }
end

# Start the iteration and then show the result
iterate(ARGV[0].to_i)
puts "The result is: #{result}"

__END__

Expected output for an input of 4
> 1 + 1 + 1 + 1
> 1 + 1 + 2
> 1 + 2 + 1
> 1 + 3
> 2 + 1 + 1
> 2 + 2
> 3 + 1
> The result is: 7

Such code will give the correct answer 100% of the time, but with the cost of taking a long time. To calculate for the input as 24, it takes approximately 1.5 seconds, and for the input as 25, it takes approximately 2.5 seconds. This inflation prevents it from being fully useful.

The Mathematic Solution

The approach presented in this paper was found using none of the permutation-based formulas. At first, it was identified the relationship between the number of available positions and how adding a position or replacing one number for another affects the result of possibilities, regardless of the resulting number of the sum afterward. As shown in the following snipet, It was identified how such manipulations could be calculated using information available at each instance of a sequence.

Snipet: All the possible combinations of 6 positions, regardless of their result, displaying the evolution of possibilities when changing one number for another.

Result        |           | 06 12 18 |           | 07 11 08 13 16 17 |           | 08 10 10 14 14 16 |           | 09 12 15 
----------------------------------------------------------------------------------------------------------------------------
Ones          |           |  6       |           |  5  1  5     1    |           |  4  2  4     2    |           |  3  3    
Twos          |     6     |     6    |    1.0    |  1  5     5     1 |    2.5    |  2  4     4     2 |   1.333   |  3     3 
Threes        |           |        6 |           |        1  1  5  5 |           |        2  2  4  4 |           |     3  3 
----------------------------------------------------------------------------------------------------------------------------
Possibilities |           |     1    |           |         6         |           |         15        |           |    20    
              | Positions |          |           |                   | (6-1)*1/2 |                   | (6-1)*1/3 |

The math presented in the above table works when there are only two different numbers in the set. For example, one of the possible solutions to an input of 8 is to use 1 + 1 + 1 + 1 + 1 + 3 or 1 + 1 + 1 + 1 + 2 + 2, which both have 6 positions. Then, there are 6 different ways of rearranging the first sequence and 15 ways for the second sequence.

With that in mind, the code just has to identify the amount of each number that can be used to form the expected result. Table 2 shows the breakdown for the number 4 as the input.

Table 2: Breakdown of the combinations of numbers that can form an input of 4.

Number of 1s	4	2	0	1
Number of 2s	0	1	2	0
Number of 3s	0	0	0	1

In the table, the sum of each column shows the total of positions, and each value shows how many of each number will be used. This approach already shows an improvement because there are way fewer calculations needed to be performed to find the final result. Another interesting point is that the denominator is represented by the smallest quantity of the used numbers. To reach the rightmost result from the Snipet, we just need to multiply each intermediate number by the number of positions, as in 6 * 1 * 2.5 * 1.3333 = 20.

A similar approach can be made when all three numbers are used. For instance, the number 15 can be formed using 1 + 1 + 2 + 2 + 2 + 2 + 2 + 3. To find the number of possibilities, we just have to multiply the result of two combinations of two numbers. The first is based on the least used number and the most used number, 1 (a single 3) and 4 (all 2s), respectively, which results in 5. The second uses the intermediate used number and the sum of both numbers used previously, 2 (all 1s) and 5, which results in 21. Therefore, the total is given by 5 * 21, which is equal to 105.

The final result is then found by summing the result of each combination. See Table 3 that shows the result of each combination given 8 as the input. The final result summing all the combinations' results is 81.

Table 3: All the combinations and their results for 8 as the input.

Number of 1s	8	6	4	2	0	5	3	1	2	0
Number of 2s	0	1	2	3	4	0	1	2	0	1
Number of 3s	0	0	0	0	0	1	1	1	2	2
Possibilities	1	7	15	10	1	6	20	12	6	3

Conclusion

Sometimes, code challenges can have mathematical solutions, which would give the best possible performance. However, the intention of such tests needs to be clarified. Nevertheless, this challenge and solution prove how math can be an excellent tool for programmers.

References

Götschi, T., Sanders, I., & Galpin, V. (2003, January).
Mental models of recursion. In Proceedings of the 34th SIGCSE technical symposium on Computer science education (pp. 346-350).
http://www.it.uu.se/edu/course/homepage/datadidaktik/ht06/teaching/finalseminar/p346-gotschi.pdf

crashtech/Math Code Challange.md