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

オフラインリアルタイムどう書くE12参加しました

yhpg

はじめに

2017/2/4開催の「オフラインリアルタイムどう書くE12」に参加しましたので、そのレポートです。

どんな感じ?

今回から卓球台が導入されるという新しい展開を見せました。そのためか? 自己紹介のお題はスポーツ ( 観戦じゃなくて自分でやる方 ) でした。苦手、という人が多くてほっとしたような。なお、自分の場合だと、中高生の時にやってた囲碁が該当しますね。

さて、問題については松島さん出題の回でした。とてもテトリスなのですが、世代によっては当然の知識ではないという、ちょっと衝撃的な…。

問題としては簡単め、なんでも通算初の全勝だったようです。松島さんにはショックだったようですが、楽しめればいいのではないかと。私には相性が良かったようで、20分くらいで通すことができました。

問題

問題は積んでも消えないでした。概要は次の通りです。

  • テトリスめいて、5種類のブロック ( テトロミノ ) を順番に積み上げる時の、積み上げられたブロックの最上面の高さを求める ( ただしブロックが消えることはない )
  • 入力は、ブロックを降らせる左右の位置を表す数 ( 左端からのオフセット ) と、ブロックの種類を表すアルファベットを繋げた文字列
  • ブロックの降る姿勢は固定で、回転等はしない。( ずらしてはめ込むようなこともしない )

詳細は上のリンクからご覧ください。なんだか、問題の説明図をSVGで作るのが快感になってるらしい…?

解説

RubyPerlで組みましたが、内容は同じなのでRuby版で。( Perl版は http://ideone.com/CjFGFJ )

基本方針は、大体の人が同じでした。横の位置に対する、ブロックの最上面の高さを管理し、ブロックを積む毎に更新していく、というものです。なお、横幅は約1,000あれば十分だったのですが、ずぼらのためハッシュで管理しました。

結局のところ、ブロックを落とした時、接地面の高さがどこになるか、が重要なのですが、次の図のような状況を見た時、

f:id:ange1:20170305204626p:plain

ブロックが全くテトロミノではないということはさて置き。接地しているのは○のついたところで、結果としてブロックの一番下の面は高さ8に収まっています。 この高さは、「(現在の最上面の高さ)-(落とすブロックの下面の高さ)の最大値」で求められるだろう、というのが基本的なアイデアです。

後は、この高さを元に、最上面の高さを更新していけば良いです。そのため、各テトロミノのブロックは、(下面の高さ)(下面・上面の差)のペアの配列としてデータしておきます。

終わりに

PerlでもRubyとほとんど同じことをやっていたので、「PerlRuby、同じですね」とコメントしたら、「いや、それは違う」と総ツッコミを喰らう羽目に。なぜでしょう…。

なお、色々な方の実装例は、オフラインリアルタイムどう書くE12 の問題 - Qiitaに紹介されています。