2009年03月30日

IPアドレスからホスト名を取得する

   このエントリーをはてなブックマークに追加 Clip to Evernote
備忘メモ

 // IPアドレスからホスト名を取得する
static string GetHostNameFromIp(string ipAddress) {
var ip = IPAddress.Parse(ipAddress); // ex "10.1.2.3"
IPHostEntry hostInfo = Dns.GetHostEntry(ip);
return hostInfo.HostName;
}



 // ホスト名からIP V4のアドレスを取得する
static IEnumerable<IPAddress> GetIpV4FromHostName(string hostName) {
IPHostEntry ipInfo = Dns.GetHostEntry(hostName);
foreach (IPAddress address in ipInfo.AddressList) {
if (address.AddressFamily == System.Net.Sockets.AddressFamily.InterNetwork)
yield return address;
}
}



  

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

2009年03月29日

[パズル]わなにはまるまで

   このエントリーをはてなブックマークに追加 Clip to Evernote
問題
「桁切り2のべき乗和」という関数 f(x)を考えます。たとえば、234という数値を引数に渡すと、
f(234) = 2^2 + 2^3 + 2^4
= 4 + 8 + 16
= 28
※ ^はべき乗を表す

となります。
この関数を使い

f(a) -> f(f(a)) -> f(f(f(a))) -> f(f(f(f(a)))) -> ...

と求めて行くと、無限に発散するか、同じところに戻ってきてループするかのどちらかです。
例えば、a が 1 のときは、

1, 2, 4, 16, 66, 128, 262, 72, 132, 14, 18, 258, 292, 520, 37, 136, 74, 144, 34, 24, 20, 5, 32, 12, 6, 64, 80, 257, 164, 82, 260, 69, 576, 224, 24, ...

となり、ループに陥ります。

このとき、任意の数値 a(1..10000000)のなかで、最も早くループに陥るのはどの数かを求めてください。

---

この問題は、ループにならずに、発散してしまう場合があったらどうするのかとうことを考えなくてはいけません。

しかし、a = 1 のときにはループに陥ることが分かっているので、この回数より多いものはすべて除外する、というコードを加えれば、発散する場合があっても対応できることになります。

で、C#で書いたコードは、以下のとおりです。

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication1 {
class Program {
static void Main(string[] args) {
Solver sol = new Solver();
sol.Solve();
}
}

class Solver {
public int Solve() {
int ans = -1;
int maxloop = int.MaxValue;
foreach (var a in Enumerable.Range(1, 300)) {
SumPower s = new SumPower();
int f = s.SigmaF(a, maxloop);
if (f < maxloop) {
maxloop = f;
ans = a;
}
}
Console.WriteLine("{0} {1}",ans, maxloop);
SumPower sp = new SumPower();
sp.SigmaF(ans,int.MaxValue);
Console.WriteLine(sp);
return 1;
}

}
class SumPower {
private List<int> List = new List<int>();
public override string ToString() {
return string.Join(", ", List.Select(n => n.ToString()).ToArray());
}
public int F(int n) {
string s = n.ToString();
int f = 0;
foreach (var c in s) {
int i = int.Parse(c.ToString());
f += (int)Math.Pow(2, i);
}
return f;
}

public int SigmaF(int a, int maxloop) {
try {
List.Clear();
List.Add(a);
while (true) {
a = F(a);
if (List.Contains(a))
break;
List.Add(a);
if (maxloop < List.Count)
return int.MaxValue;
}
List.Add(a);


return List.Count - 1;
} finally {
;
//Console.WriteLine(this); debug用
}
}
}
}





結果は、148 でした。

148 -> 274 -> 148 -> ...

となって、なんと2回目には、ループに入ってしまいます。ということで、これ以上やっても、これ以上短い答えはありません。
そういう意味では、さらに実行時間を短くできますね。

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

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

2009年03月25日

[パズル]七対子

   このエントリーをはてなブックマークに追加 Clip to Evernote
前回、清一色かどうかを調べるコードの中で、七対子かどうかを調べる部分がありました。
再度掲載します。

 private bool Is7Pair(List<int> nums) {
if (nums.Count() == 0)
return true;
for (int i = 1; i <= 9; i++) {
if (nums.FindAll(n => n == i).Count >= 2) {
2.Times(() => nums.Remove(i));
try {
if (Is7Pair(nums))
return true;
} finally {
2.Times(() => nums.Add(i));
}
}
}
return false;
}


かなり、複雑です。この部分が気になったので、もう少し考えてみました。
事前にソートしておけば、もっと簡単になりますね。

 private bool Is7Pair(List<int> nums) {
return IsPair7Inner(nums.OrderBy(n => n));
}

private bool IsPair7Inner(IEnumerable<int> nums) {
if (nums.Count() == 0)
return true;
if (nums.ElementAt(0) != nums.ElementAt(1))
return false;
return IsPair7Inner(nums.Skip(2));
}


再帰処理のお手本のようなコードになったと思います。  
Posted by gushwell at 22:46Comments(0)TrackBack(0)

2009年03月22日

[パズル]清一色 チンイ―ソウ

   このエントリーをはてなブックマークに追加 Clip to Evernote
問題
マージャンの清一色となる待ち牌をすべて調べるプログラムを作ってください。
ただし、単純化するために、前面でチー、ポン、カンは一度もしていないものとします。また、データとしては数値だけを与えることとし、牌に関する他の情報は無視してかまいません。

---
僕は、マージャンに詳しくないので、用語などに自身がありません。無瑛やり英単語にしているので、これは自己流の用語ですのでご容赦を。

まずは、14個の牌が、清一色で上がっているかどうかを調べるメソッドを書きます。
IsFinishがそのメソッドですが、七対子(Is7Pair)と通常の上がり(IsNormalComplete)を別メソッドとして判断するようにしています。
その下請けメソッドとして、IsSeries3とIsSame3というメソッドを用意します。
IsSeries3は、順子かどうかを調べるメソッドですが、引数で数値を与えると、その数値から始まる連続した3つの数があるかどうかを調べるメソッドです。
IsSame3は、引数で与えた数値が3枚(以上)あるかどうかを調べます。

IsPair7もIsNormalCompleteも再帰処理を使っています。IsPair7は、もう少し簡単になりそうな気もするのですが...

IsNormalCompleteの中に、

3.Times(n => nums.Remove(i + n));

というコードがありますが、これは、

nums.Remove(i);
nums.Remove(i+1);
nums.Remove(i+2);

を1行にまとめてみました。かえって解りにくくなったような気もしますが、まあ、自己満足です。

ここまでできれば、待ち牌をすべて調べるコードはそれほど難しくありませんね。
BestPiecesメソッドがそのメソッドです。

Mainメソッドは、IsFinishとBestPiecesメソッドの動作を調べるテストコードです。

using System;
using System.Collections.Generic;
using System.Linq;

namespace FullFlash {
class Program {
static void Main(string[] args) {
Pieces t = new Pieces(new[] { 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5 });
Console.WriteLine(t.IsFinish());

t = new Pieces(new[] { 1, 2, 2, 2, 3, 3, 3, 1, 4, 4, 4, 5, 5, 6 });
Console.WriteLine(t.IsFinish());

t = new Pieces(new[] { 1, 3, 2, 3, 4, 2, 3, 4, 4, 2, 4, 5, 6, 7 });
Console.WriteLine(t.IsFinish());

t = new Pieces(new[] { 5, 1, 2, 3, 4, 5, 6, 5, 5, 6, 7, 6, 7, 8 });
Console.WriteLine(t.IsFinish());

t = new Pieces(new[] { 1, 2, 3, 4, 5, 5, 5, 5, 6, 7, 3, 6, 7, 8 });
Console.WriteLine(t.IsFinish());

t = new Pieces(new[] { 1, 2, 3, 3, 4, 5, 5, 6, 7, 6, 7, 8, 5, 2 });
Console.WriteLine(t.IsFinish());

t = new Pieces(new[] { 1, 2, 3, 4, 5, 5, 5, 3, 6, 7, 6, 7, 8, 3 });
Console.WriteLine(t.IsFinish());

Pieces tb = new Pieces(new[] { 1, 2, 3, 3, 4, 4, 5, 5, 6, 7, 6, 7, 8 });
tb.BestPieces().ToList().ForEach(n => Console.Write("{0} ", n));
Console.WriteLine();

t = new Pieces(new[] { 1, 1, 2, 6, 2, 6, 4, 4, 4, 7, 7, 9, 9 });
t.BestPieces().ToList().ForEach(n => Console.Write("{0} ", n));
Console.WriteLine();

}
}

// 手牌を表すクラス (上がりかどうかの判断もこのクラスで行う)
class Pieces {
private List<int> Numbers = new List<int>();

public Pieces(IEnumerable<int> nums) {
foreach (var n in nums)
Numbers.Add(n);
}

// 上りになる手を探す
public IEnumerable<int> BestPieces() {
for (int i = 1; i <= 9; i++) {
List<int> work = Numbers.ToList();
work.Add(i);
if (IsNormalComplete(work) || Is7Pair(work))
yield return i;
}
}

// 上がりか?
public bool IsFinish() {
return (IsNormalComplete(Numbers) || Is7Pair(Numbers));
}

// 七対子か?
private bool Is7Pair(List<int> nums) {
if (nums.Count() == 0)
return true;
for (int i = 1; i <= 9; i++) {
if (nums.FindAll(n => n == i).Count >= 2) {
2.Times(() => nums.Remove(i));
try {
if (Is7Pair(nums))
return true;
} finally {
2.Times(() => nums.Add(i));
}
}
}
return false;
}

// 七対子以外の上がり(なんて言うんだろう?)
private bool IsNormalComplete(List<int> nums) {
if (nums.Count == 2)
return (nums[0] == nums[1]);
for (int i = 1; i <= 9; i++) {
if (IsSame3(nums, i)) {
3.Times(() => nums.Remove(i));
try {
if (IsNormalComplete(nums.ToList()))
return true;
} finally {
3.Times(() => nums.Add(i));
}
}
if (IsSeries3(nums, i)) {
3.Times(n => nums.Remove(i + n));
try {
if (IsNormalComplete(nums.ToList()))
return true;
} finally {
3.Times(n => nums.Add(i + n));
}
}
}
return false;
}

// 順子(シュンツ)か?
private bool IsSeries3(List<int> nums, int i) {
return Enumerable.Range(i,3).All(x => nums.FindIndex(n => n == x) >= 0);
}

// 刻子(コーツ)か?
private bool IsSame3(List<int> nums, int i) {
return nums.FindAll(n => n == i).Count >= 3;
}
}

// intに対する拡張メソッドを提供。
public static class IntExtentions {
public static void Times(this int value, Action action) {
for (int i = 0; i < value; i++)
action();
}

public static void Times(this int value, Action<int> action) {
for (int i = 0; i < value; i++)
action(i);
}
}
}



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

2009年03月18日

Microsoft Wireless keyboard 6000

   このエントリーをはてなブックマークに追加 Clip to Evernote
Windows VistaのPCのキーボードを英語版のMicrosoft Wireless keyboard 6000(101キーボード)に変更したのですが、Alt+`(チルダ)でのIME On/Offが面倒です。

IMEのプロパティ画面で、漢字/半角キー以外に、IMEのOn/Offを割り当てることが可能です。Ctrl+Spaceに割り当てることが多いようですが、Visual Studio 2008のキーアサインとバッティングしてしまうため、使えません。
その他、いくつか試してみましたが、これだ!というキーコンビネーションがありませんでした。
使わない特殊キーに割り当てることができれば良いのですが、できないようです。

なにか良いほうがないかなと調べたところ、AXキーボードと認識にさせれば右ALtキーでIMEのOn/Offができると分かりました。
レジストリを以下のようにすればOKです。

[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\i8042prt\Parameters]
"PollingIterations"=dword:00002ee0
"PollingIterationsMaximum"=dword:00002ee0
"ResendIterations"=dword:00000003
"LayerDriver JPN"="kbdax2.DLL"
"LayerDriver KOR"="kbd101a.dll"
"OverrideKeyboardType"=dword:00000007
"OverrideKeyboardSubtype"=dword:00000001
"OverrideKeyboardIdentifier"="AX_105KEY"

変更点は、
LayerDriver JPN
OverrideKeyboardSubtype
OverrideKeyboardIdentifier
の3箇所です。

ただ、この設定にすると、右Ctrlが使えないようです。
僕はほとんど使わないので関係ないのですが、レジストリをいじり、Scancodeを差し替えれば、右Ctrlキーを左Ctrlキーとして使うことができます。

[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Keyboard Layout]
"Scancode Map"=hex:00,00,00,00,00,00,00,00,02,00,00,00,1D,00,1d,e0,00,00,00,00

当たり前ですが、左Ctrlキーはそのまま使えます。

http://www.atmarkit.co.jp/fwin2k/win2ktips/041axkbd/axkbd.html

を参考にさせていただきました。


  
Posted by gushwell at 22:07Comments(4)TrackBack(0)

2009年03月15日

[パズル]パワーアップの問題

   このエントリーをはてなブックマークに追加 Clip to Evernote
問題
ある任意のxに対して、xのn乗を求めたいとします。
演算としては乗算しかできないものとします。
このとき、最小の乗算回数で求めたいのですが、この
回数を 関数M(n)で表すことにします。
このM(n)を求めるプログラムを書いてください。
なお、一度計算した値は、覚えておいてかまいません。
M(23) と M(127)の値を求めてください。

たとえば、
M(2) は、1回です。これは x * xで求まるから自明ですね。
M(3) は、2回です。(x * x) * x
M(4) は、これも2回です。まず、(x * x) を求めれて、これを w とすれば、 w * w で求まるので、2回の掛け算で 4 乗が求まることになります。

----
この問題、解説にも書いてあるとおり、計算式を求めようとしてもその計算式を導き出すのは難しそうです。

で、この問題をよくよく吟味すると、問題にはn乗とありますが、xのn乗を求める必要は無いことに気がつきます。
必要なのは足し算だということがわかります。

例えば、M(9)で考えてみます。
すでに計算済みの値を F(z) と表します。F(3) は、xを3乗した値です。

どのような掛算で xの6乗になるかですが、最悪の計算は、
(x * x) * x * x * x * x * x * x * x で、8回の乗算が必要です。一度も計算済みの値を利用していません。
最小のだと、
((x * x) * x) * F(3) * F(3)
で、4回で求められます。
あるいは、同じ4回でも、
(x * x) * F(2) * F(4) * X
という求め方もあります。
その中間として、
((x * x) * x) * F(3) * F(2) * X
という計算方法もあります。この場合は、5回の計算結果となります。
つまり、M(9) = 4 です。

計算途中で何乗まで求めたかを表す数列で表すと、上の4つは、
2,3,4,5,6,7,8,9
2,3,6,9
2,4,8,9
2,3,6,8,9
となります。

ここからわかることは、9にたどりつく組み合わせを調べ、一番短い値を探せばよいことがわかります。
M(23)ならば、23に辿り着く数列を列挙し、その一番短いものを答えとすればよいのです。

結局、今まで解いてきたパズルと同様に、バックトラッキング手法を使い、しらみつぶしに調べて行くことにします。

何も考えずに書いたら、M(127)を求めるのにものすごく時間がかかってしまいました。
いろいろと工夫(枝刈りなど)をして、ようやく満足できるものができました。
以下、C#で書いた最終コードです。


using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;

namespace PowerUp {
class Program {
static void Main(string[] args) {
Stopwatch sw = new Stopwatch();
sw.Start();
Solver s = new Solver();
s.Found += new Action<List<int>>(s_Found);
int r = s.M(127);
Console.WriteLine("答え={0}回 (発見されたパターン={1})", r, count);
sw.Stop();
Console.WriteLine(sw.Elapsed);
}
static private int count = 0;

static void s_Found(List<int> list) {
count++;
list.ToList().ForEach(n => Console.Write("{0} ", n));
Console.WriteLine(": {0}回の乗算", list.Count - 1);
}
}

class Solver {
public event Action<List<int>> Found;
private List<int> _list = new List<int>(20);
private int _num;
private int _min;
public int M(int n) {
_num = n;
_min = int.MaxValue;
_list.Add(1);
Solve(1);
return _min - 1;
}

private void Solve(int n) {
if (n > _num)
return;
if (n == _num) {
if (_list.Count < _min) {
_min = _list.Count;
Found(_list);
}
return;
}

var q = from a in _list.Reverse<int>()
from b in _list.Reverse<int>()
select new Tuple { A = a, B = b };
foreach (var x in q.Distinct(new MyComparer()).ToList()) {
int c = x.A + x.B;
if (_list.ElementAt(_list.Count - 1) < c && !_list.Contains(c)) {
if (_list.Count + 1 < _min) {
_list.Add(c);
Solve(c);
_list.RemoveAt(_list.Count - 1);
}
}
}
}
}

class MyComparer : IEqualityComparer<Tuple> {
public bool Equals(Tuple x, Tuple y) {
return (x.A + x.B == y.A + y.B);
}

public int GetHashCode(Tuple obj) {
return (obj.A + obj.B).GetHashCode();
}
}

class Tuple {
public int A { get; set; }
public int B { get; set; }
}

}

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

2009年03月14日

メルマガ:C#プログラミングレッスン  祝:読者数1700名突破&第200号

   このエントリーをはてなブックマークに追加 Clip to Evernote
メールマガジン「C#プログラミングレッスン」の読者数がまぐまぐとメルマを合わせて1700名を突破しました。

そして、来週の発行で、とうとう記念すべき第200号の発行となります。
購読してくださっている皆さん、どうもありがとうございます。
感謝です。


現在は、LINQ to XMLについて連載中です。

  
Posted by gushwell at 12:44Comments(0)TrackBack(0)

2009年03月11日

3項演算子

   このエントリーをはてなブックマークに追加 Clip to Evernote
 Color backColor;
if (line % 2 == 1)
backColor = Color.Aqua;
else
backColor = Color.White;

これは、何のへんてつも無いコードですが、最近、初期化のない
Color backColor;
この部分がものすごく気になってしまいます。

そういったときは、3項演算子の出番です。

  Color backColor = (line % 2 == 1)
? Color.Aqua
: Color.White;

こすれば、変数宣言と初期化を同時にできます。  
Posted by gushwell at 22:34Comments(2)TrackBack(0)