www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - How to sort byCodeUnit.permutations.filter(...)

reply Uknown <sireeshkodali1 gmail.com> writes:
I wrote a small program for Project Euler problem 41 ( 
https://projecteuler.net/problem=41 ).

--- project_euler_41.d
void main()
{
	import math_common : primesLessThan;
	import std.stdio : writeln;
	import std.conv : parse;
	import std.algorithm : permutations, canFind, filter, each, sort;
	import std.utf : byCodeUnit;
	import std.range : assumeSorted;
	import std.array : array;

	auto primes = primesLessThan(9_999_999UL).assumeSorted;

	"1234567".byCodeUnit
		.permutations
		.filter!(a => primes.canFind(a.parse!uint))
		.each!(a => a.writeln);
}
---

The problem is this prints a list of numbers. The task requires 
only the largest, so the intuitive fix is to add `.array.sort[$ - 
1].writeln` in place of the `each`, but this prints an array of 
`1234567`s instead of the permutations. Does anyone know how to 
sort the filter result without modifying the individual results?
Jun 10 2018
parent reply Adam D. Ruppe <destructionator gmail.com> writes:
On Monday, 11 June 2018 at 04:06:44 UTC, Uknown wrote:

 The problem is this prints a list of numbers. The task requires 
 only the largest, so the intuitive fix


I would just pull the max out of it.

http://dpldocs.info/experimental-docs/std.algorithm.searching.maxElement.2.html
Jun 10 2018
parent reply Uknown <sireeshkodali1 gmail.com> writes:
On Monday, 11 June 2018 at 04:12:57 UTC, Adam D. Ruppe wrote:

 On Monday, 11 June 2018 at 04:06:44 UTC, Uknown wrote:

 The problem is this prints a list of numbers. The task 
 requires only the largest, so the intuitive fix


 I would just pull the max out of it.

 http://dpldocs.info/experimental-docs/std.algorithm.searching.maxElement.2.html


Thanks for your reply. I completely forgot about maxElement. I 
used it, but it prints 1234567, not the permutations. The same 
happens when using array. Why are the strings getting modified? 
The same happens with this:

"123".byCodeUnit.permutations.writeln;//[123, 213, 312, 132, 231, 
321]
"123".byCodeUnit.permutations.array.writeln;//[123, 123, 123, 
123, 123, 123]
Seems odd. Is this a bug or expected behaviour?
Jun 10 2018
parent reply Adam D. Ruppe <destructionator gmail.com> writes:
On Monday, 11 June 2018 at 04:39:54 UTC, Uknown wrote:

 Why are the strings getting modified?


I'm guessing it reuses a buffer as it iterates.


 "123".byCodeUnit.permutations.writeln;//[123, 213, 312, 132, 
 231, 321]


so here, it switches them, prints, switches, prints, switches, 
prints,e tc


 "123".byCodeUnit.permutations.array.writeln;//[123, 123, 123, 
 123, 123, 123]


but here it adds the same pointer to the array over and over so 
it all points to the same buffer.

I'm guessing. I don't actually know.


But hmmm... maybe throwing in a .dup would help. Really though, I 
personally would forget all the range pipeline stuff and write a 
simple loop.


         int largest = 0;
	foreach(part; "1234567".byCodeUnit.permutations) {
              auto asNumber = to!int(part);
              if(primes.canFind(asNumber)) {
                 if(asNumber > largest)
                    largest = asNumber;
              }
         }

         writeln(largest);


But, writing the simple loop did give me a solution to the 
pipeline too: map it to to!int before doing the rest, so you work 
with ints instead of with strings and char buffers:


	"1234567".byCodeUnit
		.permutations
                 .map!(to!int)
		.filter!(a => primes.canFind(a))
                 .maxElement


that should do it too.
Jun 12 2018
parent reply Uknown <sireeshkodali1 gmail.com> writes:
On Tuesday, 12 June 2018 at 14:21:48 UTC, Adam D. Ruppe wrote:

 On Monday, 11 June 2018 at 04:39:54 UTC, Uknown wrote:

 Why are the strings getting modified?


 I'm guessing it reuses a buffer as it iterates.


 "123".byCodeUnit.permutations.writeln;//[123, 213, 312, 132, 
 231, 321]


 [...]

 	"1234567".byCodeUnit
 		.permutations
                 .map!(to!int)
 		.filter!(a => primes.canFind(a))
                 .maxElement


 that should do it too.


I solved the problem by piping the output to `sort`, but your 
workaround is useful. I'll submit a bug report on this ASAP. 
Thanks for your help!
Jun 12 2018
parent Adam D. Ruppe <destructionator gmail.com> writes:
On Tuesday, 12 June 2018 at 15:16:25 UTC, Uknown wrote:

 I solved the problem by piping the output to `sort`


that works but is probably less efficient since sorting the whole 
thing just to get the one element is more work but eh.


 I'll submit a bug report on this ASAP.


I really don't think it is a bug, but perhaps the documentation 
could call it out.
Jun 12 2018