Celestial Pattern Synthesis

Published at05 Jan 2026

Like2

You are given a target mural string and a list of reusable snippets. Each snippet has both some text and a cost. The goal is to build the mural exactly, from left to right, with the smallest total cost.

If several snippets can match the current position, you are free to choose any of them, and you may reuse the same snippet multiple times. Besides the minimum total cost, you also need to return one valid sequence of snippet indices that achieves that cost.

For example, if mural = "ababa" and snippets = [("ab",3),("aba",4),("ba",2)], one minimum-cost answer is cost = 6, sequence = [2,3]. That means use snippet 2 first, then snippet 3. If no sequence of snippets can build the mural exactly, the answer should be cost = -1, sequence = [].

So the task is to cover the full mural with matching snippets while minimizing the total cost and keeping enough information to reconstruct one cheapest sequence.

Example Input & Output

Example 1

Input

mural = "ababa", snippets = [("ab",3),("aba",4),("ba",2)]

Output

cost = 6, sequence = [2, 3]

Explanation

Example 1: Minimal cost solution using snippets at indices 2 and 3

Example 2

Input

mural = "aaaa", snippets = [("aa",3),("a",2)]

Output

cost = 6, sequence = [2, 2, 2, 2]

Explanation

Example 2: Using snippet at index 2 four times

Example 3

Input

mural = "abc", snippets = [("ac",5),("bc",4)]

Output

cost = -1, sequence = []

Explanation

Example 3: No valid solution exists

Algorithm Flow

Recommendation Algorithm Flow for Celestial Pattern Synthesis

Solution Approach

This is a weighted version of word break, so dynamic programming fits nicely. Let dp[i] mean the minimum cost needed to build the suffix starting at position i in the mural.

At position i, try every snippet that matches the mural starting there. If a snippet of length len matches, then it can transition to:

dp[i] = min(dp[i], snippetCost + dp[i + len])

The base case is dp[mural.length] = 0, because once we reach the end, no more cost is needed.

To reconstruct the sequence, we store which snippet gave the best answer at each position. After the DP finishes, we can walk forward from index 0 and follow those saved choices.

If dp[0] never becomes finite, then the mural cannot be built and we return -1 with an empty sequence. Otherwise, dp[0] is the minimum cost, and the recorded choices give us one optimal snippet sequence.

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

import java.util.*;

class Solution {
    public Object[] celestial_pattern_synthesis(String mural, List<Object[]> snippets) {
        if (mural == null || mural.isEmpty()) return new Object[]{0L, new ArrayList<Integer>()};
        int N = mural.length();
        int M = snippets.size();
        List<Occ>[] occurrences = new List[M];
        for (int i = 0; i < M; i++) {
            occurrences[i] = new ArrayList<>();
            String pat = (String) snippets.get(i)[0];
            int start = 0;
            while ((start = mural.indexOf(pat, start)) != -1) {
                occurrences[i].add(new Occ(start, start + pat.length()));
                start++;
            }
        }
        long[] dp = new long[N + 1];
        Arrays.fill(dp, Long.MAX_VALUE);
        dp[N] = 0;
        List<Match>[] byEnd = new List[N + 1];
        for (int i = 0; i <= N; i++) byEnd[i] = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            int cost = ((Number) snippets.get(i)[1]).intValue();
            for (Occ occ : occurrences[i]) byEnd[occ.end].add(new Match(occ.start, cost));
        }
        PriorityQueue<PQItem> pq = new PriorityQueue<>((a, b) -> Long.compare(a.val, b.val));
        for (int i = N; i > 0; i--) {
            if (dp[i] != Long.MAX_VALUE) {
                for (Match m : byEnd[i]) pq.add(new PQItem(m.cost + dp[i], m.start));
            }
            while (!pq.isEmpty() && pq.peek().start > i - 1) pq.poll();
            if (!pq.isEmpty()) dp[i - 1] = pq.peek().val;
        }
        if (dp[0] == Long.MAX_VALUE) return new Object[]{-1L, new ArrayList<Integer>()};
        List<Integer> resSeq = new ArrayList<>();
        int curr = 0;
        while (curr < N) {
            int bestIdx = Integer.MAX_VALUE;
            int bestEnd = -1;
            for (int j = 0; j < M; j++) {
                int cost = ((Number) snippets.get(j)[1]).intValue();
                int idx = j + 1;
                if (idx > bestIdx) continue;
                for (Occ occ : occurrences[j]) {
                    if (occ.start <= curr && occ.end > curr) {
                        if (dp[occ.end] != Long.MAX_VALUE && cost + dp[occ.end] == dp[curr]) {
                            if (idx < bestIdx) {
                                bestIdx = idx;
                                bestEnd = occ.end;
                            } else {
                                bestEnd = Math.max(bestEnd, occ.end);
                            }
                            break;
                        }
                    }
                }
            }
            resSeq.add(bestIdx);
            curr = bestEnd;
        }
        return new Object[]{dp[0], resSeq};
    }
    static class Occ { int start, end; Occ(int s, int e) { start = s; end = e; } }
    static class Match { int start, cost; Match(int s, int c) { start = s; cost = c; } }
    static class PQItem { long val; int start; PQItem(long v, int s) { val = v; start = s; } }
}

javascript

function celestial_pattern_synthesis(mural, snippets) {
    if (!mural) return [0, []];
    const N = mural.length, M = snippets.length;
    const occ = Array.from({ length: M }, () => []);
    for (let i = 0; i < M; i++) {
        const pat = snippets[i][0];
        let start = 0;
        while (true) {
            const pos = mural.indexOf(pat, start);
            if (pos === -1) break;
            occ[i].push([pos, pos + pat.length]);
            start = pos + 1;
        }
    }
    const dp = new Array(N + 1).fill(Infinity);
    dp[N] = 0;
    const pq = [], byEnd = Array.from({ length: N + 1 }, () => []);
    for (let i = 0; i < M; i++) {
        const cost = snippets[i][1];
        for (const [start, end] of occ[i]) byEnd[end].push([start, cost]);
    }
    for (let i = N; i > 0; i--) {
        if (dp[i] !== Infinity) {
            for (const [start, cost] of byEnd[i]) {
                pq.push({ val: cost + dp[i], start });
            }
            pq.sort((a, b) => a.val - b.val);
        }
        while (pq.length > 0 && pq[0].start > i - 1) pq.shift();
        if (pq.length > 0) dp[i - 1] = pq[0].val;
    }
    if (dp[0] === Infinity) return [-1, []];
    const sequence = [];
    let curr = 0;
    while (curr < N) {
        let bestIdx = Infinity, bestEnd = -1;
        for (let j = 0; j < M; j++) {
            const cost = snippets[j][1], idx = j + 1;
            if (idx > bestIdx) continue;
            for (const [start, end] of occ[j]) {
                if (start <= curr && end > curr) {
                    if (dp[end] !== Infinity && cost + dp[end] === dp[curr]) {
                        if (idx < bestIdx) {
                            bestIdx = idx;
                            bestEnd = end;
                        } else {
                            bestEnd = Math.max(bestEnd, end);
                        }
                        break;
                    }
                }
            }
        }
        sequence.push(bestIdx);
        curr = bestEnd;
    }
    return [dp[0], sequence];
}

php

function celestial_pattern_synthesis($mural, $snippets) {
    $N = strlen($mural);
    $matchesByEnd = array_fill(0, $N + 1, []);
    foreach ($snippets as $i => $snippet) {
        $pat = $snippet[0]; $cost = $snippet[1]; $len = strlen($pat);
        $start = 0;
        while (($pos = strpos($mural, $pat, $start)) !== false) {
            $matchesByEnd[$pos + $len][] = ["start" => $pos, "cost" => $cost, "idx" => $i + 1];
            $start = $pos + 1;
        }
    }
    
    $dpBack = array_fill(0, $N + 1, INF);
    $dpBack[$N] = 0;
    $pq = [];
    
    for ($i = $N; $i > 0; $i--) {
        foreach ($matchesByEnd[$i] as $m) {
            if ($dpBack[$i] !== INF) {
                $pq[] = ["val" => $m["cost"] + $dpBack[$i], "start" => $m["start"]];
            }
        }
        usort($pq, function($a, $b) { return $a["val"] <=> $b["val"]; });
        while (!empty($pq) && $pq[0]["start"] > $i - 1) {
            array_shift($pq);
        }
        if (!empty($pq)) {
            $dpBack[$i - 1] = $pq[0]["val"];
        }
    }
    
    if ($dpBack[0] === INF) return [-1, []];
    
    $sequence = [];
    $curr = 0;
    while ($curr < $N) {
        $bestIdx = INF;
        $bestK = -1;
        foreach ($snippets as $i => $snippet) {
            list($pat, $cost) = $snippet;
            $idx = $i + 1;
            $sSearch = max(0, $curr - strlen($pat) + 1);
            while (($pos = strpos($mural, $pat, $sSearch)) !== false) {
                if ($pos > $curr) break;
                $k = $pos + strlen($pat);
                if ($k > $curr && $dpBack[$k] !== INF && $cost + $dpBack[$k] == $dpBack[$curr]) {
                    if ($idx < $bestIdx) {
                        $bestIdx = $idx;
                        $bestK = $k;
                    } else if ($idx == $bestIdx) {
                        $bestK = max($bestK, $k);
                    }
                }
                $sSearch = $pos + 1;
            }
        }
        $sequence[] = $bestIdx;
        $curr = $bestK;
    }
    return [$dpBack[0], $sequence];
}

python

from typing import List, Tuple
import heapq

def celestial_pattern_synthesis(mural: str, snippets: List[Tuple[str, int]]) -> Tuple[int, List[int]]:
    if not mural: return (0, [])
    N = len(mural)
    M = len(snippets)
    occ = [[] for _ in range(M)]
    for i in range(M):
        pat, cost = snippets[i][0], snippets[i][1]
        start = 0
        while True:
            pos = mural.find(pat, start)
            if pos == -1: break
            occ[i].append((pos, pos + len(pat)))
            start = pos + 1
    dp = [float('inf')] * (N + 1)
    dp[N] = 0
    pq = []
    by_end = [[] for _ in range(N + 1)]
    for i in range(M):
        cost = snippets[i][1]
        for start, end in occ[i]:
            by_end[end].append((start, cost))
    for i in range(N, 0, -1):
        if dp[i] != float('inf'):
            for start, cost in by_end[i]:
                heapq.heappush(pq, (cost + dp[i], start))
        while pq and pq[0][1] > i - 1:
            heapq.heappop(pq)
        if pq:
            dp[i-1] = pq[0][0]
    if dp[0] == float('inf'): return (-1, [])
    res_seq = []
    curr = 0
    while curr < N:
        best_idx, best_end = float('inf'), -1
        for j in range(M):
            cost, idx = snippets[j][1], j + 1
            if idx > best_idx: continue
            for start, end in occ[j]:
                if start <= curr < end:
                    if dp[end] != float('inf') and cost + dp[end] == dp[curr]:
                        if idx < best_idx:
                            best_idx, best_end = idx, end
                        else:
                            best_end = max(best_end, end)
                        break
        res_seq.append(best_idx)
        curr = best_end
    return (int(dp[0]), res_seq)

rust

pub fn celestial_pattern_synthesis(mural: &str, snippets: &[(String, i64)]) -> (i64, Vec<i32>) {
    if mural.is_empty() { return (0, Vec::new()); }
    let n = mural.len();
    let m_count = snippets.len();
    let mut occ = vec![vec![]; m_count];
    for (i, (pat, _)) in snippets.iter().enumerate() {
        let mut start = 0;
        while let Some(pos) = mural[start..].find(pat) {
            let actual_pos = start + pos;
            occ[i].push((actual_pos, actual_pos + pat.len()));
            start = actual_pos + 1;
        }
    }
    let mut dp = vec![i64::MAX; n + 1];
    dp[n] = 0;
    use std::collections::BinaryHeap;
    use std::cmp::Reverse;
    let mut pq = BinaryHeap::new();
    let mut by_end = vec![vec![]; n + 1];
    for i in 0..m_count {
        let cost = snippets[i].1;
        for &(start, end) in &occ[i] {
            by_end[end].push((start, cost));
        }
    }
    for i in (1..=n).rev() {
        if dp[i] != i64::MAX {
            for &(start, cost) in &by_end[i] {
                pq.push(Reverse((cost + dp[i], start)));
            }
        }
        while let Some(&Reverse((_, start))) = pq.peek() {
            if start > i - 1 { pq.pop(); } else { break; }
        }
        if let Some(&Reverse((val, _))) = pq.peek() { dp[i - 1] = val; }
    }
    if dp[0] == i64::MAX { return (-1, Vec::new()); }
    let mut sequence = Vec::new();
    let mut curr = 0;
    while curr < n {
        let mut best_idx = i32::MAX;
        let mut best_end = 0;
        for j in 0..m_count {
            let cost = snippets[j].1;
            let idx = (j + 1) as i32;
            if idx > best_idx { continue; }
            for &(start, end) in &occ[j] {
                if start <= curr && end > curr {
                    if dp[end] != i64::MAX && cost + dp[end] == dp[curr] {
                        if idx < best_idx {
                            best_idx = idx;
                            best_end = end;
                        } else {
                            best_end = best_end.max(end);
                        }
                        break;
                    }
                }
            }
        }
        sequence.push(best_idx);
        curr = best_end;
    }
    (dp[0], sequence)
}

typescript

function celestial_pattern_synthesis(mural: string, snippets: [string, number][]): [number, number[]] {
    if (!mural) return [0, []];
    const N = mural.length, M = snippets.length;
    const occ: [number, number][][] = Array.from({ length: M }, () => []);
    for (let i = 0; i < M; i++) {
        const pat = snippets[i][0];
        let start = 0;
        while (true) {
            const pos = mural.indexOf(pat, start);
            if (pos === -1) break;
            occ[i].push([pos, pos + pat.length]);
            start = pos + 1;
        }
    }
    const dp = new Array(N + 1).fill(Infinity);
    dp[N] = 0;
    const pq: {val: number, start: number}[] = [], byEnd: [number, number][][] = Array.from({ length: N + 1 }, () => []);
    for (let i = 0; i < M; i++) {
        const cost = snippets[i][1];
        for (const [start, end] of occ[i]) byEnd[end].push([start, cost]);
    }
    for (let i = N; i > 0; i--) {
        if (dp[i] !== Infinity) {
            for (const [start, cost] of byEnd[i]) {
                pq.push({ val: cost + dp[i], start });
            }
            pq.sort((a, b) => a.val - b.val);
        }
        while (pq.length > 0 && pq[0].start > i - 1) pq.shift();
        if (pq.length > 0) dp[i - 1] = pq[0].val;
    }
    if (dp[0] === Infinity) return [-1, []];
    const sequence: number[] = [];
    let curr = 0;
    while (curr < N) {
        let bestIdx = Infinity, bestEnd = -1;
        for (let j = 0; j < M; j++) {
            const cost = snippets[j][1], idx = j + 1;
            if (idx > bestIdx) continue;
            for (const [start, end] of occ[j]) {
                if (start <= curr && end > curr) {
                    if (dp[end] !== Infinity && cost + dp[end] === dp[curr]) {
                        if (idx < bestIdx) {
                            bestIdx = idx;
                            bestEnd = end;
                        } else {
                            bestEnd = Math.max(bestEnd, end);
                        }
                        break;
                    }
                }
            }
        }
        sequence.push(bestIdx);
        curr = bestEnd;
    }
    return [dp[0], sequence];
}

Related Dynamic Programming Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Celestial Pattern Synthesis

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Dynamic Programming Challenges

Lantern Crew Rest Planner

Luminous Script Segmentation Count

Glow Market Profit Planner

Harbor Banner Schedule Slots

Lantern Melody Chain Length

Festival Coin Path Count

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.