An impossible problem to solve with our current computers?-CodePudding

I've created an account to ask for help for this equation I had assigned to myself when I was new in programming. So the problem goes like this say I have n let's say it has a value of 27 now I have another variable lets say x is equals to 6 and a final variable z equals 9. We are going to find n by decrementing numbers from z with the amount of numbers equal to x.

For example, the number 27 should have an answer of 8 6 5 4 3 1 = 27 but the problem is you do not where to start, or how much the decrement value should be and also numbers cannot be duplicated. So the only solution I have now is to bruteforce it which takes soooo long. This is my current solution for it :

(idk if this works, I haven't got a "found" print)

for x in range(9**6):
    for a in range(9):
        for b in range(9):
            for c in range(9):
                for d in range(9):
                    for e in range(9):
                        for f in range(9):
                            _arr = [a, b, c, d, e, f]
                            arr = []
                            
                            for g in _arr:
                                if g not in _arr:
                                    arr.append(g)
                            
                            result = ((a   1)    (b   1)   (c   1)   (d   1)   (e   1)   (f   1))
                            if len(arr) == 6 and result == 27 :
                                print(f"→ found! | answer : {result}")

I vaguely remember I had put this difficulty at medium turns out its very hard it just looks simple, I remember I wanted to solve n = 27, and n = 780 with z = 102, x still 6 (I came up with this very high number because I wanted to know if this was possible to solve with bruteforcing turns out 27 is already very high). So I want to ask what algorithms or theories should I use to solve this, or if its even possible or am I just a bad programmer (lol). So far I've looked into GMP, Numpy libraries etc. but do not know in what way I would implement those.

I hope you can help me in someway so I may solve this so I may finally be at peace :)

Thank you!!

CodePudding user response：

There is no need to brute force this. You can start out by the minimum sum you can get with the number of terms (i.e., 1 2 3 4..). Then consider that the greatest value can be increased up to the maximum value. This increment can be applied to the second greatest as well, ...etc. We can determine by division how many of these increments we need. The remainder of this division will determine how much the greatest value that didn't change should be incremented.

Here is an implementation:

def solve(target, num_terms, max_value):
    total = num_terms * (num_terms   1) // 2  # Triangular number
    if total > target:
        raise ValueError("target is too small")
    need = target - total
    diff = max_value - num_terms
    if need > num_terms * diff:
        raise ValueError("target is too great")
    shift = need // diff
    if num_terms == shift:
        return list(range(max_value - shift   1, max_value   1))
    return (
        list(range(1, num_terms - shift))
          [num_terms - shift   (need % diff)]
          list(range(max_value - shift   1, max_value   1))
    )

Applied on the example in the question:

print(solve(27, 6, 9))  # [1, 2, 3, 4, 8, 9]

CodePudding user response：

Approach

A backtracking approach worked quickly for the problem of number 27
Backtracking was too slow for the larger number i.e. abandoned after 30 minutes on the more difficult problem of 780
Was able to quickly solved both problems using Constraint Programming
Implemented constraint programming using Google OrTools Constraint Satisfaction
Stopped at first solution found with each run

Constraints

Have a given number of numbers
Numbers values range from 1 to a max value
Numbers are distinct
Numbers add to the desired sum

Performance

OR-Tools was able to find solutions to the posted problems in milliseconds on a 10 -year-old Windows desktop

Code

from ortools.sat.python import cp_model

def find_factors(required_sum, max_value, n_numbers):
    '''
        Find factors that:
        : required_sum- sum to n
        : max_value numbers(numbers from 1 to max_value inclusive)
        - n_numbers - number of numbers to find
        
        Approach
        
        Use google ortools constraint satisfaction
        Reference: https://developers.google.com/optimization/cp
    '''

    # Create model
    model = cp_model.CpModel()

    # Create constraint variables
    number_choices = []
    for i in range(n_numbers):
        # numbers from 1 to max_value
        number_choices.append(model.NewIntVar(1, max_value, f"number {i}"))

    # Add constraints to variables
    #   Sum of numbers equals required sum
    model.Add(sum(number_choices)==required_sum)

    #   All numbers are different
    model.AddAllDifferent(number_choices)

    #   Numbers are in Descending order
    for i in range(n_numbers-1):
        model.Add(number_choices[i] > number_choices[i 1])

    # Solve for constsraints and report results
    solver = cp_model.CpSolver()
    status = solver.Solve(model)

    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        return ([solver.Value(v) for v in number_choices])
    else:
        return None  # no solution found

Testing

print(find_factors(27, 9, 6))
# Output: [9, 8, 4, 3, 2, 1]

print(find_factors(780, 102, 14))
# Output: [102, 59, 58, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46]

Timing

%timeit find_factors(27, 9, 6)
# Result: 3.13 ms ± 489 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit find_factors(780, 102, 14)
# Result: 7.95 ms ± 396 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)