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

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

Easy exhaustive search with Java 8 Streams

Show all headers | View raw

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 — 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