[Tutor] lambdas, generators, and the like
I've got this line: for k in range(len(tcombo)): tcombo_ep.append(list(combinations(tcombo, k+1))) generating every possible length combination of tcombo. I then test them, and throw most of them away. I need to do this differently, it gets way too big (crashes my computer). I'm going to play some more, but I think I need to test the combinations as they're generated... and then only add them to a list (probably better: a set) if they meet a requirement (something like sum(specific.combination(tcombo) == goal)) AND if they are not already part of that list (the uniqueness issue is why a set might be better) I'm partially asking in order to clarify the question in my mind, but any help will be appreciated. I don't really understand lambda functions yet, but I can sort of imagine they might work here somehow... or not. Thanks! -- Keith ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] lambdas, generators, and the like
On 12/01/14 09:04, Keith Winston wrote: I'm partially asking in order to clarify the question in my mind, but any help will be appreciated. I don't really understand lambda functions yet, but I can sort of imagine they might work here somehow... or not. lambdas are just a shortcut for single expression functions. You never need them, they just tidy up the code a bit by avoiding lots of use-once short functions. I'm not sure they would help a lot in your example. And, given you don't understand them yet, they would add complexity. hth -- Alan G Author of the Learn to Program web site http://www.alan-g.me.uk/ http://www.flickr.com/photos/alangauldphotos ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] another better way to do this ?
Hello,
Here is the whole exercise with examples.
# By Sam the Great from forums
# That freaking superhero has been frequenting Udacity
# as his favorite boss battle fight stage. The 'Udacity'
# banner keeps breaking, and money is being wasted on
# repairs. This time, we need you to proceduralize the
# fixing process by building a machine to automatically
# search through debris and return the 'Udacity' banner
# to the company, and be able to similarly fix other goods.
# Write a Python procedure fix_machine to take 2 string inputs
# and returns the 2nd input string as the output if all of its
# characters can be found in the 1st input string and Give me
# something that's not useless next time. if it's impossible.
# NOTE: # If you are experiencing difficulties taking
# this problem seriously, please refer back to
# Superhero flyby, the prequel, in Problem Set 11.
# TOOLS: # if statement
# while loop
# string operations
# Unit 1 Basics
# BONUS: #
# 5* # If you've graduated from CS101,
# Gold # try solving this in one line.
# Stars! #
def fix_machine(debris, product):
### WRITE YOUR CODE HERE ###
### TEST CASES ###
print Test case 1: , fix_machine('UdaciousUdacitee', 'Udacity') == Give me
something that's not useless next time.
print Test case 2: , fix_machine('buy me dat Unicorn', 'Udacity') == 'Udacity'
print Test case 3: , fix_machine('AEIOU and sometimes y... c', 'Udacity') ==
'Udacity'
print Test case 4: , fix_machine('wsx0-=mttrhix', 't-shirt') == 't-shirt'
Roelof
To: tutor@python.org
From: alan.ga...@btinternet.com
Date: Sun, 12 Jan 2014 00:45:11 +
Subject: Re: [Tutor] another better way to do this ?
On 11/01/14 21:24, Roelof Wobben wrote:
I have two strings a and b
Now I have to check if the characters of b are all in a.
But they do have to be in the same order.
I'm not sure exactly what you mean? Can you give some examples of
data that pass and that fail the criteria?
Your algorithm below might meet one definition of the spec but
its not valid code since it uses return but is not a function.
length = len(b)
start = 1
while start length :
check = a.find (b[start])
if check == -1 :
return False
start = start + 1
return True
Problems I see are:
1) you start testing at b[1] not b[0]
2) you don't check if the letters are in the same sequence in a as in b
3) you probably could tidy it up using a for loop over b rather than
indexing
But according to the site this can be solved in a one-liner.
That depends on the spec.
And have you covered regular expressions? That is probably one
way to do a one-liner...
But just because you can do it in one line doesn't mean you
should. It's better for code to be readable than short.
HTH
--
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.flickr.com/photos/alangauldphotos
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] lambdas, generators, and the like
On Sun, Jan 12, 2014 at 4:19 AM, Alan Gauld alan.ga...@btinternet.com wrote: lambdas are just a shortcut for single expression functions. You never need them, they just tidy up the code a bit by avoiding lots of use-once short functions. Thanks, I figured out how to iterate the combinations function. I'll play with lambda functions some other time. I've been cranking away on the Project Euler stuff, it's great fun, good Python practice... -- Keith ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] another better way to do this ?
On 12/01/14 08:12, Roelof Wobben wrote:
# Write a Python procedure fix_machine to take 2 string inputs
# and returns the 2nd input string as the output if all of its
# characters can be found in the 1st input string and Give me
# something that's not useless next time. if it's impossible.
OK So there is nothing here about the orders being the same.
That makes it much easier.
# 5* # If you've graduated from CS101,
# Gold # try solving this in one line.
Its not too hard to do in one line.
I think a filtered list comprehension and the all() function
would be one way.
print Test case 1: , fix_machine('UdaciousUdacitee', 'Udacity') ==
Give me something that's not useless next time.
print Test case 2: , fix_machine('buy me dat Unicorn', 'Udacity') ==
'Udacity'
print Test case 3: , fix_machine('AEIOU and sometimes y... c',
'Udacity') == 'Udacity'
print Test case 4: , fix_machine('wsx0-=mttrhix', 't-shirt') == 't-shirt'
I'd not use the while loop personally, I'd go for a for loop over b
and use the in operation on a. So Something like
for letter in b:
if letter not in a:
return
return b
HTH
--
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.flickr.com/photos/alangauldphotos
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] another better way to do this ?
Alan Gauld wrote:
On 12/01/14 08:12, Roelof Wobben wrote:
# Write a Python procedure fix_machine to take 2 string inputs
# and returns the 2nd input string as the output if all of its
# characters can be found in the 1st input string and Give me
# something that's not useless next time. if it's impossible.
OK So there is nothing here about the orders being the same.
That makes it much easier.
# 5* # If you've graduated from CS101,
# Gold # try solving this in one line.
Its not too hard to do in one line.
I think a filtered list comprehension and the all() function
would be one way.
print Test case 1: , fix_machine('UdaciousUdacitee', 'Udacity') ==
Give me something that's not useless next time.
print Test case 2: , fix_machine('buy me dat Unicorn', 'Udacity') ==
'Udacity'
print Test case 3: , fix_machine('AEIOU and sometimes y... c',
'Udacity') == 'Udacity'
print Test case 4: , fix_machine('wsx0-=mttrhix', 't-shirt') ==
't-shirt'
I'd not use the while loop personally, I'd go for a for loop over b
and use the in operation on a. So Something like
for letter in b:
if letter not in a:
return
return b
The test cases are not explicit about what to do with multiple occurences of
the same letter. I'd expect that debris must contain two 't's for 't-shirt'
to match. So:
print Test case 5: , fix_machine('wsx0-=mtrhix', 't-shirt') == Give me
something that's not useless next time.
If my assumption is correct a containment test is not sufficient; you need
to count the characters:
def fix_machine(debris, product):
return (product
if all(debris.count(c) = product.count(c) for c in
set(product))
else Give me something that's not useless next time.)
OP: You'll get bonus points (from me, so they're pointless points, but
still) if you can solve this (including the fifth apocryphal test case)
using the collections.Counter class.
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] lambdas, generators, and the like
Keith Winston keithw...@gmail.com Wrote in message: I've got this line: for k in range(len(tcombo)): tcombo_ep.append(list(combinations(tcombo, k+1))) generating every possible length combination of tcombo. I then test them, and throw most of them away. I need to do this differently, it gets way too big (crashes my computer). You should learn how to write and use a generator. Anytime you find yourself creating a huge list, and only navigating it once, consider writing a generator instead. A generator is any function that has a yield in it. You can turn the loop above into a one-level generator by def gen (tcombo): for k in range (len (tcombo)) yield list (combinations (tcombo, k+1)) And depending how you use the nested list, remove the call to list () for some real serious space savings. (untested) any help will be appreciated. I don't really understand lambda functions yet, but I can sort of imagine they might work here somehow... or not. A lambda is seldom necessary or useful in simple programs. -- DaveA nr Android NewsGroup Reader http://www.piaohong.tk/newsgroup ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] another better way to do this ?
Roelof Wobben rwob...@hotmail.com Wrote in message: That documentation says nothing about order. And the test cases specifically contradict it. so try if set (b) = set (a): -- DaveA Android NewsGroup Reader http://www.piaohong.tk/newsgroup ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] another better way to do this ?
On Sun, Jan 12, 2014 at 8:21 AM, Peter Otten __pete...@web.de wrote:
OP: You'll get bonus points (from me, so they're pointless points, but
still) if you can solve this (including the fifth apocryphal test case)
using the collections.Counter class.
Hint:
print(Counter.__sub__.__doc__)
Subtract count, but keep only results with positive counts.
Counter('abbbc') - Counter('bccd')
Counter({'b': 2, 'a': 1})
product = Counter('t-shirt')
product - Counter('wsx0-=mttrhix')
Counter()
product - Counter('wsx0-=mtrhix')
Counter({'t': 1})
`Counter` has multiset methods for the operators +, -,
(intersection; min count), and | (union; max count). However, it
doesn't implement the `issubset` or `issuperset` methods of `set`, nor
the ordered comparisons (, , =, =) that depend on them.
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] another better way to do this ?
On 12/01/14 14:43, Dave Angel wrote: so try if set (b) = set (a): Ooh, nice! For some reason I've never thought of applying set to a string before. -- Alan G Author of the Learn to Program web site http://www.alan-g.me.uk/ http://www.flickr.com/photos/alangauldphotos ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] lambdas, generators, and the like
Thanks Dave, that looks like a good idea, I've played a little with one-line generators (? the things similar to list comprehensions), but I'm still wrapping my head around how to use them. Meanwhile I'm reorganizing my code because I now understand better how to use iterators (i.e. the combinations function), and I'm exploring using tuples where I can instead of lists... if I followed an earlier conversation properly, I think garbage collection might happen more immediately with immutables than mutables, and this program is crashing either Python or my entire computer every time I run it... I'm generating a LOT of combinations. On Sun, Jan 12, 2014 at 9:33 AM, Dave Angel da...@davea.name wrote: Keith Winston keithw...@gmail.com Wrote in message: I've got this line: for k in range(len(tcombo)): tcombo_ep.append(list(combinations(tcombo, k+1))) generating every possible length combination of tcombo. I then test them, and throw most of them away. I need to do this differently, it gets way too big (crashes my computer). You should learn how to write and use a generator. Anytime you find yourself creating a huge list, and only navigating it once, consider writing a generator instead. A generator is any function that has a yield in it. You can turn the loop above into a one-level generator by def gen (tcombo): for k in range (len (tcombo)) yield list (combinations (tcombo, k+1)) And depending how you use the nested list, remove the call to list () for some real serious space savings. (untested) any help will be appreciated. I don't really understand lambda functions yet, but I can sort of imagine they might work here somehow... or not. A lambda is seldom necessary or useful in simple programs. -- DaveA nr Android NewsGroup Reader http://www.piaohong.tk/newsgroup ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor -- Keith ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] another better way to do this ?
On Sun, Jan 12, 2014 at 7:44 AM, Alan Gauld alan.ga...@btinternet.com wrote: OK So there is nothing here about the orders being the same. That makes it much easier. There's another approach, I think, that's quite easy if order IS important. Iterate through the letters of product, find() them initially from the beginning of debris, and then from the index of the last letter found. Accounts for multiples in product, order. def fix_machine(debris, product): index = 0 success = False for letter in product: test = debris.find(letter, index) if test: index = test else: # Failure return Give me something that's not useless next time. return product # Success I suspect this could be done in one line, without regex, but it would probably take me a week to figure out... maybe next week ;) -- Keith ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] another better way to do this ?
On 12/01/2014 19:22, Keith Winston wrote: On Sun, Jan 12, 2014 at 7:44 AM, Alan Gauld alan.ga...@btinternet.com wrote: OK So there is nothing here about the orders being the same. That makes it much easier. There's another approach, I think, that's quite easy if order IS important. Iterate through the letters of product, find() them initially from the beginning of debris, and then from the index of the last letter found. Accounts for multiples in product, order. def fix_machine(debris, product): index = 0 success = False for letter in product: test = debris.find(letter, index) if test: index = test else: # Failure return Give me something that's not useless next time. return product # Success I suspect this could be done in one line, without regex, but it would probably take me a week to figure out... maybe next week ;) A better idea would be to find out why the above dosn't work correctly, I'll leave that in your capable hands :) -- My fellow Pythonistas, ask not what our language can do for you, ask what you can do for our language. Mark Lawrence ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] another better way to do this ?
OOps, I never used the success boolean in my code, but forgot to remove it. Sorry. ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] another better way to do this ?
On Sun, Jan 12, 2014 at 2:22 PM, Keith Winston keithw...@gmail.com wrote: if test: Sigh and this line needs to read (if it's going to do what I said): if test != -1: -- Keith ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] another better way to do this ?
On Sun, Jan 12, 2014 at 2:38 PM, Keith Winston keithw...@gmail.com wrote: On Sun, Jan 12, 2014 at 2:22 PM, Keith Winston keithw...@gmail.com wrote: if test: Sigh and this line needs to read (if it's going to do what I said): if test != -1: Consider the case of `product == letter`. Do you want to double match on the 't' found in `debris`? I'm +1 for finding a solution... ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] another better way to do this ?
On Sun, Jan 12, 2014 at 2:38 PM, Keith Winston keithw...@gmail.com wrote: Sigh and this line needs to read (if it's going to do what I said): As Alan pointed out, the examples provided do NOT account for order, so if one uses my (corrected) algorithm, you get different results from the examples. Without the fix you get the example results, but may not realize that it's not accounting for repeats in that case (which the instructions don't address either). It might be instructive, if it's not already obvious, to understand why this would be... ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] another better way to do this ?
On 01/12/2014 06:43 AM, Dave Angel wrote: Roelof Wobben rwob...@hotmail.com Wrote in message: That documentation says nothing about order. And the test cases specifically contradict it. so try if set (b) = set (a): or, as the OP specified, if order is relevant, def test(a,b): for ii in a: if ii not in b: a=a.replace(ii,) return b in a Emile ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] another better way to do this ?
Emile van Sebille wrote: On 01/12/2014 06:43 AM, Dave Angel wrote: Roelof Wobben rwob...@hotmail.com Wrote in message: That documentation says nothing about order. And the test cases specifically contradict it. so try if set (b) = set (a): or, as the OP specified, if order is relevant, def test(a,b): for ii in a: if ii not in b: a=a.replace(ii,) return b in a def test(a,b): ...for ii in a: ... if ii not in b: a=a.replace(ii,) ...return b in a ... test(axbxc, abc) True test(abbxc, abc) False Is the second result desired? ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] another better way to do this ?
On 01/12/2014 12:21 PM, Peter Otten wrote: test(axbxc, abc) True test(abbxc, abc) False Is the second result desired? No -- the second should match -- you found a test case I didn't... def test(a,b): for ii in a: if ii not in b: a=a.replace(ii,) while ii+ii in a: a=a.replace(ii+ii,ii) return b in a Show me another. :) Emile ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] another better way to do this ?
Emile van Sebille wrote: On 01/12/2014 12:21 PM, Peter Otten wrote: test(axbxc, abc) True test(abbxc, abc) False Is the second result desired? No -- the second should match -- you found a test case I didn't... def test(a,b): for ii in a: if ii not in b: a=a.replace(ii,) while ii+ii in a: a=a.replace(ii+ii,ii) return b in a Show me another. :) def test(a,b): ...for ii in a: ... if ii not in b: a=a.replace(ii,) ... while ii+ii in a: a=a.replace(ii+ii,ii) ...return b in a ... test(abac, abc) False ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] another better way to do this ?
On Sun, Jan 12, 2014 at 2:22 PM, Keith Winston keithw...@gmail.com wrote: There's another approach, I think, that's quite easy if order IS important. Alas, there's one further problem with my script, relating to testing multiple sequential letters in product... but I'm not going to say more, I'll leave it as a problem for the OP. It's an easy fix once you understand the issue. -- Keith ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
[Tutor] Euler Spoiler
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.
I'm sure there are wholly different approaches, feel free to hint at
them, but my real question is: is there any further fine-tuning of my
approach (or any outright problems with it) that would be instructive?
Thanks!
Also: I think it might have worked better with lists that tuples,
though I don't really understand why, unless I misunderstand speed or
memory management issues (or something else).
from itertools import combinations
coins = [100, 50, 20] # should include 1, 2, 5, 10 (plus one 200 combo)
ans = set()
goal = 200
tcombo = ()
# Iterate over all possible length combinations of coins
for i in range(len(coins)):
print(i)
# For each unique combo of coins, and...
for combo in combinations(coins, i+1):
tcombo = ()
# For each coin in that combo...
for coin in combo:
# create a new tuple of as many of those coins as
# it would take to reach the goal
tcombo = tcombo + (coin,) * int(goal/coin)
# with this new extended list, generate all possible
length combinations
for k in range(len(tcombo)):
for c in combinations(tcombo, k + 1):
if sum(c) == goal:
ans = ans | {c}
print(ans)
--
Keith
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Euler Spoiler
Hi Keith, On 12 January 2014 23:12, Keith Winston keithw...@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 ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Euler Spoiler
This sounds very much like a problem that demands trying to break the problems down into subproblems, and then applying a dynamic-programming approach to make it fairly easy to get an efficient solution. Such problems that are amendable to this approach have a substructure to them so that the main problem breaks down into smaller versions of the same problem. As an example, Problem 15 on Lattice paths is a good one: http://projecteuler.net/problem=15 Here, the problem is asking: count how many paths there are in the n*n grid. A sub-problem of this is: count how many paths there are in the (n-1)*n graph, and count how many paths there are in the N*(n-1) grid. Why are those particular subproblems interesting? Because if you have the answer for the (n-1)*n and the n*(n-1), then you add the results of those two together, and you get the answer for the original n*n case! Another example of a dynamic programming situation is in Problem 18, http://projecteuler.net/problem=18 where we can decompose the problem of trying to find the path that maximizes the sum from the triangle as a whole to the sub-triangles on the left and right hand sides. In your problem statement, you're trying to answer the question: Given some goal g, find all the ways to break change. A subproblem of this is: Given some goal (g - x) for each x in the denominations, find all the ways to break change. That is, a trick to solving the problem is to treat 'goal' as a variable, part of the problem statement that can be changed. Are you familiar with the dynamic programming approach? I'm sure folks here would be happy to talk about it more and show concrete examples; it's a very powerful tool. ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Euler Spoiler
Keith Winston keithw...@gmail.com Wrote in message: 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. Care to define bogging down? If you mean it gets REALLY slow then I'm not surprised. Do you have any idea how many combinations there are for even a moderate sized list of coins? For the call combinations(tcombo, k + 1) with k =99 and tcombo of size 200, the number of iterations has 59 digits. With a really fast computer you might scratch the surface in a trillion trillion trillion years. One way to improve on that enormously would be to scrap tcombo and call itertool.combinations_with_replacement. But I think the notion of generating all combinations and then selecting is doomed to failure for all but the smallest problems. Incidentally I think you have way too many nested loops. Even if brute force were going to work, you'd do it with itertool.combinations_with_replacement(coins without doing combo or tcombo. -- DaveA Android NewsGroup Reader http://www.piaohong.tk/newsgroup ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Euler Spoiler
Thanks everyone, things to chew on. I'll look at the other itertools functions mentioned. I did solve Proj. Euler 15 18 (and it's corresponding 67), one more elegantly than the other, and I have given some thought to how to break this one down, but haven't figured it out yet. I think I might not be willing to wait a trillion years. I think I'm going to stop development on this approach, both 1) because I don't think it's going to work, and 2) because I might have learned most of what I can from it, re: Python skills. I am quite interested in the dynamic programming approach, which I understand my approach to PE 18 was consistent with, but which I don't yet understand how to apply more broadly or consistently. I'll do some reading on it. ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Euler Spoiler
To be concrete, I think you're looking at Problem 31, right? http://projecteuler.net/problem=31 in which case, we have a few choices for denomination: 1p, 2p, 5p, 10p, 20p, 50p, 100p, 200p and we're trying to _count_ how many ways to make 200p. Here's a sketch of how I'd attack this by considering a DP-style approach. If you want to avoid any spoilers, please skip this message. Otherwise, I'll try to be as transparent as to my thought process as I can. --- We first want to name and conquer. Let C(k) be the number of ways to make change for 'k' pence. Why C(k)? Because I think C(200) is what we're looking for. I'm making 'k' be the parameter here because I think an approach that tries to figure out C, where n ranges from [0-200], should do the trick. Note: for now, let's assume that C does not remember _how_ we're making the change. It should only remember the number of ways to do so. What are some values for C? Let us try to reason what C must be for low values of 'k'. -- C(0) = 1. There's one way to make change for zero pence, namely the empty case. It might be important to argue this edge case, so that's why I'm considering it. -- C(1) = 1. We know we can do this one trivially. 1p -- C(2) = 2. We can either do it as: 1p + 1p, or 2p -- C(3) = 2. We can do it as: 2p + 1p, or 1p + 1p + 1p. Note: we don't want to treat: 1p + 2p as another possibility! Why not? Because that would be a duplicate of 2p + 1p which we already counted for already. Believe it or not, this observation is important, because we'll find in a few moments that it forces us to reconsider an amendment to our approach. --- One observation so far: it looks like we can construct more of C by looking at previous elements of C. That would mean we just run through constructing C bottom-up, from k=1 through 200. If that's the case, then we're golden. We can just keep the intermediate values of C as an array of ints. Easy. Or not. :P Let's see what happens. -- C(4) = ...? This is starting not to be so obvious. Let's try to reason it out. From our observation, let's see if we can just take previous elements that we computed for C and just sum it up in some nice way. If we're trying to make change for four pence, then... 1. If there's a change-making sequence that starts of as: 2p + ..., for example, the ... would stand for ways of making change for the remainder 4p - 2p == 2p. Looking back at how we computed C(2), we could make C(2) out of: 1p + 1p, or 2p So if we just put 2p in front of those, that gives us: 2p + 1p + 1p, or 2p + 2p. Good! 2. If there's a change-making sequence that starts off as 1p + ..., for example, the ... would stand for the ways of making change for the remainder 4p - 1p == 3p. Looking back at how we computed C(3), we know that it was constructed out of: 2p + 1p, or 1p + 1p + 1p. So maybe we can just put 1p in front of those! 1p + ... ways of making C(3) == 1p + 2p + 1p, or 1p + 1p + 1p + 1p. ... Oh! But wait, we don't want to count: 1p + 2p + 1p because we already did that, essentially, when we did 2p + 1p + 1p In fact, we ran into this issue earlier on when we were trying to figure out C(3). So C(4) is 3, because we can make it out of: 2p + 1p + 1p, or 2p + 2p, or 1p + 1p + 1p + 1p. --- Huh. That wasn't as simple as just adding up previous values for C. Nuts. Let's think about this a bit. Earlier, we were hoping we could just naively look at C for previous values of k, and just add them up. But we want to make sure we DON'T over-count ways of making the change. The difficulty that we're running across is due to the structure of C: it doesn't let us know if we're counting a change-making that already takes into consideration something we already counted. What to do? Maybe our earlier approach, to not remember how exactly we're making the change, can be amended. One approach might be to change the return type of C. Rather than have it keep track of just the number of ways of counting change, we might instead hold onto a description of the change sums themselves. This should work! But it would mean that we have to hold a list of list of denominations. And we'd have to do an additional duplication-filtering step. But we know we can do it this way, if we really needed to. But there is another approach. I will sketch this approach out because I'm pretty sure it's the one the problem writers intended. Let's look again at that troublesome change-making that's causing us grief: 1p + 2p + 1p We don't want this because it's a duplicate of: 2p + 1p + 1p Well, what's different about it? The numbers are in a different order. The case we don't care particularly for, 1p + 2p + 1p,
