31 days of problems

Why?

This is the beginning of a new year (and decade) 🎉 so it's time for a new commitment, last year I challenged myself on 365 days of coding problems with DailyCodingProblems and...I gave up after only 2 or 3 weeks...
This year I will try again! For 31 days and why not more, but let's do 31 days for now.

Why try again?

To motivate myself I choose to publish my solution of the daily problem here because you will probably have other solutions and that would be great to discuss algorithmic here.

Why do that?

Because it's fun! It's a good technique to improve your logic and secondly next year I will have to pass a technical interview for the last internship of my studies and I want to be prepared!

How this series will work

• First of all, this is my first series of articles and my first real article so don't hesitate to comments, I want to improve my writing skills (and my English also).

• Every two days (or one time a week) I will post a problem I received and my solution, you can find here the repo don't hesitate to check the repo 😃.

Day 1

• Difficulty: Medium
• Programming language used: Kotlin

Problem

Write a function, throw_dice(N, faces, total) that determines how many ways it is possible to
throw N dices with some number of faces each to get a specific total.

For example:
throw_dice(3, 6, 7) should return 15.

My solution

I used a concept called dynamic programming (DP) to solve this one.
Finding how many ways it is possible to throw N dices to get a specific amount (X) is equivalent to find (and sum) how many ways it is possible to throw N-1 dices to get an X-1 amount, N-1 to get X-2, N-1 to get X-3, etc..until X and N equals 1.

/**
 * Determine how many ways it is possible to throw N dices with the number of faces each to get the total
 *
 * @param N, number of dices
 * @param faces, number of faces of each dice
 * @param total, the sum of the dices we would like to get
 * @return Int, number of ways
 */
fun throw_dice(N: Int, faces: Int, total: Int): Int {
    val subProblems = Array(N+1) { IntArray(total+1) { 0 } }

    var i = 1
    while (i < total && i < faces) {
        subProblems[1][i] = 1
        i++
    }

    for (w in 2..N) {
        for (j in 1..total) {
            for (k in 1..faces) {
                if(k >= j)
                    break
                subProblems[w][j] += subProblems[w - 1][j - k]
            }
        }
    }

    return subProblems[N][total]
}