The Glade 4.0

"Turn the lights down, the party just got wilder."
It is currently Sun Nov 24, 2024 1:00 pm

View unanswered posts | View active topics


Board index » The Glade » Tech

All times are UTC - 6 hours [ DST ]



Post new topic Reply to topic  Page 1 of 1
  [ 9 posts ] 
  Print view Previous topic | Next topic 
Author Message
Lex Luthor
 Post subject: Cool programming problem
PostPosted: Tue Feb 01, 2011 9:58 am 
Offline

Joined: Thu Sep 03, 2009 10:03 am
Posts: 4922
My friend sent this to me last night.
Quote:
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:

(1, 2, 3, 4, 6)


the subsets would be

1 + 2 = 3
1 + 3 = 4
2 + 4 = 6
1 + 2 + 3 = 6

Here is the list of numbers you should run your code on.

The password is the number of subsets. In the above case the
answer would be 4.


This is my solution:
Spoiler:
Code:
#!/usr/bin/env python-2.4.3

#numbers = [1, 2, 3, 4, 6]
numbers = [3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99]

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


[altrefon@bxb-lds-026 ~]$ ./sums.py
4 + 15 = 19
4 + 9 + 15 = 28
9 + 19 = 28
4 + 14 + 19 = 37
3 + 15 + 19 = 37
9 + 28 = 37
4 + 9 + 15 + 19 = 47
4 + 15 + 28 = 47
19 + 28 = 47
3 + 4 + 9 + 15 + 19 = 50
3 + 4 + 15 + 28 = 50
3 + 19 + 28 = 50
4 + 9 + 37 = 50
3 + 47 = 50
3 + 9 + 14 + 28 = 54
3 + 4 + 19 + 28 = 54
3 + 14 + 37 = 54
3 + 4 + 47 = 54
4 + 50 = 54
4 + 9 + 15 + 28 = 56
9 + 19 + 28 = 56
4 + 15 + 37 = 56
19 + 37 = 56
9 + 47 = 56
3 + 4 + 9 + 15 + 28 = 59
3 + 9 + 19 + 28 = 59
3 + 4 + 15 + 37 = 59
3 + 19 + 37 = 59
3 + 9 + 47 = 59
9 + 50 = 59
3 + 56 = 59
4 + 9 + 14 + 15 + 19 = 61
4 + 14 + 15 + 28 = 61
14 + 19 + 28 = 61
9 + 15 + 37 = 61
14 + 47 = 61
3 + 4 + 54 = 61
4 + 9 + 14 + 15 + 28 = 70
9 + 14 + 19 + 28 = 70
4 + 14 + 15 + 37 = 70
14 + 19 + 37 = 70
9 + 14 + 47 = 70
4 + 19 + 47 = 70
3 + 4 + 9 + 54 = 70
14 + 56 = 70
9 + 61 = 70
3 + 4 + 9 + 14 + 15 + 28 = 73
3 + 9 + 14 + 19 + 28 = 73
3 + 4 + 14 + 15 + 37 = 73
3 + 14 + 19 + 37 = 73
3 + 9 + 14 + 47 = 73
3 + 4 + 19 + 47 = 73
9 + 14 + 50 = 73
4 + 19 + 50 = 73
4 + 15 + 54 = 73
19 + 54 = 73
3 + 14 + 56 = 73
14 + 59 = 73
3 + 9 + 61 = 73
3 + 70 = 73
3 + 4 + 9 + 15 + 19 + 28 = 78
3 + 9 + 14 + 15 + 37 = 78
3 + 4 + 15 + 19 + 37 = 78
4 + 9 + 28 + 37 = 78
3 + 4 + 9 + 15 + 47 = 78
3 + 9 + 19 + 47 = 78
3 + 28 + 47 = 78
4 + 9 + 15 + 50 = 78
9 + 19 + 50 = 78
28 + 50 = 78
9 + 15 + 54 = 78
3 + 4 + 15 + 56 = 78
3 + 19 + 56 = 78
4 + 15 + 59 = 78
19 + 59 = 78
3 + 14 + 61 = 78
3 + 4 + 9 + 28 + 37 = 81
15 + 19 + 47 = 81
3 + 4 + 9 + 15 + 50 = 81
3 + 9 + 19 + 50 = 81
3 + 28 + 50 = 81
4 + 9 + 14 + 54 = 81
3 + 9 + 15 + 54 = 81
3 + 4 + 15 + 59 = 81
3 + 19 + 59 = 81
3 + 78 = 81
3 + 4 + 9 + 14 + 15 + 19 + 28 = 92
3 + 4 + 14 + 15 + 19 + 37 = 92
4 + 9 + 14 + 28 + 37 = 92
3 + 9 + 15 + 28 + 37 = 92
3 + 4 + 9 + 14 + 15 + 47 = 92
3 + 9 + 14 + 19 + 47 = 92
3 + 14 + 28 + 47 = 92
4 + 9 + 14 + 15 + 50 = 92
9 + 14 + 19 + 50 = 92
14 + 28 + 50 = 92
9 + 14 + 15 + 54 = 92
4 + 15 + 19 + 54 = 92
3 + 4 + 14 + 15 + 56 = 92
3 + 14 + 19 + 56 = 92
4 + 14 + 15 + 59 = 92
14 + 19 + 59 = 92
3 + 4 + 9 + 15 + 61 = 92
3 + 9 + 19 + 61 = 92
3 + 28 + 61 = 92
3 + 4 + 15 + 70 = 92
3 + 19 + 70 = 92
4 + 15 + 73 = 92
19 + 73 = 92
14 + 78 = 92
3 + 4 + 9 + 14 + 28 + 37 = 95
14 + 15 + 19 + 47 = 95
3 + 4 + 9 + 14 + 15 + 50 = 95
3 + 9 + 14 + 19 + 50 = 95
3 + 14 + 28 + 50 = 95
3 + 9 + 14 + 15 + 54 = 95
3 + 4 + 15 + 19 + 54 = 95
4 + 9 + 28 + 54 = 95
4 + 37 + 54 = 95
3 + 4 + 14 + 15 + 59 = 95
3 + 14 + 19 + 59 = 95
15 + 19 + 61 = 95
3 + 4 + 15 + 73 = 95
3 + 19 + 73 = 95
3 + 14 + 78 = 95
14 + 81 = 95
3 + 92 = 95
3 + 9 + 14 + 15 + 19 + 37 = 97
3 + 14 + 15 + 28 + 37 = 97
4 + 9 + 19 + 28 + 37 = 97
3 + 4 + 9 + 15 + 19 + 47 = 97
3 + 4 + 15 + 28 + 47 = 97
3 + 19 + 28 + 47 = 97
4 + 9 + 37 + 47 = 97
4 + 9 + 15 + 19 + 50 = 97
4 + 15 + 28 + 50 = 97
19 + 28 + 50 = 97
47 + 50 = 97
9 + 15 + 19 + 54 = 97
15 + 28 + 54 = 97
3 + 9 + 14 + 15 + 56 = 97
3 + 4 + 15 + 19 + 56 = 97
4 + 9 + 28 + 56 = 97
4 + 37 + 56 = 97
9 + 14 + 15 + 59 = 97
4 + 15 + 19 + 59 = 97
3 + 4 + 14 + 15 + 61 = 97
3 + 14 + 19 + 61 = 97
4 + 9 + 14 + 70 = 97
3 + 9 + 15 + 70 = 97
9 + 15 + 73 = 97
4 + 15 + 78 = 97
19 + 78 = 97
3 + 4 + 9 + 81 = 97
15 + 19 + 28 + 37 = 99
4 + 14 + 15 + 19 + 47 = 99
9 + 15 + 28 + 47 = 99
15 + 37 + 47 = 99
3 + 4 + 9 + 14 + 19 + 50 = 99
3 + 4 + 14 + 28 + 50 = 99
3 + 9 + 37 + 50 = 99
3 + 4 + 9 + 14 + 15 + 54 = 99
3 + 9 + 14 + 19 + 54 = 99
3 + 14 + 28 + 54 = 99
9 + 15 + 19 + 56 = 99
15 + 28 + 56 = 99
3 + 4 + 14 + 19 + 59 = 99
3 + 9 + 28 + 59 = 99
3 + 37 + 59 = 99
9 + 14 + 15 + 61 = 99
4 + 15 + 19 + 61 = 99
14 + 15 + 70 = 99
3 + 9 + 14 + 73 = 99
3 + 4 + 19 + 73 = 99
3 + 4 + 14 + 78 = 99
4 + 14 + 81 = 99
3 + 15 + 81 = 99
3 + 4 + 92 = 99
4 + 95 = 99
[altrefon@bxb-lds-026 ~]$


Top
 Profile  
Reply with quote  
Stathol
 Post subject:
PostPosted: Wed Feb 02, 2011 8:44 pm 
Offline
Lean, Mean, Googling Machine
User avatar

Joined: Thu Sep 03, 2009 9:35 am
Posts: 2903
Location: Maze of twisty little passages, all alike
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])

def findSols(superSet, subSet=None, subSetSum=0):
    if subSet == None:
        subSet = []
    solCount = 0

    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)

            solCount += findSols(newSuperSet, newSubSet, newSubSetSum)
    return solCount

def main():
    superSet = [3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54,
        56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99]

    print "Total solutions: %d" % findSols(superSet)
    return(0)

if __name__ == "__main__":
    sys.exit(main())


Now I'm wondering if there's an even faster solution that involves working backwards from the possible final sums. I bet there is.

_________________
Sail forth! steer for the deep waters only!
Reckless, O soul, exploring, I with thee, and thou with me;
For we are bound where mariner has not yet dared to go,
And we will risk the ship, ourselves and all.
Top
 Profile  
Reply with quote  
Lex Luthor
 Post subject:
PostPosted: Wed Feb 02, 2011 9:27 pm 
Offline

Joined: Thu Sep 03, 2009 10:03 am
Posts: 4922
Wow, your solution is really fast! I'm trying to think of a fast way without doing recursion.
Top
 Profile  
Reply with quote  
Stathol
 Post subject:
PostPosted: Wed Feb 02, 2011 11:40 pm 
Offline
Lean, Mean, Googling Machine
User avatar

Joined: Thu Sep 03, 2009 9:35 am
Posts: 2903
Location: Maze of twisty little passages, all alike
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.

_________________
Sail forth! steer for the deep waters only!
Reckless, O soul, exploring, I with thee, and thou with me;
For we are bound where mariner has not yet dared to go,
And we will risk the ship, ourselves and all.
Top
 Profile  
Reply with quote  
Noggel
PostPosted: Thu Feb 03, 2011 2:45 am 
Offline
User avatar

Joined: Thu Sep 24, 2009 4:57 am
Posts: 849
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!

All in good fun I suppose... :p
Top
 Profile  
Reply with quote  
Noggel
PostPosted: Thu Feb 03, 2011 3:38 pm 
Offline
User avatar

Joined: Thu Sep 24, 2009 4:57 am
Posts: 849
So many lines of code!

Problem is problem 3 from this .pdf: Computer Science Olympiad

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 main()
{
   int entered;
   int dec1, dec2, dec3;

   cout << "Enter a positive 4-digit integer: ";
   cin >> entered;
   cout << endl;

   cout << "Enter three decimal digits: ";
   cin >> dec1 >> dec2 >> dec3;
   cout << endl;

   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.
      */

      if (entered == sumConstruct(convert(test,dec1,dec2,dec3))) cout << "Result: " << convert(test,dec1,dec2,dec3)/1000000%1000 << " + " << convert(test,dec1,dec2,dec3)/1000%1000 << " + " << convert(test,dec1,dec2,dec3)%1000 << " = " << entered << endl;
      
      int digit = 1;
      flag = 'n';

      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.
Top
 Profile  
Reply with quote  
Stathol
 Post subject:
PostPosted: Fri Feb 04, 2011 12:19 am 
Offline
Lean, Mean, Googling Machine
User avatar

Joined: Thu Sep 03, 2009 9:35 am
Posts: 2903
Location: Maze of twisty little passages, all alike
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.

My first crack at this was in Python:

http://meriwoker.dyndns.org/~stathol/glade/3by3.py

But morbid curiosity got the better of me, so I ported it to C++:

http://meriwoker.dyndns.org/~stathol/glade/3by3.cpp

I included the ability in both progs to loop the algo 10k times with random inputs for profiling purposes:

Python:
Code:
<redacted>@juliet:~# /usr/bin/time ./3by3.py --profile > /dev/null
8.06user 0.01system 0:08.07elapsed 100%CPU (0avgtext+0avgdata 20368maxresident)k
0inputs+0outputs (0major+1388minor)pagefaults 0swaps


C++:
Code:
<redacted>@juliet:~# /usr/bin/time ./3by3-profile > /dev/null
0.07user 0.01system 0:00.08elapsed 102%CPU (0avgtext+0avgdata 4112maxresident)k
0inputs+0outputs (0major+293minor)pagefaults 0swaps


*sigh* It's okay, Python. I still love you. :/

_________________
Sail forth! steer for the deep waters only!
Reckless, O soul, exploring, I with thee, and thou with me;
For we are bound where mariner has not yet dared to go,
And we will risk the ship, ourselves and all.
Top
 Profile  
Reply with quote  
Noggel
PostPosted: Mon Feb 07, 2011 5:07 am 
Offline
User avatar

Joined: Thu Sep 24, 2009 4:57 am
Posts: 849
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.
Top
 Profile  
Reply with quote  
Taskiss
PostPosted: Wed Feb 09, 2011 10:20 pm 
Offline
User avatar

Joined: Fri Feb 05, 2010 11:59 am
Posts: 3879
Location: 63368
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.

Note: Ah, I see what you want...

Code:
#!/usr/bin/perl -w
use strict ;

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 ($result, $mask, $loop, $maskLen) ;

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 }

_________________
In time, this too shall pass.
Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  Page 1 of 1
  [ 9 posts ] 

Board index » The Glade » Tech

All times are UTC - 6 hours [ DST ]

Who is online

Users browsing this forum: No registered users and 165 guests

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group