4 ms·

How about finding triples a<b<c<30 of pairwise relatively prime integers such that the sum of their cubes is a perfect cube? Here's a list comprehension in Pyt

How about finding triples a<b<c<30 of pairwise relatively prime integers such that the sum of their cubes is a perfect cube? Here's a list comprehension in Python (notice the weird syntax Python uses for "let x = y", namely "for x in [y]" :P): [(a,b,c) for a in range(1,30) for b in range(a+1,30) if gcd(a,b)==1 for c in range(b+1,30) if gcd(a,c)==1 and gcd(b,c)==1 for d in [int((a**3+b**3+c**3)**(1.0/3)+0.5)] if a**3+b**3+c**3==d**3] I doubt that would look any nicer with higher order functions. Specially if you want to get the same efficiency: notice how here we test that gcd(a,b)==1 as soon as possible. In general efficient comprehensions involve pushing any filtering as early as possible, so with higher order functions you get an alternation of filter with map/flatmap. Here's a (probably lame) attempt at a Python higher order version: flatmap = lambda f, l: [x for t in l for x in f(t)] flatmap(lambda a: flatmap(lambda b: flatmap(lambda c: (lambda d: [(a,b,c)] if a**3+b**3+c**3==d**3 else [])(int((a**3+b**3+c**3)**(1.0/3)+0.5)) if gcd(a,c)==1 and gcd(b,c)==1 else [], range(b+1, 30)) if gcd(a,b)==1 else [], range(a+1,30)), range(1,30)) Maybe it would look nicer with some filters thrown in instead of abusing flatmap of empty lists, but it would be longer since you definitely need a flatmap for a and b, and either a flatmap or map for c. I'd love to see a cleaner version with higher order function.

tel 7y ago
The same sensibilities apply in Haskell. These sort of longer, more structured problems are exactly when do notation comes out do a <- [1 .. 29] b <- [a+1 .. 29] guard $ gcd a b == 1 c <- [b+1 .. 29] guard $ gcd a c == 1 guard $ gcd b c == 1 let z = a ** 3 + b ** 3 + c ** 3 let d = z ** (1/3) + 0.5 guard $ z == d ** 3 return (a, b, c) Translation of this into HOFs is straightforward (the method guard uses helps tremendously), but it's not worth it most of the time. In Python where HOFs are so restricted it would be even worse.
- omaranto 7y ago
  I agree. Also as minor nitpick, I doubt your Haskell typechecks (haven't tried it): you forgot to take the floor of d.
  - tel 7y ago
    Probably, I didn't check it. I think the actual answer is messier: fromIntegral on a, b, and c.
omaranto 7y ago
Here's the flatmap version with better formatting: flatmap(lambda a: flatmap(lambda b: flatmap(lambda c: (lambda d: [(a,b,c)] if a**3+b**3+c**3==d**3 else [])( int((a**3+b**3+c**3)**(1.0/3)+0.5)) if gcd(a,c)==1 and gcd(b,c)==1 else [], range(b+1, 30)) if gcd(a,b)==1 else [], range(a+1,30)), range(1,30))
11235813213455 7y ago
the a:b notation for JS is still in proposal phase https://github.com/tc39/proposal-slice-notation/pull/32 https://github.com/tc39/proposal-slice-notation/pull/32, but I'll use it below to create ranges I don't understand your `+0.5`, I've written below the transcription for your description [...1:30].map(a => [...a+1:30].filter(b => gcd(a,b)==1).map(b => [...b+1:30].filter(c => gcd(a,c)==1 && gcd(b,c)==1 && Number.isInteger((a**3+b**3+c**3)**(1/3)) .map(c => [a, b, c]) ) ).flat(2) Or another equivalent way: [...1:30].flatMap(a => [...a+1:30].filter(b => gcd(a,b)==1).flatMap(b => [...b+1:30].filter(c => gcd(a,c)==1 && gcd(b,c)==1 && Number.isInteger((a**3+b**3+c**3)**(1/3))) .flatMap(c => [[a, b, c]]) Or another way (generating first all the triples): [...1:30].flatMap(a => [...a+1:30].flatMap(b => [...b+1:30].flatMap(c => [[a, b, c]]))) .filter(([a, b, c]) => gcd(a,b)==1 && gcd(a,c)==1 && gcd(b,c)==1 && Number.isInteger((a**3+b**3+c**3)**(1/3))) with https://github.com/tc39/proposal-iterator-helpers https://github.com/tc39/proposal-iterator-helpers, which would allow lazy evaluation, and make more sense than above (1:30).flatMap(a => (a+1:30).flatMap(b => (b+1:30).flatMap(c => [[a, b, c]]))) .filter(([a, b, c]) => gcd(a,b)==1 && gcd(a,c)==1 && gcd(b,c)==1 && Number.isInteger((a**3+b**3+c**3)**(1/3))) without the slice-notation, it's really ugly (hence the proposal in the first link) Array.from({length: 30},(_,a)=>a+1) .flatMap(a=>Array.from({length: 30-a-1},(_,b)=>a+b+1) .flatMap(b => Array.from({length: 30-b-1},(_,c)=>b+c+1).flatMap(c => [[a, b, c]]))) .filter(([a, b, c]) => gcd(a,b)==1 && gcd(a,c)==1 && gcd(b,c)==1 && Number.isInteger((a**3+b**3+c**3)**(1/3)))
- omaranto 7y ago
  I think this looks about as clean as I expected, I definitely like the look of the list comprehension better. (But of course, this is just a superficial syntactic matter: there is no essential difference.) Does JavaScript not come with a .flatmap or similar method? I'm not sure I like having to count the nesting to pass the appropriate number to .flat. Also building up a nested list and then flattening is less efficient than the comprehension which builds the flattened version directly. The +0.5 is to deal with floating point. Sadly the cube root isn't always exact enough to be an integer when it should, so I used floor(cube root + 0.5) to round to the near integer and then checked if that rounded integer really was the cube root. Have you tried running this? Is Number.isInteger lenient enough to actually find the solution?
gmiller123456 7y ago
How about finding triples a<b<c<30 of pairwise relatively prime integers such that the sum of their cubes is a perfect cube? I'd have to ask why you'd want to do that, it seems more like the problem was fit to the solution you wanted to write rather than to fulfill some piratical purpose. I'm not going to contest that there's a lot of business logic that gets more complicated than that, but they are not described so mathematically elegantly. There's no way you could tell what your code does, or why, without a comment at the top describing why. And you can do that with your example. But real business logic comes from the fact that Bob in accounting entered the wrong job codes for two months, but they can't be changed because they've already been archived, and Karen in sales told one of her customers the job code would default to the wrong value if they entered 42 as the compliance code, then the CEO said we should make that the default from now on, but we realized 2 years later that it messed some other stuff up and our manager had it changed without telling anyone, but Frank the DBA already added a flag for that, but it stopped getting updated when he left 6 months ago. In those real world situations, I doubt anyone would question that very long winded individual statements with a description for each one is way more easy to understand what's going on rather than the most concise code possible.
- omaranto 7y ago
  I am sure you are right about the real world, I wouldn't know anything about it. :) I'm a mathematician and I do use a computer whenever I can. In that domain the problem I gave is a reasonable toy model of the code I sometimes write. In particular mathematicians like comprehensions because, as I'm sure you are aware, programmers borrowed that notation from us.

tel 7y ago

The same sensibilities apply in Haskell. These sort of longer, more structured problems are exactly when do notation comes out do a <- [1 .. 29] b <- [a+1 .. 29] guard $ gcd a b == 1 c <- [b+1 .. 29] guard $ gcd a c == 1 guard $ gcd b c == 1 let z = a ** 3 + b ** 3 + c ** 3 let d = z ** (1/3) + 0.5 guard $ z == d ** 3 return (a, b, c) Translation of this into HOFs is straightforward (the method guard uses helps tremendously), but it's not worth it most of the time. In Python where HOFs are so restricted it would be even worse.

omaranto 7y ago
I agree. Also as minor nitpick, I doubt your Haskell typechecks (haven't tried it): you forgot to take the floor of d.
- tel 7y ago
  Probably, I didn't check it. I think the actual answer is messier: fromIntegral on a, b, and c.

omaranto 7y ago

Here's the flatmap version with better formatting: flatmap(lambda a: flatmap(lambda b: flatmap(lambda c: (lambda d: [(a,b,c)] if a**3+b**3+c**3==d**3 else [])( int((a**3+b**3+c**3)**(1.0/3)+0.5)) if gcd(a,c)==1 and gcd(b,c)==1 else [], range(b+1, 30)) if gcd(a,b)==1 else [], range(a+1,30)), range(1,30))

11235813213455 7y ago

the a:b notation for JS is still in proposal phase https://github.com/tc39/proposal-slice-notation/pull/32 https://github.com/tc39/proposal-slice-notation/pull/32, but I'll use it below to create ranges I don't understand your `+0.5`, I've written below the transcription for your description [...1:30].map(a => [...a+1:30].filter(b => gcd(a,b)==1).map(b => [...b+1:30].filter(c => gcd(a,c)==1 && gcd(b,c)==1 && Number.isInteger((a**3+b**3+c**3)**(1/3)) .map(c => [a, b, c]) ) ).flat(2) Or another equivalent way: [...1:30].flatMap(a => [...a+1:30].filter(b => gcd(a,b)==1).flatMap(b => [...b+1:30].filter(c => gcd(a,c)==1 && gcd(b,c)==1 && Number.isInteger((a**3+b**3+c**3)**(1/3))) .flatMap(c => [[a, b, c]]) Or another way (generating first all the triples): [...1:30].flatMap(a => [...a+1:30].flatMap(b => [...b+1:30].flatMap(c => [[a, b, c]]))) .filter(([a, b, c]) => gcd(a,b)==1 && gcd(a,c)==1 && gcd(b,c)==1 && Number.isInteger((a**3+b**3+c**3)**(1/3))) with https://github.com/tc39/proposal-iterator-helpers https://github.com/tc39/proposal-iterator-helpers, which would allow lazy evaluation, and make more sense than above (1:30).flatMap(a => (a+1:30).flatMap(b => (b+1:30).flatMap(c => [[a, b, c]]))) .filter(([a, b, c]) => gcd(a,b)==1 && gcd(a,c)==1 && gcd(b,c)==1 && Number.isInteger((a**3+b**3+c**3)**(1/3))) without the slice-notation, it's really ugly (hence the proposal in the first link) Array.from({length: 30},(_,a)=>a+1) .flatMap(a=>Array.from({length: 30-a-1},(_,b)=>a+b+1) .flatMap(b => Array.from({length: 30-b-1},(_,c)=>b+c+1).flatMap(c => [[a, b, c]]))) .filter(([a, b, c]) => gcd(a,b)==1 && gcd(a,c)==1 && gcd(b,c)==1 && Number.isInteger((a**3+b**3+c**3)**(1/3)))

omaranto 7y ago
I think this looks about as clean as I expected, I definitely like the look of the list comprehension better. (But of course, this is just a superficial syntactic matter: there is no essential difference.) Does JavaScript not come with a .flatmap or similar method? I'm not sure I like having to count the nesting to pass the appropriate number to .flat. Also building up a nested list and then flattening is less efficient than the comprehension which builds the flattened version directly. The +0.5 is to deal with floating point. Sadly the cube root isn't always exact enough to be an integer when it should, so I used floor(cube root + 0.5) to round to the near integer and then checked if that rounded integer really was the cube root. Have you tried running this? Is Number.isInteger lenient enough to actually find the solution?

gmiller123456 7y ago

How about finding triples a<b<c<30 of pairwise relatively prime integers such that the sum of their cubes is a perfect cube? I'd have to ask why you'd want to do that, it seems more like the problem was fit to the solution you wanted to write rather than to fulfill some piratical purpose. I'm not going to contest that there's a lot of business logic that gets more complicated than that, but they are not described so mathematically elegantly. There's no way you could tell what your code does, or why, without a comment at the top describing why. And you can do that with your example. But real business logic comes from the fact that Bob in accounting entered the wrong job codes for two months, but they can't be changed because they've already been archived, and Karen in sales told one of her customers the job code would default to the wrong value if they entered 42 as the compliance code, then the CEO said we should make that the default from now on, but we realized 2 years later that it messed some other stuff up and our manager had it changed without telling anyone, but Frank the DBA already added a flag for that, but it stopped getting updated when he left 6 months ago. In those real world situations, I doubt anyone would question that very long winded individual statements with a description for each one is way more easy to understand what's going on rather than the most concise code possible.

omaranto 7y ago
I am sure you are right about the real world, I wouldn't know anything about it. :) I'm a mathematician and I do use a computer whenever I can. In that domain the problem I gave is a reasonable toy model of the code I sometimes write. In particular mathematicians like comprehensions because, as I'm sure you are aware, programmers borrowed that notation from us.