Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #31619

Re: Easy exhaustive search with Java 8 Streams

Cross-posted to 2 groups.

Show all headers | View raw

Hi,

How fast is this? Any figures?

Bye

Sebastian schrieb:
> Hello there,
>
> I have just been reading this post by Mark Dominus on Haskell:
> http://blog.plover.com/prog/haskell/monad-search.html
>
> Mark discusses how the Haskell list monad can be used to hide some of
> the glue code involved in doing exhaustive searches. Java 8 Streams,
> which are somewhat similar to Haskell lists in also being monadic, lend
> themselves to the same style of coding. The example is the well-known
> crypt-arithmetics puzzle of SEND + MORE = MONEY.
>
> I quite liked Mark's post, and so I have ported his code to Java 8,
> which I'd like to share:
>
>           List<Integer> DIGITS =
>              unmodifiableList(asList(0,1,2,3,4,5,6,7,8,9));
>
>           List<String> solutions =
>              remove(DIGITS, 0).stream().flatMap( s ->
>              remove(DIGITS, s).stream().flatMap( e ->
>              remove(DIGITS, s, e).stream().flatMap( n ->
>              remove(DIGITS, s, e, n).stream().flatMap( d ->
>              remove(DIGITS, 0, s, e, n, d).stream().flatMap( m ->
>              remove(DIGITS, s, e, n, d, m).stream().flatMap( o ->
>              remove(DIGITS, s, e, n, d, m, o).stream().flatMap( r ->
>              remove(DIGITS, s, e, n, d, m, o, r).stream().flatMap( y ->
>                  { int send = toNumber(s, e, n, d);
>                    int more = toNumber(m, o, r, e);
>                    int money = toNumber(m, o, n, e, y);
>                    return send + more == money
>                       ? Stream.of(solution(send, more, money))
>                       : Stream.empty();
>                  }
>              ))))))))
>              .map(Object::toString)
>              .collect(toList());
>
>           System.out.println(solutions);
>
> The minor optimization of not unncecessarily recomputing "send" and
> "more" is left out for the sake of readability. The methods remove() -
> which implements list difference - toNumber(), and solution() have
> simple implementations. Of these, toNumber() is again a lot like the
> corresponding Haskell code:
>
>           Stream.of(digits).reduce((x,y) -> 10*x + y).get();
>
> solution() here returns a String because Java does not have tuples. The
> call to map() is there to make the compiler happy, but is functionally
> the identity.
>
> Too bad that in Java one must have the nested method calls, but the
> formatting goes some way to hide this. All in all, I think this is quite
> nice.
>
> -- Sebastian
>

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Easy exhaustive search with Java 8 Streams Sebastian <news@seyweiler.dyndns.org> - 2015-04-27 20:32 +0200
  Re: Easy exhaustive search with Java 8 Streams Jan Burse <janburse@fastmail.fm> - 2015-04-28 12:35 +0200
    Re: Easy exhaustive search with Java 8 Streams Sebastian <news@seyweiler.dyndns.org> - 2015-04-29 11:12 +0200
      Re: Easy exhaustive search with Java 8 Streams j4n bur53 <janburse@fastmail.fm> - 2015-04-30 09:02 +0200
  Re: Easy exhaustive search with Java 8 Streams Sebastian <news@seyweiler.dyndns.org> - 2015-04-29 09:45 +0200

csiph-web