Celestial Skyline Layout
The Celestial Surveyors maintain blueprints of skyline silhouettes for the capital’s floating terraces. Each skyline is defined by a nested blueprint that describes how towers at each level must mirror and extend the silhouettes beneath them. Architects want to know how many valid skylines can exist for a given blueprint, so that they can allocate resources before the next equinox.
The blueprint structure is recursive with two node types:
- Leaf: an integer
hrepresenting a single tower of heighth. The number of compatible skylines for this node is 1. - Fork:
{"base": X, "steps": [d1, d2, ..., dk]}whereXis another blueprint node and eachdiis an integer offset. The fork represents a tower built atop the skyline generated byX, plus k optional mirrored extensions. Every extension adds a new tower whose height must be exactly the height of the tallest tower in the current skyline plusdi. Each extension can either be included or skipped, but if included, it must appear in the order listed. When included, it also requires its mirrored counterpart: namely, the skyline must contain a tower of that new height, and recursively all towers below must appear in mirrored form.
For each fork, you must:
- Count the number of skylines produced by
base(recursively). - Determine the maximum height present in those skylines.
- For each extension offset
diin order, either keep the skyline unchanged or add the new mirrored tower, updating the maximum height. Adding an extension doubles the number of skylines (because each existing skyline is mirrored with the new tower), while skipping leaves the count unchanged.
Return the total number of skylines as an integer. Assume heights never exceed 109. The answer may be large; return it modulo 1_000_000_007.
Example 1:
Input: blueprint = 4
Output: 1
Example 2:
Input: blueprint = {"base": 4, "steps": [2]}
Output: 2 (either use only the height-4 tower, or add a mirrored tower of height 6)
Example 3:
Input: blueprint = {"base": {"base": 5, "steps": [1]}, "steps": [2, 3]}
Output: 8
Explanation: The inner fork allows heights 5 or {5,6}. The outer fork treats those skylines as base. Each of the two extensions doubles the count when included, so the total number of skylines is 2 (inner) × 2 × 2 = 8.
Related Problems
No related problems found
Comments (0)
Join the Discussion
Share your thoughts, ask questions, or help others with this problem.
