Re: [css-counter-styles] Additive system pathological cases

On Thu, Jun 6, 2013 at 10:09 PM, Simon Sapin <simon.sapin@exyr.org> wrote:
> Hi,
>
> The 'additive' system, as currently defined, has some pathological cases.
> For example:
>
> @counter-style funky {
>   system: additive;
>   additive-symbols: 3 ⚂, 2 ⚁;
> }
>
> The current algorithm will find a representation for value = 4 (It will use
> ⚂ once, and then exhaust the list searching for a way to represent 1.) while
> ⚁⚁ is a valid representation for 4 per the additive rules. However, fixing
> this  would require much more algorithmic complexity, it sounds like the
> NP-complete Knapsack problem.
>
> (Note: having a symbol with value 1 guarantees that this is issue never
> happens for a given style.)
>
> I suggest adding a note saying that the algorithm is known (and expected) to
> not find a solution in some cases where a solution exists, and authors
> designing their own additive counter styles should be careful about this.

Done.

~TJ

Received on Saturday, 8 June 2013 09:16:55 UTC