given ints 1-9 count the ways unique sets of 3 add up to a given sum

Question

Given a range of integers, count the number of ways each single integer can be used in unique sets of three operands that all add up to a given sum.

For a technical interview I was asked to solve a puzzle (Without coding). The puzzle was given a 3X3 grid with unique integers 1-9 each filling a location on the grid, arrange the numbers so that each set of 3 numbers in a line (Vertical, horizontal and diagonal) all add up to 15. I wanted to know what the occurrence of numbers are for all possible unique sets of 3 unique integers. That would go a long way to help solve the problem. Because different locations of the grid will have different set needs. The sides of the grid will need 2 sets that all contain the same number. The corners need 3 sets that all contain the same number. The center will need 4 sets that all contain the same number. There is only 1 center, 4 sides, and 4 corners. I suspected that there was only number that would support 4 sets of 3 unique numbers, I suspected that number was 5. I wanted to write a program to show a count the occurrence of every number across all unique sets of 3 numbers between 1 and 9, to help me solve the puzzle.

This is what I came up with in C#:

 /// <summary>
 /// Given a range of integers, count the number of ways each single integer can be used in unique sets of three 
 /// operands that all add up to a given sum.
 /// </summary>
 /// <param name="sum">The sum that each set of three operands should equal.</param>
 /// <param name="OperandMinimum">The highest integer in the range of integers included as possible opperands.</param>
 /// <param name="OperandMaximum">The lowest integer in the range of integers included as possible opperands.</param>
 /// <returns>A Dictionary of the count (value) of ways a single integer (key) can occur in unique sets of three operands 
 /// that all add up to a given sum.</returns>
 public static Dictionary<int,int> getCountofOpperandOccurancesIn_ThreeUniqueOperandsForSingleSum(int sum, int OperandMinimum = 1, int OperandMaximum = 9)
 {
 Dictionary<int, int> SumOfOperands = new Dictionary<int, int>();
 List<int[]> ListOfThreeOperands = GetAllGroupsOfThreeUniqueOperandsForSingleSum(sum, OperandMinimum = 1, OperandMaximum = 9);
 foreach(int[] operandsGroup in ListOfThreeOperands)
 {
 foreach(int operand in operandsGroup)
 {
 if (SumOfOperands.ContainsKey(operand))
 {
 SumOfOperands[operand]++;
 }
 else
 {
 SumOfOperands.Add(operand, 1);
 }
 }
 }
 return SumOfOperands;
 }
 /// <summary>
 /// Get three unique operands for a single sum such that operand1 + operand2 + operand3 = sum 
 /// where all operands are unique and within a range of adgacent integer values. 
 /// </summary>
 /// <param name="sum">The sum that all int array groups of three returned are equal to.</param>
 /// <param name="OperandMinimum">The maximum value of all unique operators that can be included as part of the int array groups returned.</param>
 /// <param name="OperandMaximum">The minimum value of all unique operators that can be included as part of the int array groups returned.<</param>
 /// <returns>A list of int array groups where all operands in a group are unique and together form a sum passed to the method.</returns>
 public static List<int[]> GetAllGroupsOfThreeUniqueOperandsForSingleSum(int sum, int OperandMinimum = 1, int OperandMaximum = 9)
 {
 List<int[]> ListOfThreeOperands = new List<int[]>();
 for (int FirstOperand = OperandMinimum; FirstOperand <= OperandMaximum; FirstOperand++){
 for (int SecondOperand = OperandMinimum; SecondOperand <= OperandMaximum; SecondOperand++){
 if (SecondOperand == FirstOperand)
 {
 break;
 }
 for (int third = OperandMinimum; third <= OperandMaximum; third++){
 if (third == FirstOperand || third == SecondOperand)
 {
 break;
 }
 if (FirstOperand + SecondOperand + third == sum)
 {
 ListOfThreeOperands.Add( new int[] { FirstOperand, SecondOperand, third });
 }
 }
 }
 }
 return FilterForUniqueOperands(ListOfThreeOperands);
 }
 public static List<int[]> FilterForUniqueOperands(List<int[]> OperandList)
 {
 List<int[]> filteredList = new List<int[]>();
 for (int i= 0; i< OperandList.Count; i++)
 {
 if (filteredList.Count <= 0)
 {
 filteredList.Add(OperandList[i]);
 }
 else
 {
 bool IsPresent = false;
 foreach (int[] operandGroup in filteredList)
 {
 if (IsAllValuesPersentInEach(OperandList[i], operandGroup))
 {
 IsPresent = true;
 break;
 }
 }
 if (!IsPresent)
 {
 filteredList.Add(OperandList[i]);
 }
 }
 }
 return filteredList;
 }
 public static bool IsAllValuesPersentInEach(int[] A, int[] B)
 {
 if (A.Length != B.Length || A.Length <= 0 || B.Length <= 0)
 {
 throw new Exception("Arrays A and B must contain the same number of values Greater than 0");
 }
 bool IsAllValuesPersent = true;
 foreach( int valPresent in A)
 {
 if (!B.Contains(valPresent))
 {
 IsAllValuesPersent = false;
 }
 }
 return IsAllValuesPersent;
 }

The results of the algorithm (shown below) have shown me that 5 has to be the middle number and the side numbers must be 1,3,7, and 9. This allowed me to solve the puzzle in 8 unique ways.

Number - occurrence count
1 - 2
2 - 3
3 - 2
4 - 3
5 - 4
6 - 3
7 - 2
8 - 3
9 - 2

• slepic: 15 is not chosen randomly here. It is the only number for which you can arrange the grid so that all rows and columns and diagonals equal that number. Because sum of all those numbers is 45. Lets say a,b,c from interval 1-9 and a<c and a+b+c=15. If b Is 5 then a<b<c is always true. For any other b, this is not always true. Therefore 5 must be in the middle :)
• slepic: Since b=5, then a+c=10 which is even. And so a and c must both be even or both be odd. If we put odd number in one corner and its opposite then we need 6 more even numbers to fill the rest, but we only have 4. Therefore corners must be even. Just to confirm, if I put 2 even numbers in a corner and its opposite, then i need 4 odd and 2 even numbers to fill the rest, which is what I have. The 8 possibilities are just rotations (x4) and reflection over a central axis (x2)
• amalgamate: @slepic I see how all you have said is true, but I find your first comment slightly confusing. Could you connect your conclusions to your statements? For example when you say "therefore 5 must be in the middle", I know that is true but I am not sure how it directly connects to your statements. I ask because I am intrigued and I want to understand you proof a little better.
• slepic: Sry I deleted my second try because it didnt feel any clearer. Ill try to find a way to explain it somewhat simpler And get Back to you...
• slepic: Btw you can turn this into a set of 9 equations with 9 unknowns, do some substitutions And figure out that 5 must be in center regardless of some conditions (ie it doesnt matter if all those numbers are different to each other or not, 5 must be in center anyway)

Answer 1

I think perhaps, you're being to literal with this.

First off, when you are grouping your data by digits and getting the count of each one, a simple int[] will do. In this case to keep things simple a 10 element array will give you indexes from 1-9.

Also consider, if you start at 9, the difference is 6 divide by 2 will result in 3 and 3 as the other 2 digits necessary. Now you must have unique digits so you increase one by 1 and decrease the other by 1. Now you start at 4 and 2. Now keep increasing and decreasing until the high one reaches the start number or the low one reaches 0. Each time you increase and decrease increment the elements at the indexes for the start, and the 2 other digits. When this loop finishes decrease the start number, until the start number reaches 5. At this point you've found all the unique combinations that add to 15. 5 works as a limit since 15/3=5. add one and subtract 1 and you get 4,5,6 any number you consider that is less than 6 will already have been considered.

It could look like this:

static int[] Sum15Dist()
{
 var dist = new int[10];
 const int target = 15;
 int start = 9;
 while(start > 5)
 {
 int intA = (int)Math.Ceiling((target - start)/2.0);
 int intB = target - start - intA;
 if(intA == intB)
 {
 ++intA;
 --intB;
 }
 while(intB > 0 && intA < start)
 {
 ++dist[start];
 ++dist[intA++];
 ++dist[intB--];
 }
 --start;
 }
 return dist;
}