The jackpot sign

The crate of lamps has to be emptied exactly, and the digits that fit are not the digits you would reach for first.

The problem

The shooting gallery hangs tonight's jackpot over the counter in lit digit panels. There are nine panels, one per digit 1 to 9 and none for 0. The panel for digit d has panel_lamps[d - 1] sockets, every socket must hold a lamp for the digit to read, and a panel may be hung as often as you like.

Tonight's crate holds supply lamps. The generator is rated for that exact load and stalls when under-loaded, so the sign must take every lamp in the crate — no more, none left over. Among the numbers that empty the crate exactly, hang the largest.

Report it as a string, because it can run to thousands of digits. If nothing empties the crate exactly, report "0" and leave the counter dark — 0 has no panel, so that answer is never ambiguous.

Input. panel_lamps — the socket counts of the panels for digits 1 through 9, in order. supply — how many lamps the crate holds.

Output. The largest number displayable with exactly supply lamps, as a string, or "0".

Example.

panel_lamps = [2, 5, 4, 6, 3, 5, 3, 7, 6], supply = 14   ->  "1111111"

Digit 1 is cheapest at 2 sockets, so 14 lamps buy seven digits. Nothing shorter competes: 9, 9 and 1 empty the crate too, at 6 + 6 + 2, but spell only 991.

A second example, where the cheapest panel cannot finish the job:

panel_lamps = [2, 5, 4, 6, 3, 5, 3, 7, 6], supply = 9   ->  "7111"

Nine is odd and digit 1 costs 2, so an all-1s sign strands a lamp. Four digits still fit — three 1s and one 3-socket panel — and since 5 and 7 both cost 3, take the 7 and hang it in front.

Constraints.

• len(panel_lamps) == 9
• 1 <= panel_lamps[i] <= 5000
• 1 <= supply <= 5000

Hints

Approach

Brute force

Generate digit strings, add up their sockets, and keep the largest that totals supply exactly. With a cheapest panel of 2 sockets a full crate allows signs 2500 digits long, and there are 9²⁵⁰⁰ strings of that length.

The insight

Length outranks every digit, so fill a table of "most digits for exactly t lamps" first, then read the digits back from the largest downward.

Any seven-digit sign beats any six-digit one, so the digit count is the skeleton: most[t] = 1 + max(most[t - cost]) over the panels, unreachable totals marked so they never seed a later cell. The read-back is then safe because most is exact — if most[left - cost] == most[left] - 1, hanging that digit still leaves room for every digit you owe, so no later step is forced to give one up. Earlier positions outrank later ones, so the largest such digit goes first.

Algorithm

1. Set most[0] = 0 and mark every other total unreachable.
2. For t from 1 to supply, take most[t] = 1 + max(most[t - panel_lamps[d]]) over panels that fit and start from a reachable total.
3. If most[supply] is unreachable, return "0".
4. With left = supply, scan digits 9 down to 1 and take the first whose cost fits and satisfies most[left - cost] == most[left] - 1.
5. Hang it, subtract its cost, repeat until left is 0.

Complexity

Time O(9 · supply) to fill the table, plus O(9 · length) for the read-back with length <= supply / min(panel_lamps). Space O(supply) for the table, plus the output string.

Solution

"""The jackpot sign — exact-budget DP for the digit count, then a greedy read-back."""

UNREACHABLE = float("-inf")


def solve(panel_lamps, supply):
    # most[t] = the largest number of digits whose panels take exactly t lamps.
    # UNREACHABLE marks a total no set of panels can hit.
    most = [UNREACHABLE] * (supply + 1)
    most[0] = 0
    for total in range(1, supply + 1):
        for cost in panel_lamps:
            if cost <= total and most[total - cost] + 1 > most[total]:
                most[total] = most[total - cost] + 1

    if most[supply] <= 0:
        return "0"                       # the crate cannot be emptied exactly

    digits = []
    left = supply
    while left > 0:
        # invariant: `left` lamps remain and most[left] digits still fit exactly,
        # so the largest digit that keeps that count is safe to hang now
        for digit in range(9, 0, -1):
            cost = panel_lamps[digit - 1]
            if cost <= left and most[left - cost] == most[left] - 1:
                digits.append(str(digit))
                left -= cost
                break
    return "".join(digits)

TESTS = [
    (([2, 5, 4, 6, 3, 5, 3, 7, 6], 14), "1111111"),
    (([2, 5, 4, 6, 3, 5, 3, 7, 6], 9), "7111"),
    (([2, 5, 4, 6, 3, 5, 3, 7, 6], 1), "0"),
    (([2, 5, 4, 6, 3, 5, 3, 7, 6], 5), "71"),
    (([4, 4, 4, 4, 4, 4, 4, 4, 4], 12), "999"),
    (([4, 4, 4, 4, 4, 4, 4, 4, 4], 13), "0"),
    (([9, 9, 9, 9, 9, 9, 9, 9, 5], 5), "9"),
]

Pitfalls

• Reading the crate as a ceiling, not an exact total. Allow leftovers and panel_lamps = [4] * 9, supply = 13 answers "999", lighting 12 lamps and leaving one behind. 13 is unreachable in fours, so the answer is "0".
• Using 0 as the "unreachable" mark. The table then claims a total of 5 is reachable with one digit, and on the same input the read-back hangs 999 before jamming with a lamp left. The mark must sit below every real count.
• Buying the cheapest panel first. At supply = 9 that takes four 1s for 8 lamps and strands the ninth; the longest exact sign mixes in one 3-socket panel, giving "7111".

Variants

• The knapsack family — the unbounded recurrence behind this table, in its plain counting form.
• Two crews, one siding — another table filled for its own sake, with an opponent in place of a fixed budget.