ココナツの問題をC++で解く

■前回の記事「Maybeの(>=>)を使って問題を解く」ではHaskellでココナツ問題を解いてみたが、もし使える言語がC++しかなかったらどうするか考えてみた。Haskellでは失敗する可能性のある関数を「合成」することができたが、C++にはそのような機能がないのでif文で分岐することになる。

#include <iostream>
#include <utility>

#define MAX 100000

using namespace std;

pair<bool,int>  g(int n, int r)
{
  pair<bool,int> retval = make_pair(false,0);
  if(0 == (n-r) % 5){
    const int x = 4*((n-r)/5);
    retval = make_pair(true,x);
  }
  return retval;
}

typedef pair<bool,int> mint;

bool check_num(int n)
{
  //1,1,1,1,1,0
  const mint n1 = g(n,1);
  if(n1.first){
    const mint n2 = g(n1.second,1);
    if(n2.first){
      const mint n3 = g(n2.second,1);
      if(n3.first){
        const mint n4 = g(n3.second,1);
        if(n4.first){
          const mint n5 = g(n4.second,1);
          if(n5.first){
            const mint nfin = g(n5.second,0);
            if(nfin.first){
              return true;
            }
          }
        }
      }
    }
  }
  return false;
}

int get_ans(){
  for(int n = 0; n < MAX; ++n){
    if(check_num(n)){
      return n;
    }
  }

  return -1;
}

int main()
{
  const int n = get_ans();
  cout << n << endl;
  return 0;
}

関数check_numをもう少し読みやすく出来ないかと考えてみたが、良い考えを思いつかなかった。

昔の自分なら、マクロを使って

bool check_num(int n)
{
  //1,1,1,1,1,0
  const mint n1 = g(n,1);

  #define MY_MACRO(X,Y,R)   g(X.second,R);if(! Y.first){return false;}

  const mint n2 = MY_MACRO(n1,n2,1);
  const mint n3 = MY_MACRO(n2,n3,1);
  const mint n4 = MY_MACRO(n3,n4,1);
  const mint n5 = MY_MACRO(n4,n5,1);
  const mint nfin = MY_MACRO(n5,nfin,0);

  return true;
}

のように書いたかもしれないが、疲れているときにこのようなコードを書くことの恐ろしさを何度か経験したのであまり乗り気にはなれない。

■結論は特にない。(HaskellがすごいとかC++がダメだと主張したいわけではない)。

広告

OpenCV2 で自分がよく使う画像操作まとめ

OpenCV で画像をサクッと作りたい場合があります。そんなときに自分が非常に良く使う機能をまとめておきます。自分向け記事です。


//OpenCV2 image handling
#include <cv.h>
#include <highgui.h>
#include <iostream>
#include <sstream> //for ostringstream

#define image_path_string "madoka.png"
#define W 500
#define H 350


#define IMAGESHOW(X) do{  \
  cvNamedWindow(#X);      \
  imshow(#X, X);          \
  }while(0)


int main()
{
  using namespace std;
  using namespace cv;


  //画像の読み込み
  Mat img1 = imread( image_path_string );


  //画像をグレースケールで読み込む
  Mat img2 = imread( image_path_string, 0);


  //カラー画像の作成
  Mat img3 = Mat::zeros(Size(W, H), CV_8UC3);


  //応用:img2と同じサイズでグレー画像を作成
  Mat img4 = Mat::zeros(Size(img2.cols, img2.rows), CV_8UC1);


  //グレースケール画像をカラー画像に変換する
  Mat img2_color;
  cvtColor(img2, img2_color, cv::COLOR_GRAY2BGR);


  //比較のために両方に「赤い対角線」を入れてみる
  const int W2 = img2.cols;
  const int H2 = img2.rows;
  line(img2, Point(0,0), Point(W2,H2)
    , Scalar(0,0,255), 3, CV_AA);
  line(img2_color, Point(0,0), Point(W2,H2)
    , Scalar(0,0,255), 3, CV_AA);
  //Scalar(b,g,r,alpha=0)


  //コピーコンストラクタ
  Mat img5(img2);
  //これは「浅い」コピーになる。
  //したがって、img5 に対する操作は img2 に反映される。
  line(img5, Point(0,H2/2), Point(W2,H2/2)
    , Scalar(0,255,0), 3, CV_AA);


  Mat img6 = img2.clone();
  //これは「深い」コピーになる。
  //したがって、img6 に対する操作は img2 には全く反映されない。


  //画素に対する直接操作(グレースケール画像の場合)
  //市松模様にしてみる
  for(int y = 0; y < img6.rows; ++y)
  {
    for(int x = 0; x < img6.cols; ++x)
    {
      img6.at<unsigned char>(y,x)
        = 255 * ((x/10+y/10) % 2);
      // (y,x) という順であることに注意する。
    }
  }


  //画素に対する直接操作(カラー画像の場合)
  //一列毎に色が変わる市松模様にしてみる
  Mat img7 = img3.clone();
  for(int y = 0; y < img7.rows; ++y)
  {
    for(int x = 0; x < img7.cols; ++x)
    {
      img7.at<Vec3b>(y,x)[0] = ((y/10)%3 == 0)? 255 * ((x/10+y/10) % 2) : 0;//B
      img7.at<Vec3b>(y,x)[1] = ((y/10)%3 == 1)? 255 * ((x/10+y/10) % 2) : 0;//G
      img7.at<Vec3b>(y,x)[2] = ((y/10)%3 == 2)? 255 * ((x/10+y/10) % 2) : 0;//R
      // (y,x) という順であることに注意する。
    }
  }


  //画像の「原点」は左上である;
  //つまりx軸は左から右へ、y軸は上から下に走っている。
  circle(img6, Point(0,0), 100
    , Scalar(0,250,250), 5, CV_AA);
  circle(img7, Point(0,0), 100
    , Scalar(0,250,250), 5, CV_AA);


  //画像の保存:拡張子に応じた形式で保存される。
  imwrite("img7.png", img7);
  imwrite("img7.jpg", img7);
  imwrite("img7.bmp", img7);

  //文字列への書き出し
  //(検証しやすくするため小さめの画像でやる)
  Mat img8 = Mat::zeros(Size(20, 15), CV_8UC1);
  for(int y = 0; y < img8.rows; ++y)
  {
    for(int x = 0; x < img8.cols; ++x)
    {
      img8.at<unsigned char>(y,x) = 255 * ((x+y) % 2);
    }
  }

  //C言語のデータとして使える形式で書き出し
  ostringstream C_out;
  C_out << cv::format(img8,"C") << flush;
  cout << "C:" << C_out.str() << endl;

  //CSV形式で書き出し
  ostringstream CSV_out;
  CSV_out << cv::format(img8,"csv") << flush;
  cout << "CSV:" << CSV_out.str() << endl;

  //Pythonのデータとして使える形式で書き出し
  ostringstream Python_out;
  Python_out << cv::format(img8,"python") << flush;
  cout << "Python:" << Python_out.str() << endl;

  IMAGESHOW(img1);
  IMAGESHOW(img2);
  IMAGESHOW(img2_color);
  IMAGESHOW(img3);
  IMAGESHOW(img4);
  IMAGESHOW(img5);
  IMAGESHOW(img6);
  IMAGESHOW(img7);

  cout << "hit any key on some image window" << endl;
  cvWaitKey(0);

  return 0;
}

※ブログのコード欄を左右スクロールせずに読めるようにするために幾つかの箇所で不自然な改行を挟んであります。

.PHONY : all clean

LD_LIBRARY_PATH = $(PATH)
OPENCV_32_TRUNC = /d/opencv2.4.6.0-MSYS32
OPENCV_VERSION_SUFFIX = 246
OPENCV_HEADERS_INCLUDE32 = -I$(OPENCV_32_TRUNC)/include/opencv  \
-I$(OPENCV_32_TRUNC)/include

OPENCV_LIB_32_LOADPATH = -L$(OPENCV_32_TRUNC)/lib

LINK_OPENCV_LIBS = \
-lopencv_highgui$(OPENCV_VERSION_SUFFIX) \
-lopencv_core$(OPENCV_VERSION_SUFFIX) \
-lopencv_imgproc$(OPENCV_VERSION_SUFFIX) \

#libopencv_imgproc is for "cvCvtColor"

LDFLAGS = -lm -lstdc++ $(OPENCV_LIB_32_LOADPATH) $(LINK_OPENCV_LIBS)

all : opencvsample

opencvsample : opencvsample.cpp
	g++ $< -o a.exe $(OPENCV_HEADERS_INCLUDE32) $(LDFLAGS)
	./a.exe

clean:
	$(RM) *.o
	$(RM) *.exe
C:{0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255,
  255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0,
  0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255,
  255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0,
  0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255,
  255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0,
  0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255,
  255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0,
  0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255,
  255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0,
  0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255,
  255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0,
  0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255,
  255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0,
  0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255}
CSV:0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255
  255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0
  0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255
  255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0
  0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255
  255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0
  0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255
  255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0
  0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255
  255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0
  0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255
  255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0
  0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255
  255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0
  0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255

Python:[[0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255],
  [255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0],
  [0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255],
  [255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0],
  [0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255],
  [255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0],
  [0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255],
  [255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0],
  [0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255],
  [255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0],
  [0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255],
  [255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0],
  [0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255],
  [255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0],
  [0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255]]
hit any key on some image window

bi

※自分用メモです。bison is what とか、どんな原理で動作するかとかの話は書きません(書けません)。

久しぶりにbison(とflex)で遊ぼうと思ったら使い方を色々忘れてしまいました。紙のノートに記録したものがあったのでそれを参考に自分向けのメモを残しておきます。

■bisonファイルの形式
メモ:二箇所に出てくる「%%」が大事。

%{
/*---- C/C++で色々書く ----*/
%}

/*---- Bison宣言部 ----*/
%token ....
%left ....
%right ....
%union ....

%%

/*---- Bison文法部 ----*/

%%

/*---- C/C++で色々書く(その2) ----*/

void helper_func(){ ... }

■OMake関連ファイルの編集

OSTYPE = msys

open build/C
open build/OCaml
open build/LaTeX

DefineCommandVars()

.SUBDIRS: .
.PHONY : all
.DEFAULT : all

TARGET = simple.exe
OBJS = simple.tab.o simple.lexer.o simple_main.o
HEADERS = simple_lexer.h
PREMATURE=premature.
VALUETYPE = double

INCLUDES += -IC:\MinGW\msys\1.0\include -IC:\MinGW\lib\gcc\mingw32\4.8.1\include
LIBPATHS = -LC:\MinGW\lib -LC:\MinGW\lib\gcc\mingw32\4.8.1
LIBS = -lstdc++ -lm

CXX = g++
CXXFLAGS += -Wall -O2 $(INCLUDES)

all : $(TARGET)

%.o: %.cc
	$(CXX) $(CXXFLAGS) -c -o $@ $< 

simple.lexer.cc : simple.l
	flex -o$(PREMATURE)$@ $<
	grep -v "    #define yyFlexLexer yyFlexLexer"  $(PREMATURE)$@ > $@
	$(RM) $(PREMATURE)$@ 

simple.tab.cc  simple.tab.h  : simple.y
	bison -d --verbose $<
	perl -pe 's/typedef int YYSTYPE/typedef $(VALUETYPE) YYSTYPE/;' simple.tab.c > simple.tab.cc
	sed '53c\#define YYSTYPE $(VALUETYPE)' simple.tab.h > $(PREMATURE)simple.tab.h
	mv $(PREMATURE)simple.tab.h  simple.tab.h

$(TARGET) : $(OBJS)
	$(CXX) -o $@ $(LIBPATHS) $(LIBS) $^

■この記事をかくにあたって参考にした記事:
http://d.hatena.ne.jp/fwtmp/20081209

vector<pair<T,U> > から vector<T> や vector<U> を抜き出す

小ネタです。最近、作業をしていてこんな関数が欲しくなりました:

template <typename T, typename U>
vector<T> first_vec(const vector<pair<T,U> >& x);

template <typename T, typename U>
vector<U> second_vec(const vector<pair<T,U> >& x);

Boostにこんなのあるだろと思ったけど探すのが大変だし簡単なので自分で書いてみました。

template <typename T, typename U>
vector<T> first_vec(const vector<pair<T,U> >& x)
{
    typedef vector< pair<T, U> > pairvec_t;
    typedef vector<T> retval_t;
    retval_t retval;
    retval.reserve(x.size());
    for(pairvec_t::const_iterator i = x.begin(); i != x.end(); ++i)
    {
        retval.push_back(i->first);
    }
    return retval;
}

template <typename T, typename U>
vector<U> second_vec(const vector<pair<T,U> >& x)
{
    typedef vector< pair<T, U> > pairvec_t;
    typedef vector<U> retval_t;
    retval_t retval;
    retval.reserve(x.size());
    for(pairvec_t::const_iterator i = x.begin(); i != x.end(); ++i)
    {
        retval.push_back(i->second);
    }
    return retval;
}