オフラインリアルタイムどう書くE28の実装例 ( c++17 )

オフラインリアルタイムどう書くE28の問題「増築の果ての隣室」の実装例を、C++17 で。

問題 : http://nabetani.sakura.ne.jp/hena/orde28sqst/
実装リンク集 : https://qiita.com/Nabetani/items/4e3fac2746ca05a93165
イベント : https://yhpg.doorkeeper.jp/events/81346

次回のイベントは 12/8。
詳しくは
https://yhpg.doorkeeper.jp/events/82699
を御覧ください。楽しいよ？

で。
実装例は以下の通り：

c++17

//clang++ -std=c++17 -Wall -O2 e28.cpp
#include <iostream>
#include <string>
#include <sstream>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <numeric>

struct room{
  std::int64_t left;
  std::int64_t top;
  std::int64_t w;
  room() = delete;
  room( std::int64_t l_, std::int64_t t_, std::int64_t w_ )
    : left(l_), top(t_), w(w_)
  {}
  std::int64_t right() const { return left + w; }
  std::int64_t bottom() const { return top + w; }
  std::pair<std::int64_t, std::int64_t> horz() const {
    return { left, right() };
  }
  std::pair<std::int64_t, std::int64_t> vert() const {
    return { top, bottom() };
  }
};

struct operation{
  char dir;
  int count;
  operation() = delete;
  operation( char d_, int c_ )
    : dir(d_), count(c_)
  {}
};

std::int64_t top_of( std::vector<room> const & rooms ){
  return std::accumulate(
    cbegin(rooms), cend(rooms),
    rooms[0].top,
    []( int64_t acc, room const & ro ){
      return std::min(acc, ro.top);
  } );
}

std::int64_t bottom_of( std::vector<room> const & rooms ){
  return std::accumulate(
    cbegin(rooms), cend(rooms),
    rooms[0].bottom(),
    []( int64_t acc, room const & ro ){
      return std::max(acc, ro.bottom());
  } );
}

std::int64_t left_of( std::vector<room> const & rooms ){
  return std::accumulate(
    cbegin(rooms), cend(rooms),
    rooms[0].left,
    []( int64_t acc, room const & ro ){
      return std::min(acc, ro.left);
  } );
}

std::int64_t right_of( std::vector<room> const & rooms ){
  return std::accumulate(
    cbegin(rooms), cend(rooms),
    rooms[0].right(),
    []( int64_t acc, room const & ro ){
      return std::max(acc, ro.right());
  } );
}

std::vector<room>
newrooms( operation const & op, std::vector<room> const & rooms ){
  std::int64_t t = top_of( rooms );
  std::int64_t b = bottom_of( rooms );
  std::int64_t l = left_of( rooms );
  std::int64_t r = right_of( rooms );
  auto w = ( op.dir == 'N' || op.dir == 'S' ? r-l : b-t ) / op.count;
  auto ret = std::vector<room>();
  ret.reserve(op.count);
  for( int i=0 ; i<op.count ; ++i ){
    switch( op.dir ){
      case 'N':
        ret.emplace_back(l+w*i, t-w, w );
        break;
      case 'S':
        ret.emplace_back(l+w*i, b, w );
        break;
      case 'W':
        ret.emplace_back(l-w, t+w*i, w );
        break;
      case 'E':
        ret.emplace_back(r, t+w*i, w );
        break;
      default:
        throw std::exception();
    }
  }
  return ret;
}

template< typename t >
std::vector<t>
concat( std::vector<t> const & a0, std::vector<t> const & b ){
  auto a = a0;
  a.insert( a.end(), cbegin(b), cend(b) );
  return a;
}

std::vector<room>
build( std::vector<operation> const & ops ){
  int64_t w = std::accumulate( cbegin(ops), cend(ops), 1LL,
    [](int64_t acc, operation const & op ){return acc * op.count;}
  );
  auto rooms = std::vector<room>{room(0, 0, w)};
  return std::accumulate(
    cbegin(ops), cend(ops),
    rooms,
    []( std::vector<room> const & acc, operation const & op ){
      auto nr = newrooms(op, acc);
      return concat( acc, nr );
    });
}

template< typename pair >
bool has_intersectoin( pair const & a, pair const & b ){
  if ( a.first < b.first ){
    return b.first < a.second;
  } else if ( b.first< a.first ){
    return a.first < b.second;
  } else {
    return true;
  }
}

bool is_neibour( room const & a, room const & b ){
  if ( a.top == b.bottom() || a.bottom()==b.top ){
    return has_intersectoin( a.horz(), b.horz() );
  } else if ( a.left == b.right() || a.right() == b.left ){
    return has_intersectoin( a.vert(), b.vert() );
  } else {
    return false;
  }
}

std::pair<std::vector<operation>, int>
parse( std::string const & src ){
  std::vector<operation> ops;
  ops.reserve( src.size()/2 );
  size_t pos = 0;
  for( ; src[pos] != '/' ; pos+=2 ){
    ops.emplace_back( src[pos], src[pos+1] - '0' );
  }
  int num = std::atoi( src.c_str() + pos + 1 );
  return { ops, num };
}

template< typename container_t >
std::string string_join( container_t const & c, std::string const & delim ){
  std::stringstream ss;
  bool first_time = true;
  for( auto && e : c ){
    if ( first_time ){
      first_time = false;
    } else {
      ss << delim;
    }
    ss << e;
  }
  return ss.str();
}

std::string solve( std::string const & src ){
  auto[ ops, room_number ] = parse( src );
  auto rooms = build( ops );
  auto myroom = rooms.at(room_number-1);
  auto neis = std::vector<size_t>();
  for( size_t i=0 ; i<rooms.size() ; ++i ){
    if ( is_neibour( myroom, rooms[i] ) ){
      neis.push_back(i+1);
    }
  }
  return string_join(neis, ",");
}

void test( std::string const & src, std::string const & expected ){
  auto actual = solve( src );
  auto okay = actual == expected;
  std::cout
    << ( okay ? "ok " : "**NG** " )
    << src << " / "
    << actual << " / "
    << expected << "\n";
}

int main(){
  /*0*/ test( "N7N4E5/8", "1,7,12,13,14" );
  /*1*/ test( "E1/1", "2" );
  /*2*/ test( "N6/5", "1,4,6" );
  /*3*/ test( "W5/3", "1,2,4" );
  /*4*/ test( "S1N2/1", "2,3,4" );
  /*75*/ test( "N9S9S3S6N6S7N8W4E9W7E3N5W8S9E9E9W6N3N9W8/119", "73,74,78,113,120,122,123,124,131,132,133,134" );
}

テストデータの大半は省略。
で。
ruby版( https://qiita.com/Nabetani/items/bb4b06467dbe1cc6c6dd )を移植した。

構造化束縛( https://cpprefjp.github.io/lang/cpp17/structured_bindings.html )を使いたかったので、早速使ってみた。これは楽しい。

あと、std::accumulate を積極的に使ってみた。わかりやすくはならないよなぁ。

go よりもだいぶ長くなったのがなんか悔しい。字句解析と文字列整形にコードを要してしまった。

ruby で1行だった

ruby

  t = f.map(&:top).min

は、C++ では

c++17

std::int64_t top_of( std::vector<room> const & rooms ){
  return std::accumulate(
    cbegin(rooms), cend(rooms),
    rooms[0].top,
    []( int64_t acc, room const & ro ){
      return std::min(acc, ro.top);
  } );
}

と、関数呼び出しひとつで済んでいるような、かえってわかりにくいような、そんな感じになった。

しかしなんで std::accumulate は <algorithm> ではなくて <numeric> なんだろう。不思議。