2009年04月26日

[パズル]オセロ最短詰め

   このエントリーをはてなブックマークに追加 Clip to Evernote
問題
黒と白のプレイヤーが二人で協力して、番面の石を黒か白一色にする最短の手順を求めよ。
石を裏返すルールはオセロのルールをそのまま採用する。

『ナノピコ教室』では、最短の9手解をひとつだけ求めるプログラムを作ってください、という問題ですが、ここでは、すべての解を求めるプログラムをC#で書いてみることにしました。
ただし、最初の一手は、どこに打っても、回転させれば同じことになるので、 3−4固定にしています。

プログラムを作っていざ実行したら、予想以上に時間がかかってしまいます。
そのため、スレッドを起動し、キーボードから Q が押されるまで、解を求め続けることにしました。

これまでこのブログに掲載してきたパズルの問題は、探索するのに深さ優先のアルゴリズムを採用していましたが、ここでは、幅優先のアルゴリズムを採用しています。こうすることで、最短手から解を表示するようにできます。

ちょっと苦労したのは、これまでのパズルは、プレイヤーはひとりだったわけですが、このパズルはプレイヤーが2人いるので、その制御に手こずりました。

実は、この文章を書きながら、プログラムを実行させているのですが、まだ全部求め終わっていません。

と、ここまで書いたら、OutOfMemoryExceptionが発生してしまいました。
プログラム内で用意しているキューがメモリを食いつぶしてしまったみたいです。 求めた結果のいくつかを検証してみましたが、合っているようなので、 考え方自体はよいと思うのですが。。。
たしかに、キューに入っている数がものすごく多いので、この数だけ、Boardオブジェクトのクローンを作っているので、メモリのバカ食いです。

10手解も含めて求めようとしていたので、これは諦めて、9手解のすべてを求めるように修正しました。

10手解まで求めようとすると、もっとメモリを使わないようにデータ構造・アルゴリズムまで含めて設計し直しが必要そうです。そこまでの気力がないので、とりあえず、このままコードを掲載します。

興味のある方、是非、直してください。


※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題を一部変更し、GushwellがC#で解いたものです。
  

Posted by gushwell at 22:16Comments(0)TrackBack(0)

2009年04月21日

新しいブログ始めました

   このエントリーをはてなブックマークに追加 Clip to Evernote
今度、techbank.jpというコミュニティのブログスペースで、
Gushwell's F# Programming Diary」というブログを始めました。
タイトルにあるとおり、F#に関して書いてゆくつもりです。
まだ、インストールのことしか書いていませんが、F#の学習の過程を
綴ってゆくつもりです。
F#に少しでも興味があるかたは、是非お立ち寄りください。


コミュニティtechbank.jpについて
マイクロソフト製品&技術を専門にした、複合型コミュニティです。
FAQ掲示板、勇志メンバーによるBlogでの技術情報の発信、
メーリングリストの配信、技術本執筆プロジェクト、
オフラインイベント・勉強会の開催等、多岐に渡り、幅広く運営しています。

学生さん・初心者の方から、経験があるプロの方まで、どなたでも参加可能です。
参加者は皆平等で、技術情報を発信したい、世の中にノウハウを
広めていきたい気持ちがあれば、どなたでも参加できます。
ID登録者、Blog Writer、書籍執筆希望者、オフラインイベントスタッフを
大募集しています。まずは、ID登録から!Entry Now !!!!!

URL:
http://techbank.jp/
http://techbank.jp/community/

  
Posted by gushwell at 23:36Comments(2)TrackBack(0)

2009年04月19日

[パズル]数独を解く

   このエントリーをはてなブックマークに追加 Clip to Evernote
数独は、あまりにも有名なパズルなので、説明するまでもないと思います。
この数独を解くプログラムを書くのが今回の問題です。

数独について知らない方は、こちら
http://www.sudoku.name/rules/jp
をご覧ください、また、このサイトでは、無料で数独に挑戦することもできるようです。
http://www.sudoku.name/index-jp.php

これも、今までの問題同様に、再帰処理による総あたり処理をしています。
今回もLINQを使ってます。LINQ便利ですね。

コメント途中まで書きましたが、面倒になったので、やめました。
あとは、以下のC#のソースコードを読んでください。

Mainメソッドのnums変数の値を書き変えれば、雑誌などに載っている 問題の答えを知ることができます。
なお、Mainメソッドで解いている数独の問題は、解答が2つ存在します。

コンソールアプリとして作成しているので、どなたかGUIをつけてください。


※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題を一部変更し、GushwellがC#で解いたものです。   
Posted by gushwell at 21:57Comments(0)TrackBack(0)

2009年04月14日

マニフェストファイルで管理者権限を付与

   このエントリーをはてなブックマークに追加 Clip to Evernote
Vistaでは、管理者権限でログインしていても、デフォルトでは管理者権限が付与されずにプログラムが実行されます。
そのため、実行に管理者権限が必要なアプリケーションでは、マニフェストファイルを用意する必要があります。
こうすれば、UACのダイアログは出ますが、明示的に「管理者権限で実行」で起動する必要はありません。
(証明書で署名する方法もあるようですが、ここでは割愛)

以下、そのサンプルです。

<?xml version="1.0" encoding="utf-8"?>
<asmv1:assembly manifestVersion="1.0"
xmlns="urn:schemas-microsoft-com:asm.v1"
xmlns:asmv1="urn:schemas-microsoft-com:asm.v1"
xmlns:asmv2="urn:schemas-microsoft-com:asm.v2"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
<assemblyIdentity version="1.0.0.0" name="MyApplication.app"/>
<trustInfo xmlns="urn:schemas-microsoft-com:asm.v2">
<security>
<requestedPrivileges xmlns="urn:schemas-microsoft-com:asm.v3">
<requestedExecutionLevel level="requireAdministrator" uiAccess="false" />
</requestedPrivileges>
</security>
</trustInfo>
</asmv1:assembly>



なお、Visual Studio 2008では、「新しい項目の追加」でマニフェストファイルを選ぶと、雛形のマニフェストファイルが生成されるので、コメントにしたがって書き換えるだけでOKです。


■未確認情報
Visual Studio 2005で作成されたマニフェストファイルの場合、Windows XPで実行すると、PCが再起動してしまうようです。
http://support.microsoft.com/kb/921337/ja  
Posted by gushwell at 22:59Comments(0)TrackBack(2)

2009年04月10日

Stopwatch.StartNew()

   このエントリーをはてなブックマークに追加 Clip to Evernote
Stopwatch.StartNew();

へー!
.NET FrameworkのStopwatchクラスには、こんなメソッドがあったんだ。

  Stopwatch sw = new Stopwatch();
sw.Start();

は、

  Stopwatch sw = Stopwatch.StartNew();

とかけるんですね。

  
Posted by gushwell at 23:01Comments(0)TrackBack(0)

2009年04月09日

MemoryStream は、配列に変換できる

   このエントリーをはてなブックマークに追加 Clip to Evernote
MemoryStream は、簡単に配列に変換できます。

 string s = "テスト用文字列";
byte[] bytes = System.Text.Encoding.Unicode.GetBytes(s);
System.IO.MemoryStream mem = new System.IO.MemoryStream();
for (int i = 0; i < 20; i++) {
mem.Write(bytes, 0, bytes.Length);
}
byte[] bs = mem.ToArray();




のように、ToArray() メソッドを呼べば、簡単にbyte[]に変換できる。
巨大なデータじゃなければ、このほうがその後の処理が簡単に書ける場合が多いと思います。  
Posted by gushwell at 23:06Comments(0)TrackBack(0)

2009年04月07日

TypeCode 列挙体

   このエントリーをはてなブックマークに追加 Clip to Evernote
前にも書いたような気もするけど、
GetTypeCodeを使うと、その型の TypeCodeを取得できます。

 static void Foo(object c) {
TypeCode code = Type.GetTypeCode(c.GetType());
Console.WriteLine(code);
}


TypeCode 列挙体 は、

TypeCode.Boolean
TypeCode.Char
TypeCode.Int16
TypeCode.Int32
TypeCode.Double
TypeCode.Decimal
TypeCode.DateTime
TypeCode.String

などの値があります。switch文等で分岐したいときに使えます。

 if (type == typeof(System.Int16)) {


などと、型比較するよりも速度が速いです。
こういったミクロな視点での速度を云々言うのは好きではないですが...  
Posted by gushwell at 23:17Comments(0)TrackBack(1)

2009年04月05日

[パズル]面積最大の領域

   このエントリーをはてなブックマークに追加 Clip to Evernote
問題

下のように、黒と白からなる配列があります。

○○○○●●●●●○
○○●●●●●●○●
○○●●●●○●●●
●●●●●●●●●○
●●○○○●○●●●
●●○○●●○●●●
●●○○●●○●●○

この中で、最大となる黒の正方形の面積を求めてください。
上の例では、9が最大の面積となります。

----------------------------
厳密にはパズルとは言えませんが、プログラミングにおける頭の体操としてはなかなか良い問題だと思います。

データとしては、0を白、1を黒として表現することにします。
すべての地点に対し、その地点を正方形の左上としたしたときの面積を求め、一番大きなのがどれかを求めることとします。
では、どうやって正方形かどうかを判断するかですが、これも再帰処理の応用としてとらえることができます。

例えば、以下の図で、△部分が正方形であると分かっている場合を考えます。

△△△△☆
△△△△☆
△△△△☆
△△△△☆
★★★★●

△部分の右下を(x,y)地点とすると、
(1) (x+1,y+1) が黒
(2) ☆部分がすべて黒
(3) ★部分がすべて黒
を満たした場合、正方形の辺の長さは + 1 となり、
△部分が増えることになります。これを繰り返していけば、正方形の辺の長さが求まることになります。

C#で書いたコードを示します。今回も LINQ使ってます。

using System;
using System.Linq;

namespace MaxSize {
class Program {
static void Main(string[] args) {
int[,] mat = new int[,] {
{1,0,0,0,1,1,1,1,1,0},
{0,0,1,1,1,1,1,1,0,1},
{0,0,1,1,1,1,0,1,1,1},
{1,1,1,1,1,1,1,1,1,0},
{1,1,1,1,1,1,0,1,1,1},
{1,1,1,0,1,1,0,1,1,1},
{1,1,0,0,1,1,0,1,1,1},
};
Solver solver = new Solver();
int n = solver.Solve(mat);
Console.WriteLine(n*n);
}
}

class Solver {
public int Solve(int[,] mat) {
Board board = new Board(mat);
// すべての地点での正方形の辺の長さを求め、その最大値を返す。
return (from x in Enumerable.Range(0, board.XSize)
from y in Enumerable.Range(0, board.YSize)
select new { x, y }
).Max(o => board.GetAreaSize(o.x, o.y));
}
}

class Board {
private int[,] mat;

public int XSize {
get { return mat.GetLength(0); }
}

public int YSize {
get { return mat.GetLength(1); }
}

public Board(int[,] mat) {
this.mat = mat;
}

public int this[int x, int y] {
get { return mat[x, y]; }
}

public int GetYCount(int x, int y) {
return Enumerable.Range(0, y + 1).Reverse()
.TakeWhile(n => mat[x, n] == 1)
.Count();
}

public int GetXCount(int x, int y) {
return Enumerable.Range(0, x + 1).Reverse()
.TakeWhile(n => mat[n, y] == 1)
.Count();
}

public int GetAreaSize(int x, int y) {
return GetAreaSize(x, y, 0);
}

public int GetAreaSize(int x, int y, int width) {
// インデックスオーバーしないようにチェックする
if (x >= mat.GetLength(0))
return width;
if (y >= mat.GetLength(0))
return width;
// 黒じゃなければ、今まで求めたwidthが、正方形の辺の長さ
if (mat[x, y] == 0)
return width;
// X方向がすべて黒でないならば、今まで求めたwidthが、正方形の辺の長さ
int xc = GetXCount(x, y);
if (xc < width + 1)
return width;
// Y方向がすべて黒でないならば、今まで求めたwidthが、正方形の辺の長さ
if (GetYCount(x, y) < width + 1)
return width;
// width+1の可能性があるので、右下まで広げて調べる(再帰処理)
return GetAreaSize(x + 1, y + 1, width + 1);
}
}

}




※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題を一部変更し、GushwellがC#で解いたものです。
  
Posted by gushwell at 22:17Comments(0)TrackBack(0)