Organise the Gregorian Church's Music

Question

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.

Answer 1

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.

Answer 2

Haskell - 152

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)

Answer 3

CJam - 61

C,q',/f{"FCGDAEB"_5<'#f++:s@m<7<:A-!{"Dorian scale in "A3=}*}

Try it at http://cjam.aditsu.net/

Answer 4

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].

Answer 5

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

Answer 6

Haskell - 140

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.

scales = [take 7 . drop i $ circle | i <- [0..11]]

In each scale constructed by this way, scale !! 3, the 4th element is the scale name.

Code

w=words
n=w"C G D A E B F# C# G# D# A# F"
f s="Dorian scale in "++[x!!3|x<-[take 7.drop i$n++n|i<-[0..]],all(`elem`x)s]!!0
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)

Answer 7

Scala, 130 128 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