読者です 読者をやめる 読者になる 読者になる

give IT a try

プログラミング、リモートワーク、田舎暮らし、音楽、etc.

Excel列名変換問題で第2回社内プログラミングコンテストを開催してみた(前編)

社内勉強会
2011.12.31 追記

後編を書きました。こちらもあわせてどうぞ。
Excel列名変換問題で第2回社内プログラミングコンテストを開催してみた(後編) - give IT a try

はじめに

先日、FizzBuzz問題を使って社内プログラミングコンテストを開きました。
このブログでも書いた通り、なかなか興味深い結果になりましたが、一方で反省点もいくつか見つかりました。
特に問題が解けなかった人が出てしまったのは痛い誤算だったので、今回はできるだけ最後まで解けるような配慮をしてみました。
ただし、問題自体はFizzBuzz問題よりもずっと難しくしてあります。


今回もちょっと長いエントリになっていますが、よろしければ最後までお付き合いくださいませ。

前回の反省点

詳しくはこちらのエントリに書きましたが、簡単にまとめると

  • 言語の得意・不得意が結果に大きく影響した
  • 抜き打ちで実施したことがその影響をより大きくした

という2点に集約されます。

今回の変更点

前回の反省点を活かし、今回はコンテストのルールを以下のように変更してみました。

  • 開催日と使用言語を事前に通知する。
    • 開催日は約2週間前に通知。
    • 使用する言語をPerlに統一することも同時に通知。
    • 「基本構文と文字列関数が重要。ファイル操作は出題しない。」というように、予習項目もある程度通知。
    • その代わり、Perlが苦手なんで解けませんでした」はNGとする。
  • 速さを競わない。
    • いくら予習しても実務経験の差は縮まらないので、解答の速さは評価しない。
    • 前回は速く解けた人にボーナスポイントを与えたが、今回は無し。
  • 問題は2問、解答時間は90分とする。
    • 前回は1問30分だったが、今回は量を増やす。
    • 問題の難易度も上げる。
    • 問題1が解けるまで、問題2を見ることはできない。スキップもNG。
  • 異常系入力の考慮は不要
    • 起動時引数の個数異常や、フォーマット異常を考慮したロジックは不要とする。
    • 問題に書かれた仕様を充たすだけで良い。
  • Perlが無理ならコメントで逃げる。
    • Perlの構文やイディオムが分からないせいでどうしてもロジックが書けない場合は、コメントを使ってロジックを表現する。
    • ただし、これはあくまで最終手段とする。

コメントを使ってロジックを表現する例

my $endval = #起動時引数を取得

foreach my $i (1 .. $endval) {
    my $fizz = # i ÷ 3のあまりを求める;
    my $buzz = # i ÷ 5のあまりを求める;

    if ($fizz == 0 and $buzz == 0) {
        print "FizzBuzz";
    }

    #(以下略)

*1


最後の「コメントで逃げる」というルールについては、「そんなバカな」と思われる人がいるかもしれません。
確かにかなり変なルールですが、解けなかった人がまた出てきた場合に、ロジック自体が頭の中でできていなかったのか、それとも使用する言語のせいで動作するプログラムが書けなかったのかを判断するための苦肉の策として用意しました。

前回から変わらない点

それ以外は基本的に第1回と同じルールになっています。

  • インターネットや書籍の利用を許可する。
    • ただし、解答そのものを検索したり、メインロジックを全く不要にするようなライブラリの使用は禁止する。
  • 投票によって優勝者を決定する。
    • メンバーの前で動作確認とプログラムの説明を行う。
    • メンバーは気に入ったプログラムを3本選出し、投票する。
    • 評価ポイントは基本的に個人の自由。
    • 1位3点、2位2点、3位1点となり、合計点が多い人が優勝。
  • コンテストの目的:
    • 自分のスキルを相対的に評価する。
    • 他人のロジックやコードから新しい発見を得る。
    • 良い意味でメンバー内の競争心をあおる。
  • 出題者は解答と投票には参加するが、評価の対象にはならない。(順位は付かない)

当日の参加人数

  • プログラマは自分を含めて11人。
    • 下は20代後半、上は50前後。
    • 業務経験年数は全員5年以上。
    • 当日は家庭の事情により出席でないメンバーが2人いた。(ただし、1名は家で解答していた)

今回の問題

今回はFizzBuzz問題よりもずっと難しいです。
一見、簡単そうに見えますが、実際やってみると「あれれ??」となってしまう人が結構いるんじゃないかと思います。
もちろん、このブログを見てる方の中にはかなりの強者もたくさんおられると思うので、優秀な皆さんなら、さらっと解いてしまうと思いますが・・・。

問題1: Excel列名変換問題
  • 仕様
    • 入力されたアルファベットを数字に変換する。
    • 変換ルールはExcelの列名と同等。
    • 例) A=1、B=2、Z=26、AA=27、XFD=16384
  • 起動時引数
    • [0] アルファベット (A〜ZZZZ...[上限なし])*2
  • 実行例
    • ExcelColConv.pl A → 1
    • ExcelColConv.pl AA → 27
問題2: Excel列名変換問題(逆変換)
  • 仕様
    • 入力された数字をアルファベットに変換する。
    • ただし、問題1で作ったプログラムを拡張すること。
  • 起動時引数
    • [0] 0=数字へ変換、1=アルファベットへ変換
    • [1] 変換する数字またはアルファベット(どちらも上限なし)
  • 実行例
    • ExcelColConv.pl 0 AA → 27 *3
    • ExcelColConv.pl 1 27 → AA


問題1も問題2も、見た目はどちらも同じような難易度に見えますが、実は問題2には大きな落とし穴が潜んでいます。
問題2は問題1よりもはるかに難しいです・・・!!

で、実際にやってみた

実はコンテストの前においらはこの問題を解いてました。ただし、使った言語はF#とC#です。Perlでは解いていません。
最初60分にしようと思っていた解答時間を90分に伸ばしたのは、実際にやってみて予想以上に難しいことがわかったからです。


ただ、そんなわけで実装すべきロジック自体はやる前から完全にわかっていました。
なので楽勝楽勝〜♪とTest::Moreを使ってテスト駆動開発を始めたのですが・・・。


ごめんなさい、Perlをナメてました。


Perlは決して得意な言語ではありませんが、基本構文ぐらいなら大体理解しているつもりです。
この問題で使いそうな標準関数も事前にチェックしていました。


が、実際書いてみると変なエラーが続出したり、サブルーチンの引数の受け渡し方法が分からなくなったり、思ったようなスピードで解き進めることができませんでした。


あと、その日は運悪くPCのウイルスチェックが走ってしまい、やたらPCが遅かったのも痛手でした。
実行するのに毎回5秒以上待たされる始末。
うわ、エラーが出た!修正!実行!・・(5秒)・・あれ?またエラーが出た!よし修正!実行!・・(5秒)・・ああっ、またエラーが!
というテンポはかなり辛かったです。普通だったら0.5秒ぐらいで実行できるのに・・・(T T)。


事前に考えていたペース配分では第1問30分、第2問45分、リファクタリング15分、ぐらいで考えていたのですが、なんと第1問だけで1時間も食ってしまいました。


ロジックが最初からわかっているおいらですらこんな状況なので、他のメンバーは結構悲惨な感じでした。

そして90分が経過した

はい、それまで!!


・・・と切り上げたかったのですが、おいらも含めて周りはまだ誰も完全に終わっていない様子・・・。
マネージャーも「終わって・・・いいのかな?」みたいな感じで、すぐには終わりの合図を出せないようでした。


結局おいらは90分と5分ぐらいで第2問まで完了しました。
忌々しいウイルスチェックさえなければきっと時間内に終了していたはず・・・っていうのは、やっぱ言い訳ですよね?


そしておいら以外のメンバーはというと・・・


第1問を解けたメンバーが7人。解けなかったメンバーが3人。
ただし、1人は90分以内には解けなかったものの、動作確認の時間までには何とか完成させたそうです。


そして、第2問を解けたメンバーは残念ながら一人もいませんでした。


これまた予想外。
今回こそは全員に解答してもらって、楽しい動作確認とプログラム説明タイムにしようと思ったのですが・・・。
難易度と解答時間の適切なさじ加減は本当に難しいです。

急遽コンテストが前編・後編の2部構成に

本当であれば第2問の動作確認とプログラム説明をメインにしようと思っていたのですが、誰も解けていない以上、そんなことをしてもほとんど意味がありません。
そこで急遽ルールを変更し、第2問は各自の宿題とすることにしました。
適当に空いている時間を見つけて、じっくりと解いてもらうことにしました。


動作確認&プログラム説明タイムも2日にわけます。
この日の説明は第1問に限定し、第2問の説明タイムは1週間後の11月7日に実施することになりました。
このエントリのタイトルに「前編」という文字が入っているのはそれが理由です。
実はこのエントリを書いている現時点では、コンテストは完全に終わっていないのです。


まあ、スピード重視の前編と、品質重視の後編にうまく分かれて、面白そうじゃない?と、自分に言い聞かせるようにしています。はい・・・。orz

動作確認&説明タイム

というわけで第1問に限定した動作確認&説明タイムが始まりました。
FizzBuzz問題と違って、今回の問題はパッと見ただけではどういうカラクリで動作しているのか、なかなかわかりづらかったです。
プログラムを書いた本人の中では筋が通っていても、第三者がそれを見ると一体何をやっているのか、すぐにはわからないものです。


ただ、説明を聞いていると全員のロジックはそこまで大きく変わったのものではないことが徐々にわかってきました。
ほとんどのパターンは、以下のようになります。


"XFD"を変換する場合

  1. X、F、Dを後ろから一文字ずつ取得する。
  2. D は アルファベットの4番目でかつ、後ろから1番目(0)なので「26の0乗 × 4 = 1 × 4 = 4」と評価する。
  3. F は アルファベットの6番目でかつ、後ろから2番目(1)なので、「26の1乗 × 6 = 26 × 6 = 156」と評価する。
  4. X は アルファベットの24番目でかつ、後ろから3番目(2)なので、「26の2乗 × 24 = 676 × 24 = 16224」と評価する。
  5. 3つの値を合計した「4 + 156 + 16224 = 16384」が答えとなる。


組み方自体は個人個人でバリエーションはありますが、計算式としては結局同じことをやっていたはずです。
なお、動作確認中にバグを発生させた人はいませんでした。


結局、最後まで解けなかった2人のうち、1人は「AZ=52、BA=28」となってしまう不具合を解決できなかったそうです。
もう1人は完全に問題を読み間違えていたらしく、実際のExcelファイルを読み込んで、ファイル内に書きこまれた値と列名をマッピングするプログラムを書こうとして時間が足りなくなったそうです。う〜ん、すごい勘違い・・・。


ただし、最終手段として用意しておいた「コメントで逃げる」作戦を選択したメンバーは誰もいませんでした。
さすがにこれを使う人はいないですよね〜。おいらとしても使ってほしくないです、ほんまに。


ちなみに、「これまで全く同じプログラムを書いたことがありますか?」という質問に対しては、全員がNOと答えました。(おいらはその昔、VBAで作ったような気がしますが。。。)
ただ、問題を解く際に基数変換の知識を応用した、と答えたメンバーは何人かいました。

投票&開票結果

さて、全員の解説が終わり、いよいよ投票によるベストプログラマの選出です!
ドキドキドキ・・・。今回の優勝者は誰でしょう??


優勝者は・・・前回と同じAさんでした!2冠達成です!
2位も前回と同じMさんでした。
3位は前回欠席していたKさんです。


というわけで、1位と2位は前回と同じプログラマが選ばれる結果となりました。
獲得ポイントを見ても、1位28点、2位23点、3位10点なので、1位と2位のメンバーは3位のメンバーにかなり差をつけています。
前回と同じく、ごちゃごちゃしたプログラムよりも、ぱっと見、シンプルで洗練されているように感じるプログラムの方が、高い評価を得ています。(ある意味当然ですけどね)


それから、このコンテストが前述した「目的」を実現するのに役立っているかどうかもアンケートしてみました。
これについてはほぼ全員からYESという回答をもらいました。
決してムダにはなっていないようなので、とりあえず安心しました。


なお、後編(第2問)でも改めて投票を行い、ランキングを付ける予定です。
果たしてAさんはこのまま3冠を達成するのか?ちょっと興味深いポイントです。

前編のまとめ

今回こそは全員が時間内に解答できるように、じっくり策を練ったつもりだったのですが、結果は期待と大きく外れてしまったので、ちょっとヘコみました。
「これはどう見ても楽勝でしょ」と思うぐらいのレベルじゃないと、全員が初見で時間内に解答するというのは難しいのかもしれません。


あと、出題者であり、すでに別の言語で解いたことのあるおいら自身が終始苦戦してしまったというのも、個人的には痛かったです。
解答時間中に嫌な汗をいっぱいかいてしまいました、ホント・・・。


まあ、そんな反省点はありますが、見方を変えればFizzBuzzみたいな簡単すぎる問題よりも、ちょっと難しくて時間が足りない問題ぐらいの方がスリリングで面白いのかもしれません。一応、コンテストですから。
ただ、問題が難しいと他人の書いたロジックが即座に理解しにくくなる、という弊害も垣間見えました。


とりあえず、まだ後編が残っているので、前編のまとめはこれぐらいにとどめておきます。
それではまた後編でお会いしましょう!

参考資料

今回は上位3人のプログラムとおいらが書いたプログラムを載せておきます。
また、前回と同様、コンテストで使用したスライドも載せておきますので、ご参考までにどうぞ。

1位の人が書いたプログラム

最初にハッシュを手書きで作ってしまっているのが少し気になりますが、それ以外はかなりシンプルにまとまっていると思います。

my %table = (
        ('A', 1),
        ('B', 2),
        ('C', 3),
        ('D', 4),
        ('E', 5),
        ('F', 6),
        ('G', 7),
        ('H', 8),
        ('I', 9),
        ('J', 10),
        ('K', 11),
        ('L', 12),
        ('M', 13),
        ('N', 14),
        ('O', 15),
        ('P', 16),
        ('Q', 17),
        ('R', 18),
        ('S', 19),
        ('T', 20),
        ('U', 21),
        ('V', 22),
        ('W', 23),
        ('X', 24),
        ('Y', 25),
        ('Z', 26),
);

my $answer = 0;
my $n;

my @input = split(//, $ARGV[0]);


for (my $i = 0; $i < ($#input + 1); $i++) {

        $n = $table{$input[$i]};
        $answer = ($answer * 26) + $n;
}

print "$answer\n";
2位の人が書いたプログラム

最初にコメントを書いてからプログラムを書いていったそうです。
こちらはハッシュではなく、ord関数を使ってアスキー文字コードを取得しています。個人的にはこちらのアプローチの方が洗練されていて好みです。

use strict;
use warnings;

#### Convert Excel style column letters to index numbers

# Get parameter
my $input = $ARGV[0];

# Convert to upper case
#
# ABC... Z
# 123...26
# AA AB AC
# 27 28 29

# We are essentialy working in base 26 but without zero's i.e. A0
# Reverse the string for easy column counting
my $reversed_string = reverse($input);
# Split our "number" into columns
my @columns = split(//, $reversed_string);

my $total;

# Loop over columns (units, 26s, 26^2s, 26^3s etc
for(my $i = 0; $i < scalar(@columns); $i++) {
    # Convert A-Z to a number
    my $ascii_code = ord($columns[$i]);
    # subtract 64 (to convert A to 1 B to 2 etc)
    my $value = $ascii_code - 64;

    # Raise to the power appropriate to current numbers column
    if ($i > 0) {
        $value = $value * (26 ** $i);
    }
    # Add to total variable (making a cumulative sum)
    $total += $value;
# end loop
}

# print out the total
print "$total\n";
    
3位の人が書いたプログラム

こちらはハッシュでもord関数でもなく、文字列とindex関数を使っている点がユニークです。
同じ問題なのにそれぞれアプローチが全然異なっていることがよくわかります。

use strict;

my $input_string = $ARGV[0];

#配列に格納する
my @number_array = split(//,$input_string);

#文字数
my $keta = @number_array;

#A-Zを格納
my $jisyo = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

my $find=0;
my $result = 0;

foreach my $kazu(@number_array)
{

	#何番目のアルファベットか?
	$find = index ($jisyo, $kazu)+1;

	#26進 -> 10進
	$result = $result + ($find * (26 ** ($keta-1)) );

	#階乗用の値を減らす (桁が下がるから)
	$keta = $keta -1;
	$find = 0;
}

print "$result\n";
おいらが書いたプログラム

アプローチが違うという点では、おいらもかなりアプローチが違います。
まず、Test::Moreを使ってテスト駆動開発(TDD)しました。
テストしやすいように、メインロジックはモジュールとして別ファイルにしてあります。
そういやTDDで作ってたのもおいらだけだったなあ・・・。


また、ループ処理ではなく再帰を使ってメインロジックを実装しました。
再帰を使った理由はまず最初にF#でこの問題を解いたからです。
F#ではリストを使った再帰処理が面白かったので、Perlでもそのアプローチをそのまま採用しました。


あと、焦って作っていたので、変なコメントやデバッグ用の文が一部残ったままになっています (^o^;;


実行用プログラム(ExcelColConv.pl)

use strict;
use Carp;
use warnings;
use ExcelUtil;
main(@ARGV);
sub main {
    my @args = @_;
    my $arg = $args[0];
    my $ans = ExcelUtil::to_n($arg);
    print "$ans\n";
}


メインロジック用モジュール(ExcelUtil.pm)

package ExcelUtil;

use strict;
use warnings;

use base qw/Exporter/;
our @EXPORT_OK = qw(to_n);

my $az_cnt = 26;
my $offset_n = 64;

sub to_n {
    my ($s) = @_;

    my @s_array = split(//, $s);


    return conv_s(0, @s_array);
}

sub conv_s {
    #my ($acc_n, $s_array) = @_;
    my $acc_n = shift @_;
    my @s_array = @_;

    my $len = @s_array;
    if ($len == 0) {
        return $acc_n;
    }

    my $c = shift @s_array;
    my $c_val = a_to_i($c);
    my $len2 = @s_array;
    return conv_s(($az_cnt ** $len2) * $c_val + $acc_n, @s_array);

}

sub a_to_i {
    my ($c) = @_;
my $ord_val = ord $c;
    return ord($c) - $offset_n;
}


1;


ユニットテスト(test.pl)

use strict;
use warnings;

use Test::More 'no_plan';

my @subs = qw(to_n);

use_ok('ExcelUtil', @subs);
can_ok(__PACKAGE__, 'to_n');
my $n;

$n = to_n('A');is($n, 1, 'A');
$n = to_n('B');is($n, 2, 'B');
$n = to_n('C');is($n, 3, 'C');
$n = to_n('Y');is($n, 25, 'Y');
$n = to_n('Z');is($n, 26, 'Z');
$n = to_n('AA');is($n, 27, 'AA');
$n = to_n('AB');is($n, 28, 'AB');
$n = to_n('AY');is($n, 51, 'AY');
$n = to_n('AZ');is($n, 52, 'AZ');
$n = to_n('BA');is($n, 53, 'BA');
$n = to_n('BB');is($n, 54, 'BB');
$n = to_n('IV');is($n, 256, 'IV');
$n = to_n('XFD');is($n, 16384, 'XFD');
当日使用したスライド

こんな感じのスライドでメンバーに説明してました。
動作確認のスライド(P20)以降は第1回とほぼ同じですね。

*1:2011.11.07 05:00am 「i ÷ 3」を「i ÷ 5」に修正。

*2:上限なしというのは、Excelと同等とは言ってもIVやXFDまでではなく、それ以上の値も許容すること、という意味です。実際のプログラムではデータ型やメモリの制約があるので、完全に上限をなくすのはほとんど不可能です。もし「上限はXFDとする」のように書くと、「3桁の場合の計算式、2桁の場合の計算式、1桁の場合の計算式」みたいな柔軟性のないロジックを書く人がたまに出てくるので、こういう注釈を付けました。問題2も同様。

*3:2011.11.03 09:50am 修正