Predicate with Lambda and String, is this possible?

[Pete Letkeman]

On another site I came across this programming challenge. While the challenge did not state that you had to use Lamdas or Predicates I suspect that it's possible, however my Java skills with regards to Lamdas and Predicates  are not there yet.

Challenge:
Given the following string

CodeRanch

Split the string into two different strings, one with all of the even numbered letters and one with the odd numbered letters to produce this

CdRnH oeac

This challenge is easy enough to do without Predicates and/or Lamdas but can this challenge be completed with Predicates and/or Lamdas?
I really don't know. So give this a shot if you are up for the challenge.

[Jesper de Jong]

Here is a solution. Not very elegant or efficient, but now the puzzle for you is to find out how it works.  

import static java.util.stream.Collectors.groupingBy;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.mapping;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

public class Challenge {

    static class Pair {
        private final int index;
        private final char ch;

        Pair(int index, char ch) {
            this.index = index;
            this.ch = ch;
        }

        String getCh() {
            return String.valueOf(ch);
        }

        boolean isOdd() {
            return index % 2 != 0;
        }
    }

    public static void main(String[] args) {
        String input = "CodeRanch";

        List<Pair> list = new ArrayList<>();
        for (int i = 0; i < input.length(); i++) {
            list.add(new Pair(i, input.charAt(i)));
        }

        Collection<String> output = list.stream()
                .collect(groupingBy(Pair::isOdd, mapping(Pair::getCh, joining())))
                .values();

        System.out.println(output);
    }
}

[Pete Letkeman]

Thanks Jesper de Jong. That does seem to be more then needed and not what I expected but I was able to get your code without without any problems. However like I said my Predicate & Lamda knowledge is not as good as others out there.
Here is my solution to this challenge which doesn't use Predicates and/or Lamdas.

import java.io.*;
import java.util.*;

public class Challenge {
	public static void main(String[] args) {
		String words = "CodeRanch";
		StringBuilder part1 = new StringBuilder();
		StringBuilder part2 = new StringBuilder();
		for (int j = 0; j < words.length() ; j++) {
			if (j % 2 == 0)	{
				part1.append(words.charAt(j));
			}
			else{
				part2.append(words.charAt(j));
			}
			if (j == words.length()-1) {
				System.out.println(part1.toString() + " " + part2.toString());
			}
        	}
    	}
}

[Jesper de Jong]

I would put line 17 after the for-loop, then you don't need the if-statement (line 16).

[Pete Letkeman]

I see what you are saying and that is the better solution. This is actually adapted from a challenge where you are given many string values that you have to get from within the program using System.in.

[Stephan van Hulst]

I think C# handles this much better, where most functions allow you to provide a lambda that has access to the index the element was encountered in.

If Java did this as well, you could have written the following:

Map<Boolean, String> partition = input.codePoints().collect(
  partitioningBy(
    (codePoint, index) -> index % 2 == 0,
    mapping(Challenge::codePointToString, joining())
  )
);

System.out.printf("%s %s%n", partition.get(true), partition.get(false));

[Pete Letkeman]

Thank you @Stephan van Hulst. That is more along the lines of what I was expecting. However as you said this doesn't work and as I've stated Lamdas and Predicates are trouble areas for me at this point in time. Which is why I copied this challenge from an other site and added the Lamda and Predicate requirements so that I could see how it's done using them.

[Jesper de Jong]

Stephan van Hulst wrote:I think C# handles this much better, where most functions allow you to provide a lambda that has access to the index the element was encountered in.

That was the point of my Pair class. Unfortunately, as far as I know, Java streams don't have such methods.

[Tobias Bachert]

If you don't mind iterating two times over the input string, you could use:

public enum Kind { EVEN, ODD; }
public static String extractByIndex(String s, Kind kind) {
    // Java8 version:
    // return IntStream.range(0, s.length()).filter(i -> (i & 1) == kind.ordinal()).map(s::charAt)
    //        .collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append).toString();
    // Without filter:
    // return IntStream.range(0, s.length() + 1 - kind.ordinal() >>> 1).map(i -> (i << 1) + kind.ordinal()).map(s::charAt)
    //         .collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append).toString();
    return IntStream.iterate(kind.ordinal(), i -> i < s.length(), i -> i + 2).map(s::charAt)
            .collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append).toString();
}
public static void main(String[] args) {
    String s = "CodeRanch";
    System.out.println(extractByIndex(s, EVEN));
    System.out.println(extractByIndex(s, ODD));
}

Alternatively to process the string in one iteration:

Map<Boolean, String> map = IntStream.range(0, s.length()).boxed().collect(partitioningBy(i -> (i & 1) != 0,
        of(StringBuilder::new, (sb, i) -> sb.append(s.charAt(i)), StringBuilder::append, StringBuilder::toString)));

or, if you want to avoid boxing of the indices:

StringBuilder[] evenOdd = IntStream.range(0, s.length()).collect(
        () -> new StringBuilder[] {new StringBuilder(), new StringBuilder()},
        (sb, i) -> sb[i & 1].append(s.charAt(i)),
        (left, right) -> { left[0].append(right[0]); left[1].append(right[1]); });

[Piet Souris]

In cases where an index is playing a role, you can use an IntStream as a sort of workaround for Stephan's index.
For instance:

public static <S, T> Map<S, List<T>> group(List<T> list, Function<Integer, S> mapper) {
    return IntStream.range(0, list.size())
            .boxed()
            .collect(Collectors.groupingBy(
                    mapper::apply,
                    Collectors.mapping(list::get, Collectors.toList())
            )
    );
}

If you have a method that converts a String to, say, a List<Character>, and a Function<Integer, Boolean>, then you almost have your result. The limitation is that you need a Collection for which an index is defined, like a List.

String s = "123456789";
Function<Integer, Integer> modulo3 = i -> i % 3;
Map<Integer, List<Character>> map = group(convert(s), modulo3);
System.out.println(map);

[Stephan van Hulst]

The problem with that approach is that it performs in quadratic time for sequential lists.

[Piet Souris]

Yep.

But that is a general problem if the get method is O(n). If that could be a problem (I use say LinkedLists only for Queues), then I would not use any streams, but a simple forEach, using a counter if needed. That is a lot less fun to write, though. But then again, writing it in a simple pre java 8 way takes O(1) time, getting it working with Streams and lambda's takes O(n^2) time.

Edit: on second thoughts: that quadratic time is indeed a very big disadvantage. Having to say that this method is no good for some types of Lists, hmm... to translate it literally from Dutch to English: "shamered on your jaws".
So, no stream, a simple forEach with a counter and a Predicate to make a partition of the List, as you and others showed. And for me a reminder that a List s not always an ArrayList.

Thanks for the remark!

[Stephan van Hulst]

I don't understand why you would avoid streams for sequential lists. The problem is using the get() method inside loops and higher level functions. Don't do it. Use the tools as they're supposed to be used. You can solve this problem on sequential lists using streams in linear time exactly as Jesper has shown. I once wrote in the Java 8 forum how you can expand Stream with a zip() function. You can then perform this operation in one single pass through a stream, regardless of the underlying type:

Map<boolean, String> getEvenAndOddIndexedCodePoints(String input) {
  final class CodePointAndIndex {

    private final int codePoint;
    private final int index;

    CodePointAndIndex(int codePoint, int index) {
      this.codePoint = codePoint;
      this.index = index;
    }

    boolean isIndexEven() {
      return index % 2 == 0;
    }

    String codePointToString() {
      return new StringBuilder().appendCodePoint(codePoint).toString();
    }
  }

  return ExtendedStream.extend(input.codePoints())
    .zip(ExtendedIntStream.naturalNumbers().boxed(), CodePointAndIndex::new)
    .collect(partitioningBy(
      CodePointAndIndex::isIndexEven,
      mapping(CodePointAndIndex::codePointToString, joining())
    ));
}

[Piet Souris]

I can't remember having seen your zip method, but I saw your takewhile method using Streams. Now, that was complex. I once wrote a zip method using a simple forEach, and that took about a minute to write.
I like using streams, but I try to make a balance between complexity and elegance of code, as far as my knowledge and experiece let me. And your latest code is ugly to look at, IMHO.

[Stephan van Hulst]

Yes, implementing high level functions on streams is very complex, and the code is not easy to read. However, once you've done it properly you have a very useful general purpose operation that performs efficiently and lazily. You can't implement a zip() method with a for-loop and have it perform lazily (which is essential when zipping with infinite streams, such as naturalNumbers()).

Elegance is in the eye of the beholder. I don't find it elegant to iterate over a collection more than once, if the first time will do. It also depends on what you're used to. I agree that many people who are used to procedural code will find my stream operation difficult to read, but it reads very naturally if you're used to functional code.

Note that I would solve the original problem with a simple for-loop. The challenge however was to do it with streams.

[Stephan van Hulst]

For fun and profit, here's how this looks in Haskell:
evenAndOddIndexed = mapPair snd . partition (even . fst) . zip [0..]    where mapPair f (x,y) = (map f x, map f y)
Read it like this: Whatever the input is, apply the following functions to it:

zip [0..]

partition (even . fst)

mapPair snd

So, first zip the input (which is a list of characters) with the list of natural numbers, resulting in a list of tuples: [(num,char)].

Then, partition the list of tuples according to the predicate (even . fst), which means: "Take the first element of the tuple and see if it's an even number". The result of this operation is a tuple containining a list of tuples that matched the predicate and a list of tuples that didn't: ([(num,char)], [(num,char)]).

Finally, map the two lists to equivalent lists containing only the second element, being the char. So you end up with ([char], [char]).

In Haskell [char] is the same thing as a string.

[Liutauras Vilda]

Pete, Cowgratulations, your topic has been published in our July's Edition Journal.

[Sean Corfield]

Seeing a Haskell solution, I thought I'd post a Clojure version since it runs on the JVM and we have a Clojure forum here...

(defn split-string [s]
  (reduce (fn [[evens odds] [e o]] [(str evens e) (str odds o)])
          ["" ""]
          (partition-all 2 s)))

(split-string "CodeRanch")
;;=> ["CdRnh" "oeac"]

The partition-all call turns the string into a list of pairs of characters. The function passed to reduce takes a pair of strings (evens and odds) and a pair of characters, and it returns a pair of strings -- with the new characters appended. The reduction starts with a pair of empty strings.

If you're concerned about the repeated string appending, an alternative is to start with a pair of empty vectors -- [[] []] -- and use conj instead of str which conjoins the new element onto the end of each vector as O(1) -- by virtue of Clojure's vector performance guarantees -- so the reduction produces a pair of vectors (of characters) and then you could (map (partial apply str) ...) to that to perform a single string append on each vector at the end.

[Sean Corfield]

p.s. if you have an even length string, you can do something much shorter in Clojure: (apply map str (partition-all 2 s))

The reason this doesn't work with odd length strings is that partition-all will produce several pairs followed by a single element and map stops consuming the arguments when the shortest one runs out.