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

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

From: Tab Atkins Jr. <jackalmage@gmail.com>
Date: Sat, 8 Jun 2013 02:16:04 -0700
Message-ID: <CAAWBYDB6hU+hYEr=QUSPqEerLHaVJ2oaKynbj=bz_gCwL7Rsvg@mail.gmail.com>
To: Simon Sapin <simon.sapin@exyr.org>
Cc: www-style list <www-style@w3.org>
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

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