昨日、美術館からの帰りの電車の中、暇潰しに技術系のサイトを見ていて見つけた問題がちょっと面白かった。
問題
いくつかの椅子がある。 そこにひとりずつ人が現れ、あるいは立ち去る。
椅子は一列に並んでいる。
人が座る席は以下のルールで決まる:
- どちら側の隣にも人が座っていない席を選ぶ。
- それが無理なら、片側にしか人が座っていない席を選ぶ。
- それも無理なら、両側に人が座っている席を選ぶ。
- 上記の条件で一つに決まらない場合は、候補のうち最も左にある席を選ぶ。
- 一度座ったら立ち去るまでその場を動かない。
指定された順序で人が来たり立ち去ったりした結果、それぞれの椅子に誰が座っているのかを出力せよ。
入力
入力は 6:NABEbBZn のような形式になっている。
「 : 」の前(上記の例では 6 ) は椅子の数を示す。
「 : 」の後(上記の例では NABEbBZn ) は人の出入りを示す。 A〜Z は、それぞれの人の到着を意味し、a〜z は、対応する大文字の人が立ち去ったことを意味する。
出力
出力は、席に座っている人を左から順に並べる。 誰も座っていない席は - で示す。
入力が 6:NABEbBZn の場合、
記号 説明 席の状態 初期状態 ------ N N があらわれた N----- A A があらわれた N-A--- B B があらわれた N-A-B- E E があらわれた N-A-BE b B が立ち去った N-A--E B B があらわれた N-AB-E Z Z があらわれた NZAB-E n N が立ち去った -ZAB-E となるので、文字列 -ZAB-E を出力すれば良い。
補足
- 空席がない状態で人が来ることを考慮する必要はない。
- 席の数は 30 ぐらいまで対応できれば良い。
- 不正な入力（ 4:ABCxyz のように座っていない人が退席した、 :2:ABC@%$ のような不正な書式のもの、など）には対処しなくてよい。
- 両端の処理に注意かも。
実装ができた方は Qiitaの記事 のコメント欄からリンクを張っていただくと見つけやすくて助かります。
サンプルデータ
# 入力 期待 1 6:NABEbBZn -ZAB-E 2 1:A A 3 1:Aa - 4 2:AB AB 5 2:AaB B- 6 2:AZa -Z 7 2:AZz A- 8 3:ABC ACB 9 3:ABCa -CB 10 4:ABCD ADBC 11 4:ABCbBD ABDC 12 4:ABCDabcA -D-A 13 5:NEXUS NUESX 14 5:ZYQMyqY ZM-Y- 15 5:ABCDbdXYc AYX-- 16 6:FUTSAL FAULTS 17 6:ABCDEbcBC AECB-D 18 7:FMTOWNS FWMNTSO 19 7:ABCDEFGabcdfXYZ YE-X-GZ 20 10:ABCDEFGHIJ AGBHCIDJEF
そんなに難しくもなく、しかし色々工夫ができそうなのが面白そう。 可読性を考えなければ、10行ぐらいでいけそうな気がするな。
電車の中でどう実装するかをあれこれ考えて、家に帰ってrubyでやってみたのがこれ。
seats.rb
#!/usr/local/bin/ruby
class Seats
@seats
def handle( data )
( n, s ) = data.split ":"
_init n
s.split( "" ).each do |c|
_accept c if ( "A" .. "Z" ).include? c
_reject c if ( "a" .. "z" ).include? c
end
_show
end
private
def _init( n )
@seats = Array.new( n.to_i + 2, "-" )
end
def _show
p @seats[ 1 .. -2 ].join
end
def _eval
vals = @seats.map { |v| v == "-" ? 1 : 0 }
( vals[ 0 .. -3 ].zip vals[ 1 .. -2 ], vals[ 2 .. -1 ] ).map { |v| v.reduce(:+) * v[ 1 ] }
end
def _accept( c )
idx = nil
vals = _eval
@seats[ idx + 1 ] = c if [ 3, 2, 1 ].any? { |v| idx = vals.index( v ) }
end
def _reject( c )
idx = @seats.index c.upcase
@seats[ idx ] = "-" if idx
end
end
seats = Seats.new
[ "6:NABEbBZn",
"1:A",
"1:Aa",
"2:AB",
"2:AaB",
"2:AZa",
"2:AZz",
"3:ABC",
"3:ABCa",
"4:ABCD",
"4:ABCbBD",
"4:ABCDabcA",
"5:NEXUS",
"5:ZYQMyqY",
"5:ABCDbdXYc",
"6:FUTSAL",
"6:ABCDEbcBC",
"7:FMTOWNS",
"7:ABCDEFGabcdfXYZ",
"10:ABCDEFGHIJ" ].each do |s|
seats.handle s
end
席のクラス Seats を作り、この中で配列 @seats に、以下に示す席の状態値を持たせている。
| 値 | 状態 |
|---|---|
| - | 空席。 |
| A〜Z | 値の人が座っている。 |
_init は、内部に抱える @seats の初期化をするメソッド。 指定の数より2つ多い要素を確保し、空席を示す"-"を初期値として設定する。
@seats の要素数が席の数より2つ多いのは、後述する評価値の計算を楽にするため。
_eval は、席の評価値を作るメソッド。 どこに座るかを決めるために、席の状態から各席の評価値の配列を作る。
評価値を作る手順は以下の通り。
( v1 + v2 + v3 ) * v2
で得られる値の配列を作る。
3つの値の合計が、自席と両隣との空席の数になる。 で、両隣が空席でも自席が埋まっていると座れないので、自席の値（0か1）をかけることで、最終評価値とする。
その結果、評価値の取り得る値とその意味は以下となる。
| 値 | 状態 |
|---|---|
| 0 | 誰かが座っている。 |
| 1 | 空席。両隣は誰かが座っている。 |
| 2 | 空席。隣のどちらかも空席。 |
| 3 | 空席。両隣も空席。 |
実際の席の並びの前後に一つずつ仮想の席を用意しているのは、評価値を作るのを簡単にするのと、席の両端を選ぶ優先順位をあげるため。 仮想席は評価値の計算には使うが、評価値の配列は実際の席のみになるので、人が座ることはない。 ずっと空席のまま。
_accept は、誰かが現れた時のためのメソッド。 空席があれば、ルールによって決まる席に来た人を座らせる。 空席がない場合は放置。
このルール適用に使うのが、_eval で作る評価値配列。 具体的には、以下の通り。
_reject は、誰かが立ち去る時のためのメソッド。 指定した人がどこかの席に座っていれば、その人を立ち退かせて空席にする。
席のオブジェクトを用意し、これに対して人を座らせたり立ち退かせたりさせ、結果を表示する。 特にトリッキーなこともせず、出来事をそのまま割と素直に実装したつもりだったのだが。
もう3年以上前のお題なので回答もそれなりに寄せられているのだが、それらと見比べると結構違う。 何で実装するかで違いが生じるのは当然だが、むしろ同じrubyでの実装の方が違う気がする。 人って違うんだなぁ… なんて、今更だけどしみじみと。
しかし、なあ。 オブジェクトとメソッドの関係を、主語とそいつの行動となるようにしたかったのだが、オブジェクトを席（の並び）にしたせいで適当な言葉が思い浮かばなかった。 その結果が handle であり accept であり reject なのだが、なんだか人よりも席の方が偉そうな雰囲気なんだよな。 シート様。 まあ、俺には解り易いから良いか。