As [breadcrumb menùs](https://en.wikipedia.org/wiki/Breadcrumb_%28navigation%29) are quite popular today, I won't digress much on explaining them, leaving the wiki link to do all the dirty work in my place.

What might not be so trivial is instead to get a decent breadcrumb from your current url. For this kata, your purpose is to create a function that takes a url, strips the first part (labelling it always `HOME`) and then builds it making each element but the last a `` element linking to the relevant path; last has to be a `` element getting the `active` `class`.

All elements need to be turned to uppercase and separated by a separator, given as the second parameter of the function; the last element can terminate in some common extension like `.html`, `.htm`, `.php` or `.asp`; if the name of the last element is `index`.something, you treat it as if it wasn't there, sending users automatically to the upper level folder.

A few examples can be more helpful than thousands of words of explanation, so here you have them:
```python
generate_bc("mysite.com/pictures/holidays.html", " : ") == 'HOME : PICTURES : HOLIDAYS'
generate_bc("www.codewars.com/users/GiacomoSorbi", " / ") == 'HOME / USERS / GIACOMOSORBI'
generate_bc("www.microsoft.com/docs/index.htm", " * ") == 'HOME * DOCS'
```
Seems easy enough?

Well, probably not so much, but we have one last extra rule: if one element (other than the root/home) is longer than 30 characters, you have to shorten it, acronymizing it (i.e.: taking just the initials of every word); url will be always given in the format `this-is-an-element-of-the-url` and you should ignore words in this array while acronymizing: `["the","of","in","from","by","with","and", "or", "for", "to", "at", "a"]`; a url composed of more words separated by `-` and equal or less than 30 characters long needs to be just uppercased with hyphens replaced by spaces.

Ignore anchors (`www.url.com#lameAnchorExample`) and parameters (`www.url.com?codewars=rocks&pippi=rocksToo`) when present.

Examples:
```python
generate_bc("mysite.com/very-long-url-to-make-a-silly-yet-meaningful-example/example.htm", " > ") == 'HOME > VLUMSYME > EXAMPLE'
generate_bc("www.very-long-site_name-to-make-a-silly-yet-meaningful-example.com/users/giacomo-sorbi", " + ") == 'HOME + USERS + GIACOMO SORBI'
```

You will always be provided **valid url** to webpages **in common formats**, so you probably shouldn't bother validating them.

If you like to test yourself with actual work/interview related kata, please also consider this one about building [a string filter for Angular.js](http://www.codewars.com/kata/number-shortening-filter).

_Special thanks to [the colleague](http://www.codewars.com/users/jury89) that, seeing my code and commenting that I worked on that as if it was I was on CodeWars, made me realize that it could be indeed a good idea for a kata_ :)

Difficulty: interview

Starter code:

def generate_bc(url, separator):
	

Solutions:
from re import sub

ignoreList = ["THE", "OF", "IN", "FROM", "BY", "WITH", "AND",  "OR",  "FOR",  "TO",  "AT",  "A"]

def generate_bc(url, separator):
    # remove leading http(s):// and trailing /
    url = sub("https?://", "", url.strip("/"))
    
    # skip index files
    url = sub("/index\..+$", "", url)
    
    # split url for processing
    url = url.split("/")
    
    # remove file extensions, anchors and parameters
    url[-1] = sub("[\.#\?].*", "", url[-1])
    
    # first element is always "home"
    menu = ["HOME"]
    # generate breadcrumb items
    for item in url[1:]:
        # replace dashes and set to uppercase
        item = sub("-", " ", item.upper())
        # create acronym if too long
        if len(item) > 30:
            item = "".join([w[0] for w in item.split() if w not in ignoreList])
        menu.append(item)
    
    # generate paths
    path = ["/"]
    for i in range(len(url) - 1):
        path.append(path[i] + url[i+1] + "/")
    
    # generate html code
    html = []
    for i in range(len(url) - 1):
        html.append("<a href=\"" + path[i] + "\">" + menu[i] +"</a>")
    html.append("<span class=\"active\">" + menu[-1] +"</span>")
    
    return separator.join(html)

common_extensions = ["html", "htm", "php", "asp", "jsp"]
acronym_ignore = ["the","of","in","from","by","with","and", "or", "for", "to", "at", "a"]
protocols = ["http://", "https://"]
home_tpl = "<a href=\"/\">HOME</a>"
span_tpl = "<span class=\"active\">%s</span>"
link_tpl = "<a href=\"%s\">%s</a>"


def generate_bc(url, separator):
    """
    Turn an url into an html breadcrumb
    """
    print url
    url = no_protocol(url)
    bread = home_tpl
    crumbs = url.split("/")[1:]
    crumbs = [c for c in crumbs if not(is_index(c)) and len(c) > 0]
    previous = "/"
    print crumbs
    if len(crumbs) == 0:
        return "<span class=\"active\">HOME</span>"
    for crumb in crumbs[:-1]:
        previous, html = knead(crumb, previous)
        bread += separator + html
    bread += separator + brown(crumbs[-1])
    return bread


def knead(crumb, previous):
    """
    Turn a crumb into breadcrumb element
    :param crumb Url part to turn into breadcrumb part
    :param previous url part if any
    :return Tuple containing url and html Breadcrumb element (url, html)
    """
    assert type(crumb) is str
    assert type(previous) is str
    crumb = no_extension(no_params(crumb))
    url = previous + crumb + "/" 
    name = to_acronym(crumb, "", 30)
    name = name.upper()
    return url, link_tpl % (url, name)


def brown(crumb):
    """
    Brown the last crumb into an active span
    :param url_part URL part to check
    :return HTML active span for the crumb
    """
    assert type(crumb) is str
    name = to_acronym(no_extension(no_anchor(no_params(crumb))), " ", 30)
    return span_tpl % (name.upper())


def to_acronym(url_part, joiner, max):
    """
    Turn the given string into an acronym if the size > :max
    :param url_part URL part to check
    :param joiner char to place between word
    :max max number of letter allowed before turning the string into an acronym
    :return Name or acronym if size is too big
    """
    assert type(url_part) is str
    assert type(joiner) is str
    assert type(max) is int
    if len(url_part) >= max:
        url_part="".join([word[0] for word in url_part.split("-") if word not in acronym_ignore])
    return url_part.replace("-", " ")


def is_index(url_part):
    """
    Check if url part is index
    :param url_part URL part to check
    :return True if the name of the element is index.something
    """
    assert type(url_part) is str
    return "index" in url_part


def no_extension(url_part):
    """
    Remove common extension from the end of the url part
    :param url_part URL part to treat
    :return url part as a string without any known extension
    """
    assert type(url_part) is str
    splitted = url_part.split(".")
    if splitted[-1] in common_extensions:
        splitted = splitted[:-1]
    return '.'.join(splitted)
    
    
def no_params(url_part):
    """
    Remove uri params
    :param url_part URL part to treat
    :return url part as a string without uri params
    """
    assert type(url_part) is str
    return url_part.split("?")[0]
    

def no_protocol(url):
    """
    Remove protocol from url string
    :param url URL to strip
    :return URL string without protocol
    """
    assert type(url) is str
    for p in protocols:
        if url.startswith(p):
            url = url[len(p):]
    return url
    

def no_anchor(url_part):
    """
    Remove anchor from url
    :param url_part URL part to treat
    :return url part as a string without anchor
    """
    assert type(url_part) is str
    return url_part.split("#")[0]

import re

INVALID_WORDS = set("the of in from by with and or for to at a".upper().split())

def formater(part):
    part = part.replace("-"," ").upper()
    if len(part) > 30: part = ''.join( w[0] for w in part.split() if w not in INVALID_WORDS )
    return part
    
def generate_bc(url, separator):
    ans, urlLst = [], re.sub(r'(/index\..*)|(\?.*)|(#.*)|(https?://)|/$', '', url).split('/')
    lenLst = len(urlLst)
    
    for i in range(lenLst):
        if i == 0 and lenLst > 1:               ans.append('<a href="/">HOME</a>')
        elif i != lenLst-1 and len(urlLst) > 2: ans.append('<a href="/{}/">{}</a>'.format( '/'.join(urlLst[1:i+1]), formater(urlLst[i]) ))
        elif i == lenLst-1:                     ans.append('<span class="active">{}</span>'.format( 'HOME' if i == 0 else formater(re.sub(r'\..*','',urlLst[-1])) ))
        
    return separator.join(ans)

from re import sub, search

def generate_bc(url, separator):
  url = sub("https?:\/\/","", sub("\/index\..+$","",sub("[?#].+$","", url)))
  base = search(".+?\/", url).group(0) if search(".+?\/", url) else url
  #if (base==nil): return '<span class="active">HOME</span>'
  paths = url[len(base):].split("/")
  path = "/"
  breadcrumbedPath = ['<a href="/">HOME</a>']
  if (url==base): return '<span class="active">HOME</span>'
  classes = None; last = False
  for i in xrange(len(paths)):
      if i==len(paths)-1:
          classes='active'
          last=True
      path += paths[i] + "/"
      bcName = paths[i]
      if len(paths[i])>30: bcName=acronymize(bcName)
      bcName = parseName(bcName)
      breadcrumbedPath+=[createHTMLPath(bcName, path, classes, last)]
  return separator.join(breadcrumbedPath);

createHTMLPath=lambda bcName, url, classes, last: ''.join(['<a href="',url,'"',('' if classes==None else ''.join([' class="',classes,'"'])),'>',bcName,'</a>']) if not last else ''.join(['<span',('' if classes==None else ''.join([' class="',classes,'"'])),'>',bcName,'</span>'])

parseName=lambda bcName: sub("\.\w+","", " ".join(bcName.split("-"))).upper()

acronymize=lambda bcName: "".join([x[0] for x in bcName.lower().split("-") if x not in ["the","of","in","from","by","with","and", "or", "for", "to", "at", "a"]])

def generate_bc(url, separator):
    a, span = '<a href="%s/">%s</a>', '<span class="active">%s</span>'
    restricted = set("THE OF IN FROM BY WITH AND OR FOR TO AT A".split())
    def bc(menu):
        menu = menu.upper().replace('-', ' ')
        if len(menu) > 30: menu = ''.join(w[0] for w in menu.split() if w not in restricted)
        return menu or 'HOME'
    url = ''.join(url.strip('/').rpartition('//')[2].partition('/')[1:]) \
            .rsplit('?',1)[0].rsplit('#',1)[0].rsplit('.',1)[0].rsplit('/index')[0].split('/')
    return separator.join([a % ('/'.join(url[:i]), bc(m)) for i, m in enumerate(url[:-1], 1)] + [span % bc(url[-1])])

IGNORE = "THE OF IN FROM BY WITH AND OR FOR TO AT A".split()

def generate_bc(url, separator):
    if url.startswith("http"):
        url = url.split("//")[1]
    crumbs = url.split("/")
    links  = crumbs[1:]
    crumbs[0] = 'HOME'
    for i, crumb in enumerate(crumbs):
        crumb = crumb.split(".")[0].split("?")[0].split("#")[0].replace("-", " ").upper()
        if len(crumb) > 30:
            crumb = [c for c in crumb.split() if c not in IGNORE]
            crumb = ''.join(map(lambda c: c[0], crumb))            
        crumbs[i] = crumb
    if crumbs[-1] in ('', 'INDEX'):
        crumbs.pop()
    output = []
    for i, crumb in enumerate(crumbs[:-1]):
        element = '<a href="/%s/">%s</a>' % ("/".join(links[:i]), crumb)
        output += [element.replace("//", "/")]
    output += ['<span class="active">%s</span>' % crumbs[-1]]
    return separator.join(output)

import re
def base_name(fullname):
    return re.sub(r'[.].*$', '', fullname)

ignore_words = ["the", "of", "in", "from", "by", "with", "and", "or", "for", "to", "at", "a"]
def short_name(name):
    if len(name) <= 30:
        return re.sub(r'[-]',' ', name)
    else:
        return ''.join([a[0] for a in name.split('-') if a not in ignore_words] )


def generate_bc(url, separator):
    url_striped = re.sub(r'[#?].*', '',url)
    url_striped = re.sub(r'(http|https)://', '', url_striped)
    url_striped = re.sub(r'/$', '', url_striped)
    url_splited = url_striped.split("/")

    if base_name(url_splited[-1]) == "index":
        del url_splited[-1]
    if len(url_splited) <= 1:
        return '<span class="active">HOME</span>'

    path = "/"
    res = list()
    res.append('<a href="/">HOME</a>')
    for e in url_splited[1:-1]:
        path += e + "/"
        res.append('<a href="%s">%s</a>'%(path, short_name(e).upper()))
    res.append('<span class="active">%s</span>' % (short_name(base_name(url_splited[-1])).upper()))

    return separator.join(res)


from typing import List, Tuple
from urllib.parse import urlparse
import re


def generate_bc(url: str, separator: str) -> str:
    # print(f'url = {repr(url)}')
    # print(f'separator = {repr(separator)}')

    home_url = '<a href="/">HOME</a>'  # type: str

    (path_components, last_path) = split_url(url)
    if last_path.startswith("index."):
        last_path = ''

    last_path = re.sub(r"(.html|.htm|.php|.asp)$", "", last_path)

    if not path_components:  # empty
        if not last_path:
            return '<span class="active">HOME</span>'
    elif not last_path:
        last_path = path_components.pop()

    return separator.join([
        home_url, *generate_bc_middle(path_components),
        generate_bc_last(last_path)
    ])


def generate_bc_middle(path_components: List[str]) -> List[str]:
    # return ['<a href="/important/">IMPORTANT</a>', '<a href="/important/confidential/">CONFIDENTIAL</a>']
    cumulative_path = ''
    result: List[str] = []
    for path in path_components:
        cumulative_path = (cumulative_path + '/' +
                           path) if cumulative_path else path
        bc = path.replace('-',
                          ' ').upper() if len(path) <= 30 else acronymyze(path)
        result.append(f'<a href="/{cumulative_path}/">{bc}</a>')
    return result


def acronymyze(long_word: str) -> str:
    """ Shorten it, acronymizing it
    (i.e.: taking just the initials of every word) """
    ignore_words = [
        "the", "of", "in", "from", "by", "with", "and", "or", "for", "to",
        "at", "a"
    ]
    return ''.join(word[0].upper() for word in long_word.split('-')
                   if word not in ignore_words)


def generate_bc_last(last_path: str) -> str:
    if len(last_path) > 30:
        bc = acronymyze(last_path)
    else:
        bc = last_path.replace('-', ' ').upper()
    return f'<span class="active">{bc}</span>'


def split_url(url: str) -> Tuple[List[str], str]:
    """ Returns a tuple by splitting the given url
    url = 'mysite.com/years/pictures/holidays.html'
    returns a tuple ([years,pictures], 'holidays.html')
    """

    # Example url = 'https://mysite.com/years/pictures/holidays.html'
    parse_result = urlparse(url)
    # ParseResult(scheme='https', netloc='mysite.com', path='/years/pictures/holidays.html',
    #               params='', query='', fragment='')

    # urlparse recognizes a netloc only if it is properly introduced by ‘//’.
    # Otherwise the input is presumed to be a relative URL and thus to start
    # with a path component.

    # Redo urlparse to make sure that parse_result.path has only filepath and not hostpath part
    if not parse_result.scheme and not url.startswith('//'):
        parse_result = urlparse('//' + url)

    if not parse_result.path:  # empty path
        path_components = []
        last_path = ''
    elif parse_result.path.startswith('/'):
        path_components = [
            component for component in parse_result.path.split("/")
        ]
        path_components.pop(0)  # Remove ''
        # ['', 'years', 'pictures', 'holidays.html']
        last_path = path_components.pop()  # type: str
    else:
        raise Exception("Invalid url")

    # (['years', 'pictures'], 'holidays.html')
    return (path_components, last_path)


def generate_bc(url, separator):
    print(url)
    print(separator)
    url = str(url.replace("https://", ""))
    url = str(url.replace("http://", ""))

    try:
        questionIndex = url.index("?")
    except ValueError:
        questionIndex = -1

    try:
        hashIndex = url.index("#")
    except ValueError:
        hashIndex = -1

    if questionIndex != -1:
        url = str(url[:questionIndex])

    if hashIndex != -1:
        url = str(url[:hashIndex])

    names = list(filter(None, url.split('/')))
    html = ""

    commonExtensions = [".html", ".htm", ".php", ".asp"]
    ignoreWords = [
        "the",
        "of",
        "in",
        "from",
        "by",
        "with",
        "and",
        "or",
        "for",
        "to",
        "at",
        "a"
    ]
    pastLinks = []

    for index, name in enumerate(names):
        isFirstIndex = index == 0
        isLastIndex = index == len(names) - 1

        if not isLastIndex and "index" in names[index + 1]:
            isLastIndex = True

        if isLastIndex:
            for commonExtension in commonExtensions:
                name = name.replace(commonExtension, "")

        tagValue = ""
        if isFirstIndex:
            tagValue = "HOME"
        elif len(name) > 30:
            tagValue = ''.join(
                str.upper(a[0:1]) for a in name.split('-') if a not in ignoreWords)
        else:
            if '-' in name:
                tagValue = name.upper().replace('-', ' ')
            else:
                tagValue = name.upper()

        html += "<{element}".format(element='span' if isLastIndex else 'a')
        if isLastIndex:
            html += ' class="active"'
        else:
            currentLink = name.strip().lower()
            hrefValue = ''
            if isFirstIndex:
                hrefValue = '/'
            elif len(pastLinks) > 0:
                pastLinks.append(currentLink)
                hrefValue = '/{link}/'.format(link="/".join(pastLinks))
            else:
                pastLinks.append(currentLink)
                hrefValue = "/{link}/".format(link=currentLink)
            html += ' href="{hrefValue}"'.format(hrefValue=hrefValue)

        html += '>'
        html += tagValue
        html += '</{attribute}>'.format(
            attribute='span' if isLastIndex else 'a')
        if not isLastIndex:
            html += separator
        if isLastIndex:
            break

    return html

import re

def generate_bc(url, separator):
    def formater(name):
        if len(name) > 30:
            stoplist = ['the','of','in','from','by','with','and','or','for','to','at','a']
            return ''.join([ch[0].upper() for ch in name.split('-') if ch not in stoplist])
        else:
            return name.replace('-', ' ').upper()
    
    result = []
    
    url = re.sub(r'^https?:\/\/', '', url)      # remove protocol
    url = re.sub(r'\.[^\/]*$', '', url)         # remove extensions
    url = re.sub(r'(?:\#|\?).*$', '', url)      # remove anchors and queries
    url = re.sub(r'index$', '', url)            # remove indexes
    url = url.rstrip('/')                       # remove trailing slash
    
    crumbs = url.split('/')
    
    for i, crumb in enumerate(crumbs):
        if i == 0: result.append('<a href="/">HOME</a>' if len(crumbs) > 1 else '<span class="active">HOME</span>')
        elif i == len(crumbs) - 1: result.append('<span class="active">{}</span>'.format(formater(crumb)))
        else: result.append('<a href="/{}/">{}</a>'.format('/'.join(crumbs[1:1+i]), formater(crumb)))
    
    return separator.join(result)