オフラインリアルタイムどう書くE12参加しました
はじめに
2017/2/4開催の「オフラインリアルタイムどう書くE12」に参加しましたので、そのレポートです。
どんな感じ?
今回から卓球台が導入されるという新しい展開を見せました。そのためか? 自己紹介のお題はスポーツ ( 観戦じゃなくて自分でやる方 ) でした。苦手、という人が多くてほっとしたような。なお、自分の場合だと、中高生の時にやってた囲碁が該当しますね。
さて、問題については松島さん出題の回でした。とてもテトリスなのですが、世代によっては当然の知識ではないという、ちょっと衝撃的な…。
問題としては簡単め、なんでも通算初の全勝だったようです。松島さんにはショックだったようですが、楽しめればいいのではないかと。私には相性が良かったようで、20分くらいで通すことができました。
問題
問題は積んでも消えないでした。概要は次の通りです。
- テトリスめいて、5種類のブロック ( テトロミノ ) を順番に積み上げる時の、積み上げられたブロックの最上面の高さを求める ( ただしブロックが消えることはない )
- 入力は、ブロックを降らせる左右の位置を表す数 ( 左端からのオフセット ) と、ブロックの種類を表すアルファベットを繋げた文字列
- ブロックの降る姿勢は固定で、回転等はしない。( ずらしてはめ込むようなこともしない )
詳細は上のリンクからご覧ください。なんだか、問題の説明図をSVGで作るのが快感になってるらしい…?
解説
RubyとPerlで組みましたが、内容は同じなのでRuby版で。( Perl版は http://ideone.com/CjFGFJ )
基本方針は、大体の人が同じでした。横の位置に対する、ブロックの最上面の高さを管理し、ブロックを積む毎に更新していく、というものです。なお、横幅は約1,000あれば十分だったのですが、ずぼらのためハッシュで管理しました。
結局のところ、ブロックを落とした時、接地面の高さがどこになるか、が重要なのですが、次の図のような状況を見た時、
ブロックが全くテトロミノではないということはさて置き。接地しているのは○のついたところで、結果としてブロックの一番下の面は高さ8に収まっています。 この高さは、「(現在の最上面の高さ)-(落とすブロックの下面の高さ)の最大値」で求められるだろう、というのが基本的なアイデアです。
後は、この高さを元に、最上面の高さを更新していけば良いです。そのため、各テトロミノのブロックは、(下面の高さ)(下面・上面の差)のペアの配列としてデータしておきます。
終わりに
PerlでもRubyとほとんど同じことをやっていたので、「PerlとRuby、同じですね」とコメントしたら、「いや、それは違う」と総ツッコミを喰らう羽目に。なぜでしょう…。
なお、色々な方の実装例は、オフラインリアルタイムどう書くE12 の問題 - Qiitaに紹介されています。
