2009年02月25日

[パズル]ステインハウスの三角形

  
ステインハウスの三角形とは、以下の3つの条件を見たいています。
1.この三角形は以下のように0と1からんばっている。
2. n行目はn-1行目の隣同士の数字の排他的論理和となっている。
3. 0 の数と1の数が同じ。


ステインハウスの三角形


問題1
三角形の辺の長さ n を与えられた時、nの値ごとに、何個のステインハウスの三角形があるかを調べるプログラムを書け。
ただし、左右対象となる鏡像は同一の三角形とみなすこと。

-----

すべてのパターンに対して、1と0の数が同じになる三角形の数を数えるという、もっともオーソドックスな方法を採用することにします。
それしか、思いつかない(笑)

n個からなる0と1からなるすべてのパターンを求める方法の一つとして、
0から2^n-1までの整数をビットパターンに変換すれ方法があります。
これだと、nの上限に制限ができてしまうけど、そこまで大きな三角形は必要ないだろいと、勝手に対象外ということにしました。

つまり、

int maxcount = (int)Math.Pow(2, n);
for (int i = 0; i < maxcount; i++) {
...
}

というループで、すべてのパターンを処理できることになります。
実際のコードは、LINQを使って

Enumerable.Range(0, maxcount).Aggregate(...);

というコードにしています。

この iから、ビットパターンを生成して、逆三角形の上辺のパターンとし、排他的論理和を行い、三角形を作ります。この三角形の、0と1の数が等しければ、ステインハウスの三角形ということで、カウントアップしていけば、答えが求まることになります。

なお、0と1の和が偶数でないと、条件3を満たさないので、辺の長さを nとすれば、

n * (n + 1) / 2

が偶数のときだけ、計算すればよいことになります。
上記計算式は、三角形の面積(1と0の総数)を示しています。
また、鏡像を2重にカウントしないようにするために工夫していますが、それは実際にコードを見てください。

これをC#で書いたのが以下のコードです。
今回は、今まで以上にLINQを使っています。LINQ面白いですね。
特に、ToInt()メソッドやNeedCount()メソッド内のコードは感動的です。

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

namespace XorTriangle {
class Program {
static void Main(string[] args) {
int n = 20;
for (int i = 1; i <= n; i++) {
if (i * (i + 1) / 2 % 2 == 0) {
Solver sol = new Solver(i);
Console.WriteLine("{0} : {1}", i, sol.Execute());
}
}
}
}

class Solver {
private int width;
private bool[] buffer;
public Solver(int n) {
this.width = n;
buffer = new bool[n];
}

public int Execute() {
int maxcount = (int)Math.Pow(2, width);
return Enumerable.Range(0, maxcount).Aggregate(0, (acc, n) =>
acc + (IsSteinhausTriangle(n, width) ? 1 : 0)
);
}

// ステインハウスの三角形かどうかを調べる
private bool IsSteinhausTriangle(int baseline, int width) {
// int型のまま処理するのは、面倒なので、bool[]に変換して処理をする。
bool[] line = ToArray(baseline, width);
if (!NeedCount(line)) // 鏡像を考慮する。
return false;
int tcount = 0; // 1の数
int fcount = 0; // 0の数
while (line.Length >= 1) {
tcount += line.Where(b => b == true).Count();
fcount += line.Where(b => b == false).Count();
line = NextLine(line);
}
return tcount == fcount;
}

// 鏡像をカウントしないようにするための判定メソッド
private bool NeedCount(bool[] line) {
if (IsRound(line))
// 左右対称ならば、他に鏡像となるパターンはないので、これは調べる必要がある。
return true;
// 左右対称でないならば、鏡像のパターンが他にもうひとつあるので、
// 片方だけを調べるようにする。
return ToInt(line.Reverse().ToArray()) > ToInt(line);
}

// ビットパターンが左右対称かどうかを調べる
private bool IsRound(bool[] line) {
int j = line.Length - 1;
int i = 0;
while ( i < j ) {
if (line[i++] != line[j--]) {
return false;
}
}
return true;
}

// bool[]をビットパターンとみなし、intに変換する
private int ToInt(bool[] line) {
return line.Aggregate(0, (r, b) => r * 2 + (b ? 1 : 0));
}

// 整数nを width個からなるbool配列に変換する
public bool[] ToArray(int n, int width) {
bool[] array = new bool[width];
int mask = 1;
width.Times(i => {
array[i] = (n & mask) != 0;
mask <<= 1;
});
return array;
}

// 1段下のラインを排他的論理和を使い求める
public bool[] NextLine(bool[] line) {
bool[] next = new bool[line.Length - 1];
int i = 0;
// ここで、Aggregateを使うのは邪道かな?
line.Aggregate((a, b) => {
next[i++] = a ^ b;
return b;
});
return next;
}

// デバッグ用 
public void PrintLine(bool[] line) {
line.ForEach(b => Console.Write(b ? 1 : 0));
Console.WriteLine();
}
}


static class EnumerableExtentions {
// 要素の数だけ、actionを呼び出す
public static void ForEach<T>(this IEnumerable<T> source, Action<T> action) {
foreach (var x in source) {
action(x);
}
}

// n回、actionを呼び出す
public static void Times(this int count, Action<int> action) {
for (int i = 0; i < count; i++)
action(i);
}
}
}





結果は、以下のとおりです。

3 : 3
4 : 3
7 : 7
8 : 22
11 : 87
12 : 205
15 : 956
16 : 2595
19 : 16402
20 : 29992


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



この記事へのコメント
自己レスです。
あわててアップしたので、この記事、誤字脱字だらけですね。
意味はそれなりに取れると思いますが... お恥ずかしい。
Posted by gushwell at 2009年02月27日 12:40
 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/51762628