Count the number of ways to make a given sum using one number from each array

Question

I have three arrays, each of which contains only numbers. Given a target number, I need to return the number of ways I can make that sum, using exactly one number from each of the arrays.

For example: If I have 2 arrays [[1,2,3], [1,2,3]] and the target sum is 4, I must return the number of combinations that will sum to 4. In this case, they are:

1+3 = 4
2+2 = 4
3+1 = 4

So the function will return 3.

I wrote the function below, and it works well, but I am looking for a way to make more efficient, as well as make it scale to more input arrays - I have less than 6 arrays, but I want it to work if I have a hundred arrays. Is there any array function that can help me here?

This is the code:

<?php
function get_sum ($dice, $sum) {
    $sumcount = array();
    $num_of_dice = count($dice);    
    foreach($dice[0] as $die1){
        foreach($dice[1] as $die2){
            if($num_of_dice == 5){
                foreach($dice[2] as $die3){
                    foreach($dice[3] as $die4){
                        foreach($dice[4] as $die5){
                            if($die1 + $die2 + $die3+ $die4 + $die5 == $sum){
                                $good_res = array();
                                array_push( $good_res, $die1, $die2, $die3, $die4, $die5);
                                array_push($sumcount, $good_res);
                            }
                        }
                    }
                }
            }
            if($num_of_dice == 4){
                foreach($dice[2] as $die3){
                    foreach($dice[3] as $die4){
                        if($die1 + $die2 + $die3+ $die4 == $sum){
                            $good_res = array();
                            array_push( $good_res, $die1, $die2, $die3, $die4);
                            array_push($sumcount, $good_res);
                        }
                    }
                }
            }elseif ($num_of_dice == 3){
                foreach($dice[2] as $die3){
                    if($die1 + $die2 + $die3 == $sum){
                        $good_res = array();
                        array_push( $good_res, $die1, $die2, $die3);
                        array_push($sumcount, $good_res);
                    }
                }
            }else{
                if($die1 + $die2 == $sum){
                    $good_res = array();
                    array_push( $good_res, $die1, $die2);
                    array_push($sumcount, $good_res);
                }
            }

        }
    };



    echo count($sumcount);
}



get_sum([[1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6]], 9)
?>

Peter Taylor · Accepted Answer · 2018-06-22 10:08:42Z

function get_sum ($dice, $sum) {
    ...
    echo count($sumcount);
}

Both the stated specification and the function name say that it will return the count, not print it.

Well, the function name get_XXX says it will return something. If you gave me the signature get_sum ($dice, $sum) and asked me to implement the body I would ask what $dice was for, since the signature clearly says that the body will be return $sum;. Surely there's a better name?

    $sumcount = array();
    ...
    echo count($sumcount);

That's a rather memory-inefficient way of counting something. Why not increment an integer counter instead of adding an array to an array?

                                $good_res = array();
                                array_push( $good_res, $die1, $die2, $die3, $die4, $die5);

Why not $good_res = array($die1, $die2, $die3, $die4, $die5)?

            if($num_of_dice == 5){
                foreach($dice[2] as $die3){
                    foreach($dice[3] as $die4){
                        foreach($dice[4] as $die5){
                            if($die1 + $die2 + $die3+ $die4 + $die5 == $sum){
                                $good_res = array();
                                array_push( $good_res, $die1, $die2, $die3, $die4, $die5);
                                array_push($sumcount, $good_res);
                            }
                        }
                    }
                }
            }

Again, the aim is to count. If $die1 + $die2 + $die3 + $die4 + $die5 == $sum, why does the loop over $die5 care what $die3 is? You could as well say

foreach ($dice[0] as $die1) {
    $counter += get_sum(array_slice($dice, 1), $sum - $die1);
}

You need to handle a couple of base cases, but that gives you code which should have fairly similar performance to the current code but is much much simpler. Then ask yourself how to memoise. Then ask yourself how to replace the recursion with iteration. The final result will be an iterative method which is about 10 lines long, handles any number of dice, and runs much faster than your current code.

Stack Exchange Network

Count the number of ways to make a given sum using one number from each array

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Count the number of ways to make a given sum using one number from each array

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions