Number pyramid problem
Here's a question I was asked the other day:
Tori has a maths problem none of us can solve. You start with 6 numbers-1,2,5,6,7,11 add each
consecutive number together to form the row above-do that with the next row until you form a
triangle with 200 at the peak. Can Janis solve it for us.
Example
167
70 97
28 42 55
10 18 24 31
3 7 11 13 18
1 2 5 6 7 11
So the interesting thing about this is that there's a few ways in which you attempt to solve it, I presume that because the question was asked of someone younger some variant of trial-and-error where you permute the order of the bottom numbers is the "intended" answer. A completely trial and error approach here would mean that you have to try \(6! == 120\) arrangements of the bottom row, something that is completely feasible using a computer but not so appealing if you were to do it by hand.
Trial and error - the brute force approach
Since computers allow for cheap computation (hence the name) we can program a computer to do this computation for us. The way this would work as a trial and error naive approach with a computer is as follows:
from itertools import permutations
from typing import List
bottom_row = [1,2,5,6,7,11]
def calc_pyramid(rows):
"""recursive function that will calculate the next rows"""
top_row = rows[-1]
if len(top_row) == 1:
# we are at the top of the pyramid now so break out of the recursion
return rows
next_row_up = []
for i in range(len(top_row)-1):
next_row_up.append(top_row[i] + top_row[i+1])
rows.append(next_row_up)
return calc_pyramid(rows)
result = calc_pyramid([bottom_row])
print(result)
Then you just need to generate all the combos and you'll get the result.
def find_candidate_solution(bottom_row_numbers: List[int], top_number: int):
for bottom_row_candidate in permutations(bottom_row_numbers, len(bottom_row_numbers)):
result = calc_pyramid([list(bottom_row_candidate)])
top_number_found = result[-1][0]
if top_number_found == top_number:
print("found a candidate solution")
print(result)
return result
find_candidate_solution(bottom_row_numbers=bottom_row, top_number=200)
Now it turns out there's no bottom arrangement with these numbers row that satisfies this 200 at the top constraint. I'm sure that if you were a student and were assuming that there was an answer you'd be stressing about this question, but there's no such answer with this bottom row.
There's an important lesson to learn here, which is that many stated problems have no feasible solution. The other important lesson is that you should never have to rely solely on authority for mathematical problems, you can always verify from first principles given the time and resources.
Going beyond a brute force approach
One of the things that would have been especially annoying is that if you attempted to do the brute force approach by hand you would have had to have checked a large number of candidate solutions. Assuming a bottom row containing \(k\) items of which \(n\) were distinct we would have this many potential candidates:
Which in this case was:
Clearly checking 120 such cases is going to be tedious at best by hand and will become completely infeasible on larger sets.
Part of the intuition of this problem come from the fact that putting the larger numbers in the middle makes for a large sum at the top.
Consider these two bottom rows:
5
2 3
1 1 2
compared with:
6
3 3
1 2 1
You can see that swapping numbers such that a larger number is closer to the middle will result in a higher overall sum. This information starts to provide us with some interesting constraints.
For example if the top number we currently have is too big for the solution then any swap that will place a larger number closer to the middle will also not be a solution.
For example let's say we have the numbers 1 5 7 and we want to make a target of 20. We can start by placing those numbers down:
18
6 12
1 5 7
Now the top result 18 which is smaller than 20. Instead of just guessing at the next candidate for the bottom row we can swap two numbers such that we move a larger number closer to the center of the bottom row. Let's try swapping the 5 and 7:
20
8 12
1 7 5
This has increased the top number to 20. Because this is our goal we stop.
If you are going to attempt this problem by hand this swaps approach will drastically cut down the amount of time it takes to search for an answer. It will also sometimes show you if the answer is impossible to reach because you'll find a situation where if the sum is too small then you'd need to make a swap to make it bigger, but if you can't do any such swaps then the problem necessarily doesn't have an answer because you already have the largest sum amount possible.
Symmetry
In any combinatorial problem exploiting symmetry can lead to much smaller effective problem sizes. If we only wish to find the sum at the top of the pyramid we can mirror the problem around the central values since addition is commutative.
Note that:
a+2b+c
a+b b+c
a b c
We can switch \(a\) and \(b\) here and the results will be the same. We can't however switch \(a\) and \(b\) and retain the same result.
Going one step further reveals something interesting:
a+3d+3c+d
a+2b+c b+2c+d
a+b b+c c+d
a b c d
We can swap any 2 elements that are the same distance from the edges and the top result is the same. So we can swap \(a\) with \(d\) and nothing changes to the sum at the top, similarly for swapping \(b\) with \(c\).
Solution approach
An algorithm I'd use for this is to assign numbers into bins, this makes use of the way in which symmetry in the problem works.
Take for example:
a+2b+c
a+b b+c
a b c
The slots \({a, c}\) form one bin \(B_1\) since they are the same distance from the edges, and \(b\) alone forms the next bin \(B_2\).
If the sum at the top of the pyramid is too high then we swap a pair of numbers assigned to adjacent bins such that a larger number moves to a smaller bin and the smaller number moves to a larger bin. If the sum is too low we swap a pair of numbers such that the sum will be higher.
In order to avoid potential cycles you have to keep a list of all the previous arrangements you have tried since you can't revisit them.
You end by either not being able to swap any items or by finding the goal.
You can do this algorithm by hand if you want.
I decided it would be interesting to write some code to implement this algorithm. Turns out this was the better part of an afternoon worth of work and can be found over on github here:
https://github.com/shuttle1987/number-pyramid/blob/master/swapper.py
There's a few interesting concepts in there like the use of tuples to store results in a dictionary and just the general structure of how the candidate solutions are generated.