Challenge #8 – The Big O Problem

It’s time to get ​“algorith­mic­al” and solve a prob­lem that could eas­ily be imple­men­ted using a poorly per­form­ing algorithm the per­form­ant way.

Chal­lenge

The chal­lenge is quite straight­for­ward. For each of the entries in a struc­ture, out­put the the title of the entry and its ancest­ors in a bread­crumb man­ner. So for example giv­en the fol­low­ing structure:

Entry 1
    Entry 2
        Entry 3
        Entry 4
    Entry 5
Entry 6
    Entry 7

The out­put should be:

Entry 1
Entry 1 > Entry 2
Entry 1 > Entry 2 > Entry 3
Entry 1 > Entry 2 > Entry 4
Entry 1 > Entry 5
Entry 6
Entry 6 > Entry 7

The catch is that the algorithm should have a com­plex­ity of O(1), mean­ing that the runtime, and in our case the num­ber of data­base quer­ies, should remain con­stant regard­less of how many entries exist in the struc­ture. If, on the oth­er hand, the num­ber of data­base quer­ies grows lin­early and is pro­por­tion­al to the num­ber of entries then your algorithm has a com­plex­ity of O(n).

This is called ​“Big O nota­tion” and can be visu­al­ised as follows:

For a more in-depth explan­a­tion check out A Sim­pli­fied Explan­a­tion of the Big O Nota­tion by Kar­una Sehgal.

If you learn bet­ter from stor­ies about car­ri­er pigeons and lawn mow­ing then you can watch the first few minutes of this fun video.

Rules

The algorithm should be writ­ten in twig using Craft tags, so using the {% nav %} tag is allowed. It must out­put a structure’s entries as described above with a com­plex­ity of O(1). It should not rely on any plu­gins and the code will be eval­u­ated based on the fol­low­ing cri­ter­ia in order of priority:

1. Read­ab­il­ity
2. Brev­ity
3. Per­form­ance

There­fore the code should be read­able and easy to under­stand. It should be con­cise and non-repet­it­ive, but not at the expense of read­ab­il­ity. It should be per­form­ant, but not at the expense of read­ab­il­ity or brevity.

Tips

You can keep track of how per­form­ant your algorithm is by turn­ing on the debug tool­bar on the front-end of your site and keep­ing an eye on the num­ber of data­base quer­ies required to out­put the struc­ture. Get a baseline by out­put­ting the struc­ture entries without their ancest­ors, then see how many extra quer­ies are neces­sary to out­put the titles of their ancest­ors. If the num­ber of data­base quer­ies increases as you add more entries to the struc­ture then you’re likely work­ing with a O(n) algorithm. If it remains con­stant then con­grat­u­la­tions, you have achieved O(1)!

Solution

Submitted Solutions

• Alex Roper

Solution submitted by Alex Roper on 6 November 2019.

{% set entries = craft.entries.section('nav').all() %}
    
{% for entry in entries %}
  
  {% set crumb = [] %}
  
  {# Loop thru all entries again, matching items in the nested set model.
     Match items where the current entry's left and right domain falls between 
     the item's left and right domain, including the current entry.
  -#}
  {% for item in entries if (entry.lft >= item.lft) and (entry.rgt <= item.rgt) %}
    {% set crumb = crumb|merge([item.title]) %}
  {% endfor %}
  
  {# Output the full breadcrumb with > separators #}
  {{ crumb|join(' > ') }}<br>

{% endfor %}

• Prateek Rungta

Solution submitted by Prateek Rungta on 6 November 2019.

{% set entries = craft.entries.section('pages').all() %}

{% nav entry in entries %}
    
    {# Build ancestor lists for nested elements
       by using previous breadcrumbs #}
    {% set ancestors = entry.level > 1
      ? breadcrumbs[0 : entry.level - 1]
      : [] %}
    
    {# Add current entry to ancestors and render titles #}
    {% set breadcrumbs = ancestors|merge([entry]) %}
    {{ breadcrumbs|column('title')|join(' > ') }}
    
    {# Repeat for all children #}
    <br>
    {% children %}
    
{% endnav %}

• Sarah Schütz

Solution submitted by Sarah Schütz on 8 November 2019.

{% set entries = craft.entries().section('entry').all() %}

{% macro render(entries) %}
    {% nav entry in entries %}
        {{ entry.title }}

        {% ifchildren %}
            > {% children %}
        {% endifchildren %}
    {% endnav %}
{% endmacro %}

{% set entryStack = [] %}
{% for entry in entries %}
    {% set level = entry.level %}

    {# remove all entries with a level higher or equal to the current entry #}
    {% set entryStack = entryStack | slice(0, level - 1) %}

    {# add current entry to stack #}
    {% set entryStack = entryStack | merge([entry]) %}

    {# render the current entry stack #}
    <p>{{ _self.render(entryStack) }}</p>
{% endfor %}

• David Hellmann

Solution submitted by David Hellmann on 9 November 2019.

{% set entries = craft.entries.section('challange').all() %}
{% set storage = '' %}
{% for entry in entries %}
  {% if entry.level == 1 %}
    {% set storage = entry.title %}
    {{ entry.title }}<br>
  {% endif %}

  {% if entry.level == 2 %}
    {{ storage }} > {{ entry.title }}<br>
    {% set storage = storage ~ ' > ' ~ entry.title %}
  {% endif %}

  {% if entry.level == 3 %}
    {{ storage }} > {{ entry.title }}<br>
  {% endif %}
{% endfor %}