円卓処理のプログラミング


現在phpの学習を行なっており、なかなか解けなかったプログラムがあったのでアウトプットをこの場を借りて行う。

問題は、以下の通りである。
東京の下町に長テーブルで有名な老舗うなぎ屋がありました。

そのうなぎ屋にはとても大きい長テーブルがあり、テーブルの周りにn個の座席が配置されています。
座席には、時計回りに1, 2, …, nと番号が振られています。
座席はテーブルの周りに配置されているので、座席番号nの座席と1の座席は隣接しています。(下記図を参照の事)

今、m個のグループの人達が座席に順番に座りに来ます。i番目(1≦i≦m)のグループの人数をa_i人とします。
彼らは、長テーブルに並んだ座席の内、ある連続するa_i個の座席に一斉に座ろうとします。

ただしお客さんは江戸っ子なので、それら座席のうち、いずれか一つでも既に先客に座られている座席があった場合、
一人も座らずにグループ全員で怒って帰ってしまいます。江戸っ子は気が早いんでぃ。

入力では、i番目のグループが座ろうとする連続した座席の位置は、整数b_iにより指定されます。
i番目のグループは、座席番号b_iの座席を始点として、そこから時計回りにa_i個分の座席に座ろうとします。

最後のグループが座りに来た後、無事に長テーブルの座席に着席出来ている人数を出力するプログラムを作成してください。

なお今回の標準入力値は以下の通りである。

6 3
3 2
1 6
2 5

こちらをプログラムしていく。

まず、テーブル数、グループ数が記載されている標準入力値を
fgets関数を利用して取得していこうと思う。

list($table_counts,$group_counts)=explode(" ",fgets(STDIN));
$seats=array_pad(array(),$table_counts,0);

上記方法により、explode関数で、空白で分割をして、
一番目の配列を総テーブル数、二番目の配列を総グループ数を取得することが出来た。
また、指定した数で配列を埋めてくれるarray_pad関数によって

Array
(
    [0] => 0
    [1] => 0
    [2] => 0
    [3] => 0
    [4] => 0
    [5] => 0
)

のような配列を配列結果を得ることができた。

次に、各グループの総人数、席に着席する位置を標準入力を取得していく。
こちらは、for構文を使用して、

for($i=0;$i<$group_counts;$i++){
 list($group_member,$sit_position)=explode(" ",trim(fgets(STDIN)));  
}

これで全ての標準入力値の取得が完了した。
いよいよ、プログラムの実装へ移っていく。

まず、空席状況を確認するプログラムを作成していく。
こちらのプログラムは、先程記載したfor構文の
中に処理を行なっていく。

 $sit_position-=1;
for($j=$sit_position;$j<$sit_position+$group_member;$j++){
    if($j>$table_counts){
        $circle_sit=$j-$table_counts;
    }
    if($seats[$j]>0){
        $is_empty=false;
        break;
    }
}

注意する点としては、$jの範囲を指定する際に、

$sit_position+$group_member

と定義すると$seats配列が一つ分配列がずれるので予め

 $sit_position-=1;

のように定義する。
そして、次の条件式

  if($j>$table_counts){
        $circle_sit=$j-$table_counts;
    }

によって変数jが変数table_countsより大きくなった際にまた、テーブル一番目の位置にループするように
変数jからテーブル分引くことで円卓処理を行うことができた。

そして、

if($seats[$j]>0){
        $is_empty=false;
        break;
    }

誰かが座っている時を

if($seats[$j]>0)

のように表現し、その場合処理をbreakによって中断させている。
また、$is_emptyにより空席かどうかを定義している。
これで、空席時の処理が完了したので、
座席に着席するときの処理を行う。
この場合,変数is_emptyはtrueなので

if($is_empty==true){
    for($j=$sit_position;$j<$sit_position+$group_member;$j++){
    if($j>$table_counts){
        $circle_sit=$j-$table_counts;
    }
    $seats[$j]=1;
}
}

のように処理を行う。
ここでの処理は、先ほどの空席時でのループ処理と同様である。
また、着席の場合には、

$seats[$j]=1;

のように記載することで
空席のときは、
配列のvalueが0
着席している時は、
配列のvalueが1になる。

これで、

print_r($seats);

を行うと

Array
(
    [0] => 0
    [1] => 1
    [2] => 1
    [3] => 1
    [4] => 0
    [5] => 0
)
Array
(
    [0] => 0
    [1] => 1
    [2] => 1
    [3] => 1
    [4] => 0
    [5] => 1
)
Array
(
    [0] => 0
    [1] => 1
    [2] => 1
    [3] => 1
    [4] => 0
    [5] => 1
)

のような出力結果が得られる。
これにより空席、着席状況が分かるプログラムが完成した。
最後に

  $count=0;
for($i=0;$i<$table_counts;$i++){
   if($seats[$i]>0){
     $count+=1;
} 
}
echo $count;

とすることでテーブルに座っている人数を
調べることができる。

全コードは、以下の通りである。

<?php

list($table_counts,$group_counts)=explode(" ",fgets(STDIN));
$seats=array_pad(array(),$table_counts,0);
print_r($seats);

for($i=0;$i<$group_counts;$i++){
 list($group_member,$sit_position)=explode(" ",trim(fgets(STDIN)));  
 $sit_position-=1;
//echo $group_member;
//echo $sit_position;
//空席の処理
$is_empty=true;
for($j=$sit_position;$j<$sit_position+$group_member;$j++){
    if($j>$table_counts){
        $circle_sit=$j-$table_counts;
    }
    if($seats[$j]>0){
        $is_empty=false;
        break;
    }
}
if($is_empty==true){
    for($j=$sit_position;$j<$sit_position+$group_member;$j++){
    if($j>$table_counts){
        $circle_sit=$j-$table_counts;
    }
    $seats[$j]=1;
}
}
print_r($seats);
}
  $count=0;
for($i=0;$i<$table_counts;$i++){
   if($seats[$i]>0){
     $count+=1;
} 
}
echo $count;
?>

是非ともフィードバッグ等頂けたら嬉しいです。
よろしくお願い致します。