code challenge: generate minimal expressions using only digits 1,2,3
anyone interested in looking at the following problem. we are trying to express numbers as minimal expressions using only the digits one two and three, with conventional arithmetic. so for instance 33 = 2^(3+2)+1 = 3^3+(3*2) are both minimal, using 4 digits but 33 = ((3+2)*2+1)*3 using 5 is not. I have tried coding a function to return the minimal representation for any integer, but haven't cracked it so far. The naive first attempt is to generate lots of random strings, eval() them and sort by size and value. this is inelegant and slow. I have a dim intuition that it could be done with a very clever bit of recursion, but the exact form so far eludes me. -- http://mail.python.org/mailman/listinfo/python-list
Re: code challenge: generate minimal expressions using only digits 1,2,3
On 20 Feb, 16:02, Paul Rubin <http://phr...@nospam.invalid> wrote: > Trip Technician writes: > > I have a dim intuition that it could be done with a very clever bit of > > recursion, but the exact form so far eludes me. > > This sounds a little like a homework assignment, or maybe a challenge > you are trying to solve for yourself, rather than be given a complete > answer for. Anyway, the basic idea is to enumerate the expression > trees with 1 digit, then 2 digits, then 3 digits, etc, and compute the > value expressed by each tree. Thanks will get onto it. It's just a challenge I set myself so hints only are cool. -- http://mail.python.org/mailman/listinfo/python-list
Re: code challenge: generate minimal expressions using only digits 1,2,3
On 20 Feb, 15:39, Nigel Rantor wrote: > Trip Technician wrote: > > anyone interested in looking at the following problem. > > if you can give me a good reason why this is not homework I'd love to > hear it...I just don't see how this is a real problem. > > > > > > > we are trying to express numbers as minimal expressions using only the > > digits one two and three, with conventional arithmetic. so for > > instance > > > 33 = 2^(3+2)+1 = 3^3+(3*2) > > > are both minimal, using 4 digits but > > > 33 = ((3+2)*2+1)*3 > > > using 5 is not. > > > I have tried coding a function to return the minimal representation > > for any integer, but haven't cracked it so far. The naive first > > attempt is to generate lots of random strings, eval() them and sort by > > size and value. this is inelegant and slow. > > Wow. Okay, what other ways have you tried so far? Or are you beating > your head against the "search the entire problem space" solution still? > > This problem smells a lot like factorisation, so I would think of it in > terms of wanting to reduce the target number using as few operations as > possible. > > If you allow exponentiation that's going to be your biggest hitter so > you know that the best you can do using 2 digits is n^n where n is the > largest digit you allow yourself. > > Are you going to allow things like n^n^n or not? > > n- Hide quoted text - > > - Show quoted text - yes n^n^n would be fine. agree it is connected to factorisation. building a tree of possible expressions is my next angle. -- http://mail.python.org/mailman/listinfo/python-list
not homework... something i find an interesting problem
although it's not homework (how can i prove that...?) i am still happy with just hints +++ we want to express integers as sums of squares. (repeated squares are allowed) most numbers have one minimal representation e.g. 24=16+4+4, some have two or more e.g. 125 = 121+4 = 100+25 so far I have created a simple recursive function that expresses a given number as a sum of squares in the obvious and naive way. it returns a nested tuple , which is then flattened for simplicity...then to cover the possibility that there might be one other minimal representation i call another similar function which will find one other representation, not necessarily shorter or of equal length, finally these are sorted and the results displayed, with the minimal result or the 2 equal-length minimal results. as the numbers get bigger (i believe) there will be some which have 3 or more minimal representations which this code will miss. what I want to do is come up with a recursion that will find all possible minimal representations in one function (if possible ) in an optimally elegant and scalable way. There's no application in mind, i just love playing with math. code so far below: # express numbers as sum of squares a=[x**2 for x in range(50,0,-1)] # finds obvious candidate def squ(z): if z==0: return 0 for x in a: if z>=x: return x,squ(z-x) # finds another candidate with largest square as next square down from above function def squ2(z): if z==0: return 0 for x in a: if z>=x: return a[a.index(x)+1],squ(z-a[a.index(x)+1]) def flatten(lst): for elem in lst: if type(elem) in (tuple, list): for i in flatten(elem): yield i else: yield elem q=[] r=[] for aa in range(100): r.append([]) for xx in range(10,100): q=[] for ss in flatten(squ(xx)): if ss!=0: q.append(ss) r[xx].append(q) for xx in range(10,100): q=[] for ss in flatten(squ2(xx)): if ss!=0: q.append(ss) r[xx].append(q) for eee in r: if eee: if len(eee[0])==len(eee[1]): print r.index(eee),eee[0],eee[1] else: print r.index(eee),eee[0] -- http://mail.python.org/mailman/listinfo/python-list
Re: not homework... something i find an interesting problem
Thank you Dave. This does it but slowly. takes every subset of the list a of squares, and then gets a 'partition' that will work, many are very inefficient (with lots of 1s). any hints about how to speed up ? def subset(x): for z in range(1,2**len(x)): q=bin(z) subs=[] for dig in range(len(q)): if q[dig]=='1': subs.append(x[dig]) yield subs def bin(x): q="" while x>=1: q+=str(x%2) x//=2 return q def squ(z,b): if z==0: return 0 for x in b: if z>=x: return x,squ(z-x,b) def flatten(lst): for elem in lst: if type(elem) in (tuple, list): for i in flatten(elem): yield i else: yield elem sizelim=150 a=[x**2 for x in range(int(sizelim**0.5),1,-1)] q,r=[],[] for aa in range(sizelim): r.append([]) for xx in range(1,sizelim): for z in subset(a): q=[] z.append(1) for rr in flatten(squ(xx,z)): if rr !=0: q.append(rr) item=[len(q),q] if item not in r[xx]: r[xx].append(item) r[xx].sort() for eee in r: if eee: print r.index(eee),eee[0:3] -- http://mail.python.org/mailman/listinfo/python-list
Re: not homework... something i find an interesting problem
On 21 Apr, 14:46, MRAB wrote: > Trip Technician wrote: > > Thank you Dave. This does it but slowly. takes every subset of the > > list a ofsquares, and then gets a 'partition' that will work, many > > are very inefficient (with lots of 1s). > > > any hints about how to speed up ? > > > def subset(x): > > for z in range(1,2**len(x)): > > q=bin(z) > > subs=[] > > for dig in range(len(q)): > > if q[dig]=='1': > > subs.append(x[dig]) > > yield subs > > > def bin(x): > > q="" > > while x>=1: > > q+=str(x%2) > > x//=2 > > return q > > > def squ(z,b): > > if z==0: > > return 0 > > for x in b: > > if z>=x: > > return x,squ(z-x,b) > > > def flatten(lst): > > for elem in lst: > > if type(elem) in (tuple, list): > > for i in flatten(elem): > > yield i > > else: > > yield elem > > > sizelim=150 > > > a=[x**2 for x in range(int(sizelim**0.5),1,-1)] > > > q,r=[],[] > > > for aa in range(sizelim): > > r.append([]) > > > for xx in range(1,sizelim): > > for z in subset(a): > > q=[] > > z.append(1) > > for rr in flatten(squ(xx,z)): > > if rr !=0: > > q.append(rr) > > item=[len(q),q] > > if item not in r[xx]: > > r[xx].append(item) > > r[xx].sort() > > > for eee in r: > > if eee: > > print r.index(eee),eee[0:3] > > Even this code doesn't find them all! For 135 it finds [49, 49, 36, 1], > [81, 25, 25, 4] and [81, 36, 9, 9], but not [121, 9, 4, 1].- Hide quoted text > - > > - Show quoted text - blowed if i know why that is ! -- http://mail.python.org/mailman/listinfo/python-list
