『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文字）

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