www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Elegant Project Euler Solution

reply Leonhard Euler <leon example.org> writes:
Hi all,
Just wanted to share a very elegant solution for Project Euler, 


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 2019
next sibling parent ixid <adamsibson gmail.com> writes:
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, 


 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 2019
prev sibling next sibling parent reply Jonathan Marler <johnnymarler gmail.com> writes:
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, 


 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 2019
parent Soulsbane <paul acheronsoft.com> writes:
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 2019
prev sibling parent reply Kreikey <rick.kreikebaum gmail.com> writes:
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 2019
parent reply Lurker1 <lurker1 lurking.org> writes:
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 2019
parent Kreikey <rick.kreikebaum gmail.com> writes:
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 2019