opengarden puzzle

bruteforce.py

#!/usr/bin/env python
# @see http://opengarden.com/senior-software-engineer.php
# @see http://xkcd.com/287/

from itertools import combinations

l = [
 18897109,
 12828837,
  9461105,
  6371773,
  5965343,
  5946800,
  5582170,
  5564635,
  5268860,
  4552402,
  4335391,
  4296250,
  4224851,
  4192887,
  3439809,
  3279833,
  3095313,
  2812896,
  2783243,
  2710489,
  2543482,
  2356285,
  2226009,
  2149127,
  2142508,
  2134411
]
need = 100000000

sum_l = sum(l)

# >>> 1.0 * sum(l) / need
# 1.29161818
# so I'm going to implement "deleting bruteforce" instead of "accumulating bruteforce"

range_l = range(len(l))

for elem_count in xrange(len(l)):
    print "Checking", elem_count, "combinations"
    is_more = False
    for ndx_lst in combinations(range_l, elem_count):
        todel = sum(l[i] for i in ndx_lst)
        if sum_l - todel == need:
            print "Found: todel =", ndx_lst, " include = ", tuple([l[i] for i in range_l if i not in ndx_lst])
        elif sum_l - todel > need:
            is_more = True
    if not is_more:
        print "Opps, all combinations del more than required"
        break

stdout

darkk@darkk-ya-thinkpad:~$ time python bruteforce.py 
Checking 0 combinations
Checking 1 combinations
Checking 2 combinations
Checking 3 combinations
Checking 4 combinations
Checking 5 combinations
Checking 6 combinations
Checking 7 combinations
Checking 8 combinations
Found: todel = (4, 7, 13, 14, 18, 19, 21, 23)  include =  (18897109, 12828837, 9461105, 6371773, 5946800, 5582170, 5268860, 4552402, 4335391, 4296250, 4224851, 3279833, 3095313, 2812896, 2543482, 2226009, 2142508, 2134411)
Checking 9 combinations
Checking 10 combinations
Checking 11 combinations
Checking 12 combinations
Opps, all combinations del more than required

real	0m34.389s
user	0m34.322s
sys	0m0.012s