Workstation minimum price
A configurator prices a custom workstation. part_names lists every part on the shelf, part_groups[i] names the slot part i fills, for example case or board, and part_cents[i] is its price in cents. A build takes exactly one part from every slot that appears in part_groups. clashes holds pairs written as "case_mini|board_a", meaning those two parts cannot sit in the same build. A pair may be listed more than once and may be written in either order, it always names two different parts, and both names come from part_names. Return the lowest total price in cents of a build that fills every slot with no clash inside it. Return -1 when no such build exists, and 0 when the shelf is empty. Prices are never negative and there are at most 12 parts.
cheapest_valid_build(part_names: list[str], part_groups: list[str], part_cents: list[int], clashes: list[str]) → int[["case_mini","case_tower","board_a","board_b"],["case","case","board","board"],[4500,7000,9900,12000],["case_mini|board_a"]]out16500[["case_mini","case_tower","board_a","board_b"],["case","case","board","board"],[4500,7000,9900,12000],[]]out14400[["cooler_low","cooler_tall","case_slim"],["cooler","cooler","case"],[2500,3100,6000],["cooler_low|case_slim","case_slim|cooler_tall"]]out-1State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
[["case_mini","case_tower","board_a","board_b"],["case","case","board","board"],[4500,7000,9900,12000],["case_mini|board_a"]]16500not run yetsample[["case_mini","case_tower","board_a","board_b"],["case","case","board","board"],[4500,7000,9900,12000],[]]14400not run yetsample[["cooler_low","cooler_tall","case_slim"],["cooler","cooler","case"],[2500,3100,6000],["cooler_low|case_slim","case_slim|cooler_tall"]]-1not run yetsample