Re: code challenge: generate minimal expressions using only digits 1,2,3
On Feb 20, 6:31 am, Trip Technician luke.d...@gmail.com wrote: 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. Actually, representing 33 has an even shorter answer: '33' There is actually a really easy solution for this. What you are really doing is finding the shortest path from point A (the expression '') to another expression that evaluates to the target number. From each point, you can take steps that (a) add a digit to the end or (b) add an operator---but only if it makes sense. Since operators don't count, those steps don't add anything to the distance, while the digits do. What you do is you start walking the map from point A to some mysterious point that evaluates to the result you want. Actually, you send out walkers in all directions, and tell only the walkers that have taken the fewest steps to take another step. Once a walker gets to an expression with the result, you have your answer since he is the first walker to get there. When a walker gets to an expression that has already been visited, you can tell that walker to go home since his path was no good. When a walker gets to an expression that evaluates to a value you have already seen, that walker too should go home since he has just found a longer path to the same result. So you have a set of walkers, and each walker has the expression they used to get to where they are and how many steps they took to get there. You also have a set of values you have seen before and thus values that if a walker finds you are no longer interested in. For each iteration, you take each surviving walker and spawn a new walker that takes a step in each possible direction. Then you check if any of those walkers found the value you are looking for. If so, you've found the answer. If they hit a value you've already seen, you drop that walker from the set. The only hanging point is parentheses. What you can do here is instead of building a linear expression, build a tree expression that shows the operations and the values they operate. It should be trivial to calculate all the different new trees that are one digit longer than a previous tree. -- http://mail.python.org/mailman/listinfo/python-list
Re: code challenge: generate minimal expressions using only digits 1,2,3
On Thu, 26 Feb 2009 23:10:20 -, Jonathan Gardner jgard...@jonathangardner.net wrote: [snip] For each iteration, you take each surviving walker and spawn a new walker that takes a step in each possible direction. Then you check if any of those walkers found the value you are looking for. If so, you've found the answer. If they hit a value you've already seen, you drop that walker from the set. This relies each value having the same set of next states no matter how it's reached. Unfortunately that's not true. Consider what happens when you walk on from (1+3) and (2+2): One possible step from (1+3) is ((1/3)+3) == 3.33... There's no single step from (2+2) that can get you to the same place. The only hanging point is parentheses. What you can do here is instead of building a linear expression, build a tree expression that shows the operations and the values they operate. It should be trivial to calculate all the different new trees that are one digit longer than a previous tree. Trivial yes, but the number of different new trees is large when you're dealing with four digits, and ridiculous with 5. -- Rhodri James *-* Wildebeeste Herder to the Masses -- http://mail.python.org/mailman/listinfo/python-list
Re: code challenge: generate minimal expressions using only digits 1,2,3
Trip Technician wrote: 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. Here's my solution (I haven't bothered with making it efficient, BTW): import operator def solve(n): best_len = n best_expr = for x in range(1, n - 2): for y in range(x, n): for op, name in operator_list: # Does this pair with this op give the right answer? if op(x, y) == n: lx, ex = numbers[x - 1] ly, ey = numbers[y - 1] # How many digits in total? l = lx + ly # Fewer digits than any previous attempts? if l best_len: # Build the expression. e = (%s %s %s) % (ex, name, ey) best_len, best_expr = l, e return best_len, best_expr operator_list = [(operator.add, +), (operator.sub, -), (operator.mul, *), (operator.div, /), (operator.pow, ^)] # Tuples contain number of digits used and expression. numbers = [(1, str(n)) for n in range(1, 4)] for n in range(4, 34): numbers.append(solve(n)) for i, (l, e) in enumerate(numbers): print %2d = %s % (i + 1, e) -- http://mail.python.org/mailman/listinfo/python-list
Re: code challenge: generate minimal expressions using only digits 1,2,3
Use 1 and 2 and treat them as equivalent to boolean true and false. -- http://mail.python.org/mailman/listinfo/python-list
Re: code challenge: generate minimal expressions using only digits 1,2,3
MRAB wrote: Here's my solution (I haven't bothered with making it efficient, BTW): import operator def solve(n): best_len = n best_expr = for x in range(1, n - 2): for y in range(x, n): for op, name in operator_list: # Does this pair with this op give the right answer? if op(x, y) == n: lx, ex = numbers[x - 1] ly, ey = numbers[y - 1] # How many digits in total? l = lx + ly # Fewer digits than any previous attempts? if l best_len: # Build the expression. e = (%s %s %s) % (ex, name, ey) best_len, best_expr = l, e return best_len, best_expr operator_list = [(operator.add, +), (operator.sub, -), (operator.mul, *), (operator.div, /), (operator.pow, ^)] # Tuples contain number of digits used and expression. numbers = [(1, str(n)) for n in range(1, 4)] for n in range(4, 34): numbers.append(solve(n)) for i, (l, e) in enumerate(numbers): print %2d = %s % (i + 1, e) Sadly this doesn't work because you're assuming that the shortest expression always involves increasing the size of the numbers at every step. For example, your algorithm for 63 gives: (3 * (3 * (1 + (2 * 3 which involves 4 operations, whereas the simplest is: 2**(2*3)-1 which only involves 3 (but has an intermediate value 2**6=64 above the target value). Fixing this is actually pretty hard, because the search space becomes very large if you allow yourself arbitrarily large numbers. You can't do any obvious pruning that I can think of, because operations between very large numbers can end up very small (for example, 13**3-3**7=10 even though 13**3=2197 and 3**7=2187 are both very large), and the shortest path to a small number might go through very large numbers (I bet with a bit more thought than I have put into it, you could come up with some examples where the intermediate calculations are arbitrarily larger than the end result). As well as the growth of the search space, the computations get hairy too, try computing 3**3**3**3 for example (or better, don't, because it has 3638334640025 digits). I haven't got a solution that can be guaranteed correct and is feasible to compute for anything but very small examples - anyone done better? Dan -- http://mail.python.org/mailman/listinfo/python-list
Re: code challenge: generate minimal expressions using only digits 1,2,3
test On Sat, Feb 21, 2009 at 3:31 AM, Trip Technician luke.d...@gmail.comwrote: 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 -- http://mail.python.org/mailman/listinfo/python-list
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
Having looked long at this how does the prime factorization play into this. I would consider an approach similar to factoring a number. Of course the issue with prime factoring is your ned to know the primes. I assume this would be a similar problem you may need to know the solutions to the factors. I might look closer at this please post if you come across a solution. Thanks Vincent Davis 720-301-3003 On Fri, Feb 20, 2009 at 7:31 AM, Trip Technician luke.d...@gmail.comwrote: 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: code challenge: generate minimal expressions using only digits 1,2,3
I am teaching myself coding. No university or school, so i guess its homework if you like. i am interested in algorithms generally, after doing some of Project Euler. Of course my own learning process is best served by just getting on with it but sometimes you will do that while other times you might just choose to ask for help. if no one suggests then i will probably shelve it and come back to it myself when I'm fresh. no it's not a real world problem but my grounding is in math so i like pure stuff anyway. don't see how that is a problem, as a math person i accept the validity of pure research conducted just for curiosity and aesthetic satisfaction. it often finds an application later anyway Thanks for your helpful suggestion of trying other methods and i will do that in time. my motive was to share an interesting problem because a human of moderate math education can sit down with this and find minimal solutions easily but the intuition they use is quite subtle, hence the idea of converting the human heuristic into an algorithm became of interest, and particularly a recursive one. i find that the development of a piece of recursion usually comes as an 'aha', and since i hadn't had such a moment, i thought i'd turn the problem loose on the public. also i found no online reference to this problem so it seemed ripe for sharing. On Fri, Feb 20, 2009 at 3:39 PM, Nigel Rantor wig...@wiggly.org 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: code challenge: generate minimal expressions using only digits 1,2,3
yes power towers are allowed exponentiation, multiplication, division, addition and subtraction. Brackets when necessary but length is sorted on number of digits not number of operators plus digits. I always try my homework myself first. in 38 years of life I've learned only to do what i want, if I wanted everyone else to do my work for me I'd be a management consultant ! On Fri, Feb 20, 2009 at 3:52 PM, Luke Dunn luke.d...@gmail.com wrote: I am teaching myself coding. No university or school, so i guess its homework if you like. i am interested in algorithms generally, after doing some of Project Euler. Of course my own learning process is best served by just getting on with it but sometimes you will do that while other times you might just choose to ask for help. if no one suggests then i will probably shelve it and come back to it myself when I'm fresh. no it's not a real world problem but my grounding is in math so i like pure stuff anyway. don't see how that is a problem, as a math person i accept the validity of pure research conducted just for curiosity and aesthetic satisfaction. it often finds an application later anyway Thanks for your helpful suggestion of trying other methods and i will do that in time. my motive was to share an interesting problem because a human of moderate math education can sit down with this and find minimal solutions easily but the intuition they use is quite subtle, hence the idea of converting the human heuristic into an algorithm became of interest, and particularly a recursive one. i find that the development of a piece of recursion usually comes as an 'aha', and since i hadn't had such a moment, i thought i'd turn the problem loose on the public. also i found no online reference to this problem so it seemed ripe for sharing. On Fri, Feb 20, 2009 at 3:39 PM, Nigel Rantor wig...@wiggly.org 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: code challenge: generate minimal expressions using only digits 1,2,3
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: code challenge: generate minimal expressions using only digits 1,2,3
this is a neat problem. here is what i would do: use generators that extend an input. a stream approach. the initial input would be the numbers themselves. [('1', 1),('2', 2),('3', 3)] those are (expression, value) pairs then an initial attempt at the next function would be to extend that list with additions: def additions(pairs): for (expr1, value1) in pairs: # first, pass through unchanged yield (expr1, value1) # then generate all possible additions for (expr2, value2) in pairs: yield ('%s+%s'%(value1, value2), value1 + value2)) this would give you: [('1', 1),('2', 2),('3', 3), ('1+1', 2), ...] (you may need to add parentheses to expressions to preserve meaning correctly) you could extend that with an extra loop over different operations. (subtraction, multiplication, etc) then you could repeat that as often as you want (eating its own tail, in a sense, i think). an infinite list is ok because these are generators. then you could filter that to group expressions that give a certain value, and find the shortest. andrew Trip Technician wrote: 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 -- 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 luke.d...@gmail.com 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 wig...@wiggly.org 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
Re: code challenge: generate minimal expressions using only digits 1,2,3
Luke Dunn wrote: yes power towers are allowed right, okay, without coding it here's my thought. factorise the numbers you have but only allowing primes that exist in your digit set. then take that factorisation and turn any repeated runs of digits multiplied by themselves into power-towers any remainder can then be created in other ways, starting with a way other than exponentiation that is able to create the largest number, i.e. multiplication, then addition... I've not got time to put it into code right now but it shouldn't be too hard... e.g. digits : 3, 2, 1 n : 10 10 = 2*5 - but we don't have 5... 10 = 3*3 + 1 10 = 3^2+1 3 digits n : 27 27 = 3*3*3 27 = 3^3 2 digits n : 33 33 = 3*3*3 + 6 33 = 3*3*3 + 3*2 33 = 3^3+3*2 4 digits exponentiation, multiplication, division, addition and subtraction. Brackets when necessary but length is sorted on number of digits not number of operators plus digits. I always try my homework myself first. in 38 years of life I've learned only to do what i want, if I wanted everyone else to do my work for me I'd be a management consultant ! On Fri, Feb 20, 2009 at 3:52 PM, Luke Dunn luke.d...@gmail.com mailto:luke.d...@gmail.com wrote: I am teaching myself coding. No university or school, so i guess its homework if you like. i am interested in algorithms generally, after doing some of Project Euler. Of course my own learning process is best served by just getting on with it but sometimes you will do that while other times you might just choose to ask for help. if no one suggests then i will probably shelve it and come back to it myself when I'm fresh. no it's not a real world problem but my grounding is in math so i like pure stuff anyway. don't see how that is a problem, as a math person i accept the validity of pure research conducted just for curiosity and aesthetic satisfaction. it often finds an application later anyway Thanks for your helpful suggestion of trying other methods and i will do that in time. my motive was to share an interesting problem because a human of moderate math education can sit down with this and find minimal solutions easily but the intuition they use is quite subtle, hence the idea of converting the human heuristic into an algorithm became of interest, and particularly a recursive one. i find that the development of a piece of recursion usually comes as an 'aha', and since i hadn't had such a moment, i thought i'd turn the problem loose on the public. also i found no online reference to this problem so it seemed ripe for sharing. On Fri, Feb 20, 2009 at 3:39 PM, Nigel Rantor wig...@wiggly.org mailto:wig...@wiggly.org 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: code challenge: generate minimal expressions using only digits 1,2,3
Trip Technician wrote: yes n^n^n would be fine. agree it is connected to factorisation. building a tree of possible expressions is my next angle. I think building trees of the possible expressions as a couple of other people have suggested is simply a more structured way of doing what you're currnetly doing. Right now you're throwing darts at the problem space, and hoping that the next one point you hit will be a more optimal solution. If you enumerate all the expression trees you are just ensuring you don't miss any solutions. I think the algorithm/hueristic I just posted should get you to the answer quicker though... n -- http://mail.python.org/mailman/listinfo/python-list
Re: code challenge: generate minimal expressions using only digits 1,2,3
On Fri, 2009-02-20 at 16:38 +, Nigel Rantor wrote: Luke Dunn wrote: snip That was my initial thought when I read this too - but I'm not certain that is guaranteed to find a solution (i.e. a solution that's optimal). I'd welcome a proof that it will though, a few minutes thought hasn't found a counter-example. yes power towers are allowed right, okay, without coding it here's my thought. factorise the numbers you have but only allowing primes that exist in your digit set. then take that factorisation and turn any repeated runs of digits multiplied by themselves into power-towers any remainder can then be created in other ways, starting with a way other than exponentiation that is able to create the largest number, i.e. multiplication, then addition... I've not got time to put it into code right now but it shouldn't be too hard... e.g. digits : 3, 2, 1 n : 10 10 = 2*5 - but we don't have 5... 10 = 3*3 + 1 10 = 3^2+1 3 digits n : 27 27 = 3*3*3 27 = 3^3 2 digits n : 33 33 = 3*3*3 + 6 33 = 3*3*3 + 3*2 33 = 3^3+3*2 4 digits exponentiation, multiplication, division, addition and subtraction. Brackets when necessary but length is sorted on number of digits not number of operators plus digits. I always try my homework myself first. in 38 years of life I've learned only to do what i want, if I wanted everyone else to do my work for me I'd be a management consultant ! On Fri, Feb 20, 2009 at 3:52 PM, Luke Dunn luke.d...@gmail.com mailto:luke.d...@gmail.com wrote: I am teaching myself coding. No university or school, so i guess its homework if you like. i am interested in algorithms generally, after doing some of Project Euler. Of course my own learning process is best served by just getting on with it but sometimes you will do that while other times you might just choose to ask for help. if no one suggests then i will probably shelve it and come back to it myself when I'm fresh. no it's not a real world problem but my grounding is in math so i like pure stuff anyway. don't see how that is a problem, as a math person i accept the validity of pure research conducted just for curiosity and aesthetic satisfaction. it often finds an application later anyway Thanks for your helpful suggestion of trying other methods and i will do that in time. my motive was to share an interesting problem because a human of moderate math education can sit down with this and find minimal solutions easily but the intuition they use is quite subtle, hence the idea of converting the human heuristic into an algorithm became of interest, and particularly a recursive one. i find that the development of a piece of recursion usually comes as an 'aha', and since i hadn't had such a moment, i thought i'd turn the problem loose on the public. also i found no online reference to this problem so it seemed ripe for sharing. On Fri, Feb 20, 2009 at 3:39 PM, Nigel Rantor wig...@wiggly.org mailto:wig...@wiggly.org 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 -- http://mail.python.org/mailman/listinfo/python-list -- http://mail.python.org/mailman/listinfo/python-list
Re: code challenge: generate minimal expressions using only digits 1,2,3
from subsequent posts i think you were looking for something smarter than my streams, but i was interested in the idea, so i wrote an implementation. hope this is ok - if you don't want to see a worked solution, read no further... i have been using generators a lot recently; now that i understand them better i really like the laziness they give. this code is perhaps more like you would see in haskell than in python... some results from the code as below: -725 = (((1)+(1))+((1)+(1)))-(((1)+(2))^((2)*(3))) (length 8) ... -2 = (1)-(3) (length 2) -1 = (1)-(2) (length 2) 0 = (1)-(1) (length 2) 1 = 1 (length 1) 2 = 2 (length 1) 3 = 3 (length 1) 4 = (1)+(3) (length 2) ... 972 = (((1)+(1))+((1)+(1)))*(((1)+(2))^((2)+(3))) (length 8) note that because this is a brute-force search it is limited in the number of combinations it considers (for a given take, below), and not at all smart (in preferring pow over other values for example), so the extreme values are nothing like optimal (the final invocation, commented out, uses sorting to improve things). also, complex and float values are generated; i discard those with a filter, but you can drop that if you are curious. #!/usr/bin/python3 ''' See http://groups.google.com/group/comp.lang.python/browse_thread/thread/b387f99deb376392 This is a brute force approach using streams, implemented with generators. ''' from operator import add, sub, mul, truediv as div, pow OPERATORS = [('+', add), ('-', sub), ('*', mul), ('/', div), ('^', pow)] START = [(str(i), 1, i) for i in [1,2,3]] def all_operators(stream): ''' Generate new values by combining the values in 'stream' in all the different ways possible. ''' for (exprn, length, value) in stream: for (symbol, op) in OPERATORS: for (exprn2, length2, value2) in stream: try: yield ('({0}){1}({2})'.format( exprn, symbol, exprn2), length + length2, op(value, value2)) except Exception as e: #print('Ignoring {}',format(e)) pass def repeat(generator, preproc=lambda x: x): ''' Make a generator 'eat its own tail', primed with 'start'. All output is kept and fed back into the generator as input. Note that memory use increases steadily. ''' def repeater(start): start = preproc(start) for value in start: yield value while True: finish = [] for value in generator(start): yield value finish.append(value) start = finish return repeater def value(elv): ''' Pick the value from an elv triplet. ''' (exprn, length, value) = elv return value def take(n): ''' Build a filter that takes the first n values from a stream. ''' def taker(stream, n=n): while n 0: yield next(stream) n -= 1 return taker def mkfilter(predicate): ''' Curry Python's filter function. ''' def myfilter(stream): return filter(lambda elv: predicate(value(elv)), stream) return myfilter def compose(*filters): ''' Compose several filters to give a new filter. (Is there a better way to write this?) ''' def composer(iter1, iter2): def composed(stream): for value in iter1(iter2(stream)): yield value return composed if len(filters) == 1: return filters[0] else: return composer(filters[0], compose(*filters[1:])) def summarise(stream): ''' Group values by value, keeping the shortest expression, then print everything. ''' exprns = {} lengths = {} for (exprn, length, value) in stream: if value not in exprns or length lengths[value]: exprns[value] = exprn lengths[value] = length values = [value for value in exprns if type(value) is int] for value in sorted(values): print('{0:5} = {1:20} (length {2})'.format( value, exprns[value], lengths[value])) if __name__ == '__main__': ints = mkfilter(lambda x: type(x) is int) small = mkfilter(lambda x: abs(x) 1000) # this gets very slow after 2 values #summarise(compose(take(2), # repeat(compose(ints, # all_operators)))(START)) # clipping values to below 1000 makes things much faster # note 200,000 below, 20,000 above! summarise(compose(take(20), repeat(compose(ints, small, all_operators)))(START)) # get to larger values faster by sorting in the repeat #sort = lambda x: sorted(x, key=value,
Re: code challenge: generate minimal expressions using only digits 1,2,3
This sounds kind of similar to a problem I posted to this list last year, you might find that thread gives you some ideas: http://mail.python.org/pipermail/python-list/2008-January/474071.html Dan -- http://mail.python.org/mailman/listinfo/python-list