Pipeline of Operations

Problem

The first line has the numbers. Every next line is one operation applied to all numbers, in the order given: add x (add x to each), mul x (multiply each by x), even (keep only even numbers), gt x (keep numbers greater than x) or lt x (keep numbers smaller than x). Print the numbers that are left (empty if none). Build the pipeline as a list of small functions, and push each number through the whole pipeline (lazy style).

Constraints

  • 1 <= numbers <= 10^4
  • 1 <= operations <= 50
  • values stay below 10^12

Examples

Input

1 2 3 4 5 6
add 1
even
mul 10

Output

20 40 60

Solutions

Best approachTime O(n * stages)Space O(1) extra

Each operation is a small function and the pipeline is the list of these functions. Lazy evaluation sends every number through all stages one after the other, so no temporary lists are created.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process lines.
 * Input   : First line numbers, then one operation per line.
 * Output  : The numbers left, or empty.
 * Approach: Lazy pipeline.
 * Time    : O(n * stages)
 * Space   : O(1) extra
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static String solve(String[] lines) {
        // Step 1: Read the numbers into a stream. Streams are lazy: each number goes through all steps before the next number starts.
        java.util.stream.LongStream stream = java.util.Arrays.stream(lines[0].split(" ")).mapToLong(Long::parseLong);
        // Step 2: Add one stage for each operation line.
        for (int i = 1; i < lines.length; i++) {
            String[] part = lines[i].split(" ");
            final long x = part.length > 1 ? Long.parseLong(part[1]) : 0;
            if (part[0].equals("add")) {
                stream = stream.map(v -> v + x);
            } else if (part[0].equals("mul")) {
                stream = stream.map(v -> v * x);
            } else if (part[0].equals("even")) {
                stream = stream.filter(v -> v % 2 == 0);
            } else if (part[0].equals("gt")) {
                stream = stream.filter(v -> v > x);
            } else {
                stream = stream.filter(v -> v < x);
            }
        }
        String result = stream.mapToObj(String::valueOf).collect(java.util.stream.Collectors.joining(" "));
        return result.isEmpty() ? "empty" : result;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        java.util.List<String> all = new java.util.ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (!line.isEmpty()) {
                all.add(line);
            }
        }
        String[] lines = all.toArray(new String[0]);
        System.out.println(solve(lines));
    }
}
Hints (2)
  1. Why must x be frozen for each stage?
  2. When does a number leave the pipeline?