![]() ![]() So we might as well add the constraint that a color must appear in the input multiple times. If a color appears only once in the input, an optimal solution can simply include a single paper on top that only covers its hole. ![]() Here's everything useful I've been able to come up with toward a solution (that I can remember as of writing this) so far. If such an algorithm is not possible, then a polynomial-time algorithm which gets as close to the optimal output within what is possible would be acceptable instead. Your algorithm should ideally take polynomial time. But not efficiently, as that takes exponential time (or worse) (relative to the number of holes and colors in the input). ![]() Obviously, an algorithm which comprehensively generates every possible output and compares each output's cost to find an optimal one would solve this problem. It isn't necessary to find every optimal solution for a given input you only need one. Here are two examples of cheaper, optimal solutions (with cost 15) given the same input: I'm trying to minimize the number of characters required to encode the formatting of arbitrary rich text.) (If it helps to understand why cost depends on character counts, the motivation for this is rich text minification. The size of each paper has no effect on cost. An optimal solution is an arrangement of papers with the least total cost, and there may be multiple optimal solutions. For example, a "red" paper costs 3, a "blue" paper costs 4, and two "green" papers cost 2 * 5 = 10. What is optimal?Įach paper's cost is the number of characters in its color. The first element of the sequence is the paper you'd set down first (the bottommost paper), followed by the one you'd set down second, and so on. The configuration of all the papers together can be thought of as a sequence of such tuples. Consider the position before the first hole to be 0, then 1 if it's between the first and second holes, then 2 if it's after the second, and so on. (red * (blue *) *) (green *) (blue *) IS a valid solution, but not an optimal one (see later section).įormalization (if it helps to understand the problem)Įach paper's configuration can be thought of as a 3-tuple: (its color string, an integer for where it starts, an integer for where it ends). This (not representable) is NOT a valid solution because there are overlapping edges (marked by white Xs). (red * * *) (green *) (blue *) is NOT a valid solution because a red paper appears behind a blue hole. ![]() Representing each hole as an asterisk and each paper as its color wrapped in parentheses with the holes it covers and any papers on top of it, here are some examples using the same input as the previous examples: The papers' edges must not cross, but a paper may be placed above another if it is entirely within its bounds. The output, then, would be visualized as a number of colored rectangular papers arranged behind the holes such that each hole is filled with the color it's outlined with. Using the (red, blue, red, green, blue) example (color labels added for accessibility): You can visualize the input as a sequence of holes outlined by those respective colors. Color is merely a convenient way to conceptualize this problem. Each color is represented in the input as a string, not as any abstract notion of a color, so "green" is different from "#008000" is different from "the color between yellow and blue", because these are all different strings. For example, (red, blue, red, green, blue). Let the input be a sequence of colors with any length at least 1. ![]()
0 Comments
Leave a Reply. |