Organise the Gregorian Church's Music

The year is 930, and the Gregorian Church is having a problem. They have thousands of pages of chant music, but the problem is that all the sheet music was simply thrown onto a pile instead of having any real organisation system:

Image by user gamerprinter at Cartographers' Guild.

The Church needs to organise all the sheet music, so they have hired a medieval software engineer to write a program to organise it for them. You are the software engineer that has been hired. However, the compilation process in medieval times involves the program being written onto paper by a team of slow biblical scribes. To decrease the time it takes for the team of scribes to compile your code, you must make the program as small as possible.

The Church wants the chant music to be organised based off the musical scale they are written in. All of the Church's chant music is written in Dorian scales. Given the notes of a certain piece of music, your program will output the Dorian scale that it is in. Here, I will explain exactly what a Dorian scale is. If you already know, you may skip this section.

There are 12 possible notes in any melody. Here they are in order:

C C# D D# E F F# G G# A A# B


A semitone (represented using a S) is incrementing one step to the right, wrapping around (so a semitone up from B would be back to C). A tone (represented using a T) is two semitones. For instance, a semitone up from F# would be G. A tone up from F# would be G#.

To create a Dorian scale, we start from any note in the list, and then move up in the following pattern, listing the notes that we encounter:

T, S, T, T, T, S


An example. I start from A. The notes of my Dorian scale becomes:

A
B  (up a tone)
C  (up a semitone)
D  (up a tone)
E  (up a tone)
F# (up a tone)
G  (up a semitone)


The scale has the notes A, B, C, D, E, F#, and G. Because I started from A, we will call this the Dorian scale in A. There are therefore 12 different Dorian scales, each of which are named after the note that they started from. Each of them use the same pattern of tones and semitones, just starting from a different position. If my explanation is not coherent you may also consult Wikipedia.

The input of the program can be given from whatever is appropriate for your program (e.g. STDIN, command line argument, raw_input()). It may be not pre-initialised in a variable. The input will be a list of comma seperated notes, representing the melody of the piece. There may be repeated notes. There will always be enough different notes in the input to be able to decisively deduce the scale of the piece. An example input:

B,B,D,E,D,B,A,G#,A,G#,E,D,F#,E,F#,E,F#,G#,A


The output of the program should be the string Dorian scale in X, where X is the starting note of the scale. The output of the example input:

Dorian scale in B


Comparing this with the Dorian scale in B (B C# D E F# G# A) we see that all the notes of the melody are within this scale. The note C# is unused in this case. However there are sufficient notes to unambiguously identify B Dorian as the correct key. No other Dorian scale fits, because whatever other scale we try, there is always at least one note of the melody that does not belong to the scale.

This is code golf, so the entry with the shortest number of characters wins. Ask in the comments if you have questions.

• So, what we should do is to only interpret the first tone/semitone? Aug 20, 2014 at 6:58
• ​​​​​​​​​​​​​​​@avall I'm sorry, I don't understand your question. The input won't always start with the tonic, if that's what you're asking. Aug 20, 2014 at 7:02
• Please provide us more examples. Especially those, which don't start with the tonic. Aug 20, 2014 at 7:03
• The inverse problem is Scale from key and mode Aug 20, 2014 at 7:35
• ​​​​​​​​​​​​​​​@David As per this meta question, I awarded the accept to the shortest answer after a waiting period of 12 days since I started the challenge. It just happened the CJam answer was posted right when I was going to accept the next shortest one. Sep 1, 2014 at 11:39

C, 171 146

i,b;main(int c,char**v){for(;c=v[1][i];)b|=c/65<<c*2%7+v[1][++i]%2*7;for(i=12;i--;)b&(1016056>>i)||printf("Dorian scale in %c%c",65+i*3%7,(i<5)*35);}


Parsing strings in C is not that easy, so I went for a more mathematical approach.

I take advantage of the Circle of Fifths. If we arrange the notes in the following order based on counting up 7 semitones at a time (known as a "fifth"), we find that all the notes permitted in any given scale form a consecutive block of 7 notes and all the prohibited notes form a consecutive block of 5 notes.

F C G D A E B F# C# G# D# A#


(it's a circle, it wraps back around to F at the end.)

The position of a natural note in the above sequence can be calculated as (ASCII code) * 2 % 7. Then if the next character is odd (applies to # but not comma, space or zero byte) we add 7 to make it sharp. We store a bitmap of the notes that have been used.

The number 243 (binary 11111000) corresponds to the notes prohibited in the scale of A# Dorian. I multiplied this by (1<<12)+1=4097 to give the magic number 1016056. This is rightshifted to check (by ANDing) if the melody contains prohibited notes for each of the 12 scales in turn. If the melody does not contain prohibited notes, the scale is printed.

For the output we need to print the scale name encoded in the reverse order to cycle of fifths above, remember we are going backwards because we are rightshifting.) The ASCII sequence ADGCFBEADGCF is generated by 65+i*3%7. For the first five of these a sharp must also be printed.

Ungolfed code

i,b;
main(int c,char**v){
for(;c=v[1][i];)                          //for each character in first commanline argument v[1]
//if it is a letter (assume uppercase, ASCII 65 or over)
b|=c/65<<c*2%7+v[1][++i]%2*7;               //convert to position in the circle of fifths.
//Add 7 if the next character is odd (ASCII'#')
//leftshift 1 by this number and OR this with the contents of b.

for(i=12;i--;)b&(1016056>>i)||printf         //if melody includes no prohibited notes for the scale i, print
("Dorian scale in %c%c",65+i*3%7,(i<5)*35); //the scale letter, and a # (ASCII 35) if required, otherwise an ASCII 0.
}


Invalid input behaviour: If insufficient notes are supplied to unambiguously determine the scale, it will output all possible scales. If an impossible combination of notes is supplied, it will output nothing. Notes must be delimited by a comma (or other non-whitespace character with an even ASCII code <= 64.) Spaces cannot be used as everything after the first space would be considered a different argument. ASCII codes >64 will be interpreted as notes in the manner described.

• It shocked me that the circle of fifths has this property! Maybe I can use it to golf a bit more.
– Ray
Aug 21, 2014 at 21:37
• @Ray This is actually why we have the set of notes that we have. The octave has a frequency ratio 2:1. The fifth as defined by Pythagoras has a ratio of 3:2 and is the most important musical interval after the octave. Because 1.5^12 is close to but not equal to 2^7, the modern equal tempered fifth is squeezed down to 1.4983 so that exactly 12 fifths fit in 7 octaves. The old fashioned solution was to only use 7 notes out of the available 12 from the circle. That's why we have a scale based on 7 unevenly spaced notes. It's not some random convention, there's some solid maths behind it. Aug 21, 2014 at 22:23
• There are a number of instruments that arrange notes in fifths for convenience reasons (the violin is tuned in this way, and the bass guitar is tuned in fourths, which is a ratio of 4:3). The most striking example (and the only instrument I know of that has notes layed out in a circle of fifths for good acoustic design) is the steelpan: google.es/patents/US7696421 . With this layout it doesn't matter if the note next to the one you are hitting rings a bit. Aug 21, 2014 at 22:45

w=words
n=w"C C# D D# E F F# G G# A A# B"
f s="Dorian scale in "++[n!!i|i<-[0..11],all(elem[(n++n)!!(i+j)|j<-[0,2,3,5,7,9,10]])s]!!0
main=interact$f.w  Ungolfed type Note = String type Scale = [Note] notes :: [Note] notes = words "C C# D D# E F F# G G# A A# B" isScale :: Scale -> [Note] -> Bool isScale scale notes = all (elem scale) notes takeScale :: Int -> Scale takeScale i = [(notes ++ notes) !! (i + j) | j <- [0, 2, 3, 5, 7, 9, 10]] findScale :: [Note] -> Note findScale xs = head [notes !! i | i <- [0..11], isScale (takeScale i) xs] main = interact (("Dorian scale in "++) . findScale . words)  CJam - 61 C,q',/f{"FCGDAEB"_5<'#f++:s@m<7<:A-!{"Dorian scale in "A3=}*}  Try it at http://cjam.aditsu.net/ • Wow, this must be my quickest win.. less than 1 minute :) Sep 1, 2014 at 10:45 Python 2 - 177 characters It's not that short, but I find it the joy of Python to write multiple nested for loops in one line, even when not golfing. Unfortunately, I had to put the input statement on a separate line so that it would not execute more than once. j=set(raw_input().split(',')) print"Dorian Scale in",[x for x in[["A A# B C C# D D# E F F# G G#".split()[(b+n)%12]for n in[0,2,3,5,7,9,10]]for b in range(12)]if j<set(x)][0][0]  I don't use Python 3, but I believe this is a rare instance when the print statement would not need more characters. Since print is a function there, I would be able to offset the need for parentheses with the use of the * list unpacking operator to replace the last [0]. • You'd also be able to substitute input for raw_input and save 4 characters in Python 3. Aug 20, 2014 at 20:00 • "I find it the joy of Python to write multiple nested for loops in one line": but do you find joy in reading them? Aug 22, 2014 at 1:10 • @Wideshanks Of course not... it's all about the write-only code! Aug 22, 2014 at 3:25 Ruby - 132 12.times{|i|$*[0].split(?,)-(g=(0..6).map{|j|%w{C C# D D# E F F# G G# A A# B}[-i+=~(58>>j&1)]})==[]?(puts"Dorain scale in "+g[0]):g}


Input from command line args.
e.g. ruby dorianscale.rb B,B,D,E,D,B,A,G#,A,G#,E,D,F#,E,F#,E,F#,G#,A

Try it at: ideone

Make use of the Circle of Fifths property introduced by @steveverrill. If we let circle0 = words "C G D A E B F# C# G# D# A# F" and circle = circle0 ++ circle0, then we can construct all scales by taking consecutive 7 notes in circle.

main=interact$f.w  Ungolfed type Note = String type Scale = [Note] notes :: [Note] notes = words "C G D A E B F# C# G# D# A# F" scales :: [Scale] scales = [take 7 . drop i$ notes ++ notes | i <- [0..11]]

findScale :: [Note] -> Note
findScale xs = head [scale !! 3 | scale <- scales, all (elem scale) xs]

main = interact (("Dorian scale in "++) . findScale . words)


Scala, 130128 127

print("Dorian scale in "+(".#?".r findAllIn "FCGDAEBF#C#G#D#A#"*2 sliding(7)find{l=>args(0)split','forall(l contains _)}get 3))


Using the circle of fifths method. Input from command line args ie

scala dorianscale.scala B,B,D,E,D,B,A,G#,A,G#,E,D,F#,E,F#,E,F#,G#,A