StringsAndTabs
SRM 412 · 2008-07-30 · by Eryx
SRM 412 · 2008-07-30 · by Eryx · Brute Force, Simulation, Sorting, String Manipulation, String Parsing
Problem Statement
Problem Statement
Tablature is a popular way of notating songs played on fretted string instruments. Each line represents a string, and numbers written on the lines tell you which frets to press down when playing those strings. Here is an example:
Each open string may have a different pitch (i.e. may produce a higher or lower sound). For example, in standard guitar tuning, the pitch of the first string is 5 semitones higher than the second string. When you hold down the n-th fret (where 1 is the first fret) while playing a string, the resulting pitch is n semitones higher than that open string's pitch.
You are given aString[] tab containing the tablature for a song played on some instrument A (a guitar, for example). However, you want to play it on a different instrument B (maybe a mandolin, for example). You know the pitches of the open strings on each instrument, and they are given in the int[] s stringsA and stringsB. The i-th element of each int[] represents the pitch of the i-th string, and is given as the number of semitones above some base pitch 0. Both instrument A and instrument B have 35 frets. Frets numbered 10 through 35 are represented by the uppercase letters 'A' to 'Z'.
Your task is to write a program that will automatically transform the original tablature so it can be played on instrument B. Since different instruments have different ranges, you may also want to transpose the song to a different key. For this, you are given anint d, and you must increase the pitch of every note by d semitones (d can be negative, so you may end up lowering the pitches). Note that it is possible for different strings to play the same exact pitch at the same time in the original song. When that happens, the transformed tablature must also play that sound the same number of times as in the original version.
Sometimes there will be multiple ways to play a note on instrument B. In such cases, choose the string with the highest open pitch that can play that note. If there are multiple such strings, choose the bottom-most one among them (strings are listed from top to bottom). For chords, apply that same rule to each individual note in the chord. You must assign the notes in order, starting with the note that has the highest pitch, then the note with the second-highest pitch, and so on. You can only play a single note on each string, so only consider unused strings when assigning the notes of a chord. If you are unable to find a valid way to play a note or chord on instrument B using these rules, fill the entire column with lowercase 'x' characters instead. Return aString[] containing the transformed tablature for instrument B.
------------ -3---------- -------0---- ---2-------- -------0---- ------------The top line is the first string, the line below that is the second string, and so on. Tablature is read from left to right, and the i-th column represents the notes played at time i. In this example, there are no numbers in column 0, so this means that nothing is played at time 0. At time 1, a note is played by holding down the 3rd fret of the second string and plucking that string. At time 3, a note is played on the 2nd fret of the fourth string. Finally, at time 7, there are two notes played simultaneously as a chord. The number 0 means that you should pluck a string without holding down a fret. This is called an open string. In this example, you play the open third and fifth strings simultaneously.
Each open string may have a different pitch (i.e. may produce a higher or lower sound). For example, in standard guitar tuning, the pitch of the first string is 5 semitones higher than the second string. When you hold down the n-th fret (where 1 is the first fret) while playing a string, the resulting pitch is n semitones higher than that open string's pitch.
You are given a
Your task is to write a program that will automatically transform the original tablature so it can be played on instrument B. Since different instruments have different ranges, you may also want to transpose the song to a different key. For this, you are given an
Sometimes there will be multiple ways to play a note on instrument B. In such cases, choose the string with the highest open pitch that can play that note. If there are multiple such strings, choose the bottom-most one among them (strings are listed from top to bottom). For chords, apply that same rule to each individual note in the chord. You must assign the notes in order, starting with the note that has the highest pitch, then the note with the second-highest pitch, and so on. You can only play a single note on each string, so only consider unused strings when assigning the notes of a chord. If you are unable to find a valid way to play a note or chord on instrument B using these rules, fill the entire column with lowercase 'x' characters instead. Return a
Notes
- The input tablature tab is not necessarily created using the rules given.
Constraints
- tab will contain between 1 and 50 elements, inclusive.
- Each element of tab will contain between 1 and 50 characters, inclusive.
- Each element of tab will contain the same number of elements.
- stringsA and tab will contain the same number of elements.
- Each element of stringsA will be between -50 and 50, inclusive.
- stringsB will contain between 1 and 50 elements, inclusive.
- Each element of stringsB will be between -50 and 50, inclusive.
- d will be between -50 and 50, inclusive.
- Each element of tab will contain only dashes ('-'), digits ('0'-'9'), and uppercase letters ('A'-'Z').
Examples
0)
{"-----------------",
"-------------0-1-",
"---------0-2-----",
"---0-2-3---------",
"-3---------------",
"-----------------"}
{28,23,19,14,9,4}
{9}
0
Returns: {"-3-5-7-8-A-C-E-F-" }
This sequence of sounds (an octave of a major scale), played on several guitar strings, could be also played on a single string (the 5th one).
1)
{"-4457754-20024422-4457754-20024200-"}
{0}
{28,23,19,14,9,4}
12
Returns: {"-----------------------------------", "-----------------------------------", "----00---------------00------------", "-223--32-0--02200-223--32-0--020---", "----------33---------------33---33-", "-----------------------------------" }
This time, we have a sequence of sounds played on a single string (the beginning of Beethoven's Ode to Joy), and we want to play it on several strings of the guitar. We also make each sound higher by 12 semitones.
2)
{"-----------------------------------",
"-----------------------------------",
"----00---------------00------------",
"-223--32-0--02200-223--32-0--020---",
"----------33---------------33---33-",
"-----------------------------------"}
{28,23,19,14,9,4}
{33,28,24,31}
12
Returns: {"-----------------------------------", "-001--10-----00---001--10-----0----", "---------2002--22---------2002-200-", "----00---------------00------------" }
We translate the guitar tablature from the previous example to be played on a ukulele. Note that the strings of a ukulele are not ordered from highest to lowest.
3)
{"-----0------2-2222--0-------0-",
"----0------2---222---5-----55-",
"---0------2-----22----9---999-",
"--0------2-------2-----E-EEEE-",
"-0------2---------------------",
"0------2----------------------"}
{28,23,19,14,9,4}
{33,28,28}
12
Returns: {"xxx-27-xx-049-999x--7777-777x-", "xxx----xx-------5x---------Cx-", "xxx3---xx0-----99x--------CCx-" }
It is sometimes impossible to play a chord, for example, when one of the sounds is too low for the second instrument, or when it doesn't have enough strings.
4)
{"---H-----T----Q-----------B-------U---------------",
"------E---E---E-E---------Y--------------V--9----W",
"-X-----H-ZM--Y---3-------H-------X-B-M-----9-V--O-",
"----------8--------T----RT----------1-------U-W---",
"---------T--S-----O---T--------------KQ------7-QG-",
"------------7----O-------------L--8-U-------9----T",
"-----------2---------T--------U--H--------Z----Z--",
"6H----V-------HZ-----ZL-AH-W-MEO-8-------------FI5",
"B--------V--V---Q-----H-A-M-----I---7--1--B-U--P--",
"----O---O--S-V0---------------T---7--T------------",
"N-E-----3H6-VA---------E--D-F----------PK-9--T-SA-",
"-P---C-B-S---G---------L---7------4--U-N-------V-W",
"-------5R---------H------T-0K-P-----R----5L-------",
"------H----T-O----6I---------Q--F----0-L---------Y",
"-XG---------R-LV--U--ERYX-WAS-HERE------K--Z------",
"------2---------P--5-----X-----X---3--36-----A--7-",
"-NE---------V----VE----KS-6---0------6-------Y----",
"-A---A-----------U---H---K---------8--------------",
"---R----O6----JE--------LA-WR-B-----------Z-R--5--",
"-----R52----------L-----C--8--------E------PGV----",
"--3---------I--8--4---W-------R-Z----------0------",
"-M-R-----------------7--X---------------------4Y--",
"--0-X----Z-----P---I--3---9--U---K---7--8------U--",
"U--------TQ--A----YA-------------8----L-C------IT-",
"6--N-N-----UXPD--D------5--U--------8----R-------N",
"---------N---I---P-P----TO------3--E----X------V--",
"----------------L-O-----Z-5T-----3-QPT-2-------1--",
"Z------------C-L------D------Z--0------N----I-5--B",
"---T-H---V8------38--H-----------6-------U------7E",
"-A--1-Z-----7------D-------2---5-----------P--P---",
"-----O--------V------T-FC1------0Y20---C---E---7-N",
"2----S1--6----------6F-BJ-N----------A-------T----",
"--B83PN-A---F---F-ELZ------P---------8---------XY1",
"---R--------6-J---Q--X--I-D-5--9-4---C-2----E-----",
"----Y-------4----7----S---6----Z-----K-J----9-----",
"------------------SM25-9E--UQ--ZB------------W---B",
"--8-G---Y-----I-Q-P--NP---Q--------U--F-----------",
"-O--9L----------C---B--V--------------UN--X---Z---",
"9----6-----------L----W---K--C-6-----L--6----6----",
"DB----A-H1--M-H-------Q--G----Q5-------I-5-S--D---",
"---------N-----------2---------R------------V-R---",
"-2------2-Q----6-L-----Q25-----K-S----P5--0----G--",
"-YG-R2Y----Y-------B--A-GA--6-----A------------S-5",
"---0------------------8--B---O----------QM-----O--",
"G7----6--EM----------------J-8---------R----------",
"-------Q-LN------8------O--------L-0--------0-----",
"-----J---0-----Z-----------Z---LJ------8-----R----",
"--L-------N-X------N------4-R------S---------B----",
"----------M--V---1------------YL--U---4---K--H-OVE",
"--------Y-------C--5----I------------2--C---------"
}
{38,6,-43,16,7,28,49,24,5,41,40,-18,8,46,-33,40,17,-43,-16,-4,12,-48,-11,-24,45,-44,-36,0,36,29,26,-28,29,-49,-38,26,14,7,20,-12,-38,-6,11,30,-50,-7,6,11,-3,-11}
{-42,40,2,29,-32,-31,-43,34,-3,27,25,-37,-41,21,-8,-11,-14,-29,-49,-16,-21,8,-14,19,47,-46,48,-48,-45,-12,-18,15,-34,31,29,-27,-23,21,-37,32,-10,-34,38,-31,39,-37,9,1,21,33}
1
Returns: {"-0----------0-----------------------------x----x--", "-61G-EG-4I5U9VI25959-G62661H-70A-3-5-247-Dx1-C3x8I", "5-----0-451---4-00-----263-3----------050-x1-04x4A", "------------------------------------------x----x--", "-0---0---------------------------0--------x----x--", "--------------------------0---------------x----x--", "------0---------------------0-------------x---0x--", "26----9-231-3------9--5254---201--3-2-0---x-20-x-5", "-3--0-220----2-2-21-----433----1-----0191-x----x--", "--1--0------------------111----10-10-1--0-x--1-x--", "-----1---00-------1------------21---------x--2-x--", "------------------------------------------x----x--", "-----------------2---1-------0-21---------x----x--", "------------------------------------------x----x--", "-5---3-2-1--30-7---3--3-83724-423--2-2-8-2x-2--x--", "---------1----0---0---2-3---------------0-x--0-x--", "------------------------0-----------------x----x--", "--------------0--------------------0------x-1--x--", "------------------------------------------x----x--", "--0------------------1-0------1--1--------x----x--", "---1-----11---------0----2-----------4----x----x--", "-0----------------30----1-----------3-----x-4--x-4", "---------0---1--0--1----0---------1-------x----x--", "-------1--1-----1---0--------1-0------1---x-0--x--", "5--J-8H-2L0TPOC--664-D----3A68OF1E2-70-JAKx-0C2x4M", "---------------------------------------0--x----x--", "G-7LILH-IK-SVPHCIB7HHV573Q6S8PWQEJL-BN-KDPx7-M7xGX", "------------------------------------------x----x--", "---------------------------------1--------x----x--", "-----------------0---0------------------0-x----x--", "-----------------0-0-0---------0-0---1-0--x----x0-", "2-1-2----02----0-13---0-3-123-30-0--3--0--x210-x-2", "------------------------------------------x----x--", "0--00-------5-----1--------------------0--x----x-0", "1---20------20------0-------0-----0---1---x----x01", "22----12--0--2-------2---2----------------x----x--", "---2-----2--------1------1-1---------3-1--x----x--", "----------0----0------1-------------------x----x--", "------------------------------------------x----x--", "-00---------4---0-0--0-----0--0-----------x----x--", "-10------1------------3-7-60---0-1-102--0-x-4-0x--", "1-----------1----------------------0---1--x10--x--", "-3-0--8----87-4--228-0203434----0--2-00--0x-0--x5C", "-----------------1------1-11-------0------x----x--", "-3--0CE-1--D6C3-2357-F60532G0-0A---5---0--x--C-x5C", "---------2-----------2----2----------1----x----x--", "---3-5-502--24----8---5-7--03-6--1--44---5x446-x-6", "10---0---5----30-------15-------0------6--x---1x--", "--2-230-3-0---010--2--20-13-----321--3-3--x1-2-x3-", "--0-0----4--4-0----2--4-2----0---0--------x----x-5" }
Quite hard to play. [Are 'easter eggs' allowed in systests?]
6)
{"---H-----T----Q-----------B-------U---------------",
"------E---E---E-E---------Y--------------V--9----W",
"-X-----H-ZM--Y---3-------H-------X-B-M-----9-V--O-",
"----------8--------T----RT----------1-------U-W---",
"---------T--S-----O---T--------------KQ------7-QG-",
"------------7----O-------------L--8-U-------9----T",
"-----------2---------T--------U--H--------Z----Z--",
"6H----V-------HZ-----ZL-AH-W-MEO-8-------------FI5",
"B--------V--V---Q-----H-A-M-----I---7--1--B-U--P--",
"----O---O--S-V0---------------T---7--T------------",
"N-E-----3H6-VA---------E--D-F----------PK-9--T-SA-",
"-P---C-B-S---G---------L---7------4--U-N-------V-W",
"-------5R---------H------T-0K-P-----R----5L-------",
"------H----T-O----6I---------Q--F----0-L---------Y",
"-XG---------R-LV--U--ERYX-WAS-HERE------K--Z------",
"------2---------P--5-----X-----X---3--36-----A--7-",
"-NE---------V----VE----KS-6---0------6-------Y----",
"-A---A-----------U---H---K---------8--------------",
"---R----O6----JE--------LA-WR-B-----------Z-R--5--",
"-----R52----------L-----C--8--------E------PGV----",
"--3---------I--8--4---W-------R-Z----------0------",
"-M-R-----------------7--X---------------------4Y--",
"--0-X----Z-----P---I--3---9--U---K---7--8------U--",
"U--------TQ--A----YA-------------8----L-C------IT-",
"6--N-N-----UXPD--D------5--U--------8----R-------N",
"---------N---I---P-P----TO------3--E----X------V--",
"----------------L-O-----Z-5T-----3-QPT-2-------1--",
"Z------------C-L------D------Z--0------N----I-5--B",
"---T-H---V8------38--H-----------6-------U------7E",
"-A--1-Z-----7------D-------2---5-----------P--P---",
"-----O--------V------T-FC1------0Y20---C---E---7-N",
"2----S1--6----------6F-BJ-N----------A-------T----",
"--B83PN-A---F---F-ELZ------P---------8---------XY1",
"---R--------6-J---Q--X--I-D-5--9-4---C-2----E-----",
"----Y-------4----7----S---6----Z-----K-J----9-----",
"------------------SM25-9E--UQ--ZB------------W---B",
"--8-G---Y-----I-Q-P--NP---Q--------U--F-----------",
"-O--9L----------C---B--V--------------UN--X---Z---",
"9----6-----------L----W---K--C-6-----L--6----6----",
"DB----A-H1--M-H-------Q--G----Q5-------I-5-S--D---",
"---------N-----------2---------R------------V-R---",
"-2------2-Q----6-L-----Q25-----K-S----P5--0----G--",
"-YG-R2Y----Y-------B--A-GA--6-----A------------S-5",
"---0------------------8--B---O----------QM-----O--",
"G7----6--EM----------------J-8---------R----------",
"-------Q-LN------8------O--------L-0--------0-----",
"-----J---0-----Z-----------Z---LJ------8-----R----",
"--L-------N-X------N------4-R------S---------B----",
"----------M--V---1------------YL--U---4---K--H-OVE",
"--------Y-------C--5----I------------2--C---------"
}
{38,6,-43,16,7,28,49,24,5,41,40,-18,8,46,-33,40,17,-43,-16,-4,12,-48,-11,-24,45,-44,-36,0,36,29,26,-28,29,-49,-38,26,14,7,20,-12,-38,-6,11,30,-50,-7,6,11,-3,-11}
{38,6,-43,16,7,28,49,24,5,41,40,-18,8,46,-33,40,17,-43,-16,-4,12,-48,-11,-24,45,-44,-36,0,36,29,26,-28,29,-49,-38,26,14,7,20,-12,-38,-6,11,30,-50,-7,6,11,-3,-11}
0
Returns: {"-1--0---1--------11---100-2-0-1----1---0-------1-0", "---------------------------------------0----------", "--------------------------------------------------", "0---0-----3-------0--------0--------------10-----0", "--------------------------------------------------", "-----0------20------0-------0-----0-------------0-", "E-5JGJF-GI-QTNFAG95FFT351O4Q6NUOCHJ-9L-IBNZ5-K5ZEV", "-----1---00-------1-------------1-----------------", "--------00----0---------0--------------0------0-0-", "-0---9B-2-3A39003034-C3020-D---7-1-3-02------91D29", "------2------------2------0-----------------------", "--1------------------2-13------------0---------4--", "--------02--2-----2-----0--0-----1--2----------2--", "5--J-8H-2L0TPOC--664-D----3A68OF1E2-70-JAK3-0C2M4M", "-0---0--------3--2------2722-----0-3--------4-----", "-00---5----54-1-0-35----0101-------3------00----29", "-------2--3----32-0-1-4-0---0201----0-2---2-1--2--", "-0----------0----3---2-------1-32-----------------", "---------1---2--13-2-3--1-----0--02-----3------3--", "-0--0---0------2--------0-2----------0------------", "-----1-1-----0--------1-------------00---1-002-1--", "---------------------------------3-----1----------", "---------1------------1---------------------------", "---3-----33------51525---4-1---5-5---6-5--------5-", "-0-A-8A--C-O3PC--3-3-A0-00-B-1-4-------1-7---6-H2C", "------0---------------------0-----------------0---", "2--------0--2--------0----4--------4---2---21--1--", "10---01---2---3011-----304-4----0-----1-1--2-11---", "---1-----0--0--------121-1----2-1-0--11--1--1--3-1", "0---1-------6----------------------------------1--", "-------------------------------0-------------0----", "22-6--12-60--2-------2---5-----------7-5----------", "1-2-1-------6-----2----------32-------0---0----4-0", "--------------------------------------------------", "--------------------------------------------------", "--1--0------------------111----10-10-1--0----1----", "--1------02----0-1----0-1-1---00-0-----0--2-10---0", "-0-----------------0----0-------------------------", "--2-230-3-0---010--2--20-13-----321--3-3---1-2-13-", "---------1----0---0---------------------0----0----", "--------------------------2--------3-1------------", "-----0------0------0--0--01-1-1-0---------0----0--", "-------------------------------------------------0", "51202---564-6-2-1-14-1654--1-534-2--5-30----53-3-0", "--------------------------------------------------", "-------0-------------------0---0---0-0---0--0-----", "0--------0-----------------------------0----------", "---0------------------------0---------------0----0", "-2----11-----1-1-10----4222----0------020---------", "-10------3---2--------3-2--0---0-1-102--0---4-00--" }
We translate to the same instrument. (According to our previous rule, starting from lowest sounds, it was impossible to play.)
11)
{"012345---------",
"---------UVWXYZ"}
{-2,2}
{0}
0
Returns: {"xx0123---WXYZxx" }
The first two sounds are too low to be played on this string. The last two sounds are too high.
12)
{"0220----02--",
"75--75----57",
"------B9B9B9",
"--242424----"}
{33,28,24,31}
{33,28,28}
0
Returns: {"222222222222", "------------", "555555555555" }
One chord played in many different ways on a ukulele. Since we always start assigning the strings from the sound of the highest pitch, our method transforms them all to be played in the same way on a balalaika.
Submissions are judged against all 80 archived test cases, of which 8 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class StringsAndTabs with a public method vector<string> transformTab(vector<string> tab, vector<int> stringsA, vector<int> stringsB, int d) · 80 test cases · 2 s / 256 MB per case