2011年01月24日 22:00 [Edit]

Math - 5×5のマス目に6個の○を次の条件を満たすように全部書く

体調もやる気も

このやる気はフィクションであり、実在の人物・団体・事件などとは一切関係ありません < dankogaiのやる気スイッチは幻想でした。 http://shindanmaker.com/14342 #yarukiless than a minute ago via HootSuite

というありさまなので、リハビリ代わりに

の最後の問題をiMacに解かせてみた


問題7

5×5のマス目に6個の○を次の条件を満たすように書きます。

条件:各行・各列に少なくとも1個は○を書く。同じマスには2個以上の○を書くことはできない。

このとき、6個の○を書く方法は全部で何通りありますか。

これを何も考えずCに直訳したのが以下。

5x5x6.c
#include <stdlib.h>
#include <stdio.h>

#define printit(a,b,c,d,e,f) printf("%02d,%02d,%02d,%02d,%02d,%02d\n",\
				    a,b,c,d,e,f)

int main(void){
    char rows[5], cols[5];
    int a, b, c, d, e, f, i, p = 0, t = 0;
    for (i = 0; i < 5; i++) rows[i] = cols[i] = 0; /* init */
    for (a = 0; a < 25; a++){
	rows[a % 5]++; cols[a / 5]++;
	for (b = 0; b < 25; b++){
	    if (a == b) continue;
	    rows[b % 5]++; cols[b / 5]++;
	    for (c = 0; c < 25; c++){
		if (a == c) continue;
		if (b == c) continue;
		rows[c % 5]++; cols[c / 5]++;
		for (d = 0; d < 25; d++){
		    if (a == d) continue;
		    if (b == d) continue;
		    if (c == d) continue;
		    rows[d % 5]++; cols[d / 5]++;
		    for (e = 0; e < 25; e++){
			if (a == e) continue;
			if (b == e) continue;
			if (c == e) continue;
			if (d == e) continue;
			rows[e % 5]++; cols[e / 5]++;
			for (f = 0; f < 25; f++){
			    if (a == f) continue;
			    if (b == f) continue;
			    if (c == f) continue;
			    if (d == f) continue;
			    if (e == f) continue;
			    rows[f % 5]++; cols[f / 5]++;
			    t++;
			    if(    rows[0] && cols[0]
				&& rows[1] && cols[1]
				&& rows[2] && cols[2]
				&& rows[3] && cols[3]
				&& rows[4] && cols[4]
				) {
				printit(a,b,c,d,e,f);
				p++;
			    }
			    rows[f % 5]--; cols[f / 5]--;
			}
			rows[e % 5]--; cols[e / 5]--;
		    }
		    rows[d % 5]--; cols[d / 5]--;
		}
		rows[c % 5]--; cols[c / 5]--;
	    }
	    rows[b % 5]--; cols[b / 5]--;
	}
	rows[a % 5]--; cols[a / 5]--;
    }
    fprintf(stderr, "%d / %d\n", p, t);
    return 0;
}

こんな力押しコードに20分も罹って、大丈夫か?

しかもこれ、例えば(00,06,12,18,24,01)と(01,06,12,18,24,00)を別カウントしているので、○をそれぞれ別ものとして扱った場合は正しいのだろうけど、問題を見る限りこういう場合は同一視しなければならなさそう。とすると、3,024,000を6! = 720 で割った 4,200が正解ということかな?

この場合の全組み合わせは、上のstdoutをさらに以下のperl scriptに食わせれば出る。

5x5x6-pp.pl
#!/usr/bin/env perl
use 5.010;
use strict;
use warnings;

my %dupe;
while(<>){
    chomp;
    $dupe{ join ",", sort split /,/, $_ }++
};
say for sort keys %dupe;

こんだけ力押ししても、Core i7なiMacでは実行はこんなもん。

% gcc -W -Wall -O6 5x5x6.c
% /usr/bin/time -l ./a.out >! 5x5x6.out
3024000 / 127512000
        3.68 real         3.15 user         0.14 sys
         0  maximum resident set size
         0  average shared memory size
         0  average unshared data size
         0  average unshared stack size
         0  page reclaims
         0  page faults
         0  swaps
      1007  block input operations
         1  block output operations
         0  messages sent
         0  messages received
         0  signals received
      1025  voluntary context switches
         0  involuntary context switches
% wc 5x5x6.out
 3024000 3024000 54432000 5x5x6.out
% perl 5x5x6-pp.pl 5x5x6.out |wc
    4200    4200   75600
  • 6重ループってなにこれきもい
  • continueの使い方とかコピペ濫用にもほどがある。
  • それでも一応問題の見積もりはしている。チェックすべき組み合わせは 25P6 = 127,512,000。この時点でCで書くことを決定。
  • キモいループが正しくまわっているかどうかを、一応ループカウントしてチェック。確かに127512000と出ている。
  • アンチョコは一切見ていない。「エレガントな問題解決」に似たような問題が出ていたような気はするのだけど…

なんて書いておくと、MacBook Airくれるのかしらん…

Dan the Brute Forcer


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

この記事へのトラックバック
はてなブックマークニュースで見た算数オリンピックの問題を、総当りせずに、算数的に解けたので嬉しくなってエントリ。 5×5のマス目に6個の○を次の条件を満たすように書きます ...
算数オリンピックの問題をちゃんと算数的に考えて解いたよー【アフィリエイトでたばこの値上がりを取り戻したいブログ】at 2011年01月25日 23:31
この記事へのコメント
YahooJAPANのOpenID?でログインしたら名前がこんなだが大丈夫か?
Posted by https://me.yahoo.co.jp/a/5S_TQ5UPOYb8vOmByHubIvHk#11f3d at 2011年01月28日 16:07
for(b=0;...)
ではなく、
for(b=a+1;...)
(c,d,e,fについても同様)
とすれば、最初から重複なくチェックでき、
if (a==b) continue;
も不要で処理速度も一瞬で4200と結果が出ます。

$ time ./a.exe > /dev/null
4200 / 177100

real 0m0.042s
Posted by https://me.yahoo.co.jp/a/5S_TQ5UPOYb8vOmByHubIvHk#11f3d at 2011年01月28日 16:06
ごめんなさい、なんか、まちがってるうえに変な操作して、連投しちゃいました。
Posted by tomoharu2525 at 2011年01月26日 05:06
(1) 5つの○を、どの行・列でも重複しないで配置するやり方  5! = 120

(2) (1)の各々について、残りの1つの丸を配置するやり方
=残ってるマスの数
Posted by tomoharu2525 at 2011年01月26日 04:56
(1) 5つの○を、どの行・列でも重複しないで配置するやり方  5! = 120

(2) (1)の各々について、残りの1つの丸を配置するやり方
=残ってるマスの数
Posted by tomoharu2525 at 2011年01月26日 04:56
(1) 5つの○を、どの行・列でも重複しないで配置するやり方  5! = 120

(2) (1)の各々について、残りの1つの丸を配置するやり方
=残ってるマスの数
Posted by tomoharu2525 at 2011年01月26日 04:56