[css-counter-styles] Additive system pathological cases

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.

-- 
Simon Sapin

Received on Friday, 7 June 2013 05:10:23 UTC