『第4回デスマコロシアム』私の Perl (57)

CodeIQ

はじめに

『第4回デスマコロシアム』に参加しました。今回のルールは、

  • $&(*,.02468:<>@BDFHJLNPRTVXZ\^`bdfhjlnprt$(,048<@DHLPTX\`dhlpt$*06<BHNTZ`flr$,4<DLT\dlt$.8BLV`jt$0<HT`l$2@N\j$4DTdt
    という文字列を出力するプログラムを書く
  • 評価基準は【文字数×(重複文字数+1)】が小さいほど良い
  • 言語ペナルティやトーナメントはいつもと同じ

といったところです。要するに、短くて、しかもなるべく同じ文字を使わないものが高評価ということです。

出題者様による結果記事
https://codeiq.jp/magazine/2014/07/12364/

私は、最終的に Perl (57) でエントリして、最小賞をいただきました。前々回と前回に続いて、3度目の最小賞受賞です。おめでとうございます。ありがとうございます。

結果の公開後、私のコードに対して、ツイッター上で「すごい」「頭おかしい」「変態」など、見ず知らずの多くの方々からお褒めの言葉をいただきました。ゴルファー冥利に尽きます。

コードとその解説

私が提出した Perl (57) のコードは、次の通りです。

eval
q<悃int ch掃雛_四郎囎2抛36f恃雎刈40/把郛;>=~y{遂胄刊掛}[$o-s*.+]drx8

文字数 57、重複文字 0で、大きさは 57×(0+1) =57 です。

文字化けしているわけではありません。わけがわからないと思いますが、正直、書いた本人にもさっぱり読めません。ともあれ、１つずつ解釈していくことにします。

まず、

y{遂胄刊掛}[$o-s*.+]dr

の部分を見てみましょう。 Ideone.com では、日本語文字は UTF-8 として解釈されますから、1文字につき3バイト（例えば「遂」という文字は \xe9, \x81, \x82 の3バイト）です。 Perl の y/// は、どうやらマルチバイト文字は特に認識せずに、単純にバイト単位で置換を行うようで、この置換の対応を表にすると次のようになります。

元の文字置換後の文字
遂 \xe9 $
\x81 o
\x82 p
胄 \xe8 q
\x83 r
\x84 s
刊 \xe5 *
\x88 .
\x8a +
掛 \xe6 （削除）
\x8e
\x9b

この置換を、

悃int ch掃雛_四郎囎2抛36f恃雎刈40/把郛;

という文字列に適用しています。（なお、コードでこの文字列を囲んでいる q<......> というのは、展開を伴わない文字列を表す '......' の別記法です。）例えば先頭の「悃」という文字のバイト値は \xe6, \x82, \x83 なので、上の表によって pr という2文字に置換されることがわかります。文字列全体を置換すると、

print chr$_*$r*2+36for$*..40/++$r;

という文字列になります。

この文字列、どこかで見たな… という鋭い方もいらっしゃるかと思います。そう、結果記事で解説されている antimon2 さんの文字列とほとんど同じなのです（こういう一致は嬉しいですね(^^)）。違いとしては、私の文字列では、 $k が $r に、  0 が $* になっていますが、置換の圧縮効果のため、私の解法ではこのほうが文字数的に有利なのであって、コードとしての意味は一緒です。

この後のプログラムの動作は antimon2 さんの解説の通りで、 y/// に r オプションを付けることで結果の文字列を取得し、それを x8 で8回繰り返し、それを eval で評価しています（詳しくは結果記事の antimon2 さんの解説を読んでください…）。めでたし、めでたし。

結局、置換対象を日本語文字で表現する解法には、

  • 同じバイト値を複数回使っても、組み合わせを変えて別の文字にすることで、重複文字になるのを回避できる。
  • 最大でコード3文字を日本語1文字で表現できるので、圧縮が効く

という一石二鳥の利点があります。ちなみに、 NeoCat さんも全く同じアプローチだったようです。

余談：「機種依存文字」

ところで、デスマコロシアムの解答のルールとして、 CodeIQ の入力欄で「機種依存文字」と判定される文字は使用禁止という制限があります。これは問題文には記載されていない（出題者様のブログのQ&Aに記載されている）細則なのですが、今回はこの細則が本質的に重要だったように思います。というのも、「機種依存文字」でない漢字は、 Unicode のコードポイントにおいて飛び飛びに（しかも不規則に）存在しているため、任意の3バイトを組み合わせた文字が解答で使用可能とは限らない（むしろ使用不可能な文字の方が圧倒的に多い）からです。

そこで、私の解法では、手探りでいろいろ試行錯誤して「遂」「胄」「刊」「掛」の4文字を選び、これらを構成するバイト値を組み替えて文字列を表現することにしました。その結果、日本語文字1文字でコード3文字を表現できたのは「刈」→ *.. の1か所だけで、他は全て1文字で1～2文字しか表現できていない、非効率なものになってしまっています。日本語文字の選択や置換の割り当てを最適化するツールを作って文字列を生成すれば、もっと短い解が得られたはずだと思いますが、今回は解答期間の多くを nasm での解の短縮につぎ込み、この Perl の解は途中集計の最終回になんとか間に合わせたため、そこまでする余裕がありませんでした。（解答をファイルでアップロードする形式か、 Ideone.com のURLを解答する形式だったら、「機種依存文字」を気にしなくていいので、もう少し楽ができたなあ…と思います。）

 

『魔方陣ヌルヌル』別の解法

CodeIQ

はじめに

CodeIQ で出題された『魔方陣ヌルヌル』について、公式のまとめ記事が出た後で解説を書こうと思って構想を温めていたのですが、公式まとめ記事に全部書かれてしまったため、ほとんど書くことがなくなってしまいました。

公式まとめ記事
https://codeiq.jp/magazine/2014/06/11455/

一応、問題の内容を大雑把に言うと、

  • タテ・ヨコ・ナナメの和が 0 になるような魔方陣を作る。
  • 魔方陣のサイズは 3×3，4×4，5×5 。
  • 魔方陣の各マスに入れる数は互いに異なる整数でなければならない。

といったところです。また、ここから暗黙にわかることとして、

  • 数は正の整数でなくてもよい。
  • 数は連続していなくてもよい。

ということが言えます（そうでないと作れない）。

素直な解法

公式まとめ記事では、通常の魔方陣を元に、各マスの数から一定の数を引く方法が紹介されています。私も 3×3 と 5×5 はこの方法で作りました。通常の魔方陣の作り方は、 Wikipedia の魔方陣の記事で非常に詳しく説明されています。

Wikipedia : 魔方陣
http://ja.wikipedia.org/wiki/%E9%AD%94%E6%96%B9%E9%99%A3

4×4 については、公式まとめ記事には「全体を2倍してから 17 を引く」方法と「9 以上の数だけから 17 を引く」方法が解説されていますが、私は「1～16 を -8～8 （ただし途中 0 を飛ばす）にマッピングする」という方法を採りました。まあ、結果的には「9 以上の数だけから 17 を引く」方法と大して変わりません。

別の解法

公式まとめ記事にも Wikipedia にも紹介されていない、別の解法を１つ紹介したいと思います。例として 5×5 のサイズを作りますが、他のサイズにも応用可能です。

まず、和が 0 になるように、中央の1行を次のように作ります。

         
         
-2 -1 0 1 2
         
         

これを左右に巡回させながら、上下の行に並べます。

0 1 2 -2 -1
-1 0 1 2 -2
-2 -1 0 1 2
2 -2 -1 0 1
1 2 -2 -1 0

これで、タテ・ヨコ・ナナメの和が 0 の行列を作ることができました。しかし、このままでは、同じ数が使われてしまっています。

次に、これと同じようなものを、もう1つ作ります。ただし、中央の行は

-10 -5 0 5 10

とし、巡回の向きも逆になるようにします。

5 10 -10 -5 0
10 -10 -5 0 5
-10 -5 0 5 10
-5 0 5 10 -10
0 5 10 -10 -5

もちろん、この行列も、タテ・ヨコ・ナナメの和が 0 になっていますね。

最後に、この2つの行列を加えます。

0 1 2 -2 -1
-1 0 1 2 -2
-2 -1 0 1 2
2 -2 -1 0 1
1 2 -2 -1 0
＋
5 10 -10 -5 0
10 -10 -5 0 5
-10 -5 0 5 10
-5 0 5 10 -10
0 5 10 -10 -5
＝
5 11 -8 -7 -1
9 -10 -4 2 3
-12 -6 0 6 12
-3 -2 4 10 -9
1 7 8 -11 -5

これで 5×5 ヌルヌル魔方陣の完成です！

めでたし、めでたし。

ちなみに、サイズが奇数×奇数の場合には、この方法で数が連続するヌルヌル魔方陣を作ることができるので、最小の数が 1 になるように全体に一定の数を加えれば、普通の魔方陣になります。

『Ruby警官から警告を受けろ』環境構築チュートリアル（超初心者向け）

CodeIQ

（6/1 環境構築の説明を書き直しました。誤りがありましたら是非ご指摘ください。ここには書かれていないハマリ点とその回避方法の情報も歓迎します。）

はじめに

『Ruby警官から警告を受けろ Lv1』 https://codeiq.jp/ace/tbpgr_badge/q883

『Ruby警官から警告を受けろ Lv2』 https://codeiq.jp/ace/tbpgr_badge/q884

ｏＯ（これ、面白そうなんだけど、なんか準備がいろいろ大変そうだなあ… あまり大変じゃないのならやってみたいんだけど、実際どうなんだろう…）

そんなことを思っている人、多いと思います。私もそうでした。でも、実際は意外と簡単ですよ。特に5月27日に出題者様が32ビット版の環境を用意してくださってからは、私の Celeron M のような廉価な CPU でも、問題なく環境構築できるようになりました。必要なのは、

  • Windows （7 及び Vista で確認済み）
  • 2～3GB の HDD 空き容量
  • 1～2時間ほどの作業時間

といったところです。え、2時間もかかるのかって？ ダウンロードするものが全部で 700MB ほどありますので、環境にもよりますが、私のようにネット代をケチって ADSL 接続にしていたりすると、どうしても時間がかかってしまいますね… まあ、作業時間の半分がダウンロード待ち時間、残りも後述の vagrant up というコマンドの待ち時間です。

必要なモノの紹介

とは言っても、やっぱり不安で踏み切れないと思います。私の場合、今思えば、不安を感じていた最大の要因は、必要とされるモノの正体がわからない、というところにありました。そこで、これらのモノの正体を簡単に紹介したいと思います。

まずは、自分で用意する必要のない（自動で準備される）モノです。

Ruby

これはさすがにいいですよね。 Ruby スクリプトを実行するための処理系です。バージョンが指定されていますが、自動で準備されるので、気にしなくて構いません。そもそも、書いたスクリプトは、実行するのではなく、静的解析するだけですので、処理系のことはまったく気にする必要がありません。

rubocop

Ruby スクリプトを静的解析して警告を出してくれるツールのです。この rubocop で警告をわざと多く出すのが、この問題の目的です。 rubocop の出す警告の種類は設定で変更することができ、問題の Lv1 用と Lv2 用とで異なる設定が用意されています。

rspec

書いたスクリプトが 100文字以下という条件を満たすか、 rubocop の警告数がバッジの目標数に届いているか、といったチェックをやってくれるツールです。解答スクリプトを書いて rspec を実行すれば、内部で自動的に rubocop が呼ばれて、どのバッジが取得できるか判定してくれます。なので、環境構築後の作業ルーチンは、解答スクリプトの修正と rspec の実行との繰り返しです。

Ubuntu

「俺 Windows だし…」と、これで腰が引けている人が多いのではないかと思いますが、心配いりません。読み進めていただければわかりますが、すべて Windows 上で実行できます。とは言っても、上記の Ruby, rubocop, rspec は Ubuntu 上に用意されますので、 Linux のシェル（bash）の知識が多少必要です。 cd とか ls とかの基本コマンドを使えるのに加えて、 vi でスクリプトの書き換えができると作業が格段に捗ります。

そして、以下は自分で用意する必要があるモノです。

VirtualBox

仮想マシンの実行環境です。これで Windows 上で Ubuntu を実行します。上記の rubocop や rspec は、 VirtualBox 上の Ubuntu で実行されることになります。 VirtualBox の入手方法は、後で紹介する出題者様の「環境構築について」に書かれています。

Vagrant

設定通りの VM （仮想マシン）を全自動で構築してくれるコマンドラインツールです。この問題では、指定のバージョンの Ruby, rubocop, rspec をセットアップした Ubuntu の VM をコマンド一発で作ってくれます（ただし数十分かけて）。 Vagrant の入手方法も、出題者様の「環境構築について」に書かれています。

Git （または ZIP 展開ツール）

出題者様がこの問題用に用意した各種ファイル（Vagrant の設定ファイルや各レベル用の作業環境）を取得するために Git というツールが必要ですが、なければ zip ファイルをダウンロードして展開するのでも構いません（私はそうしました）。

SSH クライアント

VirtualBox 上で実行されている Ubuntu に接続するために SSH が必要です（Vagrant から呼ばれます）。Git をインストールするとついてくるようですが、私はたまたま Cygwin 使いなので持っていました。

環境構築

さて、環境構築の具体的なやり方ですが、出題者様の「環境構築について」と「環境構築支援ツール」の README.md に素直に従うのが吉です。

「環境構築について」
http://d.hatena.ne.jp/tbpg/20140520/1400595738

「環境構築支援ツール」（GitHub リポジトリ）
https://github.com/tbpgr/codeiq_vagrant_for_rubocop

「環境構築について」の「ホストOSにVagrant＋VirtualBox環境がないが、これから入れようとしている場合」に基づいて、下準備やハマり点などを補足しつつ説明します。ホスト OS としては、とりあえず Windows Vista 32bit 版を仮定しますので、適宜読み替えてください。

SSH クライアントをインストール

「環境構築について」には明示されていませんが、作成した VM に接続するために Vagrant が SSH クライアントを要求しますので、先に準備しておきましょう。

SSH クライアントは、 Windows ネイティブ版でも Cygwin 版でも構いません。普段 Cygwin を使っている人は、http://www.cygwin.com/ の setup-86.exe で追加するのが最も簡単です。ただし、 Vagrant を Cygwin ターミナル上で実行する必要があります。

どうせならネイティブの SSH がいいという方は、 Git をインストールすれば一緒に付いてくるようです（未確認）。もちろん OpenSSH など SSH 単独で提供されているものを入手しても構いません（未確認）。または  TeraTerm や PuTTY など GUI 版 SSH クライアントでも構いませんが、この場合には後述の vagrant ssh コマンドが利用できないため、自分で VM に接続することになります。

VirtualBox のインストール

https://www.virtualbox.org/wiki/Downloads からインストーラ（100MB程度）をダウンロードできます。 Windows 用は「VirtualBox 4.3.12 for Windows hosts - x86/amd64」一択なので、迷うことはないと思います。ダウンロードしたものを実行すると、ネットワークドライバなどのデバイスドライバが Windows にびしばしとインストールされますが、驚かないようにしましょう。

環境変数 PATH に VirtualBox のパスを追加

VirtualBox は Vagrant から呼び出されるため、 VirtualBox のパスが環境変数 PATH に含まれている必要がありますが、 VirtualBox のインストーラは PATH の設定をしてくれませんので、自分でやる必要があります。 VirtualBox のパスは、デフォルトのインストール設定では C:\Program Files\Oracle\VirtualBox です。

念のため、環境変数の設定の仕方を説明しておきます。エクスプローラで「コンピュータ」を右クリックして「プロパティ」を選択（または、ショートカット [Win]+[Pause/Break]）で「システム」ウィンドウを開きます。その中に「システムの詳細設定」というのがありますのでクリックすると別のウィンドウが開きます。その中の下のほうに「環境変数」というボタンがありますのでクリックします。すると「ユーザの環境変数」「システムの環境変数」という上下2段のボックスが現れますので、下側の「システムの環境変数」のボックスの中から「Path」という項目を選択して、ボックスの下の「編集」ボタンをクリックします。「変数名」「変数値」という項目が表示されますので、「変数値」の文字列の最後に「;」（半角セミコロン）を追加し、その後に VirtualBox のパスを追加してください。このとき、最初から設定されている文字列を誤って消したり書き換えたりしないよう、くれぐれもご注意ください。

Vagrant のインストール

http://www.vagrantup.com/downloads.html からインストーラ（200MB程度）をダウンロードできます。こちらも Windows 用は「WINDOWS Universal (32 and 64-bit)」一択なので、迷うことはないと思います。

支援ファイルの取得

出題者様が用意してくれた、この問題用の支援ファイルを、上記「環境構築支援ツール」（GitHub のリポジトリ）から取得します。「支援」と言いつつ、問題挑戦に不可欠なファイルが含まれていますので、 Vagrant を使うつもりのない剛の者も、とりあえず一式取得しましょう。

取得は、 Git でリポジトリを clone する方法と、 ZIP ファイルをダウンロードして展開する方法がありますが、ここでは後者を説明します。「環境構築支援ツール」ページの右端にある「Download ZIP」というボタンをクリックして ZIP ファイルをダウンロードし、適当なフォルダに展開してください。

32bit 版 Ubuntu を利用するための設定

ダウンロードした支援ファイルは、そのままの状態では、 64bit 版 Ubuntu を利用する設定になっていますので、 32bit 版 Ubuntu を利用するように変更します。 Vagrantfile というファイルの

config.vm.box = "precise64"

という行を

config.vm.box = "precise32"

に書き換えればOKのようです（「ようです」というのは、私がやったときには確か書き換えるべき行が2行指定されていたはずで、現状を未確認なので）。

Vagrantfile の書き換えは、やらなくても動く可能性はありますが、やれば確実にハマリ要因が減ります。特に、 Celeron M など一部の廉価 CPU では 64bit 版 Ubuntu の VM が動かないため、この場合には必須の作業になります。

VM の構築及び起動

コマンドプロンプト（Cygwin の SSH を使う予定の場合には Cygwin ターミナル）を開き、 ZIP を展開したフォルダに移動して、そこで

vagrant up

を実行します。初回実行時には、まず VM が作成されます。このとき、 300MB 程度のファイルのダウンロードに引き続いて、数十分の構築作業が行われますので、気長に待ちましょう。

構築が終わると、引き続いて VM が起動します（2回目以降に VM を起動するときも vagrant up です）。ここで VM が起動せずエラーが表示される場合には、  VirtualBox GUI （Oracle VM VirtualBox マネージャー）から VM を起動してみましょう。そこで「VT-x is not available. (VERR_VMX_NO_VMX).」と表示される場合には、 64bit 版 Ubuntu が動かない環境でそれを動かそうとしている可能性が大です。こうなってしまった場合には、一旦 vagrant destroy で VM を削除し、その後 Vagrantfile を 32bit 用に書き換え、再度 vagrant up しましょう。

VM に接続

上記に引き続き、同じディレクトリで vagrant ssh を実行します（PuTTY 等を利用する場合には、 vagrant ssh で表示されるエラーメッセージに従って、自分で接続します）。

これで問題に挑戦する準備が整いました。

別の方法

このように、 VirtualBox のインストールと Vagrant のインストールと Git の clone さえすれば、あとは vagrant up 一発で必要な環境が全て整うように、出題者様がすべて用意してくださっているのです。しかし、 VirtualBox と Vagrant がそれぞれ巨大でディスク容量を食ううえに、 vagrant up の初回の実行は非常に時間がかかります。最初に「2～3GB」「1～2時間」と書いたのは、この辺りの事情のためです。

そこで、ここまでのコストをかけたくないという人は、もっと簡易に環境を構築することも、一応できます。問題を解いてチェックするために絶対に必要なのは rubocop と rspec だけなので、これを Windows に直接インストールしてしまえばいいのです。

それぞれの方法の特徴を比較してみます。

VirtualBox + Vagrant + Ubuntu を利用する方法

利点

  • 適切なバージョンの Ruby, rubocop, rspec が自動で準備される
  • 出題者様の採点環境と同じ環境でローカルチェックができる
  • 環境を汚さなくて済む（特に Windows にインストールされている Ruby のバージョンを変えなくて済む）

欠点

  • ディスク容量を食う
  • セットアップに時間がかかる
  • Linux の知識が多少必要

Windows に直接 Ruby + rubocop + rspec をインストールする方法

利点

  • 比較的素早くセットアップできる
  • Ruby が既にインストールされていれば利用できる

欠点

  • 採点環境と異なるので、事前に正確な結果がわからない
  • Ruby, rubocop, rspec のバージョンが指定のものと異なる場合にも結果に影響しうる

さらに別のやり方として、 Vagrant は使わないけど VirtualBox + Ubuntu は使う、というハイブリッド的な方法もあります。私は、やむを得ずそのやり方にしましたが、 32bit 版 Ubuntu の環境が提供された今となっては、真似しても得はないと思います。詳しく知りたい方は、奮闘記をご覧ください。

奮闘記 http://tails.hatenablog.jp/entry/2014/05/27/034208

おわりに

この問題の締め切りは6月9日です。本稿を公開した時点ではまだまだ日数がありますので、尻込みをしていた方も、是非挑戦してみてください。（追記：締め切られました。このブログエントリは2014年のものです。）

出題者様へ：

いろいろサポートしていただいたのに、奮闘記とか書いてしまって、すみませんでした！ 挑戦者増えるといいですね(^^)

 

『Ruby警官から警告を受けろ』環境準備奮闘記

CodeIQ

はじめに

CodeIQの『Ruby警官から警告を受けろ』に挑戦しました。

今回は、解答の解説ではなく、問題を解き始める準備をするまでの経過について書きます。同じ感じで環境構築にハマっている人の参考になれば幸いです。こんなハマり方をする人が私以外にいればの話ですが…

ちなみに、私のマシン環境は次の通りです。

１日目

おっ、たべぷげらさん*1の新しい出題だ。ふむ、 Ruby でわざと警告を出すとな。 Ruby は全く触ったことがないけれど、いい機会かもしれないな。
（*1 出題者の tbpgr 様の、私の中での呼び名。関連：「おじいさん」「ばあさん」）

なになに、

  • Ruby 2.0.0-p451
  • rubocop 0.21.0
  • rspec 2.14.1

ふむ。 rubocop も rspec も、聞いたことすらない。

（要Vagrant、VirtualBox）

あれだ、英文を読んでいるときに、知らない単語が1つ出てきても何とか推測できるが、4つも続くとお手上げだ。まさにその状態。

警告を出すために以下の情報をご活用ください。

RuboCopのGitHub URL
https://github.com/bbatsov/rubocop

RuboCopのGemのURL
https://rubygems.org/gems/rubocop

 

挑戦支援ツール
https://github.com/tbpgr/codeiq_vagrant_for_rubocop

やばい。鉄壁のディフェンスだ。俺を全く寄せ付けないぞ。 GitHub とか Git って、よく聞くけど何だろ。 subversion みたいなもんかな。 Gem って、まさか Game Programming Gems のことじゃないよな。でも他に知らんし。

何から手を付けていいかさっぱりわからんが、とりあえず GitHub というのを見てみるか。

RuboCop is a Ruby static code analyzer. Out of the box it will enforce many of the guidelines outlined in the community Ruby Style Guide. Most aspects of its behavior can be …

…うむ、さっぱりわからん。

この挑戦支援ツールというのはどうだろう。

環境構築用 Vagrant

環境構成

  • OS : Ubuntu 1204 LTS 64bit
  • ……

う、う、うぶんつ！？（って読むのか？）これって確か Linux の一派だよな？ 下で ssh とかやってるし、間違いないな。そうか、どうりで、どれもこれも聞いたことがないわけだ。この Vagrant ってのも、 Ubuntu のアプリか*2。だめだ、ちょっと俺には無理。
（*2 後で誤りと判明する。）

２日目

いや、高いも何も、 Ubuntu 限定って、ありえないっしょ！ …いや、実際有り得ないよな、俺の勘違いか？ っていうか、挑戦者少ないみたいだし、みんなわかってないのでは？ 折角だから、ちょっくら聞いてみるか！

（…しばらくやり取り…）

うおぉ仕事はええ！

３日目 ～Vagrant編～

やっと週末だぜ。さて、折角書いてくれたドキュメントに素直に従ってみましょうかね。俺の場合は、この【ホストOSにVagrant＋VirtualBox環境がないが、これから入れようとしている場合】になるのかな。ええと、

・Vagrant1.5.3をインストール
・VirtualBox4.3.10をインストール
・残りは、下記のREADMEの手順で環境構築できます。
https://github.com/tbpgr/codeiq_vagrant_for_rubocop

ふむ、まずは Vagrant ですな。ダウンロード…すげーでかいな！残り10分とか言ってやがる。やっと終わった。はい、同意します、はい、はい、…と。さて実行してみよう。va… va…（スタートメニューの中を探し中）…あれ、ないぞ？ まあいいか。

次は VirtualBox か。うお、こっちもなかなかでかいな…やっと終わった、はいはい同意しますよ。うっ、何やらデバイスドライバがびしばしとインストールされるぞ。

次はREADMEか…って、これはいつぞやの挑戦支援ツールのページではないか！ ふーむ、冷静に見ると、「動作確認済み：Windows 7」って書いてあるな。そうか、 VirtualBox を使って Windows 上で Ubuntu を動かすのか！ ということは、 Vagrant は VirtualBox に環境を構築するツールなのか！ ピカッチ！

さてさて、手順通りに素直にやりますよ。今日の俺は素直だよ！

利用手順

ええと、git よくわからないし（早速素直じゃない）、ZIPをダウンロードして解凍するのでもいいみたいだから、そうしよう。

  • cloneしたフォルダに移動
  • VMを起動
vagrant up

え、なんだ、この VMを起動、vagrant up ってのは、何をどうするんだ？ まだ Ubuntu の構築前なのにシェルが必要？ 試しにコマンドプロンプトを開いてそこに打ってみるか。

C:\Users\saito\work\codeiq\q883\codeiq_vagrant_for_rubocop-master>vagrant up
The provider 'virtualbox' that was requested to back the machine
'default' is reporting that it isn't usable on this system. The
reason is shown below:

Vagrant could not detect VirtualBox! Make sure VirtualBox is properly installed.
Vagrant uses the `VBoxManage` binary that ships with VirtualBox, and requires
this to be available on the PATH. If VirtualBox is installed, please find the
`VBoxManage` binary and add it to the PATH environmental variable.

おっ、なんか出た！ やった！ …ってこれエラーメッセージじゃんか！ ええとなんだ、PATHが通ってないのかな。よし、

C:\Users\saito\work\codeiq\q883\codeiq_vagrant_for_rubocop-master>PATH=%PATH%;C:\Program Files\Oracle\VirtualBox

（↑直接打ったもんだから、コマンドプロンプトを開くたびに毎回打つはめに…）

C:\Users\saito\work\codeiq\q883\codeiq_vagrant_for_rubocop-master>vagrant up

恐ろしく時間がかかるな…

数分～十数分程度かかると思いますので、こんなことをしながら待つ
  • コーヒーを飲む
  • トイレに行く
  • CodeIQの即答系問題を解く
  • 「rubocop vagrant up なう #CodeIQ #rubocop問題」とつぶやく

まじか。

Bringing machine 'default' up with 'virtualbox' provider...
==> default: Clearing any previously set forwarded ports...
==> default: Clearing any previously set network interfaces...
==> default: Preparing network interfaces based on configuration...
    default: Adapter 1: nat
==> default: Forwarding ports...
    default: 22 => 2222 (adapter 1)
==> default: Booting VM...
==> default: Waiting for machine to boot. This may take a few minutes...
The guest machine entered an invalid state while waiting for it
to boot. Valid states are 'starting, running'. The machine is in the
'poweroff' state. Please verify everything is configured
properly and try again.

If the provider you're using has a GUI that comes with it,
it is often helpful to open that and watch the machine, since the
GUI often has more helpful error messages than Vagrant can retrieve.
For example, if you're using VirtualBox, run `vagrant up` while the
VirtualBox GUI is open.

やっと終わったけど、電源が入らないとか、 VirtualBox GUI を開いたままやってみそ、とか言ってるような。ためしに VirtualBox GUI から起動してみるか。

f:id:saito_ta:20140527013038g:plain

VT-x is not available. (VERR_VMX_NO_VMX).

ななな何ですと？ よくわかんないので、ググってみるか。…おお、対処法がいっぱい出てくる。みんなもこのエラーで困ってるのか。なになに、

VBoxManage modifyvm vmname --longmode off

うむ、試してみるか… だめだな。

<HardwareVirtEx enabled=”false”/>

…これもだめか。

VBoxManage modifyvm (VM名) –hwvirtex off
VBoxManage modifyvm (VM名) –vtxvpid off

やっぱりだめ。

Make sure Virtualization is enabled in your BIOS

これだ！ていうか、BIOS以前にそもそも、俺の石 Celeron M だからVT機能ない！おわた＼(^o^)／

ぬほー！ こうなったら、ぼくがんばっちゃう！

３日目 ～Ubuntu編～

「Ubuntuの環境を作ってから」。この一言がどのくらいの試練を意味するのか、正直判らない… さて、Ubuntuの環境を作るからには、まずは「Ubuntu」をググるか。

http://www.ubuntulinux.jp/download/ja-remix-vhd

おっ、ここでダウンロードできるらしいぞ。…って、1GBですか！ほげー！ADSL接続でダウンロードするのに何十分かかるんだ。しかもHDD空き2GBしかないのに、展開できるんかいな。…展開後3GB、むりじゃんか。

まあね、こんなこともあろうと、USB接続の外付けHDDがあるんですよフフン。この家のどこかにね！…あった。100GBほど空いてるし、ここに展開すれば完璧！

さて、 VirtualBox に VHD ファイルを設定して、いざ起動 ………動いた！動いたよ！ デスクトップが表示された！ 操作がさっぱりわからない！ しかも、超もっさり！ アイコンをクリックすると、数秒かけてゆっくり明滅した後で、20秒くらい経ってからウィンドウが開く！

っと、突然ソフトウェアのアップデートのウィンドウが開いたぞ。更新が707個あります、らしい。念のため更新しときますかね。ぽちっと。…… Disk full で仮想マシンが落ちたっ！なんで！ 仮想ディスクの上限設定は60GBで、使ってるのはまだ4GBくらいだから、……はっ、4GB！ もしや…やっぱり。この外付けHDD、FAT32だ！

仕方ない、外付けHDDのパーティションを切りなおすか。確かパーティション管理のソフトを持ってたような… あった、 Partition Wizard 4 だ。って、最新版は 8 か！メジャーバージョンが 4 つも上がってるとは。無料のようだし、折角だから更新しとくか。（激しく寄り道）

80GBほど確保して、NTFSでフォーマットして、VHDファイルを移動して、いざ起動！今度はアップデートもうまくいっているようだ。遅々として進まないが。

（3時間半経過）

やっとアップデート終わった！さて、ええと何だっけ、そうだ、「Vagrantfile内に書いてあるシェルを実行」だ。シェルということは、ターミナルか。ええと… これ Linux のくせにターミナルが見当たらないぞ！ kterm どこだ（違） ファイラから /bin/bash をダブルクリック…何も起こらないな。ググるか。「Ubuntu terminal」と。なになに、

[アプリケーション] → [アクセサリ] → [端末]をクリックする。 

ほほう… って、そもそも「アプリケーション」が見当たらないぞ。

1. デスクトップ画面左上のDashホームをクリック。
2. テキストボックスに「terminal」と入力する。

…何も一致しないらしい。「gnome-terminal」でもだめ。

[Ctrl] + [Alt] + [T]

…出た！素晴らしい！

さて、Vagrantfileの内容は… ほうほう。コピペの仕方がわからないから見ながら打つしかないけど、まあ順番に打つだけだ。おっと、カレントディレクトリが移動したことに気付かないで、Ruby のディレクトリ内に問題ファイルをばらまいてしまったぞ。まあいいや、できた！

いやもう、達成感は十二分なので、あとはどれでもバッジがもらえればいいです。っていうか、警告以前に Ruby の文法さえわからないし！ サンプルを（ネタバレ削除）すれば、6個くらいはすぐだね！ 解答欄にコードを貼り付けて、「小悪党バッジください」と書いて、いざ提出！ 今度こそおわた！＼(^o^)／

あっ… タイミグ的に、俺か！ すみません！ ごめんなさい！ 本当申し訳ないです！ もし俺なら誤答扱いしてくださって構いませんので…（フィードバックが来るまで自分の解答を確認するすべがない…）

（5/27追記）

本当だ！ 知らなかった～

自分の解答を確認してみたら、ちゃんとラベルあった。そ、そりゃそうだよね。俺がそんなヘマするわけないよねフフン…（←さっきまで青ざめてたやつ）

まあ、こんなに頑張る羽目になったのは、全て俺の知識、技術、思い込みによるわけで…

出題者様としては、 Vagrant 一発で環境が整うようにばっちり準備したのに、こんなネタにされてしまって、さぞ不本意でしょうなぁ（←どの俺が言う）

（5/28追記）

この経験を踏まえて、超初心者（私程度）向けのチュートリアルを書きました。
http://tails.hatenablog.jp/entry/2014/05/29/022033

 

『6枚のカードの並べ方を求めて！』「入れ替えの極み」コード解説

CodeIQ

はじめに

CodeIQで『6枚のカードの並べ方を求めて！』という問題が出題されました。

問題の内容を大雑把に言うと、

  • 0, 1, 2, 3, 4, 5 の 6 文字の順列 720 通りを漏れなく重複なく（順序は不問）出力する Java プログラムを作る。
  • 縛りとして、 ideone.com のテンプレートの main() メソッド内「// your code goes here」の部分のみを書き換えて作る。別メソッドやメンバ変数は使用禁止。匿名クラス等も使用禁止。テンプレートで import されているクラスは利用してよい。
  • “面白いロジックや「その手があったか！」なロジック”に対してバッジが付与される。

といったものです。

ideone.com のテンプレートは、次の通りです。

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
	}
}

解説記事

出題者のチョコレートバー様による解説記事です。

https://codeiq.jp/magazine/2014/05/10469/

「入れ替えの極み」コード

解説記事の中で、私（tails）が提出したコードは「特殊な解き方」の「入れ替えの極み」として紹介され、バッジを頂きました。

String s="012345\n";
for(int i=1;i<=720;++i){
  System.out.print(s);
  int j=i,k=2;
  while(j%k==0) j/=k++;
  s = new StringBuffer(s.substring(0,k)).reverse() + s.substring(k);
}

解説記事の通り、先頭の k 文字を順序逆転させて出力することを繰り返すだけです。「シンプル」と評されているように、紹介されているコードの中では最も短いものとなっています。しかし、これで順列が漏れなく重複なく列挙されることは、一見しただけでは明らかではありません。そこで、なぜこのロジックで順列が列挙されるのか、そもそもどのようにしてこのロジックに至ったのか、説明したいと思います。

「入れ替えの極み」に至る道

順列を列挙するプログラムの実装としては、再帰を用いるのが最も素直です。しかし、この問題では、コードを main() メソッド内に収めなければならないため、関数の再帰呼出しは困難です。 main() メソッド自体を再帰呼出しするのは一応可能ですが、無理にそうせずとも、ループで実装できるのであれば、そのほうがシンプルです。そこで、ループで、文字列 "012345" の文字を順次入れ替えながら出力すること目指してみます。

作戦は、次の通りです。文字列 s の先頭の k 文字だけを入れ替えながら k! 通りを列挙する「手順(k)」を考えます。「手順(6)」が、最終的に作りたいコードです。そして「手順(1)」は 1 通りの列挙なので、単純に文字列 s を出力する処理です。

この「手順(k)」を、再帰のような（あるいは数学的帰納法のような）考え方で構成してみます。つまり、「手順(k-1)」を利用して「手順(k)」を作るのです。どうすればいいでしょうか？

「手順(k)」で列挙する文字列は k! 通りです。「手順(k-1)」で列挙するのは (k-1)! 通りですから、「手順(k)」は「手順(k-1)」の実行を k!/(k-1)! = k 回含むことになります。さらに、漏れなく重複なく列挙するためには、「手順(k-1)」を実行するときに、文字列 s の k 文字目以降の部分が毎回異なるようにしなければなりません。そのためには、「手順(k)」では、先頭の k 文字のそれぞれを1度ずつ k 文字目に入れ替えた状態で「手順(k-1)」を実行する必要があります。

具体的なイメージとして、例えば s="012345", k=3 の場合、次のような感じです。

手順(3) = {

   s の3文字目が "2" になるように入れ替え（s="012345"）
   手順(2)を実行
      → "012345", "102345" が出力される

   s の3文字目が "1" になるように入れ替え（s="201345"）
   手順(2)を実行
      → "201345", "021345" が出力される

   s の3文字目が "0" になるように入れ替え（s="120345"）
   手順(2)を実行
      → "120345", "210345" が出力される
}

もちろん、「手順(3)」が開始するときの s は "012345" になっているとは限りません。「手順(4)」で s の先頭4文字をいろいろ入れ替えつつ「手順(3)」を実行しますし、そもそもその「手順(4)」も s="012345" で開始するとは限らないからです。

さて、そうすると、「手順(k)」で s の先頭の k 文字のそれぞれを1度ずつ k 文字目に入れ替える処理は、具体的にどういう処理にすればいいのでしょうか？ いろいろなやり方が考えられますが、なるべくシンプルな方法を採用したいですね。

ここで、「手順(k-1)」を実行する前と後で s が変化しないと仮定してみましょう。この場合には、先頭の k 文字をローテートさせれば、 k 文字目を順番に入れ替えていくことが簡単に実現します。しかも、ローテートを k 回行った結果は、元の文字列に戻りますから、「手順(k)」でも実行の前後で s が変化しないことになります。

ローテートには右ローテートと左ローテートがあり、どちらでも良いのですが、ここでは右ローテートを採用してみます。つまり、 s の元々の k 番目の文字を先頭に移動し、元々の 1 ～ k-1 番目の文字を 2 ～ k 番目にずらす処理です。

先頭3文字の右ローテートの例

012345
  ↓
201345
  ↓
120345
  ↓
012345 … 元に戻った

さて、これで、「手順(k)」の具体的な構成ができました。

手順(k) = {
   k = 1 の場合、 s を出力する。
   k > 1 の場合、以下を k 回繰り返す。
      手順(k-1)を実行
      s の先頭 k 文字を右ローテート
}

これをJavaでループを用いて書くと、次のようになります。なお、このコードは、問題の有効な解答になっています（バッジがもらえるかどうかは判りませんが）。

String s="012345";
for(int i=1;i<=720;++i){
  System.out.println(s);
  if(i%(1)==0) s = s.substring(1,2) + s.substring(0,1) + s.substring(2);
  if(i%(1*2)==0) s = s.substring(2,3) + s.substring(0,2) + s.substring(3);
  if(i%(1*2*3)==0) s = s.substring(3,4) + s.substring(0,3) + s.substring(4);
  if(i%(1*2*3*4)==0) s = s.substring(4,5) + s.substring(0,4) + s.substring(5);
  if(i%(1*2*3*4*5)==0) s = s.substring(5,6) + s.substring(0,5) + s.substring(6);
}

このコードで例えば if(i%(1*2*3*4)==0) で始まる行は、「手順(5)」において5回実行される、「手順(4)」を呼出した後で s をローテートする処理のことで、ループ 4! 回ごとに 1 回実行されるべき処理です。

さて、これで解答のコードが作れましたが、ここからロジックは変えずに少しだけ変形を施したものが、前出の「入れ替えの極み」コードです。ロジックが同じなので、当然、出力順も同じです。ここから少しだけの変形で、本当にあのような reverse() 一発のコードになるのでしょうか？

上のコードをよく見てみましょう。 substring() を使って書かれているので多少わかりにくいですが、各行は、 s の先頭 k 文字の右ローテートです。ここで、if の条件式から明らかなように、6文字のローテートの直前には必ず5文字のローテートが行われます。その5文字のローテートの直前は必ず4文字のローテートです。つまり、 k 文字のローテートが行われる場合には、必ず 2 ～ k 文字のローテートが順に行われることになります。さて、2 ～ k 文字のローテートが順に行われると、どのような結果になるでしょうか…？ そうです！ 先頭の k 文字の順序が逆転するのです！

そこで、上のコードは、次のように変形することができます。もちろん、このコードも有効な解答です。

String s="012345";
for(int i=1;i<=720;++i){
  System.out.println(s);
  if(i%(1*2*3*4*5)==0) s = new StringBuffer(s.substring(0,6)).reverse() + s.substring(6);
  else if(i%(1*2*3*4)==0) s = new StringBuffer(s.substring(0,5)).reverse() + s.substring(5);
  else if(i%(1*2*3)==0) s = new StringBuffer(s.substring(0,4)).reverse() + s.substring(4);
  else if(i%(1*2)==0) s = new StringBuffer(s.substring(0,3)).reverse() + s.substring(3);
  else if(i%(1)==0) s = new StringBuffer(s.substring(0,2)).reverse() + s.substring(2);
}

条件分岐している所をパラメータ化して、「入れ替えの極み」コードの完成です。

String s="012345\n";
for(int i=1;i<=720;++i){
  System.out.print(s);
  int j=i,k=2;
  while(j%k==0) j/=k++;
  s = new StringBuffer(s.substring(0,k)).reverse() + s.substring(k);
}

めでたし、めでたし！

なお、パラメータ化により、 i = 720 の場合に k = 7 となり、本来存在しない「手順(7)」相当の処理が行われてしまいます。このとき、6文字しかない文字列の7文字目をアクセスしようとしてエラーになります。そこで、最初に s="012345\n" と改行コードを入れて7文字にすることによって、エラーを回避しています。これに伴い、 println(s) も print(s) に変更しています。

別の解法：コードをプログラムで生成

じつは、 main() の中だけで完結させるという縛り条件を読んだときに真っ先に思い付いた解法は、「別のプログラムで println() を720個作って並べる」というものでした。これなら再帰でも何でも自由にできますし、そもそも慣れない Java で書く必要さえありません。しかし、それはあんまりなので、思いとどまりました。

おわりに ～ さらなる極みを目指して

「入れ替えの極み」コードに対して出題者様から頂いたフィードバック（爆速で驚きました）に、このようなことが書かれていました。

入れ替え法は一般には２値入れ替えを使うのですが

締め切り後に出題者様に聞いてみたところ、要するに、2文字を入れ替えながら再帰していく（再帰から戻ったら文字も元に戻す）ような、考えてみればごく普通の処理のことでした。

しかし、当時ふと疑問に思ったのは、わざわざ reverse() などせずに、2文字を入れ替えて出力することを720回繰り返すだけの簡潔な方法があるのだろうか？ ということです。別の言い方をすれば、出力順で隣り合う2つの文字列のハミング距離がいずれも2になるような方法があるだろうか？ ということです。

「簡潔な」という条件を除けば、そのような方法が存在すること自体は明らかです。上の「入れ替えの極み」コードの説明で先頭 k 文字のローテートをしていた所を、 k 番目の文字と x (<k) 番目の文字を入れ替えるように変更すればいいからです（あと、各「手順(k)」における最後の1回の入れ替え処理を省く必要があります）。しかし、 x を適切に選ぶことは、さほど簡潔にはできないようです。というのも、このやり方だと、「手順(k-1)」の実行の前後で s が変化してしまうからです。

第2回デスマコロシアム Perlの42文字のコード

CodeIQ

はじめに

CodeIQ で出題された『第2回デスマコロシアム』に参加しました。

大雑把に説明すると、

  • 問題文で与えられたある文字列を出力するコード（プログラム）を提出する。
  • 言語は ideone で利用可能なものから選ぶ。
  • コードのサイズが短いほどよい。（1文字につき1点減点）
  • 同じ言語を選択した人が少ないほどよい。（1人につき10点減点）
  • その他、コーディングとは無関係な運の要素も加えて、トーナメントで競う。

といった感じです。要するに、コードゴルフに運の要素を加えたトーナメントです。具体的な出力の文字列などについては、出題者様によるまとめ記事をご参照ください。

出題者様によるまとめ記事：
http://d.hatena.ne.jp/tbpg/20140517/1400291776

私は、途中まで Perl （42文字）でエントリーし、その後 Perl 6 （32文字）に移行しました。結果、準々決勝で敗退しましたが、その Perl 6 のコードが全言語を通して最短（3名タイ）ということで、「最短賞」をいただきました。

結果発表（CodeIQ Magazine）：
https://codeiq.jp/magazine/2014/05/9744/

今回は、その全言語最短の Perl 6 のコードはとりあえず置いておいて、途中で提出した Perl の42文字のコードについて「見たい」という要望をいただきましたので、解説することにいたします。

Perl の42文字のコードの解説

途中で提出した Perl の42文字のコードは、次の通りです。

print chr$_++for(unpack CU7,"aAあアアあAa")x26

（ideone で実行 → http://ideone.com/aJV7I5）

全体は、式が for で後置修飾された文の形になっています（最後の ; が省略されています）。 for の右側のリストの要素が1つずつ $_ にセットされながら for の左側の式が評価されるようなイメージです。

まず、

unpack CU7,"aAあアアあAa"

の部分を見てみましょう。文字数を節約するために、関数呼び出しの括弧と文字列のクォートを省略してありますが、

unpack("CU7","aAあアアあAa")

ということです。 unpack() は、Perl の組み込み関数で、テンプレート（"CU7"）に従って文字列（"aAあアアあAa"）をリストに展開します。これで、8文字の文字コードのリストが得られます。テンプレートの 「C」は符号なし1バイト、「U」はUnicodeの1文字のコードポイント、「7」は「U」を7回、という意味です。一見、 "U8" でも良さそうな気もしますが、じつは pack() / unpack() には、テンプレートの文字列が「U」で始まる場合には Unicode を文字単位でなくバイト単位で扱うという不可解な仕様があり、これを回避するために1文字消費して "CU7" としてあります。

次に、その外側の

(……)x26

の部分ですが、この「x」はリストを繰り返す演算子です。例えば (1,2,3)x2 なら (1,2,3,1,2,3) と同じ意味になります。これによって、8文字の文字コードのリストの26回の繰返しが得られます。

さて、これで for の左側の式の $_ にセットする値のリストができました。ではその式を見てみましょう。

print chr$_++

ですね。これもちゃんと書くと

print(chr($_++))

ということです。後置 ++ はポストインクリメント、 chr() は文字コードに対応する文字を返す組み込み関数、 print() は引数を出力する組み込み関数です。さあこれで、問題文で与えられた文字列が出力されますね…？ いや、何かおかしいですね。インクリメントの効果が、後ろの文字に蓄積していっている！？ しかも、ちゃんと8文字ごとに1ずつ増えるように？ ループには毎回 "aAあアアあAa" を展開した文字コードが渡っているはずなのに、なぜそのようなことになるのでしょう。

（ここから先は、あくまで私の経験上の理解によるもので、必ずしも正確であるとは限りませんのでご了承ください。）

じつは、 Perl の for は、リストの各要素の値を $_ にセットするというより、むしろリストの各要素自体への参照を $_ にセットするようなイメージなのです。例えば、

print(++$_) for $a,$b;

というコードを実行すると、変数 $a と $b がそれぞれインクリメントされて出力されます。もちろん、インクリメントの効果は、ループを抜けた後にも残ります。これは x 演算子でリストを繰り返した場合も同様で、

print(++$_) for ($a,$b) x 3;

では、変数 $a と $b がそれぞれ3回ずつインクリメントされます。また、

print(++$_) for (1,2,3);

とすると、定数（read-only value）を変更しようとしたとして、実行時エラーになります。

イメージできますか？ もう少し複雑な例を見てみましょう。

print(++$_) for (cos(0)) x 3;

これは、やはり定数（1）を変更しようとしたことになり、実行時エラーです。ところが、

$a=0; print(++$_) for (cos($a)) x 3;

これは実行できてしまいます。この場合、 cos($a) は定数ではなく、実行時に計算されます。計算結果は、一時的な内部変数（のような何か）に格納され、その内部変数への参照が $_ に設定されるのです。その結果、内部変数は順次インクリメントされて 2 と 3 と 4 を出力することになります。

（なお、このことは for に限ったことではなく、 map や grep でも同様の挙動になります。）

これさえ理解できれば、あの42文字のコード

print chr$_++for(unpack CU7,"aAあアアあAa")x26

がなぜ正しい出力をするのか、納得できますね！

めでたし、めでたし。

 

（Perl の42文字のコードの解説に絞って全体を書き直しました。）

「あべこべのダンジョン」 私の面白コードの解説

CodeIQ

はじめに

CodeIQで、「あべこべのダンジョン」という問題が出題されました。

問題の内容を大雑把に言うと、「8桁の数 n が与えられたときに、各桁の数字（1~9）を「10-元の数字」に変換した数を作るJavaScriptのコードを書く」、というものです。

これだと何のこっちゃなので、問題と解答例について、出題者の柳井政和様による解説記事をご覧ください。（まあ、このブログを読んでいる人は、解説記事を既に読んでいるでしょうね！）

解説記事 → https://codeiq.jp/magazine/2014/05/9266/

問題はLV1, LV2, LV3の3問があり、それぞれ文字数制限と使用禁止文字列が定められています。また、コードは穴埋め形式になっていて、そこに適合させて全体で正しく動くような穴埋め部分のコードが、解答となります。つまり、元の8桁の数が変数 n で与えられたときに変換後の値を表すような式が正解となります。

さらに、この問題（に限らずダンジョンシリーズ）の面白いところは、それぞれのレベルで定められている文字数制限と使用禁止文字列を満たしていれば正解となり、バッジが付与されますが、実際には場外（TwitterとかCodeIQ MAGAZINEとか）で出題者様主導で解答コードの短さが競われているのです！ いわゆるコードゴルフです。このことは問題文には一切書かれていなくて、バッジほしさに適当に解答を送ると、知らずにコードゴルフに引きずり込まれるという、恐ろしい罠が仕掛けられているのです！

 

さて、解説記事を読んで気付いたのですが、なんと、私（tails）は、

  • レベル1の最短コード
  • レベル2の最短コード
  • レベル3の最短コード
  • 面白コード

の4部門（？）の全てに名を連ねてしまいました！（しかもレベル1とレベル2は最速だったようです。） これは私自身、全く予想していませんでしたし、狙ってさえいませんでしたから、びっくりです。

 

というわけで、前置きが長くなりましたが、今回は最短コードは置いといて、面白コードに採用された私のコードについて解説してみます。そのコードとは、レベル3の解答として提出した

n+8747258937^268435455

というものです。（最短を狙って提出したのですが、面白コードになってしまいました！）

解き方の基本方針

解説記事にも書かれているように、求めるコードは、要するに

111111110-n

です。

ところが、レベル3では「-」「~」「0」「1」がいずれも使用禁止のため、これらを使わずに等価な式になるように書き換えなければなりません。

「－」（マイナス）を外そう

「0」と「1」は後回しにして、まずは -n の部分の - を外す方法を考えてみます。

よく知られているように、 ~n が -(n+1) と等価なので、これを用いて

111111111+~n

と変形できます。さらに、「~」を外すために、

111111111+(0xffffffff^n)

と変形します。このあたりのことも解説記事に書かれていますね。（実際のコードに十六進表現を用いる必要はありませんが、このほうが解りやすい…ですよね？）

「（ ）」（括弧）を外そう

上の式を見ると、 n に対して、最初に定数値との「^」（排他的論理和）を計算し、その後で別の定数値との「+」（和）を計算しています。JavaScriptの演算子は、「+」のほうが「^」よりも優先順位が高いため、一見すると括弧は外せそうにありません。

しかし、よく考えてみましょう。上の式の結果を仮に r とします。つまり、

r = 111111111+(0xffffffff^n)

です。このとき、 r は n の各桁の数を変換（1～9 → 9～1）したものです。ということは、見方を変えれば、 n は r の各桁の数を変換したものということです！ すなわち、

n = 111111111+(0xffffffff^r)

ということですね。（このように、2回で元に戻る変換を「対合」というらしいです。）これを改めて r について解けば、

n = 111111111+(0xffffffff^r)
↓
n-111111111 = 0xffffffff^r
↓
r = n-111111111^0xffffffff

となり、見事に括弧を外すことに成功しました！

しかし、最初に折角外した「-」が復活してしまっています。どうしたものでしょうか。

心配いりません。今は変数ではなく定数のほうに「-」が付いている点で、最初の「-」とは異なっています。ある数から 111111111 を引くということは、当たり前のことですが、 -111111111 を加えるということです。ということは、…簡単ですね。どうせ後で32ビットの論理演算をするのですから、 -111111111 とビット表現が等価な正の数、すなわち -111111111 に2の32乗を加えた数で代用すればいいのです。具体的に式全体を十進数で書き下してみると、

n+4183856185^4294967295

となりました。

ビット幅を考えよう

いよいよ仕上げです。今まで無視していましたが、「0」と「1」も使用禁止です。上の式では「1」が2回使われているので、何とかしなければなりません。どうしたものでしょうか（2度目）。

これを解決するために、ビット演算について、もう少し掘り下げて考えてみます。

式をもう一度見てみましょう。

n+4183856185^4294967295

n は、8桁の比較的小さな数です。これに32ビット上限に近い 41... を加え、その後全ビットを反転させています。違和感を感じませんでしょうか？

最上位ビットを考えてみましょう。 n の最上位ビットは、当然0です。これに 41... を加えることで、最上位ビットは1になります。その後、 42... との排他的論理和を取る（つまり全ビットを反転する）ことで、最上位ビットを再び0に戻しています。これは必要な操作でしょうか？いや、明らかに無駄です。

もちろん、最上位ビットだけの話ではありません。 n は8桁の数であり、ビット数で言えば27ビットです。そして、式の結果も n と同じ範囲なので27ビットです。それより上のビットを、一旦1にしてから反転したりする必要はないのです。

ということで、上の式は

n+何か正の数^0x07ffffff

で充分ということになります。「何か正の数」の値は、 41...&0x07ffffff です。具体的に十進数で書き下してみると、

n+23106617^134217727

となります。

「0」と「1」は外れるどころかむしろ増えてしまいましたが、数値に選択の余地があることがわかりました。しかも、副作用として、元の式より短くなりました。この選択の余地を利用して、使用禁止の「0」と「1」を外すことを考えてみます。

「0」と「1」を外そう

最初に得た n+4183856185^4294967295 という式では、2つの定数の第27～31ビットは、無駄に全て1でした。これらのビットを全て0にして n+23106617^134217727 という式を得ましたが、これらのビットは、要するに、何でもいいのです。これらのビットは5ビットなので、32パターンを取ることができます。32パターンに対応する式を列挙してみましょう。果たして、「0」も「1」も含まない式があるでしょうか？

n+23106617^134217727
n+157324345^268435455
n+291542073^402653183
n+425759801^536870911
n+559977529^671088639
n+694195257^805306367
n+828412985^939524095
n+962630713^1073741823
n+1096848441^1207959551
n+1231066169^1342177279
n+1365283897^1476395007
n+1499501625^1610612735
n+1633719353^1744830463
n+1767937081^1879048191
n+1902154809^2013265919
n+2036372537^2147483647
n+2170590265^2281701375
n+2304807993^2415919103
n+2439025721^2550136831
n+2573243449^2684354559
n+2707461177^2818572287
n+2841678905^2952790015
n+2975896633^3087007743
n+3110114361^3221225471
n+3244332089^3355443199
n+3378549817^3489660927
n+3512767545^3623878655
n+3646985273^3758096383
n+3781203001^3892314111
n+3915420729^4026531839
n+4049638457^4160749567
n+4183856185^4294967295

ありました！1つだけ、「0」も「1」も含まない式が！

めでたし、めでたし。

おわりに ～ さらに縮めてみよう

上で求めたコードを、私は実際に解答として提出しました。ところが、その後、ここから1文字縮めることに成功したコードを改めて提出し、それが面白コードとして採用されました。2つのコードを比べてみましょう。

n+2573243449^2684354559 // 上で求めたコード（23文字）
n+8747258937^268435455 // 面白コード（22文字）

下のコードがどのようなものであるかは、ここまでの解説の延長線上にありますので、ちょっと考えていただければわかると思います。