## digitalmars.D - Elegant Project Euler Solution

- Leonhard Euler (20/20) Nov 03 Hi all,
- ixid (7/27) Nov 04 I'm not sure that using pre-rolled library functions is entirely
- Jonathan Marler (5/25) Nov 04 Very nice. The D standard library has alot of useful
- Soulsbane (2/6) Nov 06 So true. I've done it several times.
- Kreikey (6/6) Nov 11 That's a cool solution.

Hi all, Just wanted to share a very elegant solution for Project Euler, problem #24. This is the problem: A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are: 012 021 102 120 201 210 What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9? And my solution: ``` import std; void main() { iota(10).array.nthPermutation(999999).writeln(); } ``` Know thy standard library ;)

Nov 03

On Sunday, 3 November 2019 at 19:51:14 UTC, Leonhard Euler wrote:Hi all, Just wanted to share a very elegant solution for Project Euler, problem #24. This is the problem: A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are: 012 021 102 120 201 210 What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9? And my solution: ``` import std; void main() { iota(10).array.nthPermutation(999999).writeln(); } ``` Know thy standard library ;)I'm not sure that using pre-rolled library functions is entirely the point of Project Euler. To get the most out of it make your own functions for tasks that are core to the problem. The problems are clearly structured in a way that leads toward building your own library from puzzle to puzzle and realising when you can reuse functions from previous problems.

Nov 04

On Sunday, 3 November 2019 at 19:51:14 UTC, Leonhard Euler wrote:Hi all, Just wanted to share a very elegant solution for Project Euler, problem #24. This is the problem: A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are: 012 021 102 120 201 210 What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9? And my solution: ``` import std; void main() { iota(10).array.nthPermutation(999999).writeln(); } ``` Know thy standard library ;)Very nice. The D standard library has alot of useful functionality. I myself often make the mistake of not knowing what's in it and write my own implementation of things that are already available.

Nov 04

On Monday, 4 November 2019 at 18:18:53 UTC, Jonathan Marler wrote:On Sunday, 3 November 2019 at 19:51:14 UTC, Leonhard Euler I myself often make the mistake of not knowing what's in it and write my own implementation of things that are already available.So true. I've done it several times.

Nov 06

That's a cool solution. I noticed that this function isn't listed in the index page for std.algorithm: https://dlang.org/phobos/std_algorithm.html so it's a little hard to find. Apparently it's a bug in the documentation. Long-time lurker here, btw.

Nov 11

On Tuesday, 12 November 2019 at 01:25:02 UTC, Kreikey wrote:That's a cool solution. I noticed that this function isn't listed in the index page for std.algorithm: https://dlang.org/phobos/std_algorithm.html so it's a little hard to find. Apparently it's a bug in the documentation. Long-time lurker here, btw.Dig one layer deeper and you'll find it under https://dlang.org/phobos/std_algorithm_sorting.html

Nov 11

Yeah, I know. I found it after I returned to this thread. It was a bit confusing away from my computer cause I thought the OP must have been using the permutations() function, and I was like "wait a minute, how can that be correct when it doesn't generate them in lexicographical order." When I checked it again, I saw he used the nthPermutation() function and found it in the documentation. I'll file a bug report when I get around to it. When I solved Problem 24 myself a couple years ago, I wrote my own spaghetti code algorithm for it, as follows: Iterate backwards until you find the first item that's less than the previous Find the lowest item after that that's still greater than it Swap the two Sort the portion of the array after the index of the item in step 1 For some of the later problems, I just used the standard library's nextPermutation() function. But now that I looked at my old code again, I think I'm going to factor out my algorithm into my own nextPermutation function with the same semantics as the one in the standard library. Fun stuff...

Nov 12