W3C home > Mailing lists > Public > www-style@w3.org > June 2013

[css-counter-styles] Additive system pathological cases

From: Simon Sapin <simon.sapin@exyr.org>
Date: Fri, 07 Jun 2013 14:09:56 +0900
Message-ID: <51B16B24.1080700@exyr.org>
To: www-style@w3.org
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

This archive was generated by hypermail 2.3.1 : Monday, 2 May 2016 14:39:12 UTC