You are to write a function to transpose a guitar tab up or down a number of semitones. The amount to transpose is a number, positive or negative. The tab is given as an array, with six elements for each guitar string (fittingly passed as strings). Output your tab in a similar form.

Guitar tablature (or 'tab') is an alternative to sheet music, where notes are replaced by fret numbers and the five lines of the staff are replaced by six lines to represent each of the guitar's strings. It is still read from left to right like sheet music, and notes written directly above each other are played at the same time.

For example, Led Zeppelin's Stairway to Heaven begins:
```
e|-------5-7-----7-|-8-----8-2-----2-|-0---------0-----|-----------------|
B|-----5-----5-----|---5-------3-----|---1---1-----1---|-0-1-1-----------|
G|---5---------5---|-----5-------2---|-----2---------2-|-0-2-2-----------|
D|-7-------6-------|-5-------4-------|-3---------------|-----------------|
A|-----------------|-----------------|-----------------|-2-0-0---0--/8-7-|
E|-----------------|-----------------|-----------------|-----------------|
```
Transposed up two semitones, it would look like this:
```
e|-------7-9-----9-|-10-----10-4-----4-|-2---------2-----|------------------|
B|-----7-----7-----|----7--------5-----|---3---3-----3---|-2-3-3------------|
G|---7---------7---|------7--------4---|-----4---------4-|-2-4-4------------|
D|-9-------8-------|-7---------6-------|-5---------------|------------------|
A|-----------------|-------------------|-----------------|-4-2-2---2--/10-9-|
E|-----------------|-------------------|-----------------|------------------|
```
Note how when the 8th fret note on the top string in bar 2 gets transposed to the 10th fret, extra '-' are added on the other strings below so as to retain the single '-' that originally separated that beat (i.e. column) from the following note – fret 7 on the B string.

Each beat must retain at least one '-' separator before the next, to keep the tab legible. The inputted test tabs all obey this convention.

Electric guitars usually have 22 frets, with the 0th fret being an open string. If your fret numbers transpose to either negative values or values over 22, you should return 'Out of frets!' (and probably detune your guitar).

Tests include some randomly generated guitar tabs, which come with no guarantee of musical quality and/or playability...!

Difficulty: introductory

Starter code:

def transpose(amount, tab):
	

Solutions:
def transpose(amount, tab):
    stack, tab = [], list(map(list, tab))
    for n, col in reversed(list(enumerate(zip(*tab)))):
        if any(map(str.isdigit, col)):
            stack.append(col)
        elif stack:
            frets = [''.join(r).strip('-') for r in zip(*reversed(stack))]
            frets = [fret and int(fret) + amount for fret in frets]
            if any(fret and not 0 <= fret <= 22 for fret in frets): return 'Out of frets!'
            frets = list(map(str, frets))
            pad = max(map(len, frets))
            for row, fret in zip(tab, frets):
                row[n+1: n+1+len(stack)] = str(fret).ljust(pad, '-')
            stack.clear()
    return list(map(''.join, tab))

from itertools import groupby
import re

class OutOfFrets(Exception): pass


def convert(k,grp,amount):
    
    def convertOrRaise(m):
        v = int(m.group()) + amount
        if not (0 <= v < 23): raise OutOfFrets()
        return str(v)
        
    lst = list(map(''.join, list(zip(*grp))))
    if isinstance(k,str): return lst

    col  = [re.sub(r'\d+', convertOrRaise, l.strip('-')) for l in lst]
    maxL = max(list(map(len,col)))
    return [l.ljust(maxL, '-') for l in col]
    
    
def transpose(amount, tab):
    try:               lst = [convert(k,g,amount) for k,g in groupby(list(zip(*tab)), key=lambda t: len(set(t))!=1 or t[0])]
    except OutOfFrets: return "Out of frets!"
    
    return list(map(''.join, list(zip(*lst))))


import re

def transpose(amount, tab):
    
    # get start and end of all frets
    fret_pos = get_all_fret_positions(tab)
    # process each column that contains frets
    pos = 0
    tab_new = ['' for string in tab]
    for fret_start in sorted(fret_pos):
        fret_end = fret_pos[fret_start]
        # get all sub strings from one column
        col = [string[fret_start:fret_end] for string in tab]
        # apply amount to all frets
        col, col_width = apply_amount(col, amount)
        if col == 'Out of frets!':
            return 'Out of frets!'
        # adjust column width
        col = adjust_column_width(col, col_width)
        # add modified column back to tablature
        for i, row in enumerate(col):
            tab_new[i] = tab_new[i] + tab[i][pos:fret_start] + row
        pos = fret_end
        # add the part after the final fret
    for i, row in enumerate(col):
        tab_new[i] = tab_new[i] + tab[i][fret_end:]

    return tab_new

def get_all_fret_positions(tab):
    fret_pos = {}
    for string in tab:
        for match in re.finditer('[0-9]+', string):
            if match.start() in fret_pos.keys():
                if fret_pos[match.start()] < match.end():
                    fret_pos[match.start()] = match.end()
            else:
                fret_pos[match.start()] = match.end()
    return fret_pos

def apply_amount(col, amount):
    col_width = 0
    for i, fret in enumerate(col):
        new_fret = re.search('[0-9]+', fret)
        if new_fret:
            new_fret = int(new_fret.group(0)) + amount
            if new_fret > 22 or new_fret < 0:
                return 'Out of frets!', None
            if len(str(new_fret)) > col_width:
                col_width = len(str(new_fret))
            col[i] = str(new_fret)
    return col, col_width

def adjust_column_width(col, col_width):
    for i, row in enumerate(col):
        if len(row) < col_width:
            col[i] = col[i] + '-' * (col_width - len(row))
        if len(row) > col_width:
            col[i] = col[i][:col_width - len(row)]
    return col


t = transpose(2, [
'e|--------5-7-----7-|-8-----8-2-----2-|-0---------0-----|-----------------|',
'B|-10---5-----5-----|---5-------3-----|---1---1-----1---|-0-1-1-----------|',
'G|----5---------5---|-----5-------2---|-----2---------2-|-0-2-2-----------|',
'D|-12-------6-------|-5-------4-------|-3---------------|-----------------|',
'A|------------------|-----------------|-----------------|-2-0-0---0--/8-7-|',
'E|------------------|-----------------|-----------------|-----------------|'])        

print(t)

"""
t = transpose(-1, [
'e|-----------------|---------------|----------------|------------------|',
'B|-----------------|---------------|----------------|------------------|',
'G|--0---3---5----0-|---3---6-5-----|-0---3---5----3-|---0----(0)-------|',
'D|--0---3---5----0-|---3---6-5-----|-0---3---5----3-|---0----(0)-------|',
'A|-----------------|---------------|----------------|------------------|',
'E|-----------------|---------------|----------------|------------------|'])
t = transpose(+2, [
'e|----------5/6-6-6-5/6-6-6-6-6-6------------------------------------|',
'B|-------6--5/6-6-6-5/6-6-6-6-6-6-9-8-6-6----------------------------|',
'G|---6h7--------------------------------6h7--------------------------|',
'D|-8----------------------------------------8-6--8-8-8-8-8-8-8-8-----|',
'A|-----------------------------------------------8-8-8-8-8-8-8-8-----|',
'E|-------------------------------------------------------------------|'])
print(t)
"""

"""
'e|-----------7/8-8-8-7/8-8-8-8-8-8-----------------------------------------------|',
'B|--------8--7/8-8-8-7/8-8-8-8-8-8-11-10-8-8-------------------------------------|',
'G|----8h9----------------------------------8h9-----------------------------------|',
'D|-10------------------------------------------10-8--10-10-10-10-10-10-10-10-----|',
'A|---------------------------------------------------10-10-10-10-10-10-10-10-----|',
'E|-------------------------------------------------------------------------------|'
"""

import itertools

def transpose(amount, tab):
    shorten_dash = False
    for i in range(0,6):
        split_i = ["".join(y) for x,y in itertools.groupby(tab[i],key=str.isdigit)]
        trans = ""
        for gr in split_i:
            if gr.isnumeric():
                old = int(gr)
                new = old + amount
                if not 0 <= new <=22: return 'Out of frets!'
                trans += str(new)
                if (old < 10) and (new >= 10):
                    ins = len(trans) - 1
                    for j in range(0,6):
                        if not j == i:
                            if tab[j][ins-1:ins+1].isdigit(): shorten_dash = True
                    if not shorten_dash:
                        for j in range(0,6):
                            if not j == i:
                                tab[j] = tab[j][:ins] + "-" + tab[j][ins:]
                if (old >= 10) and (new < 10):
                    ins = len(trans)
                    add_dash = False
                    for j in range(0,6):
                        if not j == i:
                            if tab[j][ins-1:ins+1].isdigit(): add_dash = True
                    if add_dash:
                        trans += "-"
                    else:
                        for j in range(0,6):
                            if not j == i:
                                tab[j] = tab[j][:ins] + tab[j][ins+1:]
            else:
                if shorten_dash:
                    gr = gr[1:]
                    shorten_dash = False
                trans += gr
        tab[i] = trans
    return tab

def transpose(amount, tab):
    col_tab = list(map(list, zip(*tab)))

    for i, j in enumerate(col_tab):
        double = False
        for a in range(len(j)):
            if col_tab[i][a].isdigit() and col_tab[i+1][a].isdigit():
                double = True
                col_tab[i][a] = col_tab[i][a] + col_tab[i+1][a]

        if double:
            col_tab.remove(col_tab[i+1])

    for i, j in enumerate(col_tab):
        for a in range(len(j)):
            if j[a].isdigit(): 
                new_note = int(j[a]) + amount
                if new_note < 0 or new_note > 22:
                    return 'Out of frets!'
                else:
                    col_tab[i][a]  = str(new_note)

    for j, k in enumerate(col_tab):
        if any(len(x) > 1 for x in k):
            col_tab[j] = [i + '-' if len(i) < 2 else i for i in k]
            
    return [''.join(j) for i, j in enumerate(list(map(list, zip(*col_tab))))]

def transpose(amount, tab):
    position = []
    position_neg = False
    result = []
    for line in tab:
        res = ''
        for counter, letter in enumerate(line):
            if letter.isdigit():
                if line[counter-1].isdigit():
                    continue
                if line[counter+1].isdigit():
                    if (int(letter+line[counter+1]) + amount) <= 22:
                        res += str(int(letter+line[counter+1]) + amount)
                        if len(str(int(letter+line[counter+1]) + amount)) == 1:
                            position.append(counter)
                            position_neg = True
                    else:
                        return 'Out of frets!'
                else:
                    if len(str(int(letter) + amount)) == 2:
                        if int(letter) + amount < 0:
                            return 'Out of frets!'
                        res += str(int(letter) + amount)
                        position.append(counter)
                    else:
                        res += str(int(letter) + amount)
            else:
                res += letter
        result.append(res)

    position = list(set(position))
    position.sort()
    for counter, line in enumerate(result):
        added = 0
        for insert in position:
            if not position_neg:
                double_in_col = False
                for line2 in tab:
                    if line2[insert].isdigit() and line2[insert + 1].isdigit():
                        double_in_col = True
                if double_in_col:
                    if result[counter][insert + added].isdigit():
                        if result[counter][insert + added + 1].isdigit():
                            if not tab[counter][insert + 1].isdigit():
                                result[counter] = result[counter][:insert + added + 2] + result[counter][insert + added + 3:]
                else:
                    if result[counter][insert+added].isdigit():
                        if result[counter][insert+added+1].isdigit():
                            if tab[counter][insert+1].isdigit():
                                result[counter] = result[counter][:insert+added+2] +'-'+ result[counter][insert+added+2:]
                        else:
                            result[counter] = result[counter][:insert+added+1] +'-'+ result[counter][insert+added+1:]
                    else:
                        result[counter] = result[counter][:insert + added + 1] + '-' + result[counter][insert + added + 1:]
                    added += 1
            else:
                double_in_col = False
                for line2 in result:
                    if line2[insert+added].isdigit() and line2[insert+1+added].isdigit():
                        double_in_col=True
                if double_in_col:
                    if result[counter][insert + added].isdigit():
                        if not result[counter][insert + added + 1].isdigit():
                            if tab[counter][insert + 1].isdigit():
                                result[counter] = result[counter][:insert + added + 1] + '-' + result[counter][insert + added + 1:]
                else:
                    if result[counter][insert + added].isdigit():
                        if not result[counter][insert + added + 1].isdigit():
                            if tab[counter][insert + 1].isdigit():
                                added -= 1
                                continue
                    result[counter] = result[counter][:insert + added + 2] + result[counter][insert + added + 3:]
                    added -= 1
    return result


def transpose(amount, tab):    
    resultTab = ['' for tabStr in tab]
    numChars = set(char for char in '0123456789')
    
    i = 0
    while i < len(tab[0]):
        for tabNum, tabStr in enumerate(tab):
            try:
                valStr = tabStr[i]
                
                # Are we looking at the second character of a two character number
                if not (i > 0 and valStr in numChars and tabStr[i-1] in numChars): 
                    
                    # If the next character is a number to complete a two character number
                    if valStr is not '-' and i+1 < len(tabStr) and tabStr[i+1] in numChars:
                        valStr += tabStr[i+1]

                    val = int(valStr)
                    transposedVal = val + amount

                    if transposedVal > 22 or transposedVal < 0:
                        return 'Out of frets!'

                    resultTab[tabNum] += str(transposedVal)
                    
            except ValueError:
                resultTab[tabNum] += tabStr[i]
                
        maxLineLength = max([len(s) for s in resultTab])
        minLineLength = min([len(s) for s in resultTab])

        shouldTrim = False
        if maxLineLength != minLineLength:
            # This happens if the input string had a two character number that went down to a one
            # character number after the transpose
            shouldTrim = all([ (len(s) == minLineLength or s[len(s)-1] == '-') for s in resultTab])
            if shouldTrim:
                i += 1
        
        
        for resTabNum, resTabStr in enumerate(resultTab):
            if shouldTrim:
                resultTab[resTabNum] = (resTabStr)[0:minLineLength]
            resultTab[resTabNum] = (resTabStr + '-')[0:maxLineLength]
            
        i += 1
    
    return resultTab


import re

empty = [''] * 6
separator = ['-'] * 6
bar = ['|'] * 6

def transpose(amount, tab):

    # "And if you listen very hard
    #  The tune will come to you at last..."

    #           -- Stairway to Heaven (1971)

    try:
        result = empty
        chunk = empty

        for i in range(len(tab[0])):
            column = get_column(tab, i)
            chunk = merge(chunk, column)
    
            if chunk == separator or chunk == bar:
                result = merge(result, chunk)
                chunk = empty
            elif column == separator:
                recalculated = recalculate(amount, chunk)
                result = merge(result, recalculated)
                chunk = empty

        return result
    except OutOfFretsException as oof:
        return str(oof)

def get_column(tab, column_idx):
    return [tab[string][column_idx] for string in range(0, 6)]

def merge(left, right):
    return [left[i] + right[i] for i in range(0, 6)]

def recalculate(amount, chunk):
    recalculated = [shift(string, amount) for string in chunk]
    max_length = max([len(s) for s in recalculated])
    padded = [string.ljust(max_length, '-') for string in recalculated]
    return shrink(padded)

def shrink(chunk):
    new_chunk = empty
    for i in range(len(chunk[0])):
        current_column = get_column(chunk, i)
        next_column = get_column(chunk, i + 1) if i + 1 < len(chunk[0]) else None

        if current_column == separator and next_column == separator:
            continue
        else:
            new_chunk = merge(new_chunk, current_column)

    return new_chunk

def shift(string, amount):
    tokens = re.findall(r'[^\d]*[0-9]+[^\d]*', string)
    if len(tokens) > 0:
        numbers = [int(re.findall(r'[0-9]+', t)[0]) for t in tokens]
        shifted = [(n, n + amount) for n in numbers]
        if (any(s[1] > 22 or s[1] < 0 for s in shifted)):
            raise OutOfFretsException()
        else:
            replaced = [tokens[i].replace(str(shifted[i][0]), str(shifted[i][1])) for i in range(len(tokens))]
            return "".join(replaced)
    else:
        return string

class OutOfFretsException(Exception):
    def __init__(self):
        Exception.__init__(self, 'Out of frets!')

def write_bar(new_bar, beat, amount):                                               
    new_beat = [str(int(fret) + amount) if fret.isnumeric() else fret for fret in beat]
    values = [int(fret) for fret in new_beat if fret.lstrip('-').isnumeric()]       
    if values and (max(values) > 22 or min(values) <= 0):                           
        raise ValueError('Out of frets!')                                           
    formatted_beat = [beat.ljust(len(max(new_beat, key=len)), '-') for beat in new_beat]
    for beat in range(len(formatted_beat)):                                         
        new_bar[beat] += formatted_beat[beat]                                       
    return new_bar                                                                  
                                                                                    
def transpose_bar(amount, bar):                                                     
    new_bar = [''] * 6                                                              
    frets = [''] * 6                                                                
    joined = False                                                                  
    for beat in range(len(bar[0])):                                                 
        if not joined:                                                              
            previous_beat = frets                                                   
        else:                                                                       
            previous_beat = [''] * 6                                                
        joined = False                                                              
        frets = [gen[beat] for gen in bar]                                          
        for fret in range(len(frets)):                                              
            if frets[fret].isnumeric() and previous_beat[fret].isnumeric():         
                previous_beat[fret] += frets[fret]                                  
                joined = True                                                       
        new_bar = write_bar(new_bar, previous_beat, amount)                         
                                                                                    
    if not joined:                                                                  
        new_bar = write_bar(new_bar, frets, amount)                                 
                                                                                    
    return new_bar                                                                  
                                                                                    
                                                                                    
def transpose(amount, tab):                                                         
    string_bars = [gen.split('|')[1:-1] for gen in tab]                             
    bars = list(zip(*string_bars))                                                  
    new_bars = [('e','B','G','D','A','E'),]                                         
    try:                                                                            
        for bar in bars:                                                            
            new_bars.append(transpose_bar(amount, bar))                             
        new_bars.append([''] * 6)                                                   
        transposed = list(zip(*new_bars))                                           
        return ['|'.join(gen) for gen in transposed]                                
    except ValueError as e:                                                         
        return str(e)   

class EndException(Exception):
    pass

class DoneAccumulatingException(Exception):
    pass

class OutOfFretsException(Exception):
    pass

def get_column(array, index):
    ret = []
    try:
        for line in array:
            ret.append(line[index])
        return ret
    except IndexError:
        raise EndException()
    
    
def add_to_tab(tab, column):
    for i, value in enumerate(column):
        tab[i] += value


def accumulate(accumulate_array, column):
    if set(map(lambda x: str.isnumeric(x), column)) == {False}:
        raise DoneAccumulatingException()
    else:
        for i, value in enumerate(column):
            accumulate_array[i] += value


def adjust_accumulator(accumulator, adjustment):
    
    column_width = 0
    adjusted_values = []
    for item in accumulator:
        item = item.strip('-')
        if str.isnumeric(item):
            new_value = int(item) + adjustment
            if new_value < 0 or new_value > 22:
                raise OutOfFretsException()
            item = str(new_value)
        adjusted_values.append(item)
        if len(item) > column_width:
            column_width = len(item)

    new_accumulator = [x + ('-' * (column_width - len(x))) for x in adjusted_values]
    return new_accumulator

def transpose(amount, tab):

    idx = 0
    new_tab = [''] * 6
    aa = [''] * 6
    while True:
        try:
            column = get_column(tab, idx)
        except EndException:
            break
        
        try:
            accumulate(aa, column)
        except DoneAccumulatingException:
            try:
                aa = adjust_accumulator(aa, amount)
            except OutOfFretsException:
                return "Out of frets!"

            add_to_tab(new_tab, aa)
            add_to_tab(new_tab, column)
            aa = [''] * 6
            
            #print("UPDATED TAB")
            #for item in new_tab:
            #    print(item[-20:])

        idx += 1
        
    return new_tab