gistfile1.6pl

#!/usr/bin/env perl6

# PROBLEM:
# 
# [14:15] <FROGGS_> hmmm, if I had a number like 283, and I'd had certain
#                   values like 23,33,44,62 that this number can consist of...
#                   how do I get the combination of the values that is equal to
#                   that number?
# [14:15] <FROGGS_> like 283 == 33×5+52+66
# [14:15] <FROGGS_> is there an easy way to get there?
# [14:18] <FROGGS_> [...] the values can be N times in there
# [14:19] <FROGGS_> so it is about the sum of a multiple of the values

# SOLUTION:
# 
# I use a simple brute-force approach. @factors represents the multiplicities of
# the input terms for a given attempt; After each attempt, @factors is
# "incremented by one" like the digits of a number would be incremented, except
# not with a fixed base but rather overflowing "digits" whenever the search
# condition has been exceeded.
# 
# I'm not a maths viz and also I'm on pain meds right now, no no guarantees of
# correctness and completeness, but it seems to work for the inputs I've tried.


my $sum = 283;
my @terms = 23, 33, 44, 62;


my @factors = 0 xx +@terms;  # First set of factors is all zeroes

loop (my $i = 0; $i < +@factors;) {
    
    @factors[$i]++;
    
#     say "[$i] ", ~@factors => [+] @factors Z* @terms;  # for debugging
    
    given [+] @factors Z* @terms {
        when * > $sum { @factors[$i] = 0; $i++ }
        when * < $sum { $i = 0 }
        default {
            say "Found solution:\n  $sum = ",
                (@terms Z=> @factors).Bag.kv.map(* ~ "×" ~ *).join(" + ");
            exit;
        }
    }
}

say "No solution found.";