mvanga/guitar_theory.py

## guitar_theory.py

# MIT License
#
# Copyright (c) 2021 Manohar Vanga
#
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in all
# copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.


import re
from pprint import pprint
from final import chromatic, make_intervals2
from collections import defaultdict

def chromatic_wrapping(key, n):
    notes = chromatic(key)
    return [notes[i % len(notes)] for i in range(n)]

def filter_by_key(scale, filter_list):
    filtered = []
    for notes in scale:
        filtered.append([x for x in notes if x in filter_list])
    return filtered

# nfrets: number of frets. Should include fret 0; for a 21-fret guitar, nfrets=22
# nstrings: number of strings
class Fretboard:
    def __init__(self, nstrings, nfrets, key, tuning=['E', 'A', 'D', 'G', 'B', 'E'], lowest_pitch=2):
        self.nstrings = nstrings
        self.nfrets = nfrets
        self.tuning = tuning
        self.key = key
        # Generate data about mappings between notes and intervals in given key
        self.note_to_interval, self.interval_to_note = self.init_key_mappings(key)
        self.notes_in_key = list(self.interval_to_note.values())
        # Generate data about each fret: notes, intervals
        self.notes = [filter_by_key(chromatic_wrapping(tuning[i], nfrets + 1), self.notes_in_key) for i in range(nstrings)]
        self.intervals = self.init_intervals()
        self.intervals2 = self.init_intervals2()
        # Analyzing the fretboard: pitches, wraparounds, and per-string offsets
        self.pitches = self.init_pitches(lowest_pitch)
        self.wraparounds = self.init_wraparounds()
        self.offsets = self.init_per_string_offsets()

    def init_key_mappings(self, key):
        interval_to_note = make_intervals2(key)
        note_to_interval = defaultdict(lambda: [])
        for (interval, note) in interval_to_note.items():
            note_to_interval[note].append(interval)
        return dict(note_to_interval), interval_to_note

    def init_intervals(self):
        intervals = [[[] for fret in range(self.nfrets)] for string in range(self.nstrings)]
        for string in range(self.nstrings):
            for fret in range(self.nfrets):
                for note in self.notes[string][fret]:
                    if note in self.note_to_interval.keys():
                        for interval in self.note_to_interval[note]:
                            intervals[string][fret].append(interval)
        return intervals

    def init_intervals2(self):
        intervals = [[[] for fret in range(self.nfrets)] for string in range(self.nstrings)]
        for string in range(self.nstrings):
            for fret in range(self.nfrets):
                for note in self.notes[string][fret]:
                    intervals[string][fret] += self.note_to_interval[note]
        return intervals

    def init_per_string_offsets(self):
        '''Find the offsets of equivalent frets relative to each string'''
        offsets = []
        offsets0 = [-sum(self.wraparounds[:string]) for string in range(self.nstrings)]
        for string in range(self.nstrings):
            offsets.append([x - offsets0[string] for x in offsets0])
        return offsets

    def init_wraparounds(self):
        wraparounds = [0 for x in range(self.nstrings)]
        for string in range(self.nstrings):
            for fret in range(self.nfrets):
                if (string < 5 and
                    self.notes[string + 1][0] == self.notes[string][fret] and
                    self.pitches[string + 1][0] == self.pitches[string][fret]):
                    wraparounds[string] = fret
        return wraparounds

    def init_pitches(self, lowest_pitch):
        pitches = [[None for i in range(self.nfrets)] for j in range(self.nstrings)]
        next_pitch = None
        for string in range(self.nstrings):
            next_pitch_set = False
            if string == 0:
                current_pitch = lowest_pitch
            else:
                current_pitch = next_pitch
            for fret in range(self.nfrets):
                if 'C' in self.notes[string][fret]:
                    current_pitch += 1
                if (not next_pitch_set) and string < 5 and self.notes[string + 1][0] == self.notes[string][fret]:
                    next_pitch_set = True
                    next_pitch = current_pitch
                pitches[string][fret] = current_pitch
        return pitches

    def frontier(self, string, fret):
        '''Given a fret, find its equivalents on all strings'''
        relative_offset = self.offsets[string]
        frets = [x + fret for x in relative_offset]
        return frets

    def iter_forward(self, start_string=0, start_fret=0, strict=False):
        frontier = self.frontier(start_string, start_fret)
        for string in range(self.nstrings):
            for fret in range(max(frontier[string] + (1 if strict else 0), 0), self.nfrets):
                yield (string, fret, self.intervals[string][fret])

    def iter_backward(self, start_string=0, start_fret=0, strict=False):
        frontier = self.frontier(start_string, start_fret)
        for string in range(self.nstrings):
            for fret in range(max(frontier[string] - (1 if strict else 0), 0), -1, -1):
                yield (string, fret, self.intervals[string][fret])

    def find_interval_on_string(self, interval, string):
        return [index
                for (index, fret_intervals)
                in enumerate(self.intervals[string])
                if interval in fret_intervals]

    def find_interval_forward(self, interval, start_string, start_fret, strict=False):
        candidates = []
        for string, fret, intervals in self.iter_forward(start_string, start_fret, strict):
            if interval in intervals:
                candidates.append({
                    'location': (string, fret),
                    'pitch': self.pitches[string][fret]
                })
        if candidates == []:
            return []
        min_pitch = min([x['pitch'] for x in candidates])
        return sorted([x['location'] for x in candidates if x['pitch'] == min_pitch])

    def find_interval_backward(self, interval, start_string, start_fret, strict=False):
        candidates = []
        for string, fret, intervals in self.iter_backward(start_string, start_fret, strict):
            if interval in intervals:
                candidates.append({
                    'location': (string, fret),
                    'pitch': self.pitches[string][fret]
                })
        if candidates == []:
            return []
        max_pitch = max([x['pitch'] for x in candidates])
        return sorted([x['location'] for x in candidates if x['pitch'] == max_pitch])

    def find_all_notes(self, mapping):
        search_space = {x: {} for x in mapping}
        for (string, interval) in mapping.items():
            search_space[string] = self.find_interval_on_string(interval, string)
        return search_space

    def find_all_notes2(self, mapping):
        return {string: self.find_interval_on_string(interval, string)
                for string, interval in mapping.items()}

    def find_all_chords(self, search_space, current_finger_pos, solutions, level=0):
        remaining = [x for x in current_finger_pos if current_finger_pos[x] == None]
        if remaining == []:
            solutions.append(current_finger_pos)
            return None

        pick = remaining[0]
        for potential in search_space[pick]:
            new_finger_pos = current_finger_pos.copy()
            new_finger_pos[pick] = potential
            self.find_all_chords(search_space, new_finger_pos, solutions, level + 1)

        if level == 0:
            return solutions

    def solve_scale(self, intervals, start_string, start_fret, level=0):
        out = []
        if intervals == []:
            return None
        locations = self.find_interval_forward(intervals[0], start_string, start_fret)
        for location in locations:
            fragments = self.solve_scale(intervals[1:], location[0], location[1], level + 1)
            out.append({'note': location, 'children': fragments})
        return out

    #def solve_scale_looping(self, original_intervals, start_string, start_fret, level=0, intervals=None):
    #    if level == 0 and intervals is None:
    #        intervals = original_intervals.copy()
    #    print(level, start_string, start_fret)
    #    out = []
    #    if intervals == []:
    #        intervals = original_intervals.copy()
    #    locations = self.find_interval_forward(intervals[0], start_string, start_fret)
    #    if locations == []:
    #        return None
    #    for location in locations:
    #        fragments = self.solve_scale_looping(original_intervals, location[0], location[1], level+1, intervals[1:])
    #        out.append({'note': location, 'children': fragments})
    #    return out


#f = Fretboard(6, 21, 'G', ['D', 'A', 'D', 'G', 'A', 'D'])
f = Fretboard(6, 21, 'C')
#pprint(f.note_to_interval)

#print(f.frontier(1, 17))
#print('FORWARD')
#pprint(list(f.iter_forward(1, 17)))
#print('BACKWARD')
#pprint(list(f.iter_backward(1, 17)))
#pprint(f.intervals[0][0])
#pprint(f.find_interval_on_string('8', 0))
#find_interval_forward('2', start_string, start_fret, strict=False):
#print(f.find_interval_forward('7', 1, 12))
#print(f.find_interval_backward('7', 3, 5))
scales = f.solve_scale(['1', '2', '3', '4', '5', '6', '7', '8'], 0, 0)
#scales2 = f.solve_scale_looping(['1', '2', '3', '4', '5', '6', '7'], 0, 0)
#pprint(scales, indent=4)
#pprint(scales[0], indent=4)

def traverse(scales):
    output = []
    for x in scales:
        if x['children'] is None:
            output.append([x['note']])
        else:
            for fragment in traverse(x['children']):
                output.append([x['note']] + fragment)
    return output

#pprint(traverse(scales))
patterns = traverse(scales)
#pprint(patterns)
#pprint(len(patterns))

from itertools import tee

def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)

def filter_cascading(solutions):
    filtered = []
    for scale in solutions:
        # No consecutive note should have the same string
        failed = False
        for note1, note2 in pairwise(scale):
            #print(note1, note2)
            if note1[0] == note2[0]:
                failed = True
                break
        if not failed:
            filtered.append(scale)
    return filtered

def filter_boxed(solutions, min_string, min_fret, max_string, max_fret):
    filtered = []
    for solution in solutions:
        strings = list(map(lambda x: x[0], solution))
        frets = list(map(lambda x: x[1], solution))
        if min(frets) < min_fret or max(frets) > max_fret:
            continue
        if min(strings) < min_string or max(strings) > max_string:
            continue
        filtered.append(solution)
    return filtered

pprint(filter_boxed(patterns, 0, 0, 5, 3))

def filter_fingerings_min_span(solutions):
    #l = list(map(lambda x: None if x == 0 else x[1], solutions[300]))
    #l = list(map(lambda x: None if x == 0 else x[1], solutions[300]))
    #print(solutions[300], l, max(l) - min(l) + 1)
    spans = []
    for solution in solutions:
        frets = list(map(lambda x: x[1], solution))
        span = max(frets) - min(frets) + 1
        spans.append(span)
    #spans = [max(x) - min(x) + 1 for x in [map(lambda x: x[1], z) for z in solutions]]
    print('min span is: {}'.format(min(spans)))
    #print(list(zip(solutions, spans)))
    return [x for i, x in enumerate(solutions) if spans[i] == min(spans)]

#pprint(filter_fingerings_min_span(filter_cascading(patterns)))
#pprint(filter_boxed(patterns, 0, 5, 5, 10))
#pprint(filter_cascading(patterns))
#pprint(f.notes_in_key)
#pprint(f.notes)
#pprint(filter_by_key(chromatic_wrapping('C', 21), f.notes_in_key))
#pprint(f.notes[0][0])
#pprint(f.notes[5][0])
#pprint(f.notes[5][12])
#pprint(f.notes[5][12])
#pprint(f.intervals)
#pprint(f.intervals2)
#assert(f.intervals == f.intervals2)
#pprint(f.intervals[0][0])
#pprint(f.intervals[5][0])
#pprint(f.intervals[5][12])
#pprint(f.intervals[5][12])
#pprint(f.pitches)
#pprint(list(reversed(f.pitches)))

pprint(f.find_all_notes2({0: '1', 1: '3', 2: '5'}))

search_space = f.find_all_notes2({0: '1', 1: '3', 2: '5'})
print(search_space)
pprint(f.find_all_chords(search_space, {x: None for x in search_space}, []))

def filter_min_span(solutions):
    spans = [max(x.values()) - min(x.values()) + 1 for x in solutions]
    return [x for i, x in enumerate(solutions) if spans[i] == min(spans)]

def filter_lower(solutions):
    pos = [min(x.values()) for x in solutions]
    return [x for i, x in enumerate(solutions) if pos[i] == min(pos)]

for a, b, c in [(0, 1, 2), (1, 2, 3), (2, 3, 4), (3, 4, 5)]:
    search_space = f.find_all_notes2({a: '1', b: '3', c: '5'})
    positions = f.find_all_chords(search_space, {x: None for x in search_space}, [])
    pprint(filter_lower(filter_min_span(positions)))

chords = {
    # Major
    'major':              '1,3,5',
    'major_6':            '1,3,5,6',
    'major_6_9':          '1,3,5,6,9',
    'major_7':            '1,3,5,7',
    'major_9':            '1,3,5,7,9',
    'major_13':           '1,3,5,7,9,11,13',
    'major_7_#11':        '1,3,5,7,#11',
    # Minor
    'minor':              '1,b3,5',
    'minor_6':            '1,b3,5,6',
    'minor_6_9':          '1,b3,5,6,9',
    'minor_7':            '1,b3,5,b7',
    'minor_9':            '1,b3,5,b7,9',
    'minor_11':           '1,b3,5,b7,9,11',
    'minor_7_b5':         '1,b3,b5,b7',
    # Dominant
    'dominant_7':         '1,3,5,b7',
    'dominant_9':         '1,3,5,b7,9',
    'dominant_11':        '1,3,5,b7,9,11',
    'dominant_13':        '1,3,5,b7,9,11,13',
    'dominant_7_#11':     '1,3,5,b7,#11',
    # Diminished
    'diminished':         '1,b3,b5',
    'diminished_7':       '1,b3,b5,bb7',
    'diminished_7_half':  '1,b3,b5,b7',
    # Augmented
    'augmented':          '1,3,#5',
    # Suspended
    'sus2':               '1,2,5',
    'sus4':               '1,4,5',
    '7sus2':              '1,2,5,b7',
    '7sus4':              '1,4,5,b7',
}

def make_chord_mapping(strings, name):
    intervals = chords[name].split(',')
    return {x: intervals[i] for i, x in enumerate(strings)}

#print(make_chord_mapping((0, 1, 2), 'major'))

def inversion(name, n):
    parts = chords[name].split(',')
    return ','.join(parts[n:] + parts[:n])

def first_inversion(name):
    return inversion(name, 1)

def second_inversion(name):
    return inversion(name, 2)

def third_inversion(name):
    return inversion(name, 3)

#print(first_inversion('major'))
#print(second_inversion('major'))
#print(third_inversion('major_7'))
#pprint(f.offsets)
#pprint(list(f.iter_forward(4, 5)))

f = Fretboard(6, 12, 'C', ['D', 'A', 'D', 'G', 'A', 'D'])
scales = f.solve_scale(['1', '3', '5', '7', '8'], 1, 3)
patterns = traverse(scales)
pprint(patterns)
print(len(patterns))

for p in patterns:
    x = p + list(reversed(p[1:4]))
    val = ['\\tab{' + str(6 - string) + '}{' + str(fret) + '}' for string, fret in x]
    print('\\startextract')
    print('  \\Notes ' + ' '.join(val[:4]) + ' \\en')
    print('  \\bar')
    print('  \\Notes ' + ' '.join(val[4:]) + ' \\en')
    print('\\endextract')

	# MIT License
	#
	# Copyright (c) 2021 Manohar Vanga
	#
	# Permission is hereby granted, free of charge, to any person obtaining a copy
	# of this software and associated documentation files (the "Software"), to deal
	# in the Software without restriction, including without limitation the rights
	# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
	# copies of the Software, and to permit persons to whom the Software is
	# furnished to do so, subject to the following conditions:
	#
	# The above copyright notice and this permission notice shall be included in all
	# copies or substantial portions of the Software.
	#
	# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
	# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
	# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
	# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
	# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
	# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
	# SOFTWARE.


	import re
	from pprint import pprint
	from final import chromatic, make_intervals2
	from collections import defaultdict

	def chromatic_wrapping(key, n):
	notes = chromatic(key)
	return [notes[i % len(notes)] for i in range(n)]

	def filter_by_key(scale, filter_list):
	filtered = []
	for notes in scale:
	filtered.append([x for x in notes if x in filter_list])
	return filtered

	# nfrets: number of frets. Should include fret 0; for a 21-fret guitar, nfrets=22
	# nstrings: number of strings
	class Fretboard:
	def __init__(self, nstrings, nfrets, key, tuning=['E', 'A', 'D', 'G', 'B', 'E'], lowest_pitch=2):
	self.nstrings = nstrings
	self.nfrets = nfrets
	self.tuning = tuning
	self.key = key
	# Generate data about mappings between notes and intervals in given key
	self.note_to_interval, self.interval_to_note = self.init_key_mappings(key)
	self.notes_in_key = list(self.interval_to_note.values())
	# Generate data about each fret: notes, intervals
	self.notes = [filter_by_key(chromatic_wrapping(tuning[i], nfrets + 1), self.notes_in_key) for i in range(nstrings)]
	self.intervals = self.init_intervals()
	self.intervals2 = self.init_intervals2()
	# Analyzing the fretboard: pitches, wraparounds, and per-string offsets
	self.pitches = self.init_pitches(lowest_pitch)
	self.wraparounds = self.init_wraparounds()
	self.offsets = self.init_per_string_offsets()

	def init_key_mappings(self, key):
	interval_to_note = make_intervals2(key)
	note_to_interval = defaultdict(lambda: [])
	for (interval, note) in interval_to_note.items():
	note_to_interval[note].append(interval)
	return dict(note_to_interval), interval_to_note

	def init_intervals(self):
	intervals = [[[] for fret in range(self.nfrets)] for string in range(self.nstrings)]
	for string in range(self.nstrings):
	for fret in range(self.nfrets):
	for note in self.notes[string][fret]:
	if note in self.note_to_interval.keys():
	for interval in self.note_to_interval[note]:
	intervals[string][fret].append(interval)
	return intervals

	def init_intervals2(self):
	intervals = [[[] for fret in range(self.nfrets)] for string in range(self.nstrings)]
	for string in range(self.nstrings):
	for fret in range(self.nfrets):
	for note in self.notes[string][fret]:
	intervals[string][fret] += self.note_to_interval[note]
	return intervals

	def init_per_string_offsets(self):
	'''Find the offsets of equivalent frets relative to each string'''
	offsets = []
	offsets0 = [-sum(self.wraparounds[:string]) for string in range(self.nstrings)]
	for string in range(self.nstrings):
	offsets.append([x - offsets0[string] for x in offsets0])
	return offsets

	def init_wraparounds(self):
	wraparounds = [0 for x in range(self.nstrings)]
	for string in range(self.nstrings):
	for fret in range(self.nfrets):
	if (string < 5 and
	self.notes[string + 1][0] == self.notes[string][fret] and
	self.pitches[string + 1][0] == self.pitches[string][fret]):
	wraparounds[string] = fret
	return wraparounds

	def init_pitches(self, lowest_pitch):
	pitches = [[None for i in range(self.nfrets)] for j in range(self.nstrings)]
	next_pitch = None
	for string in range(self.nstrings):
	next_pitch_set = False
	if string == 0:
	current_pitch = lowest_pitch
	else:
	current_pitch = next_pitch
	for fret in range(self.nfrets):
	if 'C' in self.notes[string][fret]:
	current_pitch += 1
	if (not next_pitch_set) and string < 5 and self.notes[string + 1][0] == self.notes[string][fret]:
	next_pitch_set = True
	next_pitch = current_pitch
	pitches[string][fret] = current_pitch
	return pitches

	def frontier(self, string, fret):
	'''Given a fret, find its equivalents on all strings'''
	relative_offset = self.offsets[string]
	frets = [x + fret for x in relative_offset]
	return frets

	def iter_forward(self, start_string=0, start_fret=0, strict=False):
	frontier = self.frontier(start_string, start_fret)
	for string in range(self.nstrings):
	for fret in range(max(frontier[string] + (1 if strict else 0), 0), self.nfrets):
	yield (string, fret, self.intervals[string][fret])

	def iter_backward(self, start_string=0, start_fret=0, strict=False):
	frontier = self.frontier(start_string, start_fret)
	for string in range(self.nstrings):
	for fret in range(max(frontier[string] - (1 if strict else 0), 0), -1, -1):
	yield (string, fret, self.intervals[string][fret])

	def find_interval_on_string(self, interval, string):
	return [index
	for (index, fret_intervals)
	in enumerate(self.intervals[string])
	if interval in fret_intervals]

	def find_interval_forward(self, interval, start_string, start_fret, strict=False):
	candidates = []
	for string, fret, intervals in self.iter_forward(start_string, start_fret, strict):
	if interval in intervals:
	candidates.append({
	'location': (string, fret),
	'pitch': self.pitches[string][fret]
	})
	if candidates == []:
	return []
	min_pitch = min([x['pitch'] for x in candidates])
	return sorted([x['location'] for x in candidates if x['pitch'] == min_pitch])

	def find_interval_backward(self, interval, start_string, start_fret, strict=False):
	candidates = []
	for string, fret, intervals in self.iter_backward(start_string, start_fret, strict):
	if interval in intervals:
	candidates.append({
	'location': (string, fret),
	'pitch': self.pitches[string][fret]
	})
	if candidates == []:
	return []
	max_pitch = max([x['pitch'] for x in candidates])
	return sorted([x['location'] for x in candidates if x['pitch'] == max_pitch])

	def find_all_notes(self, mapping):
	search_space = {x: {} for x in mapping}
	for (string, interval) in mapping.items():
	search_space[string] = self.find_interval_on_string(interval, string)
	return search_space

	def find_all_notes2(self, mapping):
	return {string: self.find_interval_on_string(interval, string)
	for string, interval in mapping.items()}

	def find_all_chords(self, search_space, current_finger_pos, solutions, level=0):
	remaining = [x for x in current_finger_pos if current_finger_pos[x] == None]
	if remaining == []:
	solutions.append(current_finger_pos)
	return None

	pick = remaining[0]
	for potential in search_space[pick]:
	new_finger_pos = current_finger_pos.copy()
	new_finger_pos[pick] = potential
	self.find_all_chords(search_space, new_finger_pos, solutions, level + 1)

	if level == 0:
	return solutions

	def solve_scale(self, intervals, start_string, start_fret, level=0):
	out = []
	if intervals == []:
	return None
	locations = self.find_interval_forward(intervals[0], start_string, start_fret)
	for location in locations:
	fragments = self.solve_scale(intervals[1:], location[0], location[1], level + 1)
	out.append({'note': location, 'children': fragments})
	return out

	#def solve_scale_looping(self, original_intervals, start_string, start_fret, level=0, intervals=None):
	# if level == 0 and intervals is None:
	# intervals = original_intervals.copy()
	# print(level, start_string, start_fret)
	# out = []
	# if intervals == []:
	# intervals = original_intervals.copy()
	# locations = self.find_interval_forward(intervals[0], start_string, start_fret)
	# if locations == []:
	# return None
	# for location in locations:
	# fragments = self.solve_scale_looping(original_intervals, location[0], location[1], level+1, intervals[1:])
	# out.append({'note': location, 'children': fragments})
	# return out


	#f = Fretboard(6, 21, 'G', ['D', 'A', 'D', 'G', 'A', 'D'])
	f = Fretboard(6, 21, 'C')
	#pprint(f.note_to_interval)

	#print(f.frontier(1, 17))
	#print('FORWARD')
	#pprint(list(f.iter_forward(1, 17)))
	#print('BACKWARD')
	#pprint(list(f.iter_backward(1, 17)))
	#pprint(f.intervals[0][0])
	#pprint(f.find_interval_on_string('8', 0))
	#find_interval_forward('2', start_string, start_fret, strict=False):
	#print(f.find_interval_forward('7', 1, 12))
	#print(f.find_interval_backward('7', 3, 5))
	scales = f.solve_scale(['1', '2', '3', '4', '5', '6', '7', '8'], 0, 0)
	#scales2 = f.solve_scale_looping(['1', '2', '3', '4', '5', '6', '7'], 0, 0)
	#pprint(scales, indent=4)
	#pprint(scales[0], indent=4)

	def traverse(scales):
	output = []
	for x in scales:
	if x['children'] is None:
	output.append([x['note']])
	else:
	for fragment in traverse(x['children']):
	output.append([x['note']] + fragment)
	return output

	#pprint(traverse(scales))
	patterns = traverse(scales)
	#pprint(patterns)
	#pprint(len(patterns))

	from itertools import tee

	def pairwise(iterable):
	"s -> (s0,s1), (s1,s2), (s2, s3), ..."
	a, b = tee(iterable)
	next(b, None)
	return zip(a, b)

	def filter_cascading(solutions):
	filtered = []
	for scale in solutions:
	# No consecutive note should have the same string
	failed = False
	for note1, note2 in pairwise(scale):
	#print(note1, note2)
	if note1[0] == note2[0]:
	failed = True
	break
	if not failed:
	filtered.append(scale)
	return filtered

	def filter_boxed(solutions, min_string, min_fret, max_string, max_fret):
	filtered = []
	for solution in solutions:
	strings = list(map(lambda x: x[0], solution))
	frets = list(map(lambda x: x[1], solution))
	if min(frets) < min_fret or max(frets) > max_fret:
	continue
	if min(strings) < min_string or max(strings) > max_string:
	continue
	filtered.append(solution)
	return filtered

	pprint(filter_boxed(patterns, 0, 0, 5, 3))

	def filter_fingerings_min_span(solutions):
	#l = list(map(lambda x: None if x == 0 else x[1], solutions[300]))
	#l = list(map(lambda x: None if x == 0 else x[1], solutions[300]))
	#print(solutions[300], l, max(l) - min(l) + 1)
	spans = []
	for solution in solutions:
	frets = list(map(lambda x: x[1], solution))
	span = max(frets) - min(frets) + 1
	spans.append(span)
	#spans = [max(x) - min(x) + 1 for x in [map(lambda x: x[1], z) for z in solutions]]
	print('min span is: {}'.format(min(spans)))
	#print(list(zip(solutions, spans)))
	return [x for i, x in enumerate(solutions) if spans[i] == min(spans)]

	#pprint(filter_fingerings_min_span(filter_cascading(patterns)))
	#pprint(filter_boxed(patterns, 0, 5, 5, 10))
	#pprint(filter_cascading(patterns))
	#pprint(f.notes_in_key)
	#pprint(f.notes)
	#pprint(filter_by_key(chromatic_wrapping('C', 21), f.notes_in_key))
	#pprint(f.notes[0][0])
	#pprint(f.notes[5][0])
	#pprint(f.notes[5][12])
	#pprint(f.notes[5][12])
	#pprint(f.intervals)
	#pprint(f.intervals2)
	#assert(f.intervals == f.intervals2)
	#pprint(f.intervals[0][0])
	#pprint(f.intervals[5][0])
	#pprint(f.intervals[5][12])
	#pprint(f.intervals[5][12])
	#pprint(f.pitches)
	#pprint(list(reversed(f.pitches)))

	pprint(f.find_all_notes2({0: '1', 1: '3', 2: '5'}))

	search_space = f.find_all_notes2({0: '1', 1: '3', 2: '5'})
	print(search_space)
	pprint(f.find_all_chords(search_space, {x: None for x in search_space}, []))

	def filter_min_span(solutions):
	spans = [max(x.values()) - min(x.values()) + 1 for x in solutions]
	return [x for i, x in enumerate(solutions) if spans[i] == min(spans)]

	def filter_lower(solutions):
	pos = [min(x.values()) for x in solutions]
	return [x for i, x in enumerate(solutions) if pos[i] == min(pos)]

	for a, b, c in [(0, 1, 2), (1, 2, 3), (2, 3, 4), (3, 4, 5)]:
	search_space = f.find_all_notes2({a: '1', b: '3', c: '5'})
	positions = f.find_all_chords(search_space, {x: None for x in search_space}, [])
	pprint(filter_lower(filter_min_span(positions)))

	chords = {
	# Major
	'major': '1,3,5',
	'major_6': '1,3,5,6',
	'major_6_9': '1,3,5,6,9',
	'major_7': '1,3,5,7',
	'major_9': '1,3,5,7,9',
	'major_13': '1,3,5,7,9,11,13',
	'major_7_#11': '1,3,5,7,#11',
	# Minor
	'minor': '1,b3,5',
	'minor_6': '1,b3,5,6',
	'minor_6_9': '1,b3,5,6,9',
	'minor_7': '1,b3,5,b7',
	'minor_9': '1,b3,5,b7,9',
	'minor_11': '1,b3,5,b7,9,11',
	'minor_7_b5': '1,b3,b5,b7',
	# Dominant
	'dominant_7': '1,3,5,b7',
	'dominant_9': '1,3,5,b7,9',
	'dominant_11': '1,3,5,b7,9,11',
	'dominant_13': '1,3,5,b7,9,11,13',
	'dominant_7_#11': '1,3,5,b7,#11',
	# Diminished
	'diminished': '1,b3,b5',
	'diminished_7': '1,b3,b5,bb7',
	'diminished_7_half': '1,b3,b5,b7',
	# Augmented
	'augmented': '1,3,#5',
	# Suspended
	'sus2': '1,2,5',
	'sus4': '1,4,5',
	'7sus2': '1,2,5,b7',
	'7sus4': '1,4,5,b7',
	}

	def make_chord_mapping(strings, name):
	intervals = chords[name].split(',')
	return {x: intervals[i] for i, x in enumerate(strings)}

	#print(make_chord_mapping((0, 1, 2), 'major'))

	def inversion(name, n):
	parts = chords[name].split(',')
	return ','.join(parts[n:] + parts[:n])

	def first_inversion(name):
	return inversion(name, 1)

	def second_inversion(name):
	return inversion(name, 2)

	def third_inversion(name):
	return inversion(name, 3)

	#print(first_inversion('major'))
	#print(second_inversion('major'))
	#print(third_inversion('major_7'))
	#pprint(f.offsets)
	#pprint(list(f.iter_forward(4, 5)))

	f = Fretboard(6, 12, 'C', ['D', 'A', 'D', 'G', 'A', 'D'])
	scales = f.solve_scale(['1', '3', '5', '7', '8'], 1, 3)
	patterns = traverse(scales)
	pprint(patterns)
	print(len(patterns))

	for p in patterns:
	x = p + list(reversed(p[1:4]))
	val = ['\\tab{' + str(6 - string) + '}{' + str(fret) + '}' for string, fret in x]
	print('\\startextract')
	print(' \\Notes ' + ' '.join(val[:4]) + ' \\en')
	print(' \\bar')
	print(' \\Notes ' + ' '.join(val[4:]) + ' \\en')
	print('\\endextract')