How Number of ways to get a final score help you live a better life - I

Coding Jan 18, 2020

Problem Statement

The purpose of this blog is to explain the problem of achieving a final score, given the set of input balls. Let's understand a pool game first. A pool table consists of six pockets and balls numbered from 1 to 15. A player scores when he pockets a ball (taking the ball numbered two gives the equivalent two).
Let's take an example of a custom pool game with valid balls, which is the selection of only a few numbered balls from the set. We have to find the number of ways a player can reach a final score using valid balls.
Let's say that the user has selected three balls (2, 4 and 6), and played the pool table, and his final score is 6. There are three number of ways the player can score six by pocketing [{2,2,2}, {2,4}, {6}].
We have to define a method that accepts valid and final input and return number of ways to reach a score.

Explanation

We have an input array named valid to store the chosen balls and a number final defining the final score of the player.
We define an array named ways to store the number of ways to reach an element denoted by index. Example, ways[i] means the number of ways to reach i.
Let's say that the user has selected three balls (2, 4 and 6) and achieved a final score of 6.
Given,

valid = [2, 4, 6]
final = 6
ways = [0, 0, 0, 0, 0, 0]

The idea is to iterate over each valid score and try to find how it impacts on the number of ways to achieve a higher score.
First Iteration for Valid Score (2):
Set the number of ways to reach 2, denoted by ways[2]

ways[2] = ways[2] + 1
ways[2] = 1

We know that two is a valid score means we can find ways to reach a final score of 3, using ways to reach a final score of 1

ways[3] = ways[3] + ways[1]
ways[3] = 0

similarly

ways[4] = ways[4] + ways[2]
ways[4] = 1
ways[5] = ways[5] + ways[3]
ways[5] = 0
ways[6] = ways[6] + ways[4]
ways[6] = 1
ways = [0, 1, 0, 1, 0, 1]

Second Iteration for Valid Score (4):
Set the number of ways to reach 4, denoted by ways[4]

ways[4] = ways[4] + 1
ways[4] = 2

We know that four is a valid score means we can find ways to reach a final score of 5, using ways to reach a final score of 1

ways[5] = ways[5] + ways[1]
ways[5] = 0

similarly

ways[6] = ways[6] + ways[2]
ways[6] = 2
ways = [0, 1, 0, 2, 0, 2]

Third Iteration for Valid Score (6):
Set the number of ways to reach 6, denoted by ways[6]

ways[6] = ways[6] + 1
ways[6] = 3
ways = [0, 1, 0, 2, 0, 3]

We can get the number of ways to reach six, as three (using ways[6]).

Code

//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
    public class Program
    {
        public static void Main(string[] args)
        {
            // Input
            // Valid Points - 2, 4, 6
            // Final Point - 6
            
            // Output - Ways to achieve final point using valid points without specific combination
            // 6 can be achieved using 3 ways - [2,2,2], [2,4] and [6]
            // 8 can be made using 4 ways - [2,2,2,2], [2,2,4], [2,6] and [8]
            Console.WriteLine(NumberOfWays(new int[]{2, 4, 6}, 6));
            Console.WriteLine(NumberOfWays(new int[]{2, 4, 6}, 8));
        }        
        
        public static int NumberOfWays(int[] valid, int final) {
            if(valid == null || valid.Length == 0 || final <= 0) {
                return 0;
            }   
            var ways = new int[final + 1];
            // Base condition to denote a number can be formed by it's own
            // e.g. 2 can be formed if 2 is a valid score and so on
            ways[0] = 1;
            
            // The idea is to perform additive operation for all the valid scores
            // until we reach the final
            foreach(var input in valid) {
                for(var i = input; i <= final; i++) {
                    ways[i] += ways[i-input];
                }
            }
            
            return ways[final];
        }
    }
}