Generate outputs for images and pipelines

You are given m input images and n processing pipelines.

• Each pipeline is an ordered list of k operations (e.g., resize, rotate, crop, blur, color transform).
• Applying a pipeline to an image produces a new output image.

Task

Write a function/program that produces m × n output images by applying every pipeline to every input image.

Requirements

• Each output should be associated with (image_id, pipeline_id).
• The pipeline operations must be applied in order.
• Assume images are stored as file paths; pipelines are provided as callable operations.
• Your implementation should be structured so it can be parallelized easily (e.g., avoid unnecessary repeated work such as reading the same image multiple times).

Input/Output (one reasonable interface)

• Input:
  • image_paths: List[str] (size m)
  • pipelines: List[List[Callable[[Image], Image]]] (size n, each of length k)
  • output_dir: str
• Output:
  • Write m*n images to output_dir with deterministic names like img{idx}_pipe{j}.png, or return a list of output file paths.

Constraints (assume)

• m, n can be large enough that runtime and I/O efficiency matter.
• Operations may be CPU-bound; image decoding/encoding is I/O-bound.

Follow-up discussion (no need to implement)

• How would you scale this for large m and n?
• What parallelization strategy would you choose and why?

Generate Outputs for Images and Pipelines

Apply a set of integer pipelines to a set of images and produce one named output for every (image, pipeline) pair.

This is an interview-friendly version of an image-processing problem: instead of real image objects, each image path maps to a single integer value in image_store. Each pipeline is a list of operations applied in order, left to right.

What to implement

def solution(image_paths, image_store, pipelines, output_dir):
    ...

For every image index i (over image_paths) and every pipeline index j (over pipelines), run pipeline j on image i's value and emit one result.

Input

• image_paths — list of image-path strings. The value of image i is image_store[image_paths[i]].
• image_store — dict mapping each image path to its integer value. Every path in image_paths is present as a key.
• pipelines — list of pipelines. Each pipeline is a list of operation tuples (a pipeline may be empty).
• output_dir — string used as the directory prefix for output file names.

Operations

Each operation transforms the current integer value v:

• ('ADD', x) → v + x
• ('SUB', x) → v - x
• ('MUL', x) → v * x
• ('NEG',) → -v

Operations within a pipeline are applied sequentially in the order they appear. An empty pipeline performs no operations and leaves the value unchanged (identity).

Output

Return a list of (output_path, result_value) tuples.

For image index i and pipeline index j:

• result_value is image i's value after running pipeline j's operations in order.
• output_path is built from output_dir plus the file name img{i}_pipe{j}.png:
  • Strip any trailing / characters from output_dir, then join with /. Example: output_dir = 'tmp/' (or 'tmp') → tmp/img0_pipe0.png.
  • If output_dir is the empty string '' (or becomes empty after stripping trailing slashes), there is no leading separator → img0_pipe0.png.

Ordering: results are ordered first by image index i, then by pipeline index j (image 0 with every pipeline, then image 1 with every pipeline, and so on).

The returned list therefore has exactly len(image_paths) * len(pipelines) entries.

Notes & edge cases

• If the same image path appears multiple times in image_paths, an output is still produced for each position (each index i is independent).
• An empty image_paths or empty pipelines yields an empty result list.
• Your approach should avoid unnecessary repeated work — e.g. don't reload the same image path more than once, and don't re-run a pipeline's operation list from scratch for every image.

Constraints

• 0 <= len(image_paths), 0 <= len(pipelines)
• A pipeline may be empty.
• All paths in image_paths exist in image_store.
• The total number of operations across all pipelines is at most 2 * 10^5.
• The returned list has exactly len(image_paths) * len(pipelines) entries, so any solution must spend at least O(m * n) time to build the output (where m = len(image_paths), n = len(pipelines)).

Example

image_paths = ['a.png', 'b.png']
image_store = {'a.png': 2, 'b.png': 5}
pipelines   = [[('ADD', 3), ('MUL', 2)], [('NEG',), ('SUB', 4)]]
output_dir  = 'out'

# pipeline 0 on 2: (2+3)*2 = 10 ; pipeline 1 on 2: -(2)-4 = -6
# pipeline 0 on 5: (5+3)*2 = 16 ; pipeline 1 on 5: -(5)-4 = -9
=> [('out/img0_pipe0.png', 10), ('out/img0_pipe1.png', -6),
    ('out/img1_pipe0.png', 16), ('out/img1_pipe1.png', -9)]

Hints

1. Each supported operation keeps the form a*x + b. Try compressing each whole pipeline into one pair (a, b) before processing the images.
2. If the same path appears more than once in image_paths, cache its loaded value so you do not conceptually decode it multiple times.

Approach

Key idea: every pipeline is an affine function. Each operation only ever scales or shifts the value, so the whole pipeline collapses into a single linear map v -> a*v + b. We can compute (a, b) once per pipeline and then apply it in O(1) for every image, instead of replaying the operation list for each image.

Building the transforms. For each pipeline we start at the identity (a, b) = (1, 0) and fold in operations:

• ADD x / SUB x: shift only, so b += x / b -= x.
• MUL x: scales the current expression a*v + b, so both coefficients scale: a *= x; b *= x.
• NEG: negates the whole expression: a = -a; b = -b.

An empty pipeline stays (1, 0), correctly acting as identity. Unknown ops raise ValueError.

Producing outputs. loaded caches each path's value the first time it's seen, so a repeated path isn't "reloaded" (it's still emitted once per position, satisfying the multiplicity rule). base = output_dir.rstrip('/') normalizes a trailing slash; when base is empty the path has no leading /. The nested loop walks images (outer i) then pipelines (inner j), so results come out ordered by image index then pipeline index, and each value is just a*value + b.

Why correct: affine maps are closed under composition, and the fold above is exactly that composition applied left-to-right in pipeline order, so a*value + b equals running the raw operations sequentially. The cartesian-product loop yields exactly len(image_paths) * len(pipelines) tuples with the required img{i}_pipe{j}.png names and ordering.

• Time complexity: O(P + mn), where P is the total number of operations across all pipelines (≤ 210^5), m = len(image_paths), and n = len(pipelines). Building transforms is O(P); the output double loop is O(mn), which is required since the result has exactly mn entries.
• Space complexity: O(u + n) auxiliary space (excluding the returned list): O(n) for the precomputed transforms and O(u) for the loaded cache, where u is the number of distinct image paths.