Celestial Pattern Synthesis

Like2

In Celestial Pattern Synthesis you must build a target mural string using available snippets each with a cost Snippets may be reused and may overlap as long as every placed character matches the mural exactly The primary objective is minimum total cost If multiple constructions share that minimum cost you must return the lexicographically smallest sequence of snippet indices according to the required build order A practical model is shortest path DP over mural positions State i means prefix length i already built A transition exists when a snippet matches starting at i moving to i len snippet with added cost Besides cost track reconstruction metadata for index-sequence tie-breaking For equal-cost alternatives compare candidate sequences lexicographically and keep the smaller one If position N is unreachable return cost 1 with an empty sequence The judge checks tie situations impossible builds and repeated snippet use Correctness depends on both numeric optimality and exact sequence ordering not just feasibility Keep transitions strict on character matching and maintain deterministic tie resolution This hard challenge combines string matching graph-style DP and stable lexicographic decision logic in one optimization pipeline In practice this means storing both best cost and a comparable representation of the chosen index sequence for each position state Tie-breaking cannot be an afterthought if sequence order is not enforced during transitions you can get correct cost but wrong official output ordering When the task involves connectivity or route cost build adjacency carefully

Examples

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 - Budibadu

Best Answers

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];
}

Comments (0)

Join the Discussion

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

Celestial Pattern Synthesis

Examples

Algorithm Flow

Best Answers

Solutions Coming Soon

Related Dynamic Programming Problems

Garden Lantern Seating Ways

Festival Glow Step Combinations

Evening Harmony Partition Count

Twilight Lantern Garden

Lantern Vowel Pathways

Lantern Crew Rest Planner

Comments (0)

Join the Discussion