[SOLVED] Finding the most balanced combination to obtain a result

Issue

I'm working on a bash script and I've come across a problem that I can't solve.

EDIT: Thanks to @markp-fuso and @pjh for their help !

I have 2 arrays of integers, dividers_1 and dividers_2 and a third variable product containing an integer.

#!/bin/bash
dividers_1=("1" "2" "4" "6" "8" "9" "12" "16" "18" "24" "32" "36" "48" "64")
dividers_2=("1" "2" "3" "4" "7" "9" "12" "16" "18" "24" "27" "32" "36" "48" "54")
product=16

The aim is to find the most balanced combination of two numbers, one from the first array, the other from the second array (in any order), whose multiplication equals the variable product.

By the most balanced combination I mean that the 2 terms of the multiplication are distributed as evenly as possible. For example, if product=16, the most balanced combination would be 4x4, compared with 1x16 which is not distributed equally.

Obviously, a perfectly balanced combination is not necessarily possible, so if it is not possible because of the values available in the two tables, then we would look for a less evenly distributed combination. For example, if we consider the previous tables, and product=64, although the 8x8 combination is the most balanced, it is not possible because 8 is not present among the values in one of the tables. So the most balanced combination becomes 4x16 (or 16x4).

Finally, if no combination is possible, an error message is returned.

I have the feeling that the solution lies in a recursive function, but I'm not very good with that. I'm open to suggestions. The ideal is to have as few dependencies as possible because of the medium in which the script will eventually be run. I'm currently using bash 5.2

EDIT1: As @markp-fuso asked : This is what I mean by evenly distributed. In a multiplication where the two terms are evenly distributed, the terms are ideally identical, or at best the difference should be the smallest. For example, if the product you are looking for is 900, the ideal distribution is 30x30 (a difference of 0) . The next most balanced distribution would be 25x36 or 36x25 (difference of 11). And so on, until the most unbalanced distributions, 1x900 or 900x1 (difference of 899)

EDIT2: I've done so many rewrites and made so many different attempts that I've got my nose in too much. It's not optimised at all, sorry. I need outside help to help me think again.

#!/bin/bash
## find_combo.sh

# Both arrays are hard written for convenience. Usually it's generated by another function that find all the dividers from a given number.
dividers_1=(1 2 4 6 8 9 12 16 18 24 32 36 48 64)
dividers_2=(1 2 3 4 7 9 12 16 18 24 27 32 36 48 54)
product=$1

# check if combination is valid
is_valid_combination() {
    local result=$1
    for elem in "${dividers_1[@]}" "${dividers_2[@]}"; do
        if [ "$elem" == "$result" ]; then
            return 0  # valid
        fi
    done
    return 1  #not valid
}

# Find the most balanced combination
balanced_combination=""
min_difference=999999999  #initial value

for num1 in "${dividers_1[@]}"; do
    for num2 in "${dividers_2[@]}"; do
        result=$((num1 * num2))
        difference=$((num1 > num2 ? num1 - num2 : num2 - num1))

        if [ "$result" -eq "$product" ] && [ "$difference" -lt "$min_difference" ] && is_valid_combination "$num1" && is_valid_combination "$num2"; then
            balanced_combination="$num1 x $num2"
            min_difference="$difference"
        fi
    done
done

# check if a balanced combination is found
if [ -n "$balanced_combination" ]; then
    echo "Found it: $balanced_combination"
else
    echo "Sorry, no combination found for $product"
fi

./find_combo.sh 64 should return Found it: 4 x 16

Solution

Try this Shellcheck-clean pure Bash code:

#! /bin/bash -p

dividers_1=(1 2 4 6 8 9 12 16 18 24 32 36 48 64)
dividers_2=(1 2 3 4 7 9 12 16 18 24 27 32 36 48 54)

product=$1

# Set up the `divs_2_set` array, which implements the set of numbers in
# `dividers_2`.  The indices are the elements of `dividers_2` and the values
# are the `_` character (an arbitrary non-empty string).
divs_2_set=()
for i in "${dividers_2[@]}"; do
    divs_2_set[i]=_
done

# Below `f1` and `f2` are the current factors of the product and `bf1` and
# `bf2` are the most "balanced" factors found so far.
mindiff='' bf1='' bf2=''
for f1 in "${dividers_1[@]}"; do
    (( product % f1 > 0 )) && continue
    f2=$(( product/f1 ))
    [[ -n ${divs_2_set[f2]-} ]] || continue
    diff=$((f1-f2))
    (( diff < 0 )) && diff=$(( -diff ))
    if [[ -z $mindiff || diff -lt mindiff ]]; then
        mindiff=$diff
        bf1=$f1
        bf2=$f2
    fi
done

if [[ -n $bf1 ]]; then
    printf 'Found it: %d = %d x %d\n' "$product" "$bf1" "$bf2"
else
    printf 'Sorry, no combination found for %d\n' "$product"
fi

Answered By - pjh

Answer Checked By - Candace Johnson (WPSolving Volunteer)