Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
PerlMonks  

Re: Challenge: Number of unique ways to reach target sum

by Roy Johnson (Monsignor)
on Feb 14, 2006 at 15:09 UTC ( [id://530134]=note: print w/replies, xml ) Need Help??


in reply to Challenge: Number of unique ways to reach target sum

Having discussed the general form of this program with you and written code for it, I have something of an advantage over others. The code to iterate through all solutions is below, and is running on my PC as I type this, at something between 10000 and 20000 iterations/second.

I will be pondering whether there isn't a way to determine how many ways to get the result without actually generating them. I know that you can save one order of magnitude by knowing that your last dial will always have only one acceptable value, so you can just count the number of elements on the next-to-last dial, then iterate to the next incarnation of it.

use strict; use warnings; use Algorithm::Loops 'NestedLoops'; use List::Util qw'sum min'; # find all subsets of 1..$N of size $S whose sum is $T: sub selections { my ($N, $S, $T, $callback) = @_; NestedLoops( [ (sub { no warnings 'uninitialized'; my $new_t = $T - sum(@_); # Target sum for remaining dials my $new_s = $S - @_; # Number of remaining dials # Each dial is > than the one to the left of it my $min = $_[-1] + 1; # The value must be large enough that the remaining dials # can reach the target. The min formula is my @min_vals = map $N-$_, reverse 1..$new_s-1; my $s = sum @min_vals; my $x = $new_t - $s; if ($x > $min) { $min = $x } my $max = $N - $new_s; # The value must be small enough that the remaining dials # can all increase and still not overshoot the target. The # max formula is # x + (x + 1) + ... + (x + S-1) = new_t # ==> (x * S) + ((S-1)*S/2) # Solving for x: $x =int( ($new_t - (($new_s - 1) * $new_s/2))/$new_s ); if ($x < $max) { $max = $x } [$min .. $max] }) x $S ], ); } my $i = selections(100, 10, 667); my $solution_count = 0; while ($i->()) { ++$solution_count; print "$solution_count iterations\n" if $solution_count % 10_000 == +0; }

Caution: Contents may have been coded under pressure.

Replies are listed 'Best First'.
Re^2: Challenge: Number of unique ways to reach target sum
by Limbic~Region (Chancellor) on Feb 14, 2006 at 15:14 UTC
    Roy Johnson,
    I had discussed this problem along with my own meditation Arbitrarily Nested Loops with several monks, so don't feel bad about having an advantage. I do not know for a fact, my solution is correct since some of the shortcuts I took may be invalid. Since the answer itself doesn't have any tangible real-world value, I am interested in any and all responses. Some of the more astute mathematically inclined monks may come up with an answer without any code at all - that's fine too.

    Cheers - L~R

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://530134]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others surveying the Monastery: (4)
As of 2024-03-29 01:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found