るびまゴルフ 【第 5 回】

初稿：2009-02-07

書いた人：浜地慎一郎

はじめに

この連載ではゴルフについて扱います。ゴルフと言っても本当のゴルフではなく、コードを短く書くことを競うコードゴルフです。ゴルフについて詳しくは以下をご参照下さい。

簡単な問題を出題して、次回でその解答を解説しつつまた出題、というサイクルで進めて行きます。解けた人はこのページの下部にあるコメント欄でブログのURLを書いていただければ存在がアピールできるかもしれません。コードを縮めても特にいいことはありませんが、ちょっとしたパズルとして楽しんでいただけたら良いなと思います。

前回の問題の解答と解説

前回の問題は

n==0?1:0  # 以下、こっちを『前者の問題』と呼びます

や

1+(n==0?1:0)  # 以下、こっちを『後者の問題』と呼びます

をそれぞれ縮める、というものでした。今回は最短を目指す過程で、実に色々な表現が可能なことに気付いて楽しんでもらえれば、ということで考えた問題です。負でないことを仮定したり、 n を破壊することを OK としたのも、これらの条件下では表現の幅がより広がるからでした。

パーの設定はとてもいい加減だったので、多くの人に指摘していただいた通り n==0?2:1 だけでパーを切れてしまうのはイマイチでした。実のところ、何故かこの解を思いついていなかったのでした……

想定解

想定解は下記のようなものでした。

1[n]
1+1[n]

Integer クラスにはマイナーな Integer#[] というメソッドがあり、これによって最下位から数えて n 番目のビットを取得できます。この方法だと n を破壊せず、また n が負数でも問題ないため、最も良い方法ではないかと思います。

kurimura さん、mamamoto さん、ISA さん がこの解答をしてくれましたが、特に mamamoto さんは Ruby コードを生成して探索するという面白いアプローチをしておられました。

私も時々コード生成して探索をすることがありますが、あまり上手くいったことはありません。一方、特定の数値を都合よく変換してくれるマジックナンバーの探索などは割と上手くいきます。例えば、後置記法の数式を中置記法に変換する問題の私の解答には s[0]4%19-i>d[1][0]8%13/58 という謎の数値群がありますが、これは中置記法の数式にする時に括弧が必要かどうかを判定している式で、数式に使用される記号『 +、-、、/ 』の ASCII コード『 43、45、42、47 』それぞれに対して、左辺は『 1、9、16、17 』を返すようになっています。これは『 +、<、-、<、*、<、/ 』となる数式をスクリプトで探索することによって、複雑な条件である括弧が必要か否かの判定を一つの式に押し込めたものです。詳しい説明はとても長くなってしまいそうなのでここでは割愛させて下さい(決して短いコードでもないですし……)。

右シフトと累乗を使う方法

次に良いアプローチだと考えていたのは、右シフトや累乗を使う下記のようなものでした。

1>>n
0**n
1+(1>>n)
1+0**n

どちらかというと右シフトの方が思いつきやすいのではないでしょうか。ただし右シフトは加算よりも優先順位が低いため、 1+ が付く場合は上記のコードのように括弧が必要になってしまいます。また、負の数値だと上手くいきませんので、想定解と同じサイズではあるものの”次点”であると考えています。

星一さんの解答は累乗を、naka さん、znz さんの解答は右シフトを、それぞれ使ったものでした。なお naka さんは負数対応をした

1>>n*n

という解答も出されていました。

除算を使う方法 1

n/(n-1) が n = 0 の時に 0、それ以外の場合は -1 になることを利用した方法です。この方法だと後者の問題は

2+n%~n
2+n/~n

という 6B で記述できます。負数には対応できませんが、後者の問題であれば累乗と同じサイズで記述することができます。

この方法は右シフトを使った解答もされていたznz さんが使っておられました。私はこの方法には全く気付いていませんでしたが、うまい方法だと思います。

ちなみに私は似た方法として

0-2/~n

というような解答を考えていました。 0 はぱっと見いらなく見えるのですが、 -2/~n では - が先に 2 にかかってしまうためはぶけず、口惜しい感じの回答です。

除算を使う方法 2

1 を 1 で割ると 1 になり、 1 を 2 以上の数値で割ると 0 になることを利用した方法です。0 を 1 にして、 1 以上を 2 以上の数値に変換してやらないといけないわけですが、その方法には色々なやりかたがあります。

前者の方は、

1/-~n
1/n+=1
1/n.id
1./n+1
1/2**n

などがあり、後者の方は

1+1/-~n
1+1/n+=1
1+1/n.id
1+1/2**n

などがあります。単純に考えると n を 1 増やしてやれば良いのですが、 1/(n+1) だと括弧によるロスが 2B かかってしまいます。 1B ですむ方法として、 n を破壊してしまう n+=1 、 warning が出てしまうものの n.id が 2n+1 を返すことを利用する方法(理由はRHGのこの章の「小さな整数」の項などを参照して下さい)、 1./n+1 として優先順位を変えてしまう方法(ただしこれは後者の問題の解答には使用できない)、 2**n を使う方法など、バラエティに富んだ方法があります。

このやり方で最も優れた方法は、おそらく -~ を任意の数値につけると 1 増えることを利用したものだと思います。括弧を減らしたい時にはこのテクニックが使えることがよくあります。逆に、 ~- をつけると 1 減らすことができます。

maraigue さんがこの方法を使った解答をされていました。

その他の解答とまとめ

配列の範囲外アクセス時に nil を返すことを利用した

[2][n]||1

や、短くなっていませんがちょっと面白い

n/n rescue 2

という解答も考えていました。

最後に、今回登場した色々な方法を表にまとめておきます。

前者の問題の解答:

表現 サイズ 負数対応できているか nを破壊しないか 分類
1[n] 4B o o Integer#[]
1>>n 4B x o シフト
0**n 4B x o 累乗
1/-~n 5B x o 除算2
1>>n*n 6B o o シフト
1+n%~n 6B x o 除算1
1+n/~n 6B x o 除算1
1/n+=1 6B x x 除算2
1./n+1 6B x o 除算2
1/n.id 6B x o 除算2

後者の問題の解答:

表現 サイズ 負数対応できているか nを破壊しないか 分類
1+1[n] 6B o o Integer#[]
1+0**n 6B x o 累乗
0-2/~n 6B x o 除算1
2+n%~n 6B x o 除算1
2+n/~n 6B x o 除算1
1+1/-~n 7B x o 除算2
n>0?1:2 7B x o 三項演算
1+1/n+=1 8B x x 除算2
1+1/n.id 8B x o 除算2
1+(1>>n) 8B x o 累乗
n==0?2:1 8B o o 三項演算
[2][n]||1 9B x o その他
(n+2)/(n+1) 11B x o 除算2
n/n rescue 2 12B o o その他
(n==0?1:0)+1 12B o o 三項演算

解答をしていただいたみなさん、ありがとうございました。私の期待通り、色々な方法で取り組んでいただけて嬉しかったです。式をあれこれ試行錯誤することが楽しいと思っていただければ幸いです。

今回の問題

今回は 2 つ、出題したいと思います。

1 問目（パー：30B）

1 問目は、標準入力から複数の行を受け取って、同じ内容の行は捨てつつ標準出力に出力するプログラムです。具体的には、

hoge fuga hige
foo
bar
hoge fuga hige
baz
bar
fuga hoge

という入力に対して、

hoge fuga hige
foo
bar
baz
fuga hoge

を出力して下さい。ただし出力順は不問とします。また、入出力ともに末尾に改行がついているとしても、ついていないとしても構いません。解答例としては下記のようなコードが考えられます。

m={}
while l=STDIN.gets
  if !m[l]
    puts l
  end
  m[l]=1
end

パーは設定が難しいのですが、 30B とします。

2 問目（パー：45B）

2 問目は、出現した単語を同じ単語を捨てつつ出力するプログラムです。 1 つ目の問題と同じ入力に対して

hoge
fuga
hige
foo
bar
baz

を出力して下さい。こちらも出力順は不問で、末尾の改行は都合の良いようにして良い、とします。下記のプログラムと同じことをすれば良いです。

m={}
while l=STDIN.gets
  l.split.each{|w|
    if !m[w]
      puts w
    end
    m[w]=1
  }
end

パーは 45B とします。この問題は実のところ自分で考えた解答が最短であるか、自信がありません…… この文章が公開されてからしばらく経ったら私のゴルフ場でも出題してみたいと思います。

ヒント

この 2 つの問題は、とあるあまり有名でないであろう機能に気付いてしまうと、パーに意味が全くないほど短くなってしまいます。

著者について

浜地慎一郎。ゴルフ場を経営しています。

バックナンバー

解答コメント

解答をブログに書かれた方は、記事の URL と何か一言をコメントしていただけると嬉しいです（スパムが多いため、トラックバックは廃止しました）。