すっかり忘れてました。新しく開発者を採用するにあたり、会社の方針に合わせてコードを書いてもらいました。で、採用担当としてこんな問題を考えました。
問題内容
２つの文字列を与えられた時、それぞれの文字列の一致率を０～１の間で算出する関数を作成せよ。
※一致率の定義の仕様も含めて考えてください。
いろいろ考え方や思うところはあると思いますが、今回に関しては問題を解く過程をとても重視しました。どういうふうに仕様を決めるのかも含め、です。内容からして勝手に仕様を決めていいように思われるかもしれないですが、そこの解釈も重視です。与えられた情報の範囲内でどこまで飛べるのか、みたいな。
解答例
public static decimal Rate(string value1, string value2)
{
if (string.IsNullOrEmpty(value1) || string.IsNullOrEmpty(value2))
return 0m;
if (string.IsNullOrEmpty(value1.Trim()) || string.IsNullOrEmpty(value2.Trim()))
return 0m;
if (string.Compare(value1, value2, StringComparison.CurrentCulture) == 0)
return 1m;
var longer2nd = value1.Length < value2.Length;
var val1 = longer2nd ? value1 : value2; // 短い文字列
var val2 = longer2nd ? value2 : value1; // 長い文字列
int match = 0, p1 = 0, p2 = 0, p2Index = 0;
while (p1 < val1.Length && p2 < val2.Length)
{
if (val1[p1] == val2[p2Index])
{
match += 2;
p1++;
p2 = p2Index++;
}
else
{
p2Index++;
if (p2Index >= val2.Length)
{
p1++;
p2Index = p2;
}
}
if (val2.Length - 1 < p2Index) // 進みすぎたときには引き戻す
p2Index = p2;
}
return match / (decimal)(value1.Length + value2.Length);
}
最初のほうはエラーチェックだから、今回別に無くてもよかったです。
あれっすよ、こんなの10分やそこらでコード化するもんじゃないかもね。でも、考え方というか解き方というか、問題はどこでどういう回答をビジネスオーナーは望んでいるのか、ですよね。
問題を考えたものとしては、この問題で先頭一致の割合だけでとくのが一番簡単なのは分かってて、それだけじゃない解き方を答えて欲しいな～、と思ってました。
“どのくらい一致しているか”
の定義は様々だけど「全体文字数に占める一致文字数の割合」が手頃な回答ですよね。んじゃ、一致文字数というのはどういう意味だと解釈するのが面白いか。文字列を前半・中央・後半の3つの集合として考えて、それぞれの文字列の比較開始位置と一致文字数を数えていけば、それらしい数値を出すこと方法として面白いんじゃないかと思うんだけど、どうかな。
| 前半 |
中央 |
後半 |
文字列１ |
文字列２ |
|
○
|
○
|
○
|
AABBCC |
AABBCC |
|
○
|
○
|
|
AABBCC |
AABBzz
※AABBも同じ |
|
|
○
|
○
|
zzBBCC |
yyBBCC
※BBCCも同じ |
|
○
|
|
○
|
AAzzCC |
AAyyCC
※AACCも同じ |
|
|
○
|
|
zzAAyy |
xxAAww |
※前半だけ、後半だけは前半＋中央と中央＋後半と同じ。
こんな感じのパターン。ちなみにこのパターンを答えた人がひとりだけいましたよ。なんで同じ答えにたどり着いたのかというと、そういう定義をオーナーが望んでると聞き出したからです。そりゃ同じになるわね。
じゃー、このコードがホントにそれっぽく一致率がでるのか確認するテストコード。
[TestMethod]
public void 空文字渡し()
{
var rate = MatchRate.Rate(null, null);
Assert.AreEqual(0, rate);
rate = MatchRate.Rate("", null);
Assert.AreEqual(0, rate);
rate = MatchRate.Rate(null, "");
Assert.AreEqual(0, rate);
rate = MatchRate.Rate("", "");
Assert.AreEqual(0, rate);
rate = MatchRate.Rate("", "AA");
Assert.AreEqual(0, rate);
rate = MatchRate.Rate("AA", "");
Assert.AreEqual(0, rate);
}
[TestMethod]
public void 空白渡し()
{
var rate = MatchRate.Rate(" ", "");
Assert.AreEqual(0, rate);
rate = MatchRate.Rate("", " ");
Assert.AreEqual(0, rate);
rate = MatchRate.Rate("AA", " ");
Assert.AreEqual(0, rate);
}
[TestMethod]
public void 完全一致()
{
var rate = MatchRate.Rate("AA", "AA");
Assert.AreEqual(1m, rate);
rate = MatchRate.Rate("aa", "aa");
Assert.AreEqual(1m, rate);
}
[TestMethod]
public void 前方一致で６６パーセント()
{
var rate = MatchRate.Rate("AA", "AABB");
Assert.AreEqual(2m / 3m, rate);
}
[TestMethod]
public void 後方一致で６６パーセント()
{
var rate = MatchRate.Rate("AA", "BBAA");
Assert.AreEqual(2m / 3m, rate);
}
[TestMethod]
public void 中央一致で６６パーセント()
{
var rate = MatchRate.Rate("AA", "BAAB");
Assert.AreEqual(2m / 3m, rate);
}
[TestMethod]
public void 前後半一致で６６パーセント()
{
var rate = MatchRate.Rate("AA", "ABBA");
Assert.AreEqual(2m / 3m, rate);
}
[TestMethod]
public void 前後半一致で７５パーセント()
{
var rate = MatchRate.Rate("ABCDE", "ADE");
Assert.AreEqual(6m / 8m, rate);
}
だいたいいい感じなんじゃないっすかね。直感的にそんな感じ。セマンティックとか関係なく、ですから。問題はここまでで終了。
だたひとり答えにたどり着いたクマさんに拍手。
ここからさらに考え方を進めてみましょう。もし文字列が文章だとしたら。文章だと”の”とか”を”とかが入ってくるから、普通に一致させるだけだと、それっぽくならないですね。なので、このアルゴリズムを再帰に改造して、前半を無視したほうが一致率が上がるなら無視するというふうに改造してみます。何でかというと、このアルゴリズムだと一致率は上昇して頂点になったあと下降するっていう山型になるはずだからです。現在の位置と次の位置との比較で一致率が上昇してるなら、現在の位置は無視したほうがそれっぽい数値に近づくってことです。そうするとコピペ文章なんじゃん？っていうものに関しての判定が”それっぽく”できます。あくまで”それっぽく”ですよ。
public static decimal Rate(string value1, string value2)
{
return Rate(value1, value2, null);
}
public static Func<string, int, string, int, bool> RecursiveCommand = (val1, idx1, val2, idx2) =>
{
var p1Rate = Rate(val1.Substring(idx1), val2.Substring(idx2), null);
var p1IncRate = Rate(val1.Substring(idx1 + 1), val2.Substring(idx2), null);
return p1Rate < p1IncRate;
};
public static decimal Rate(string value1, string value2, Func<string, int, string, int, bool> command)
{
if (string.IsNullOrEmpty(value1) || string.IsNullOrEmpty(value2))
return 0m;
if (string.IsNullOrEmpty(value1.Trim()) || string.IsNullOrEmpty(value2.Trim()))
return 0m;
if (string.Compare(value1, value2, StringComparison.CurrentCulture) == 0)
return 1m;
var longer2nd = value1.Length < value2.Length;
var val1 = longer2nd ? value1 : value2; // 短い文字列
var val2 = longer2nd ? value2 : value1; // 長い文字列
int match = 0, p1 = 0, p2 = 0, p2Index = 0;
while (p1 < val1.Length && p2 < val2.Length)
{
// p1とp1+1で比較してp1+1のほうがRateがよければp1はスキップする
if (command != null)
{
p1 += command(val1, p1, val2, p2Index) ? 1 : 0;
}
if (val1[p1] == val2[p2Index])
{
match += 2;
p1++;
p2 = p2Index++;
}
else
{
p2Index++;
if (p2Index >= val2.Length)
{
p1++;
p2Index = p2;
}
}
if (val2.Length - 1 < p2Index) // 進みすぎたときには引き戻す
p2Index = p2;
}
return match / (decimal)(value1.Length + value2.Length);
}
で、最初のテストがパスするのを確認したうえで、以下のテスト。
[TestMethod]
public void 再帰のほうがそれっぽくなる()
{
var rate = MatchRate.Rate(
"ABCDEF",
"AECDEF"
);
var rateR = MatchRate.Rate(
"ABCDEF",
"AECDEF",
MatchRate.RecursiveCommand
);
Console.WriteLine("Rate={0} < RateR={1}", rate, rateR);
Assert.IsTrue(rate < rateR);
}
[TestMethod]
public void コピペしてちょっと手直しした文章()
{
var rate = MatchRate.Rate(
"衆院は３１日の夜、会議を開き、日本郵政３社への再編などを柱とする郵政改革法案を賛成多数で可決し、参院に送付した。与党は参院でも短時間で審議し、６月１６日までの会期内成立を目指す構え。自民、公明、みんな、たちあがれ日本の野党４党は１日、与党の意向を受け、本会議開催を強行した横路孝弘衆院議長に対する不信任決議案を提出する。",
"衆院は３１日深夜、本会議を開き、日本郵政グループの３社への再編などを柱とする郵政改革法案を民主、国民新党などの賛成多数で可決し、参院に送付した。与党は参院でも短時間で審議を終え、６月１６日までの会期内成立を目指す構え。自民、公明、みんな、たちあがれ日本の野党４党は１日、与党の意向を受け、本会議開催を強行した横路孝弘衆院議長に対する不信任決議案を提出する。",
MatchRate.RecursiveCommand
);
Console.WriteLine(rate);
}
ソースアップしておきまーす。何かの役に立つコードではないけどね！
