『ワンライナーでクールに解く！』所感（ネガティブ注意）

CodeIQ

はじめに

CodeIQ で『ワンライナーでクールに解く！』と題した2問の出題に解答してみました。どちらも、与えられた問題の答えを解くためのワンライナーを書けという問題です。「解答評価のポイント」は「冗長さをそぎ落とし、どれだけ簡潔に問題を解決できているかが評価のポイントとなります。」とのことです。（この「解答評価のポイント」は、次のリンクから読むことができます。）

挑戦者求む！【プログラミング】ワンライナーでクールに解く！その１ by 無形ソフトウェアLLC 代表社員：村山 男也│CodeIQ

挑戦者求む！【プログラミング】ワンライナーでクールに解く！その２ by 無形ソフトウェアLLC 代表社員：村山 男也│CodeIQ

その１

問題

「一番大きいマトリョーシカの中に、6つの少しずつ小さなマトリョーシカが入って10500円で売っています。（マトリョーシカは全部で7つです。） マトリョーシカはひとつ大きくなるにつれて、150円ずつ値上がりします。一番小さなマトリョーシカの値段はいくらですか？」

要するに、等差数列の総和が与えられたときの初項を求める問題です。

私の解法

真ん中の大きさ（小さいほうから4番目）のマトリョーシカが 10500 / 7 円なので、それより3つ小さい一番小さなマトリョーシカは 10500 / 7 - 150 * 3 円です。これを Perl ワンライナーで素直に書くと、

perl -e 'print 10500/7-150*3'

となります。これが私の解答です。これ以上、複雑になりようがありませんね。逆に、これ以上簡単にしようとすると単に答えを表示するだけになってしまうので、まあこんなもんでしょう。

評価結果

評価は「4」でした。

今回はプログラム言語のワンライナーというカテゴリーですので、 ループ処理や組み込みのリスト演算などをクールに使用している 回答者様に高得点を差し上げております。ご了承いただければ幸いです。

とのことで、「高評価を獲得した解答例」として示されていたのが、次のコードです。

perl -e 'for($n=10500,$i=0;$i<7;$n-=150*$i++){}print $n/7'

…へ？

まあ確かにワンライナーですが、なんというか、普通のスクリプトから改行を機械的に取り除いただけですよね。

ていうか、「冗長さをそぎ落とし、どれだけ簡潔に問題を解決できているかが評価のポイント」じゃないんですか？ 上記の「高評価を獲得した解答例」は、むしろ可能な限り複雑に書いてあるようにしか見えないんですが。

まあ、どのようなコードを「クール」と感じるかは人それぞれなのでそれはいいのですが、評価基準を示した以上、それに従って評価してもらわないと困ります。これではただの価値観の押し付けです。ともあれ、この問題や評価からは、出題意図がさっぱり見えてきません。

その２

問題

「1個の値段が40円、50円、77円の品物を合わせて11個買ったところ、代金が601円になりました。それぞれ何個ずつ買いましたか？」

私の解法

これは非常に困りました。ワンライナーで書くのに適したような簡単な解法を思いつかなかったからです。

ところで、「解答評価のポイント」には、「変数名などにキラリと光るネーミングセンスを感じるものなどは、高評価につながります。」とも書いてあります。そこで、変数名（の扱い）に趣向を凝らして、こんなコードにしてみました。

perl -e '@a=(50,40,77);$n50=11;do{$total=0;$total+=$_*${n.$_}for@a;++${n.$a[$cond=$total<=>601]};--$n50}while$cond;print"$_=>${n.$_}\n"for@a'

到底ワンライナーと呼べるような代物ではありませんが（それこそ改行を機械的に取り除いただけ）、簡単な解法を思いつかないので、仕方ありません。しかも、趣向を凝らしたせいで、可読性もさっぱりです。

評価結果

Perlの特徴を思う存分に発揮されており、文句なしの「5」評価です。

なんと、気に入られてしまいました。どうも、こういうコードが「クール」なようです。どうも私とは価値観が正反対です。

まとめ

結局、この出題者は、どのような意図でこれらの問題を出し、解答者に何を求めたかったのか、さっぱりわかりません。

CodeIQ では、以前にもひどい問題が出されたことがありますが（ボゴソートの計算量のやつとか）、 CodeIQ の中の人は、もっと問題や評価の質に気を配るべきだと思います。出題の質が低下したときに、最初に離れていくのは、スキルの高いユーザです。自分よりレベルが低い（と感じる）出題者から評価を受けようなどと思う人はいませんから。つまり、 CodeIQ の存在価値を維持し高めていくためには、出題の質は非常に重要だということです。

 

誕生日

誕生日

誕生日でした。ある意味、今までで一番賑やかな誕生日だったように思います。
もしかして：モテ期到来？

あ、今日、誕生日だ。と思って何となくつぶやいたのです。そしたら、

いや、神だなんて！ 私は、ただ、短くて、小さいだけです。私がというか、私のが。それを、なぜかみんな褒めてくれるんです。

お祝いコード

お祝いコードをいただきました。

いきなり Lazy-K ですね。以前、誰かが確か「Lispがバイナリダンプのような言われようだ」と言ったのに対して「バイナリダンプがSKIコンビネータのような言われようだ」と返したのを思い出します。ていうか、 Lazy-K は私が挫折した言語の一つです。素晴らしいです。ありがとうございます！

ありがとうございます！ ていうか、なぜ修造ｗ
それにしても、皆さん難解言語好きですねｗ

↑これではあんまりなので、私も難解言語で返事を書いてみました。

00607988772869385095152818394450817988297758363+9*+P1^6?77*3-c

Hack VM という処理系用の言語です。
Hack VM - A Virtual Machine for Hackers
実行方法は、↑このリンクのページの「Enter your code here」の所に上のコードをコピペしてから「Run!」を押してください。（コードに改行や余分な文字が入るとエラーになるので注意！）

お祝いメッセージ

コード以外にも、多数のお祝いメッセージをいただきました。本当にありがとうございます。

なんと CodeIQ 公式さんまで！

constant.pm の件は反省しておりますですｗ

年齢

（説明：「今日俺の誕生日だ」ツイートは、素数に関する問題を出題中の『第6回デスマコロシアム』のQAを受けてのものなので、「年齢が素数だったら面白い」わけです。しかし実際には素数ではなく3の倍数なので、「Fizz歳」と返しました。具体的な年齢・年代を一切明かさずに素数でないことを端的に示すのみならず、ちょうど前回の『第5回デスマコロシアム』が FizzBuzz 問題だったのでタイムリーな表現になっています。）

2D マップ上の最短パスを求める新しいアルゴリズム S* の提案

はじめに

ゲームのキャラクタを自動で移動させる場合などに、 2D マップ上の２点間の最短パスを求めることが行われます。

典型的なやり方としては、マップを格子状のマス目に分割し、マス目ごとに通れるか通れないかを決定しておき、キャラクタの現在地である開始点と、目的地となる終了点との２点間のパス（経路）を A* アルゴリズムで求める、という方法が一般的かと思います。

しかし、マップをマス目に分割するのは、本当に必要なことなのでしょうか？ もっと直接的に、幾何学的な最短パスを A* で求めればいいのではないでしょうか？ ちょっと実装して実験してみました。

デモ

未署名の Java アップレットですすんません。 Java の設定でセキュリティを下げて実行してくださいすんません。

 

線の色は、パスの長さを表しています。パスが切り替わったときにも線の色が不連続には変化していないことから、等しい長さのパスの間で切り替わっていることが確認できます。

２点を変化させながらリアルタイムに探索していますが、 CPU をほとんど使っていないことがわかります。

S* アルゴリズム

上のデモで実装したアルゴリズムを、とりあえず「S*」と呼ぶことにします。「 Saito の A*」 の略です。単純なアルゴリズムなので、考え付いたのは私が最初というわけでもないでしょうし、既にちゃんとした名前があるようにも思いますが、知りません。

アルゴリズムの内容は、上のデモから一目瞭然なのですが、次のような感じです。

準備

  1. マップ上の障害物を、多角形で近似する。（上のデモでは、障害物の形状自体を三角形にしています。）
  2. 多角形の頂点同士を結ぶ線分のうち、多角形の内部を通過しないもののリスト（頂点間リスト）を作成する。

探索

  1. 頂点間リストに、開始点と終了点を一時的に追加する。
  2. 開始点から終了点に向かって、頂点間リストに A* アルゴリズムを適用する。このとき、 A* のヒューリスティック関数には、終了点までのユークリッド距離を用いる。

以上です。とてもシンプルですね！

マス目 A* との比較

従来の探索方法を、ここでは「マス目 A* 」と呼ぶことにします。

S* の利点

  • マス目に分割する必要がない。（マス目 A* では、マス目の分割のパラメータ（特にマス目の大きさ）で探索結果が変化しうるが、 S* はそのようなパラメータの影響がない。）
  • 常にユークリッド距離での最短パスが求まる。（マス目 A* では、通過するマス目の数が最小になるようなパスが求まるが、必ずしもユークリッド距離で最短とはならない…ですよね？）
  • パスが最初から折れ線で求まるので、折れ線化するための後工程が不要。（マス目 A* では、折れ線化が必要。）

S* の欠点

  • 見晴らしの良い広大なマップでは、頂点間リストを素朴に作ると、遠くの多角形同士の頂点間で無駄に多い線分が頂点間リストに登録されるので、工夫が必要。
  • 移動する障害物が多数あるような場合には不向きかも。
  • ていうか、実際のゲームなどのアプリケーションで試したことがないので、本当に実用に耐えうるのか疑問。誰かやってみてください！

S* アルゴリズムの利用について

S* アルゴリズムに関しては、私は、何らの主張もしません。しかし、他者が特許を取っている（またはこれから取る）可能性などについては関知しませんので、その点は自己責任でお願いします。

デモアプレットについては、著作権を主張します。 All rights reserved です。ていうか、突貫で作ったウンコードなので恥ずかしいから解析するな、ってことです。

『第5回デスマコロシアム』に参加しました

CodeIQ

はじめに

『第5回デスマコロシアム』に参加しました。

「第5回デスマコロシアム」問題のトーナメント結果発表です！──優勝者は…！ #デスマコロシアム｜CodeIQ MAGAZINE

要は FizzBuzz ですが、15の倍数のときは大文字の FIZZBUZZ にするというのが特徴です。

問題を読んで、とりあえず書いた Perl (51文字) のコードに「とりあえず」とだけコメントを付けて、とりあえず提出しました。後で日々の集計を見て、短く書けそうな言語で再提出するつもりでした。「とりあえず」のコードは、暫定の全言語最短になりました。

ところが、それから何日経っても記録が更新されず、帯状疱疹を患って入院したり退院したりしているうちに締め切りを迎えました。結局、「とりあえず」のコードのまま最短賞をいただきました。チャンピオンバッジは、これで4回連続4個目です。（「決勝進出おめでとうございます！」と書いてあるのですが、決勝どころか準決勝にすら進んだことがない私が4個も持っていていいのかという妙な背徳感が…）

コード

print$_%5?$_%3?$_:fizz:$_%3?buzz:FIZZBUZZ for 1..50

Perl (51文字) です。5の倍数かどうかで場合分けし、それぞれの場合を3の倍数かどうかで場合分けするという、なんの工夫もないコードですが、これで実際に最短賞が取れてしまったので仕方ありません。

ちなみに、15の倍数のときが小文字の fizzbuzz ならば工夫の余地があって、 Perl で 45 文字で書けますので、挑戦してみてください（ググる前に！）

 

『3番目のダンジョン』私の解答

CodeIQ

テンプレ

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

はじめに

今回の問題は、相異なる5個の数値 a, b, c, d, e が与えられたときに、3番目の大きさのものを求める、というものでした。具体的な問題は、解説記事をご覧ください。

解説記事（CodeIQ MAGAZINE）
https://codeiq.jp/magazine/2014/08/14753/

今回もいつものように、途中経過を見ながら縮めていこうと思って、とりあえず様子見でコードを提出したのですが、いつもと違って途中経過の発表がほとんどありませんでした。いぶかしく思っているうちに、帯状疱疹を患って入院してしまい、入院中に締め切りとなってしまいました。しかし、蓋を開けてみると、とりあえず提出したコードがそのまま最短コードになっていました。途中経過の発表がほとんど無かったのは、そもそも動きがほとんど無かったからのようですね。

LV2の私のコード

(a<b)-(a>c)^(a>d)-(a<e)?arguments.callee(b,c,d,e,a):a

53文字です。コードゴルフでは忌み嫌われる優先順位の括弧が、なんと4組も使われています。しかし + と / が使用禁止なので、まあ仕方ないところです。

(a<b)-(a>c)^(a>d)-(a<e) の部分がやや解りにくいですが、 ^ の両辺を表にすると次のようになります。

条件(a<b)-(a>c) の値
a < b,c 1
b < a < c 0
c < a < b
b,c < a -1
条件(a>d)-(a<e) の値
d,e < a 1
d < a < e 0
e < a < d
a < d,e -1

この表から、 a の大きさが3番目のときに限り (a<b)-(a>c)^(a>d)-(a<e) が 0 になることがわかります。

LV2の私の面白コード

上記のような経緯のため提出はしませんでしたが、私の考えた面白いコードです。

f=Math.min,-f(-f(a,b,c),-f(a,b,d),-f(a,b,e),-f(a,c,d),-f(a,c,e),-f(a,d,e),-f(b,c,d),-f(b,c,e),-f(b,d,e),-f(c,d,e))

114文字です。 -f() だけで答えを求めています。

『ダブル数列のダンジョン』私の解答

CodeIQ

テンプレ

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

はじめに

今回の問題は、等差数列又は等比数列の最初の2項 a, b が与えられたときに、3項目を求める、というものでした。初項の値の範囲（10～99）と、公差・公比の値の範囲（2～9）とが定められているため、等差数列なのか等比数列なのかは一意に定まるようになっています。具体的な問題は、解説記事をご覧ください。

解説記事（CodeIQ MAGAZINE）
https://codeiq.jp/magazine/2014/06/11998/

今回も、各レベルでの最短コードに到達することができました。途中経過がほぼ2日ごとに発表されたのですが、LV3は、追い抜いたと思って次の発表を見たら先を行かれ、今度こそ追いついたと思ったらさらに突き放され、という状況で、大変精神的につらか楽しめました。幸運にも、最終的にはなんとか追いつくことができました。

私のLV3の最終コード

(b*(b/a<<13)^b%a)%8191

22文字です。LV3では、LV2の禁止文字列に加えて + - が禁止されているため、等差数列の場合の b*2-a の値をどうやって表現するかが最大の焦点になります。上記のコードでは、13ビットずらしてORをとり、さらに8191での剰余をとることによって、加算を表現しています。

私のLV3の途中経過

提出しなかったものも含めて、約60のコードを作りました。以下に全て公開します。

(b/a>=2)*(b*b/a)^!(b/a>=2)*(Math.log(Math.exp(b)*Math.exp(b)/Math.exp(a)*1.6))
m=Math,(b/a>=2)*(b*b/a)^(b/a<2)*(m.log(m.exp(b)*m.exp(b)/m.exp(a)*1.6))
m=Math,e=m.exp,(b/a>=2)*(b*b/a)^(b/a<2)*(m.log(e(b)*e(b)/e(a)*1.6))
e=Math.exp,(b/a>=2)*(b*b/a)^(b/a<2)*(Math.log(e(b)*e(b)/e(a)*1.6))
e=Math.exp,[Math.log(e(b)*e(b)/e(a)*1.6)^0,b*b/a][1>>b%a]
e=Math.exp,[Math.log(e(b)*e(b)/e(a)/.8)^0,b*b/a][1>>b%a]
(e=Math.exp)^[Math.log(e(b)*e(b)/e(a)/.8),b*b/a][1>>b%a]
e=Math.exp,[~Math.log(e(a)/e(b)/e(b)*.3),b*b/a][1>>b%a]
e=Math.exp,[~Math.log(e(a)/e(b)/e(b)/3),b*b/a][1>>b%a]
e=Math.exp,[~Math.log(e(a)/e(b*2)/3),b*b/a][1>>b%a]
m=Math,[~m.log(m.exp(a)/m.exp(b*2)/3),b*b/a][1>>b%a]
~~(b/a)*b*Math.log(Math.exp(b%a/b)*2.7183)^0
~~(b/a)*b*Math.log(Math.exp(b%a/b)/.36787)^0
(b/a^0)*b*Math.log(Math.exp(b%a/b)*2.7183)^0
!!(b%a)*((2*b^256)%(a^256))^!(b%a)*(b*b/a)
x=!(b%a),!x*(2*b^256)%(a^256)^x*b*b/a
x=b%a,(2*b^x<<8)%(a^x<<8)^!x*b*b/a
!(x=b%a)*b*b/a^(2*b^x<<8)%(a^x<<8)
!(x=b%a<<8)*b*b/a^(2*b^x)%(a^x)
x=b%a<<8,!x*b*b/a^(2*b^x)%(a^x)
x=b%a<<13,(2*b^x)%(a^=x)^b*b/a
(2*b^(x=b%a<<13))%(a^=x)^b*b/a
b*b/(a^=x=b%a<<13)^(2*b^x)%a
a^=x=b%a<<13,b*b/a^(b*2^x)%a
a^=!!(b%a)*b<<13,b*b/a^b*8194%a
a^=!!(b%a)*b<<8,b*b/a^b*258%a
a^=!!(b%a)*b<<7,b*b/a^b*130%a
a^=b>>!(b%a)*13<<7,b*b/a^b*130%a
a^=b*!!(b%a)<<7,b*b/a^b*130%a
a^=b/!!(b%a)<<7,b*b/a^b*130%a
a^=b*(b<a*2)<<7,b*b/a^b*130%a
a^=b*(2>>b/a)<<7,b*b/a^b*130%a
x=a^b%a<<13,b*b/x^(b*2^x^a)%x
a^=b%a<<13,b*b/a^(b*2^a^a%256)%a
a^=x=b%a<<13,b*b/a^(b*2^x)%a
!(b%a)*b*b/a^!!(b%a)*(a<<8^b*2)%257
!(b%a)*b*b/a^!!(b%a)*(b%a<<8^b)%255
!(b%a)*b*b/a^!!(b%a)*(b%a^b<<7)%127
!(b%a)*b*b/a^(b<<7^(b%=a))%127*!!b
!(b%a)*b*b/a^!!(b%a)*(a<<7^b)*2%257
(b%a^b<<11)%2047*~~(b/a)
(b%a^b<<10)%1023*~~(b/a)
(b^b%a<<10)%1023*~~(b/a)
(b*~~(b/a)^b%a<<13)%8191
(b*~~(b/a)<<13^b%a)%8191
(b*~~(b/a)^b%a<<26)%8191
(b%a^b*992)%991*~~(b/a)
(b%a^b*896)%895*~~(b/a)
(b%a^b<<13)%~(8191^b/a)
(b%a^b<<13)%(~8191^b/a)
(b%a^b*1e4)%(~9999^b/a)
(b%a^b*8032)%(~8031^b/a)
(b%a^b/a<<14)%(~16383^b)
(b%a^b/a<<14)%(16383^~b)
(b%a^b/a<<14)%~(16383^b)
(b<<13)%(a*~8191^b)%8191
b*8192%(a*~8191^b)%8191
(b*(b/a<<13)^b%a)%8191
(b*(b/a<<45)^b%a)%8191
(b*(b/a<<77)^b%a)%8191

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

CodeIQ

はじめに

『第4回デスマコロシアム』で、途中で提出した nasm (72) のコードです。途中集計の最終回の直前まで、このコードが単独で全言語最小でした。しかし、 Perl に抜かれる可能性があったため、自ら Perl (57) を提出し、この nasm のコードはお蔵入りとなりました。結局、 nasm (72) に naoki_kp さんが並びましたが、 Perl (57) を提出せずとも、この nasm (72) でも最小賞が取れていたようです。

コード

db`BCTYv	MU_OW]^j$ば~,z\u340X)蔔P<tqあ`

機械語のバイトコードを直接文字コードで表現したものです。 v と M の間は TAB 文字です。

ソース

このコードのソースは、次の通りです。左の列がアセンブラのソース、中央がバイトコード（16進）、右が文字表現です。

inc edx        ; 42     ; B
inc ebx        ; 43     ; C
push esp       ; 54     ; T
pop ecx        ; 59     ; Y

L1:
jbe L2         ; 76 09  ; v[TAB]
dec ebp        ; 4d     ; M
push ebp       ; 55     ; U
pop edi        ; 5f     ; _
dec edi        ; 4f     ; O
push edi       ; 57     ; W
pop ebp        ; 5d     ; ]
pop esi        ; 5e     ; ^
push 36        ; 6a 24  ; j$

L2:
jnecx L2-126   ; e3 81  ; ば
mov al,7eh     ; b0 7e  ; ~
sub al,7ah     ; 2c 7a  ; ,z
int 80h        ; cd 80  ; \u340
pop eax        ; 58     ; X
sub eax,ebp    ; 29 e8  ; )蔔
xchg eax,esp   ; 94     ;
xchg eax,esp   ; 94     ;
push eax       ; 50     ; P
cmp al,116     ; 3c 74  ; <t
jno L1         ; 71 e3  ; qあ
db 81h,82h     ; 81 82  ;

解説

Perl (57) のコードと違って、この nasm (72) のコードは、さほどトリッキーなことはしていません。気を付けた点としては、

  • int 80h で \ を使うので、他では使わないようにした。
  • 同じレジスタを2つデクリメントする代わりに、別々のレジスタで1回ずつ dec するようにした。

といった程度です。しかし、文法上どうしても ` を2回使ってしまうため、文字数に対する乗率が2になってしまうことが避けられません。 Perl (57) よりこちらのほうが文字数は少ないのですが、大きさでは上回ってしまいます。

参考にしたもの

１．インテル：日本語技術資料のダウンロード：IA-32 アーキテクチャー

http://www.intel.co.jp/content/www/jp/ja/developer/download.html#ia32

特に「中巻 A」「中巻 B」は必須でした。

２．命令コード表

http://dl.dropboxusercontent.com/u/2476414/TechResources/x86_opcodemap_1_a4.pdf

『ハンド (逆) アセンブルのための x86 ニーモニックの覚え方』
http://d.hatena.ne.jp/a4lg/20120225/1330180431
に掲載されているものを使わせていただきました。ありがとうございます。これをプリントして、6日間ひたすら眺めていたら、妻に怪訝な顔をされましたw