Pattern visualizer
Merge Triplets to Form Target
A merge takes the elementwise maximum, so every value it touches either stays put or climbs — nothing ever comes back down. That one-way property decides the whole problem. Any triplet holding a value larger than the target in some slot is poison: merge it even once and that slot is permanently too big, so it can be deleted from consideration entirely. Every remaining triplet is safe to merge, because none of its values can push a slot past the target. Merging all of the safe ones together is therefore never worse than merging some of them, and the result in each slot is simply the largest safe value there. So the answer is yes exactly when each of the three slots is matched exactly by at least one safe triplet — a single pass, no choices, no backtracking. Animated on: triplets = (2,5,3),(5,8,1),(1,6,4),(9,1,1),(5,2,7),(3,6,7),(4,6,8), target = (5,6,7) — repeatedly replace a triplet with the elementwise max of two triplets; can (5,6,7) be produced?.
Drop the overshooters, OR the exact hits of the rest
Target is (5,6,7). A merge replaces a triplet with the elementwise MAX of two, so a value can only ever climb — one slot that already sits above the target can never be brought back down. That splits the work in two: throw away every triplet that overshoots anywhere, then ask whether the survivors between them hit (5,6,7) exactly in all three slots. Covered so far: nothing yet.
1FUNCTION mergeTriplets(triplets, target)2 found <- [FALSE, FALSE, FALSE]3 FOR i <- 0 TO LENGTH(triplets) - 14 IF triplets[i][0] > target[0] OR triplets[i][1] > target[1] OR triplets[i][2] > target[2]5 CONTINUE6 FOR k <- 0 TO 27 IF triplets[i][k] = target[k]8 found[k] <- TRUE9 RETURN found[0] AND found[1] AND found[2]
← / → step · space play · Home restart