GO FOR ITに挑戦 (4) 旋律に隠された特徴
こんばんは、chen_jiです。
GO FOR ITへの挑戦も、残すところ後二つとなりました。そして、コンテストの締め切りまで、残すところ12時間を切りました。果たして全部解けるのでしょうか…。
4回目の本日は、「4) 旋律に隠された特徴」を解いてみました。（正確には解ききれなかったのですが。）
回を増すごとに難易度が上がっている気がします。後ろから順番に解いていったほうが良かったのかもしれません。
問題
本家のページをご参照下さい。
解答
今回は、すべてKonohaScriptでコーディングしました。
i), ii)の解答
Aの譜面と、Bの譜面の特徴量が異なり、Aの譜面とCの譜面の特徴量が同一となるようなプログラムを書きます。
まず、３つの譜面を見て、どの成分を特徴量に反映させるのか考えなければなりませんが、親切なことに、問題分の中にヒントが書かれています。
ヒント) 隣り合う音符同士の関係に注目してください。
隣り合う音符に注目すると良いらしいので、前音とのピッチの差分を求め、その合計値を算出することにしました。すると、もっともらしい値が出たのですが、AとBの特徴量が一致してしまいました。
そこで、差分の絶対値の合計値を算出することにして、さらに、全音が休符の場合は、もう一つ前の音との差分を考えることにしました。すると、AとCの特徴量が一致したので、これでよしということにしました。
#!/usr/local/bin/konoha """ 4-1and2.k license BSD author chen_ji <wakamori111 at gmail.com> """ using konoha.io.*; using konoha.math.*; // accidental string SHARP = "s"; DSHARP = "x"; FLAT = "b"; DFLAT = "d"; // note class class Note { boolean rest; boolean dotted; int pitch; int length; String accidental; Note(String pitch, String length, String accidental) { if (pitch == "") { _rest = true; _pitch = 0; } else { _rest = false; _pitch = (to int)pitch; } if (length.endsWith(".")) { _dotted = true; _length = (to int)length.substring(0, length.size - 1); } else { _dotted = false; _length = (to int)length; } if (accidental == "") { _accidental = ""; } else { _accidental = accidental; } considerAccidental(); considerLength(); } void considerAccidental() { int diff = 0; switch (pitch % 7) { case 0: case 1: diff = 0; break; case 2: case -1: diff = 1; break; case 3: case 4: case -2: diff = 2; break; case 5: case -3: case -4: diff = 3; break; case 6: case -5: diff = 4; break; case -6: diff = 5; break; } if (pitch >= 0) { _pitch += (pitch / 7) * 5 + diff; } else { _pitch -= ((-pitch / 7) * 5 + diff); } switch (accidental) { case SHARP: _pitch += 1; break; case DSHARP: _pitch += 2; break; case FLAT: _pitch -= 1; break; case DFLAT: _pitch -= 2; break; default: break; } } void considerLength() { _length = 64 / length; if (dotted) { _length *= 1.5; } } } // score class class Score { InputStream sfile; Note[] notes; Score(Path scorefile) { _sfile = new InputStream(scorefile); createScore(); } void createScore() { String input = sfile.read().decode().trim(); String[] notes_str = input.split(","); notes = []; foreach (String note_str in notes_str) { String[] attr = note_str.split(":"); notes.add(new Note(attr[0], attr[1], attr[2])); } } } // extractor class class Extractor { Score score; Extractor(Score score) { _score = score; } int extractFeature() { int feature_val = 0; Note pre_note = null; foreach (Note note in score.notes) { if (note.rest) { continue; } else if (pre_note != null) { feature_val += Math.abs(note.pitch - pre_note.pitch); } pre_note = note; } return feature_val; } } void main(String[] args) { if (args.size != 1) { ERR << "Usage: konoha " + $script.name + " input.score" << EOL; exit(1); } Score score = new Score(args[0]); Extractor extractor = new Extractor(score); OUT << "feature value: " << extractor.extractFeature() << EOL; }
iii)の解答
#!/usr/local/bin/konoha """ 4-3.k license BSD author chen_ji <wakamori111 at gmail.com> """ using konoha.io.*; using konoha.math.*; // accidental string SHARP = "s"; DSHARP = "x"; FLAT = "b"; DFLAT = "d"; // note class class Note { boolean rest; boolean dotted; int pitch; int length; String rawpitch; String rawlength; String accidental; Note(String pitch, String length, String accidental) { if (pitch == "") { _rest = true; _pitch = 0; } else { _rest = false; _pitch = (to int)pitch; } _rawpitch = pitch; if (length.endsWith(".")) { _dotted = true; _length = (to int)length.substring(0, length.size - 1); } else { _dotted = false; _length = (to int)length; } _rawlength = length; _accidental = accidental; considerAccidental(); considerLength(); } void considerAccidental() { int diff = 0; switch (pitch % 7) { case 0: case 1: diff = 0; break; case 2: case -1: diff = 1; break; case 3: case 4: case -2: diff = 2; break; case 5: case -3: case -4: diff = 3; break; case 6: case -5: diff = 4; break; case -6: diff = 5; break; } if (pitch >= 0) { _pitch += (pitch / 7) * 5 + diff; } else { _pitch -= ((-pitch / 7) * 5 + diff); } switch (accidental) { case SHARP: _pitch += 1; break; case DSHARP: _pitch += 2; break; case FLAT: _pitch -= 1; break; case DFLAT: _pitch -= 2; break; default: break; } } void considerLength() { _length = 64 / length; if (dotted) { _length *= 1.5; } } String toString() { return rawpitch + ":" + rawlength + ":" + accidental; } } // score class class Score { InputStream sfile; Note[] notes; Score(Path scorefile) { if ((to String)scorefile != "") { _sfile = new InputStream(scorefile); createScore(); } } void createScore() { String input = sfile.read().decode().trim(); String[] notes_str = input.split(","); notes = []; foreach (String note_str in notes_str) { String[] attr = note_str.split(":"); notes.add(new Note(attr[0], attr[1], attr[2])); } } String toString() { String score_str = ""; foreach (Note note in notes) { score_str += note.toString(); score_str += ","; } if (score_str != "") { score_str = score_str.substring(0, score_str.size - 1); } return score_str; } } class Composer { int start_pitch; int end_pitch; int measure_min; int measure_max; int feature_val; Composer(int start_pitch, int end_pitch, int measure_min, int measure_max, int feature_val) { _start_pitch = start_pitch; Note end_note = new Note((to String)end_pitch, "1", ""); _end_pitch = end_note.pitch; _measure_min = 64 * measure_min; _measure_max = 64 * measure_max; _feature_val = feature_val; } Note[] generateRandomNotes() { Note[] notes = []; Tuple<int, String>[] rand_pitches = []; for (int i = -6; i < 8; i++) { rand_pitches.add((i, "")); if (i == -5 || i == -4 || i == -2 || i == -1 || i == 0) { rand_pitches.add((i, FLAT)); } else if (i == 1 || i == 2 || i == 4 || i == 5 || i == 6) { rand_pitches.add((i, SHARP)); } } rand_pitches.shuffle(); foreach (Tuple<int, String> pitch in rand_pitches) { String pitch_str; boolean isRest; if (pitch[0] == 7) { pitch_str = ""; isRest = true; } else { pitch_str = (to String)pitch[0]; isRest = false; } Note note = new Note(pitch_str, generateLength(isRest), pitch[1]); notes.add(note); } return notes; } boolean setNote(Note[] notes, int total_val, int total_length) { if (total_val > feature_val || total_length > measure_max) { return false; } if (total_length >= measure_min) { if (notes[notes.size - 1].pitch == end_pitch) { if (total_val == feature_val) { return true; } } else { return false; } } Note[] rand_notes = generateRandomNotes(); foreach (Note note in rand_notes) { Note pre_note = notes[notes.size - 1]; int diff = 0; if (note.rest) { if (pre_note.rest) { continue; } diff = 0; } else { if (pre_note.rest) { pre_note = notes[notes.size - 2]; } diff = Math.abs(note.pitch - pre_note.pitch); } notes.add(note); if (setNote(notes, total_val + diff, total_length + note.length)) { return true; } notes.pop(); } return false; } Score generate() { Note start_note = new Note((to String)start_pitch, generateLength(), ""); Note[] notes = [start_note]; setNote(notes, 0, start_note.length); Score score = new Score(); score.notes = notes; return score; } String generateLength(boolean isRest) { int count = Int.random(6); int length = 1; for (int i = 0; i < count; i++) { length *= 2; } if (isRest) { return (to String)length; } return (to String)length + ((Int.random(2) == 0) ? "." : ""); } } void main(String[] args) { int feature_val = 51; if (args.size == 1) { feature_val = (to int)args[0]; } Composer composer = new Composer(-2, -2, 3, 4, feature_val); String str = composer.generate().toString(); OUT << str << EOL; }
実行結果
i)の解答
こちらのページで指定された文字列を入力として受け付けるようになっています。Aの譜面を書き込んだファイルa.scoreを用意して、以下のコマンドを実行します。
$ ./4-1and2.k a.score feature value: 24 $ ./4-1and2.k b.score feature value: 26 $ ./4-1and2.k c.score feature value: 24
このように、
- Aの特徴量≠Bの特徴量
- Aの特徴量=Cの特徴量
という、問題文の条件が満たされていることが分かります。
ii)の解答
i)の解答と同様のプログラムを実行させ、D、E、Fの譜面を同様に入力してみます。
$ ./4-1and2.k d.score feature value: 26 $ ./4-1and2.k e.score feature value: 28 $ ./4-1and2.k f.score feature value: 22
よって、「Bの特徴量＝Dの特徴量＝26」の関係が成り立つので、答えは「D」ということになります。
iii)の解答
この問題に相当手こずりました。私の最終的な結論としては、答えは「ない」というのが答えです。（間違ってたらごめんなさい。）
まず、Gの譜面の特徴量をこれまでと同様に求めます。
$ ./4-1and2.k g.score feature value: 51
特徴量が「51」となりましたので、問題分の条件に合致する譜面で、さらに特徴量が51となればよさそうです。
しかし、ここで問題があります。それは、条件の２つ目の項目
譜面上の位置 -2 で与えられるGの音ではじまり、同じ音で終わります。
という点です。つまり、最初の音符と最後の音符が同じピッチでなければなりません。
ところが、私の特徴量の求め方は、「全音とのピッチの差分の絶対値の合計値」を求める方法です。そうなると、開始音と終了音のピッチが一致している以上、差分の絶対値の合計値は、必ず「偶数」となってしまいます。
したがって、上記のiii)の解答のプログラムは、実行すると終了しません（笑）
しかもたちの悪いことに、特に考えなしに、単純なバックトラックで譜面のパターンを求めているため、探索自体に時間がかかります。特徴量に奇数を指定したとしても、結構時間のかかるときがあります。その結果、解答が出ないのはアルゴリズムが悪いからだと考え続け、この結論に至るまでに無駄な時間を費やしてしまいました。
一応、実行結果を以下に載せます。
$ ./4-3.k 51 （答えは出ません）
特徴量を「51」から「50」に変更してみます。運がよければすぐに解が出ますが、たまに時間がかかります。
$ ./4-3.k 50 -2:2.:,4:16:,6:2:s,-1:16:b,-6:16:,-4:8.:b,-6:16.:,-2:32:,:4:,-2:2:,-2:1: $ ./4-3.k 50 > out.score && ./4-1and2.k out.score feature value: 50
