I'm just trying to practice programming but that one is pissing me off. It's like I end up with infinitely many nested for loops and I can't quite figure out the recursion
For the final task, you must find all subsets of an array where the largest number is the sum of the remaining numbers. For example, for an input of:
for j in range(0, 1 << len(numbers)): sum = 0 max = 0 for k in range(0, len(numbers)): if j & (1 << k): sum+= max max = numbers[k] if max == sum and sum > 0: answer = "" for k in range(0, len(numbers)): if j & (1 << k) and numbers[k] != max: answer+= str(numbers[k]) + " + " #Trim off last three characters " + " answer = answer[:len(answer)-3] answer += " = " + str(sum) print answer
I banged something out pretty quickly, and then discovered that I had come up with the same solution you had. So then I started thinking about optimization. That turned out to be a lot more interesting than just finding some appropriate loop structures to deal with the combinatorics.
Eventually I wound up scrapping the iterative approach and went with a recursive design. I think I've optimized it about as much as can be, short of converting it to an equivalent iterative design. That would be a lot of headache for not much benefit, though. As is, the algo itself is about 6500-7000x faster than the brute-force iterative method.
This is probably ugly Python code, but I only started teaching it to myself a couple weeks ago, so...eh.
Spoiler:
Code:
#!/usr/bin/python
import sys
def printSol(solution): outStr = "" for i in range(len(solution)): if i < (len(solution) - 1): outStr += "%d + " % solution[i] else: print "%s = %d" % (outStr[:-3], solution[i])
for num in superSet: """ Note that even if we find a solution here, we need to continue recursing because, for instance: 9 + 19 = 28 9 + 19 + 28 = 56 """ if num == subSetSum: solution = subSet[:] solution.append(num) printSol(solution) solCount += 1
""" This bailout condition is the chief optimization. It keeps us from delving into subets that are too big to have solutions. """ newSubSetSum = subSetSum + num if newSubSetSum <= 99: newSubSet = subSet[:] newSubSet.append(num)
""" More culling that takes advantage of the fact that our recursion occurs in numerical order. Doing this avoids traversing the same subset multiple times, in different orders. """ newSuperSet = [] for x in superSet: if x > num: newSuperSet.append(x)
Now I'm wondering if there's an even faster solution that involves working backwards from the possible final sums. I bet there is.
Author:
Lex Luthor [ Wed Feb 02, 2011 9:27 pm ]
Post subject:
Wow, your solution is really fast! I'm trying to think of a fast way without doing recursion.
Author:
Stathol [ Wed Feb 02, 2011 11:40 pm ]
Post subject:
Haha, I just discovered that my algo is pretty sensitive to skewed input sets. Changing the final number in the input set from 99 to 1000 makes the total script execution time jump from ~0.025s to ~4.9s, it's not so much that it doesn't cope with large input values, but rather it really doesn't like it when there's a big gap in the numbers. Further changing the 97 to 999 brings the execution time down to ~2.9s, for instance.
The brute-force approach doesn't care about the distribution of values, it's only affected by the number of inputs. Each one roughly doubles the execution time, as you might expect. In that respect, my algo scales better. But it just goes to show that benchmarking is never quite as clear as it seems.
I may convert my algo to an iterative function with a state stack just to see how much it improves. The really nasty challenge is whether there's a constant-space iterative solution. I'm guessing not. This seems to be a close relative of the subset sum problem and the infamous knapsack problem. I'm curious where your friend encountered this, and if it's a well-known computing problem that I'm just not familiar with.
Author:
Noggel [ Thu Feb 03, 2011 2:45 am ]
Post subject:
Re: Cool programming problem
Man.
I just got three problems in this same vein from a CS professor for this Olympiad thing he is running. I like them in theory but I think I quickly wound up out of my league here in this thread. :p I keep finding ways to convert the problem at hand into something brute forceable through sheer iteration. Effective, and even pretty practical given the speed of computers, but elegant it is not.
It's way too late for me to be awake now but I just finished the third problem and it is... laughable. Oh I got a working solution, eventually, but it's kinda Rube Goldbergian. My other two aren't too bad as far as interative designs go, but this third one... yeah.
I think I'll paste it here tomorrow for everyone to mock. :p The code is all in basic C++, but the spirit of all these problems is more or less math anyway, so the language is pretty irrelevant. Because of its Goldbergian nature, I'll probably have to comment it to even make it readable, though, so it should be plenty readable no matter your knowledge of C++.
The only good to come of it was it got me thinking about things in rather unusual ways. When you end up having to develop a loop to increment in some kind of base 3, without including 0 (111 -> 112 -> 113 -> 121), you know your code went way off track somewhere a step or three back. :p I'd actually be a little proud of my solution to accomplish that if it wasn't my only way out of such a ridiculous situation to begin with!
I may have to fiddle around with the code to get exactly the desired output (think it only wants one result, for example, and some sort of 'no solutions' output needs to be added too) but the gist of the program seems complete.
Spoiler:
Code:
#include <iostream> #include <cmath> using namespace std;
int findDigit(int,int); // returns the digit in a given number at a specified position int adjustPosition(int,int,int); // adjusts the digit at a specified position in a given number by the modifier int convert(int,int,int,int); // converts digits 1, 2, and 3 used in main function to the digits the user specified int sumConstruct(int); // breaks a 9 digit number up into 3 consecutive 3-digit numbers, then returns their sum
int test = 111111111; // 000000000 might be expected, but using 1 as the lowest number eliminates problems with leading zeroes being truncated char flag;
for (int i = 0; i < 19683; i++) // 3^9 permutations to check { /* algorithm:
1. test to see if the current number, converted and summed, matches the user-input 4 digit number
2. check rightmost digit for a 3 3. if a 3 is found, check next digit to the left for a 3. repeat this step if so 4. once a digit other than a 3 is found, that digit gets incremented by 1 and all digits to the right of it get set back to 1 5. if no 3 is found in step 2, increment the entire number by 1
6. repeat from beginning
result: 111111111 -> 111111112 -> 111111113 -> 111111121 -> 111111122 -> and so on. covers all possible permutations of 1's, 2's, and 3's. */
while (findDigit(test,digit) == 3) { flag = 'y'; digit++; } if (flag == 'y') {
test = adjustPosition(test,digit,1);
for (int i = 1; i < digit; i++) test = adjustPosition(test,digit-i,-2);
flag = 'n'; } else test++; }
return 0; }
int findDigit(int fullnum, int position) // returns the digit in a given number at a specified position // position counts from rightmost digit to the left, starting with position 1 { double divisor = .1; for (int i = 0; i < position; i++) divisor *= 10;
return fullnum/int(divisor)%10; }
int adjustPosition(int given, int pos, int modifier) // adjusts the digit at a specified position in a given number by the modifier // position counts from rightmost digit to the left, starting with position 1 // ex: adjustPosition(2345,2,2) --> 2365 // adjustPosition(2345,3,-1) --> 2245 { int incrementer = pow(10.0,pos) / 10; incrementer = incrementer * modifier; given = given + incrementer;
return given; }
int convert(int preconvert, int dec1, int dec2, int dec3) // converts digits 1, 2, and 3 used in main function to the digits the user specified { int tracker = 0, placeholder = 100000000;
for (int i = 0; i < 9; i++) { int digit = (preconvert/placeholder)%10; if (digit == 1) tracker = tracker + dec1*(placeholder); else if (digit == 2) tracker = tracker + dec2*(placeholder); else tracker = tracker + dec3*(placeholder); placeholder /= 10; } return tracker; }
int sumConstruct(int given) // breaks a 9 digit number up into 3 consecutive 3-digit numbers, then returns their sum { int first, second, third; first = given / 1000000 % 1000; second = given / 1000 % 1000; third = given % 1000;
if ((first < 100) || (second < 100) || (third < 100)) return 0; // throw out results that aren't a trio of 3-digit numbers
return first + second + third; }
I cringe a little at the flag char use. It was a temporary solution when I was in the middle of some other problem that worked without problems, so it stuck around. I'll probably add input validation too before turning in any code, but I'll check with the professor running this if that's necessary or not.
I get the impression I reinvented the wheel a few times here, but alas. Working with ints are a pain in C++. Data type conversions seem like they should be so easy, but it is not so. I did want to stick to a pretty math-centric algorithm anyway as opposed to picking it apart as a string.
Author:
Stathol [ Fri Feb 04, 2011 12:19 am ]
Post subject:
I threw together a program for this. It's purely brute force, but I don't think that's much of an issue, because the keyspace is so small. If a, b, and c are all different, we can construct 27 (3^3) unique 3-digit numbers from them which are candidates for p, q, and r. Then from these we can choose any 3, with repetition, but order does not matter. That is, p + q + r = r + q + p, etc. So the maximum number of "unique" p + q + r equations that can be built is:
C(27 + 3 - 1, 3) = C(29,3) = 3654
If exactly two out a, b, c are equal to one another, then there are 2^3 = 8 candidates and therefore the unique p, q, r equations are reduced to:
C(8 + 3 - 1, 3) = C(10,3) = 120
And obviously if a = b = c, there is only one possible unique equation p + q + r that can be built.
My program operates according to the process outline above. First it builds the list of candidates for p, q, and r. Afterwards, it iterates over the unique combinations of p, q, and r, checking for sums.
I'm sure this could be made more efficient by various means. Offhand, you could certainly exploit parity rules. Divide the candidates into evens and odds. If N is odd, you can test only those combinations containing one odd and two evens, or three odds, etc. However, given that there are most <4k keys to test, the value of such optimizations seems dubious.
Always cool to see different ways to tackle the same problem!
Especially when it goes far beyond my CMPSC 101 learnings. Ah well. I suppose I only regret not figuring out some way to limit the algorithm from searching for A + C + B when it has already done A + B + C, and so on. Perhaps if I'm extra ambitious I'll try and add that in.
Author:
Taskiss [ Wed Feb 09, 2011 10:20 pm ]
Post subject:
Re: Cool programming problem
Behold the power of the camel...I just love perl!
if it could do binary natively it would have been much faster...and I calculated the series where, when the largest number was the sum of the series, I displayed it. I'm not sure if that's the goal, but it made for an interesting problem so I ran with it.
while (scalar(@array) > 2) { $result = pop (@array) ; $mask = "1" x scalar(@array) ; $loop = &mask2d($mask) ; $maskLen = length($mask) ; &doit ; } exit ; #------------------------------------------------------------------------------- sub doit { for (my $i = 0; $i <= $loop; $i++) { my @bits = split(//, &d2mask($i)) ; my @list = () ; my $sum = 0 ; LOOP: { for (my $i = 0; $i < $maskLen ; $i++) { if ($bits[$i] eq 1) { push (@list, $array[$i]) ; $sum += $array[$i] ; if ($sum > $result) { last LOOP } } } } if ($sum == $result) { print "The series \(@list\) = $result\n" } } } #------------------------------------------------------------------------------- sub d2mask { my $str = unpack("B32", pack("N", shift)) ; $str =~ s/^0+(?=\d)// ; $str = sprintf("%${maskLen}s", $str) ; $str =~ tr/ /0/ ; return ($str) ; } #------------------------------------------------------------------------------- sub mask2d { return unpack("N", pack("B32", substr("0" x 32 . shift, -32))) ; } #-------------------------------------------------------------------------------
results:
Spoiler:
The series (15 37 47) = 99 The series (15 28 56) = 99 The series (15 19 28 37) = 99 The series (14 15 70) = 99 The series (9 15 28 47) = 99 The series (9 15 19 56) = 99 The series (9 14 15 61) = 99 The series (4 95) = 99 The series (4 15 19 61) = 99 The series (4 14 81) = 99 The series (4 14 15 19 47) = 99 The series (3 37 59) = 99 The series (3 15 81) = 99 The series (3 14 28 54) = 99 The series (3 9 37 50) = 99 The series (3 9 28 59) = 99 The series (3 9 14 73) = 99 The series (3 9 14 19 54) = 99 The series (3 4 92) = 99 The series (3 4 19 73) = 99 The series (3 4 14 78) = 99 The series (3 4 14 28 50) = 99 The series (3 4 14 19 59) = 99 The series (3 4 9 14 19 50) = 99 The series (3 4 9 14 15 54) = 99 The series (47 50) = 97 The series (19 78) = 97 The series (19 28 50) = 97 The series (15 28 54) = 97 The series (9 15 73) = 97 The series (9 15 19 54) = 97 The series (9 14 15 59) = 97 The series (4 37 56) = 97 The series (4 15 78) = 97 The series (4 15 28 50) = 97 The series (4 15 19 59) = 97 The series (4 9 37 47) = 97 The series (4 9 28 56) = 97 The series (4 9 19 28 37) = 97 The series (4 9 15 19 50) = 97 The series (4 9 14 70) = 97 The series (3 19 28 47) = 97 The series (3 14 19 61) = 97 The series (3 14 15 28 37) = 97 The series (3 9 15 70) = 97 The series (3 9 14 15 56) = 97 The series (3 9 14 15 19 37) = 97 The series (3 4 15 28 47) = 97 The series (3 4 15 19 56) = 97 The series (3 4 14 15 61) = 97 The series (3 4 9 81) = 97 The series (3 4 9 15 19 47) = 97 The series (15 19 61) = 95 The series (14 81) = 95 The series (14 15 19 47) = 95 The series (4 37 54) = 95 The series (4 9 28 54) = 95 The series (3 92) = 95 The series (3 19 73) = 95 The series (3 14 78) = 95 The series (3 14 28 50) = 95 The series (3 14 19 59) = 95 The series (3 9 14 19 50) = 95 The series (3 9 14 15 54) = 95 The series (3 4 15 73) = 95 The series (3 4 15 19 54) = 95 The series (3 4 14 15 59) = 95 The series (3 4 9 14 28 37) = 95 The series (3 4 9 14 15 50) = 95 The series (19 73) = 92 The series (14 78) = 92 The series (14 28 50) = 92 The series (14 19 59) = 92 The series (9 14 19 50) = 92 The series (9 14 15 54) = 92 The series (4 15 73) = 92 The series (4 15 19 54) = 92 The series (4 14 15 59) = 92 The series (4 9 14 28 37) = 92 The series (4 9 14 15 50) = 92 The series (3 28 61) = 92 The series (3 19 70) = 92 The series (3 14 28 47) = 92 The series (3 14 19 56) = 92 The series (3 9 19 61) = 92 The series (3 9 15 28 37) = 92 The series (3 9 14 19 47) = 92 The series (3 4 15 70) = 92 The series (3 4 14 15 56) = 92 The series (3 4 14 15 19 37) = 92 The series (3 4 9 15 61) = 92 The series (3 4 9 14 15 47) = 92 The series (3 4 9 14 15 19 28) = 92 The series (15 19 47) = 81 The series (4 9 14 54) = 81 The series (3 78) = 81 The series (3 28 50) = 81 The series (3 19 59) = 81 The series (3 9 19 50) = 81 The series (3 9 15 54) = 81 The series (3 4 15 59) = 81 The series (3 4 9 28 37) = 81 The series (3 4 9 15 50) = 81 The series (28 50) = 78 The series (19 59) = 78 The series (9 19 50) = 78 The series (9 15 54) = 78 The series (4 15 59) = 78 The series (4 9 28 37) = 78 The series (4 9 15 50) = 78 The series (3 28 47) = 78 The series (3 19 56) = 78 The series (3 14 61) = 78 The series (3 9 19 47) = 78 The series (3 9 14 15 37) = 78 The series (3 4 15 56) = 78 The series (3 4 15 19 37) = 78 The series (3 4 9 15 47) = 78 The series (3 4 9 15 19 28) = 78 The series (19 54) = 73 The series (14 59) = 73 The series (9 14 50) = 73 The series (4 19 50) = 73 The series (4 15 54) = 73 The series (3 70) = 73 The series (3 14 56) = 73 The series (3 14 19 37) = 73 The series (3 9 61) = 73 The series (3 9 14 47) = 73 The series (3 9 14 19 28) = 73 The series (3 4 19 47) = 73 The series (3 4 14 15 37) = 73 The series (3 4 9 14 15 28) = 73 The series (14 56) = 70 The series (14 19 37) = 70 The series (9 61) = 70 The series (9 14 47) = 70 The series (9 14 19 28) = 70 The series (4 19 47) = 70 The series (4 14 15 37) = 70 The series (4 9 14 15 28) = 70 The series (3 4 9 54) = 70 The series (14 47) = 61 The series (14 19 28) = 61 The series (9 15 37) = 61 The series (4 14 15 28) = 61 The series (4 9 14 15 19) = 61 The series (3 4 54) = 61 The series (9 50) = 59 The series (3 56) = 59 The series (3 19 37) = 59 The series (3 9 47) = 59 The series (3 9 19 28) = 59 The series (3 4 15 37) = 59 The series (3 4 9 15 28) = 59 The series (19 37) = 56 The series (9 47) = 56 The series (9 19 28) = 56 The series (4 15 37) = 56 The series (4 9 15 28) = 56 The series (4 50) = 54 The series (3 14 37) = 54 The series (3 9 14 28) = 54 The series (3 4 47) = 54 The series (3 4 19 28) = 54 The series (4 9 37) = 50 The series (3 47) = 50 The series (3 19 28) = 50 The series (3 4 15 28) = 50 The series (3 4 9 15 19) = 50 The series (19 28) = 47 The series (4 15 28) = 47 The series (4 9 15 19) = 47 The series (9 28) = 37 The series (4 14 19) = 37 The series (3 15 19) = 37 The series (9 19) = 28 The series (4 9 15) = 28 The series (4 15) = 19
real 2m14.342s user 2m11.851s sys 0m1.013s
OK, ver 1.2... went from 2m14 to 0m50
Code:
#!/usr/bin/perl -w my @array = qw(3 4 9 14 15 19 28 37 47 50 54 56 59 61 70 73 78 81 92 95 97 99) ; #my @array = qw(1 2 3 4 6) ; my $result = pop(@array) ; my $target = pop(@array) ; my @solution ; print "Calculating...\n" ; while (scalar(@array) > 0) { my $mask = "1" x scalar(@array) ; my $maskLength = length($mask) ; my $loop = unpack("N", pack("B32", substr("0" x 32 . $mask, -32))) ; my $i = 0 ; while ($i <= $loop) { my @bits = split(//, substr(unpack("B*", pack("N", $i)), -$maskLength, $maskLength)) ; my @list = () ; my $sum = 0 ; my $x = 0 ; foreach my $bit (@bits) { if ($bit) { $sum += $array[$x] ; last if ($sum > $result) ; push (@list, $array[$x]) ; } $x++ ; } push (@solution, "\(@list\) = $result\n") if ($sum == $result ) ; push (@solution, "\(@list $target\) = $result\n") if ($sum + $target == $result ) ; $i++ ; } $result = $target ; $target = pop(@array) ; } foreach (reverse @solution) { print }
I did want to stick to a pretty math-centric algorithm anyway as opposed to picking it apart as a string.