[Tutor] Euler Spoiler

[Walter Prins]

Hi Keith,

On 12 January 2014 23:12, Keith Winston <keithwins at gmail.com> wrote:

> I'm working through some of the Project Euler problems, and the
> following might spoil one of the problems, so perhaps you don't want
> to read further...
>
>
> The problem relates to finding all possible combinations of coins that
> equal a given total. I'm basically brute-forcing it, which is probably
> not the way to go, but has already taught me a good bit about sets,
> tuples, and iterators, so... so far so good.
>
> However, after all the refactoring I can think of, I can't get it past
> a 3-coin list without it bogging down.
>

Sorry I haven't got time to look at your attempt closely (nearly 1am here),
but try/have a look at this:

from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    #Taken from: http://docs.python.org/2/library/itertools.html
    #(It doesn't strictly operate on or generate sets as can be seen.)
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

coins = [100, 50, 20, 20, 10, 10, 10]
goal = 200

solutions = set(list(s for s in powerset(coins) if sum(s) == goal))
print solutions
# outputs: set([(100, 50, 20, 20, 10), (100, 50, 20, 10, 10, 10)])



Walter
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20140113/1ad5aeed/attachment.html>