オフラインリアルタイムどう書くE12の問題をC++で

http://mtsmfm.github.io/2017/03/04/doukaku-e12.html をC++で実装した。下記のように考えた。


## shape クラス
テトリスミノを`bottom`と`height`の2つのベクトルからなるクラスと考えた。

- `bottom` : 各列の底の相対位置
- `height` : 各列の高さ

たとえば、Lミノの場合、底の位置はすべて一緒なので `bottom = [0,0].` 高さは `height = [3, 1]` となる。
![L.png](https://qiita-image-store.s3.amazonaws.com/0/80588/249a9a96-3a7a-fee0-abb6-7600bc12fe5c.png)

Sミノの場合、3番目の列だけ底が１つ浮いているので、 `bottom = [0,0,1]`. 高さは、 `height = [1,2,2]`. 
![S.png](https://qiita-image-store.s3.amazonaws.com/0/80588/1a233c51-7b45-45ee-eaf7-eef367928657.png)

このように考えると、各ミノは次のように表される。

- I: `bottom = [0], height = [4]` 
- L: `bottom = [0,0], height = [3,1]` 
- O: `bottom = [0,0], height = [2,2]` 
- S: `bottom = [0,0,1], height = [1,2,2]`
- T: `bottom = [1,0,1], height = [2,2,2]`

## Fieldクラス

一方で、ミノを積んでいく空間をフィールドと呼び、各列の高さのベクトル `height`を持つクラスとした。


## ミノを積む操作

ある位置にミノを積む時には、各列について 「フィールドのheight - ミノのbottom」を計算して、その最大値を「ベースの高さ」とする。
新しい高さは、「ベースの高さ + ミノのheight」で更新できる。

![Screenshot from 2017-03-07 02:50:49.png](https://qiita-image-store.s3.amazonaws.com/0/80588/c452cdda-5ea7-195a-19a9-ae47f97f8aef.png)

この操作を入力にあるミノについて逐次行い、最後にフィールドの高さの最大値を求めている。


```{c++}
#include <iostream>
#include <string>
#include <vector>
#include <sstream>

struct shape 
{
  // height : height of shape of each column
  // bottom : relative position of the bottom 
  std::vector<int> height; 
  std::vector<int> bottom;

  int size() { return height.size(); };
};

struct Ishape : shape
{
  Ishape()
  {
    height.resize(1, 4);
    bottom.resize(1, 0);
  }
};

struct Lshape : shape
{
  Lshape()
  {
    height.resize(2);
    height[0] = 3;
    height[1] = 1;
    bottom.resize(2, 0);
  }
};

struct Oshape : shape
{
  Oshape()
  {
    height.resize(2, 2);
    bottom.resize(2, 0);
  }
};

struct Sshape : shape
{
  Sshape()
  {
    height.resize(3);
    height[0] = 1;
    height[1] = 2;
    height[2] = 2;
    bottom.resize(3, 0);
    bottom[2] = 1;  
  }
};

struct Tshape : shape
{
  Tshape()
  {
    height.resize(3, 2);
    bottom.resize(3, 1);
    bottom[1] = 0;
  }
};


struct Field
{
  std::vector<int> height;
  Field() 
  {
    height.resize(10, 0); 
  }

  Field(int size)
  {
    height.resize(size, 0); 
  }

  int size()
  {
    return height.size(); 
  }

  void clear()
  {
    for (int i = 0; i < size(); i++)  height[i] = 0;
  }

  void resize(int size)
  {
    height.resize(size); 
  }
  

  void add_shape(shape s, int p)
  {
    // add a shape s at position p
    
    // if the position is out of bound, reshape the field
    int needed_size = p + s.size();
    if (needed_size > size()) resize(needed_size); 

    // find the maximum of field height - shape's bottom 
    // this is where the shape is stacked
    int stacked_position = 0;
    for (int i = 0; i < s.size(); i++)
    {
      if (stacked_position < height[p+i] - s.bottom[i]) {
        stacked_position = height[p+i] - s.bottom[i];
      }
    }

    // update height
    for (int i = 0; i < s.size(); i++)
    {
      height[p+i] = stacked_position + s.height[i]; 
    }
  }

  int max_height()
  {
    int out = 0;
    for (int i = 0; i < size(); i++)
    {
      if (out < height[i]) out = height[i];
    }
    return out;
  }

  void show_height()
  {
    for (int i = 0; i < size(); i++) std::cout << height[i] << " "; 
    std::cout << "\n"; 
  }
};



int str_to_int(const std::string &str) 
{
  std::stringstream ss(str);
  int num;
  ss >> num;
  return num;
}



void test(std::string input, std::string expected)
{
  Field f; 
  int start = 0;
  int pos = 0;
  while (pos < input.size())
  {
    if (input[pos] == 'I' || input[pos] == 'L' ||
        input[pos] == 'O' || input[pos] == 'S' || input[pos] == 'T') {
      int num = str_to_int(input.substr(start, pos-start));
      if (input[pos] == 'I') {
        f.add_shape(Ishape(), num);
      } else if (input[pos] == 'L') {
        f.add_shape(Lshape(), num);
      } else if (input[pos] == 'O') {
        f.add_shape(Oshape(), num);
      } else if (input[pos] == 'S') {
        f.add_shape(Sshape(), num);
      } else if (input[pos] == 'T') {
        f.add_shape(Tshape(), num);
      }
      start = pos + 1;
      //f.show_height();
    }
    pos++;
  }
 
  int myans = f.max_height();
  if (myans == str_to_int(expected)) {
    std::cout << "Good! My answer = " << myans << " as expected\n";
  } else {
    std::cout << "Sigh... I got " << myans << " where " <<
      expected << " is expected\n";
  }

}




int main()
{
  /*0*/ test("1O3L0I0T", "5");
  /*1*/ test("0I", "4");
  /*2*/ test("0I0I", "8");
  /*3*/ test("0I1I2I3I4I", "4");
  /*4*/ test("0S0I", "5");
  /*5*/ test("0I0S", "6");
  /*6*/ test("2S0T2O3I", "8");
  /*7*/ test("4O4T1T0S4L1L3L", "10");
  /*8*/ test("0S2S4S6S8S10S12S14S", "16");
  /*9*/ test("14S12S10S8S6S4S2S0S", "2");
  /*10*/ test("5I2O10I0O4L10T9T11L8I2I10I12O7L12T12T12S11T9O10O13I12O10O7I9I7O0S1O2S0L1L", "23");
  /*11*/ test("9T14L10L8T4I1T3S5I8T12O3S7L9O7L14T2I7O3S6S2L0L13T10O4I9T7L8S0I12O9S11L11T14T", "27");
  /*12*/ test("9S9S7O11O16I2T9O12L10T9O0O13I9O1I2T14S7O9S11T5L7I14T13O0T12I3S10L10O7I15I6S2L12S8I16I3L", "23");
  /*13*/ test("11T13I16S15T7O10L12S1I5I8S5I13I15O8S9I1T12I1S5S0L14I12L16T2S2S8L2S14L16O4I13L15L13S11S9T13S9S3L6O", "22");
  /*14*/ test("12L10S7I5L14T12S9L1T14I0I5L1T2O18T9L0I15I16L10S1O15I0L17O5L18T4I18L7L7I13I3I12I2S3T5T3S16L14S14O11O15T14S", "17");
  /*15*/ test("0S18S2S19I14T7L14L2L6I9I0L4I5L13L15I8S8T2I5I7O18T3S1T7I2L8O0S20T9I14T5L5I1T4L9O8T19T5S12O16T19L4O10O10T14L", "24");
  /*16*/ test("7T5L6S4S8T6S10I19O20L14I18L21S7I11S11O1L13T20O9I7L2T8L2S20L3O14L9T17I8L8S14I6T2O11T21O18O6T15T1S3L6O19S18O20S19O16T6S14T", "26");
  /*17*/ test("18S2I4S16L13S17I21O8I17T8I14O12T20I20S19S16S13T12T20I22I15O2I2I8I2S18I9I9T6O13O13L17I2L20L2L4I9I19O11T3S10O2S18T12I5O11S19O21S6I17T17S", "26");
  /*18*/ test("11L5S0T22S18O13T2O22S15I12I21T16I3I1I22L11L11L22O13S24S15L13T15S19L10O15T7S24T19L0T13O11I12T13S4I24L15O3S19O10L19O0S20L7O11L21I22S18T19T23O8I22S24L0S", "21");
  /*19*/ test("7L7I11T7S18O17L8S15L9I3O24S3O1O5O14L9T13S2O25S22T10T8L24S18S13T1O1L6I10I4S13O3S7L10T1T4L17S20I18O15S25S23S21I19T6O24S9L2O2O15L12L8L8O18I18L0T5O", "31");
  /*20*/ test("999I999I999I999I999I999I999I999I999I999I999I", "44");
  
  return 0;
}

```