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: EASY
Tags: Data structures
Skill types: Data structures

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('\\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):
	fret_pos = get_all_fret_positions(tab)
	pos = 0
	tab_new = ['' for string in tab]
	for fret_start in sorted(fret_pos):
		fret_end = fret_pos[fret_start]
		col = [string[fret_start:fret_end] for string in tab]
		(col, col_width) = apply_amount(col, amount)
		if col == 'Out of frets!':
			return 'Out of frets!'
		col = adjust_column_width(col, col_width)
		for (i, row) in enumerate(col):
			tab_new[i] = tab_new[i] + tab[i][pos:fret_start] + row
		pos = fret_end
	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)


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!'
				elif 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]
				if not (i > 0 and valStr in numChars and (tabStr[i - 1] in numChars)):
					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:
			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):
	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('[^\\d]*[0-9]+[^\\d]*', string)
	if len(tokens) > 0:
		numbers = [int(re.findall('[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
		idx += 1
	return new_tab