指定された 9 要素の配列に繰り返し番号 1、2、3、...、9 が含まれていないことを確認する 1 つのライナー (またはそれに近い) が必要です。ゼロの繰り返しはカウントされません (空のセルを表します)。
これまでに出てきた最高のものは次のとおりです。
var a = new int[9] {1,2,3,4,5,6,7,8,9};
var itIsOk = a.Join(a, i => i, j => j, (x, y) => x)
.GroupBy(y => y).Where(g => g.Key > 0 && g.Count() > 1).Count() == 0;
私の問題を解決したくない場合:)、少なくとも上記のアルゴリズムが正しく機能するかどうかを教えていただけますか?
そして、はい、これを読んだことがあります。
これは、LINQ ソリューションよりも約 50 ～ 250 倍高速です (重複がどれだけ早く検出されるかによって異なります)。
public static bool IsValid(int[] values) {
int flag = 0;
foreach (int value in values) {
if (value != 0) {
int bit = 1 << value;
if ((flag & bit) != 0) return false;
flag |= bit;
}
}
return true;
}
幸運なことに、私は少し前に数独ソルバーを自分で作成しました :) 全体は約 200 行の C# であり、私が見つけることができる最も難しいパズルを 4 秒以内で解決することができました。
.Count を使用しているため、パフォーマンスはおそらくそれほど優れていませんが、動作するはずです。
!a.Any(i => i != 0 && a.Where(j => j != 0 && i == j).Count > 1)
また、このj != 0部分は実際には必要ありませんが、動作が少し速くなるはずです。
[編集:] kvbの答えは私に別のアイデアを与えました:
!a.Where(i => i != 0).GroupBy(i => i).Any(gp => gp.Count() > 1)
グループ化する前に 0 をフィルタリングします。IEnumerable がどのように機能するかに基づいていますが、それは問題ではないかもしれません。
いずれにせよ、最高のパフォーマンスを.Count > 1得るには、これらのいずれかを次のような新しい IEnumerable 拡張メソッドに置き換えます。
bool MoreThanOne(this IEnumerable<T> enumerable, Predictate<T> pred)
{
bool flag = false;
foreach (T item in enumerable)
{
if (pred(item))
{
if (flag)
return true;
flag = true;
}
}
return false;
}
配列は 9 項目に制限されているため、おそらくそれほど問題にはなりませんが、多く呼び出すと合計される可能性があります。
!a.GroupBy(i => i).Any(gp => gp.Key != 0 && gp.Count() > 1)
拡張メソッドでテストの効率的な実装をまとめてそれを呼び出すのではなく、Linq コードの複雑な行が必要なのはなぜですか?
var a = new int[9] {1,2,3,4,5,6,7,8,9};
var itIsOk = a.HasNoNonZeroRepeats();
NoNonZeroRepeats の実装の 1 つは、short の最下位 9 ビットを使用して配列内の値の存在を示し、動的メモリを使用しない O(length(a)) テストを行うことです。Linq はかわいいですが、審美的な理由だけで使用していない限り (Linq だけを演習として使用して数独ソルバーを書いているとは特に言いません)、ここで複雑さを追加しているように見えます。
これは古い質問ですが、最近、ツリーのような構造を行うために Oracle のカスタム SQL を使用する 1 行のソリューションを指摘されました。これをLinqに変換するといいと思いました。
Linq の 1 行で Sudokuを解く方法については、私のブログで詳しく読むことができます。
コードは次のとおりです。
public static string SolveStrings(string Board)
{
string[] leafNodesOfMoves = new string[] { Board };
while ((leafNodesOfMoves.Length > 0) && (leafNodesOfMoves[0].IndexOf(' ') != -1))
{
leafNodesOfMoves = (
from partialSolution in leafNodesOfMoves
let index = partialSolution.IndexOf(' ')
let column = index % 9
let groupOf3 = index - (index % 27) + column - (index % 3)
from searchLetter in "123456789"
let InvalidPositions =
from spaceToCheck in Enumerable.Range(0, 9)
let IsInRow = partialSolution[index - column + spaceToCheck] == searchLetter
let IsInColumn = partialSolution[column + (spaceToCheck * 9)] == searchLetter
let IsInGroupBoxOf3x3 = partialSolution[groupOf3 + (spaceToCheck % 3) +
(int)Math.Floor(spaceToCheck / 3f) * 9] == searchLetter
where IsInRow || IsInColumn || IsInGroupBoxOf3x3
select spaceToCheck
where InvalidPositions.Count() == 0
select partialSolution.Substring(0, index) + searchLetter + partialSolution.Substring(index + 1)
).ToArray();
}
return (leafNodesOfMoves.Length == 0)
? "No solution"
: leafNodesOfMoves[0];
}
パフォーマンスではないにしても簡潔にするために、 var itIsOk = a.Sum() == a.Distinct().Sum(); はどうですか?
どうですか：
var itIsOk = a.Where(x => x > 0).Distinct().Count() == a.Where(x => x > 0).Count();
理由: 最初に 0 を含まない列挙を作成します。残りの数のうち、その個別のリストが実際のリストと同じ長さである場合、繰り返しはありません。
または: 一意の番号のリストが実際のリストよりも小さい場合は、番号を繰り返す必要があります。
これはワンライナーバージョンです。a.Where(x=>x>0) リストは除外できます。
var nonZeroList = a.Where(x => x > 0).ToList();
var itIsOk = nonZeroList.Distinct().Count() == nonZeroList.Count();
私は通常、キャプチャされた変数を含むソリューションには眉をひそめますが、これを書きたいという衝動に駆られました:
bool hasRepeating = false;
int previous = 0;
int firstDuplicateValue = a
.Where(i => i != 0)
.OrderBy(i => i)
.FirstOrDefault(i =>
{
hasRepeating = (i == previous);
previous = i;
return hasRepeating;
});
if (hasRepeating)
{
Console.WriteLine(firstDuplicateValue);
}