エンジニアのスキルを試すコードパズル ─この問題,あなたは解けますか?

第12回 結城浩からの挑戦(第6回)解説編

この記事を読むのに必要な時間:およそ 3 分

挑戦者の解答結果は

今回のハサミ問題は,挑戦受付人数128人に設定しましたが,挑戦開始後わずか2日間で受付人数をオーバーしてしまいました。たくさんの方の挑戦,ありがとうございました。

評価分布

評価598名
評価314名
評価116名
合計128名

評価基準

1人が複数回投稿した場合には,最終投稿のみを評価しました。評価基準は以下のとおりです。

  • 評価5⇒ ぴったり正解(小数による解答も判断の上含めました)
  • 評価3⇒ 形式上のミスはあったが,内容は正解と判断(最小面積でなくても40回ならこちら)
  • 評価1⇒ 残念ながら不正解(ハサミの回数1回ずれはこちら)

挑戦者には個別に評価フィードバックを送りましたが,その中で1点おわびをしました。ハサミ問題の公開時点では「長さは正の整数とする」という条件を入れていなかったからです(公開当日に修正)⁠面積が小さい方が高い得点と指示したこともあり,どう考えればよいか迷った挑戦者もおり,中には小数で解答した方もいらっしゃいました。

解答を吟味のうえ,長方形の辺の長さが小数になっているものは,ハサミの回数が正確に40回になっていれば評価5としました。

長方形の辺の長さが整数の場合,ハサミの回数が正確に40回になっていても,面積が最小でないならば評価3としました。たとえば,1746860020068409x4217293152016490は,ハサミの回数は正確に40回になりますが,面積が大きいため,評価3です。

たいへん惜しくも「ハサミの回数1回ずれ」の解答がいくつかありました。つまり,165580141x267914296にしてしまった方ですね。これだとハサミの回数は39回になってしまいます。今回は評価1としました。このような「1回ずれ」は,オフ・バイ・ワン(off-by-one)のエラーなどと呼ばれることもあり,プログラミングではよくあるミスなので,厳しく採点しました。

その一方で,267914296x433494437を433494437x267914296と逆に書いた解答もありました。問題の指示では「縦x横」の形式で「縦≦横」でなければならなかったのですが,こちらは評価3としました。

解答あれこれ

多くの解答者が,今回の2つのキーワード(ユークリッドの互除法・フィボナッチ数列)をメッセージ中に書いていました。

これらのキーワードに気づいたタイミングは,人それぞれです。問題を見た瞬間に気づく,具体例を作っているうちに気づく,プログラムを書いている途中で気づく,プログラムを動かして気づく……などですね。これらのキーワードにはまったく気づかずに正解している方もいらっしゃいました(もちろん,その方も文句なく正解です)⁠

解答者が使ったプログラミング言語やソフトウェアは,以下のように多彩でした(もしも抜けがあったらごめんなさい)⁠

C, C#, C++, Clojure, Common Lisp, Excel, Groovy, Haskell, Java, Objective-C, Pascal, Perl, PHP, Processing, Python, Ruby, Scala, Scheme, VBA...

最後に

以上が「ハサミ問題」です。楽しんでいただけたでしょうか。

結城はこれからもCodeIQで出題していきますので,次回もぜひチャレンジしてくださいね。挑戦ありがとうございました!

CodeIQ
URL:http://www.hyuki.com/codeiq/

参考プログラム

参考まで,結城が用意した解答を作りだすプログラム(list_scissors.pl)は以下です(Perl)⁠

リスト1 list_scissors.pl

# list_scissors.pl
use strict;
use warnings;

# F_1=1, F_2=1, F_3=2, F_4=3, F_5=5, F_6=8, ...
# ハサミを1回使う最小の長方形は,2x3のとき(1x2が「端」になる)⁠
# ハサミを2回使う最小の長方形は,3x5のとき(2x3が「端」になる)⁠
# ハサミを3回使う最小の長方形は,5x8のとき(3x5が「端」になる)⁠
# …
# ハサミをn回使う最小の長方形は,F_{n+2} x F_{n+3}のとき(F_{n+1} x F_{n+2}が「端」になる)⁠

my $height = 2;
my $width = 3;
my $n = 40;

for (my $k = 1; $k <= $n; $k++) {
    print "ハサミ$k回: ${height}x${width}\n";
    ($height, $width) = ($width, $height + $width);
}

また,解答チェックのために作った,与えられた長方形が何回ハサミを使うことになるかを調べるプログラム(try_scissors.pl)は以下です。何個かサンプルも付けました(解答のすべてではありません)⁠

リスト2 try_scissors.pl

# try_scissors.pl
use strict;
use warnings;

sub scissors {
    my ($m, $n) = @_;
    print "scissors($m, $n) = ";
    my $count = 0;
    if ($m < $n) {
        ($m, $n) = ($n, $m);
    }
    while (1) {
        my $r = $m % $n;
        if ($r == 0) {
            print "$count\n";
            return $count;
        }
        $count++;
        ($m, $n) = ($n, $r);
    }
}

&scissors(42, 144);
&scissors(267914296, 433494437);
&scissors(1746860020068409, 4217293152016490);
&scissors(1746860020068409, 2470433131948081);
&scissors(165580141, 267914296);

実行結果は以下です。

scissors(42, 144) = 2
scissors(267914296, 433494437) = 40
scissors(1746860020068409, 4217293152016490) = 40
scissors(1746860020068409, 2470433131948081) = 40
scissors(165580141, 267914296) = 39

著者プロフィール

結城浩(ゆうきひろし)

数学青春物語「数学ガール」シリーズ作者。プログラミング言語入門書,IT技術書,数学入門書などの著書多数。

日記:http://www.hyuki.com/d/
Web連載:http://www.hyuki.com/girl/note.html
メルマガ:http://www.hyuki.com/mm/
Twitter:@hyuki