Sat May 2 02:01:36 JST 2015

写真から手書きっぽい漫画の生成

ppm(P3)からppm(P2)への変換をする

#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0;i<(n);++i)
#define loop for(;;)
#define trace(var) cerr<<">>> "<<#var<<" = "<<var<<endl;
#define inf (1e9)

template<class S, class T> inline
ostream& operator<<(ostream&os, pair<S,T> p) {
  os << '(' << p.first << ", " << p.second << ')';
  return os;
}

template<class T> inline
ostream& operator<<(ostream&os, vector<T> v) {
  if (v.size() == 0) {
    os << "(empty)";
    return os;
  }
  os << v[0];
  for (int i=1, len=v.size(); i<len; ++i) os << ' ' << v[i];
  return os;
}

template<class T> inline
istream& operator>>(istream&is, vector<T>&v) {
  rep (i, v.size()) is >> v[i];
  return is;
}

template<class S, class T, class U> inline
ostream& operator<<(ostream&os, tuple<S, T, U> t) {
  return os << '(' << get<0>(t) << ", " << get<1>(t)
    << ", " << get<2>(t) << ')';
}

using vi = vector<int>;
using vvi = vector<vi>;

void display(string format, int w, int h, int c, vvi gray) {
  cout << format << endl;
  cout << w << ' ' << h << endl;
  cout << c << endl;
  rep (i, h) {
    rep (j, w) {
      cout << min(c, max(0, gray[i][j]));
      cout << (j%15==14 ? '\n' : ' ');
    }
    cout << endl;
  }
}

int main(int argc, char*argv[]) {
  string format; cin >> format;
  int w, h; cin >> w >> h;
  int area = w * h;
  int c; cin >> c;
  vector<vvi> cols(3, vvi(h, vi(w)));
  rep (i, h) {
    rep (j, w) {
      cin
        >> cols[0][i][j]
        >> cols[1][i][j]
        >> cols[2][i][j];
      rep (k, 3) cols[k][i][j] = c - cols[k][i][j];
    }
  }

  // embossing
  const int D = 4;
  rep (k, 3) {
    rep (i, h) {
      rep (j, w) {
        int max_c = 0;
        int min_c = c;
        for (int dx = -D; dx <= D; ++dx) {
          for (int dy = -D; dy <= D; ++dy) {
            int x = i + dx;
            int y = j + dy;
            if (x < 0 or y < 0 or x >= h or y >= w) continue;
            max_c = max(max_c, cols[k][x][y]);
            min_c = min(min_c, cols[k][x][y]);
          }
        }
        int mid_c = (max_c + min_c) / 2;
        for (int dx = -D; dx <= D; ++dx) {
          for (int dy = -D; dy <= D; ++dy) {
            int x = i + dx;
            int y = j + dy;
            if (x < 0 or y < 0 or x >= h or y >= w) continue;
            int c = cols[k][x][y];
            cols[k][x][y] = c < mid_c ? 0 : c;
          }
        }
      } } }
  cerr << "embossing: done" << endl;

  vvi gray(h, vi(w, c));

  rep (k, 3) { // random walk for-each color
    int x = rand() % h,
        y = rand() % w;
    rep (_, area/2) {
      const int D = 10;
      int dx, dy,
          x2, y2;
      rep (__, 10) {
        dx = rand() % (2*D+1) - D;
        dy = rand() % (2*D+1) - D;
        x2 = max(0, min(h - 1, x + dx));
        y2 = max(0, min(w - 1, y + dy));
        if (x == x2 and y == y2) continue;
        if (cols[k][x2][y2] > rand()%c) break;
      }
      { // draw a line
        int weight = (cols[k][x2][y2] + cols[k][x][y]) / 10;
        for (int d = 0; d <= D; ++d) {
          int xi = x + d * (x2 - x) / D;
          int yi = y + d * (y2 - y) / D;
          gray[xi][yi] -= weight;
          cols[k][x][y] -= weight;
        }
      }
      x = x2; y = y2;
    }
  }

  display("P2", w, h, c, gray);

  return 0;
}

魚釣り、同情、迷子ごっこ

魚釣りという行為を目の当たりにした時
魚は何のために生きているのだろうと真剣に考えたのを覚えている
あれはれっきとした、娯楽としての、狩猟だ
人間の都合のために飼われる魚は決して可愛がられる為のものじゃない
ちょっと考えを転換すると、水族館の魚というのも、ふつう、可愛がられるものではないだろう

神保町から、日付が代わる前の昨日は映画の日であったので、 映画を見るために池袋に行くことにした。 この頃また暖かなので、私の足は自転車であった。 いつも走る道だと、神保町からまっすぐに旧白山通りで北に走り、 千石のあたりで、不忍通りで今度はまっすぐ西に向かって春日通りにぶつかるまで走る。 今度はそこから少し北に走ると池袋である。 どんな道路が在るかにもよるが、一般的に言って、これは無駄のある走路であろう。 斜めに一直線に行ける方が近道である。 そういうわけで今日は、近道を目指して、今まで走ったこともない道だけを走って池袋まで行くことにした。 どうせ見知らぬ道である。 見知った道をずいずい走るほうが近いに決まっているのであるが、 これはまあ、 一つの遊びだ。 自分からすすんで迷子になる。 子供よくやる探検ごっこだ。 行きは太陽が出ていたから簡単だった。 比較的簡単に、春日通りにぶつかることができた。 神保町から、一旦、飯田橋まで走って、そこから大体真北を目指した。 小石川を通りぬけ、茗荷谷という文字を目指して走ると、春日通りは随分整備されていた。 途中で通った小石川四丁目は仏教の染み通った町であるらしく、そういった施設や幼稚園がよく見受けられた。 子どもたちは公道の上でキャッチボールをし、 播磨坂さくら並木は、東京の真ん中としては珍しいくらいの緑色を私に見せてくれて、 大変のどかで平和な印象であった。

どこをどう走っても、小石川植物園とぶつかって大変邪魔だった。 池袋からの帰りも知らない道をできるだけ走ることにした。 なんせ私は現代人らしからぬスマートフォンなんてものを持たないので、 本当に迷子になったら本当に、である。 しかしまあ、思えば、 わざとちょっと迷子になってみる趣味は大昔からだった。 これは言ってみれば、平凡な日常にちょっとしたスリルを加えることである。 スマートフォンがなくても、道路標識をよく見ていれば大体自分がどこにいるかわかるし、 自分が高校生の頃はしょっちゅう、交番に道を訪ねて、駅の場所を尋ねたらすぐ裏だったなんてことがある。 自分が行く必要のある数カ所、家、大学、本屋さん、映画館、それらをつなぐ、たかだか数本の道だけを走るのが日常だと考えているところに由来するのではないか。 つまり、 旅行に行くなんて、そんなことする人が本当にいるなんて、思わなかった。 いや、そりゃいるんだろうけどさ、 旅行会社ってあるしさ。 でもだからって、 わざわざ自分のお金を払ってだよ? 楽しいかどうかも定かじゃないただの移動だよ。 純粋に旅行を目的にした旅行なんて、自分がすることが、あるかしら

ペットショップにおいて、 大まかにいえば、犬と猫と、その他(魚とか)が扱われる。 犬と猫が主役だ。 その他、すなわち魚類なんかは、可愛がられない。 客に、ではなくて、店員に、だ。 少なからず、一部の客は、熱帯魚やらに熱心だ。 我々より熱心だ。 だって、そんなただの水草をわざわざ買っていくんだもん。 わかめでも入れておけばいいのに。 大勢の群れをなす魚は、 水族館においては、客にも水族館の人にも可愛がられないんだろうなあ。

タイルをスライドするパズル

しょうもないことをしてました。
Rubpix なるFlash製パズルをやってて、だんだん辛くなってきたので、 解くプログラムを書く作戦に変更した

  1. \(n \times n\) に色のついたタイルが並んでいる
  2. 行または列について (上下左右に一つ) シフトする操作が許されている
  3. 目標の色の配置 (\(n \times n\)) に一致させたらゴール

はじめは \(3 \times 3\) で、勘で出来るんだけど、飽きてくる
ステージが上がるごとに、\(n\)の数は徐々に増えるらしく、
\(4 \times 4\) になるともう、本格的に難しさを感じてくる
まだ私はその画面を見たことがないが、"rubpix" で画像検索をすると、 \(6 \times 6\) も出てくる

以下は \(n \times n\) の場合について、双方向探索で解くプログラム
\(6 \times 6\) でも現実的な時間で解けるのかちょっと自信がない
頭のいいヒューリスティックを入れるべきだ

// you can read this source 
// also at: https://gist.github.com/cympfh/3ddc2e84211f37a81bb1
#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0;i<(n);++i)
#define loop for(;;)
#define trace(var) cerr<<">>> "<<#var<<" = "<<var<<endl;
#define inf (1e9)

template<class S, class T> inline
ostream& operator<<(ostream&os, pair<S,T> p) {
  os << '(' << p.first << ", " << p.second << ')';
  return os;
}

template<class T> inline
ostream& operator<<(ostream&os, vector<T> v) {
  if (v.size() == 0) {
    os << "(empty)";
    return os;
  }
  os << v[0];
  for (int i=1, len=v.size(); i<len; ++i) os << ' ' << v[i];
  return os;
}

template<class T> inline
istream& operator>>(istream&is, vector<T>&v) {
  rep (i, v.size()) is >> v[i];
  return is;
}

template<class S, class T, class U> inline
ostream& operator<<(ostream&os, tuple<S, T, U> t) {
  return os << '(' << get<0>(t) << ", " << get<1>(t)
    << ", " << get<2>(t) << ')';
}

using vi = vector<char>;
using vvi = vector<vi>;

enum Dir {
  Down = 0,
  Up = 1,
  Left = 2,
  Right = 3
};

Dir invert(Dir d) {
  if (d == Down) return Up;
  if (d == Up) return Down;
  if (d == Left) return Right;
  if (d == Right) return Left;
}

struct Op {
  Dir dir; int pos;
  Op(int _pos, Dir _d) : pos(_pos), dir(_d) {}
};

inline
ostream& operator<<(ostream&os, Op o) {
  os << "pos[ " << o.pos << " ] ";
  if (o.dir == Left) os << "Left";
  if (o.dir == Right) os << "Right";
  if (o.dir == Up) os << "Up";
  if (o.dir == Down) os << "Down";
  return os;
}

inline void
mov_left(vi&v, int n, int k) {
  char tmp = v[n*k];
  rep (i, n - 1) v[n*k+i] = v[n*k+i+1];
  v[n*k+n-1] = tmp;
}

inline void
mov_right(vi&v, int n, int k) {
  char tmp = v[n*k+n-1];
  rep (i, n - 1) v[n*k+n-i-1] = v[n*k+n-i-2];
  v[n*k] = tmp;
}

inline void
mov_up(vi&v, int n, int k) {
  char tmp = v[k];
  rep (i, n - 1) v[k + n * i] = v[k + n * (i+1)];
  v[k + (n-1)*n] = tmp;
}

inline void
mov_down(vi&v, int n, int k) {
  char tmp = v[k + (n-1)*n];
  rep (i, n - 1) v[k + n*(n-i-1)] = v[k + n*(n-i-2)];
  v[k] = tmp;
}

vector<pair<vi, Op>> step(int n, vi v) {
  vector<pair<vi, Op>> ret;
  rep (k, n) {
    mov_left(v, n, k);
    ret.push_back({ v, Op(k, Left) });
    mov_right(v, n, k);
    mov_right(v, n, k);
    ret.push_back({ v, Op(k, Right) });
    mov_left(v, n, k);
  }
  rep (k, n) {
    mov_up(v, n, k);
    ret.push_back({ v, Op(k, Up) });
    mov_down(v, n, k);
    mov_down(v, n, k);
    ret.push_back({ v, Op(k, Down) });
    mov_up(v, n, k);
  }
  return ret;
}

bool equal(vi&xs, vi&ys) {
  int n = xs.size();
  if (ys.size() != n) return false;
  rep (i, n)
    if (xs[i] != ys[i]) return false;
  return true;
}

map<vi, vector<Op>> memo;
map<vi, vector<Op>> r_memo;

int main(int argc, char*argv[]) {

  int n; cin >> n;
  vi f(n*n), g(n*n);
  rep (i, n*n) cin >> f[i];
  rep (i, n*n) cin >> g[i];
  trace(f); trace(g);

  vector<Op> ops;
  queue<pair<vi, bool>> q;
  q.push({ f, true });
  q.push({ g, false });

  memo[f] = {};
  r_memo[g] = {};

  while (not q.empty()) {
    auto tp = q.front(); q.pop();
    auto&f = tp.first;
    auto d = tp.second;

    if ((d and r_memo.count(f) > 0) or ((not d) and memo.count(f) > 0)) {
      for (auto&o: memo[f])
        cout << o << endl;
      for (int i = r_memo[f].size() - 1; i >= 0; --i) {
        Op&o = r_memo[f][i];
        o.dir = invert(o.dir);
        cout << r_memo[f][i] << endl;
      }
      return 0;
    }

    for (auto&p: step(n, f)) {
      auto&f2 = p.first;
      auto o = p.second;
      if (d) {
        if (memo.count(f2) > 0) continue;
        vector<Op> hs2 = memo[f];
        hs2.push_back(o);
        memo[f2] = hs2;
      } else {
        if (r_memo.count(f2) > 0) continue;
        vector<Op> hs2 = r_memo[f];
        hs2.push_back(o);
        r_memo[f2] = hs2;
      }
      q.push({f2, d});
    }
  }
  return 0;
}
$ cat input
4

YYYY
YGYG
RRGR
RGYY

YYYY
GGGG
RRRR
YYYY

$ ./a.out < input
pos[ 1 ] Up
pos[ 2 ] Up
pos[ 2 ] Left
pos[ 1 ] Down
pos[ 0 ] Up

pos[ m ] (\(0 \leq m < n\)) \(m\) 行目、または \(m\) 列目を表す
ただし、 盤の最上段を0行目、最左列を0列目だとして数える
(人間が読む部分くらい、1-indexedにするものだと反省した)

今の場合

  1. 1列目を上にshift
  2. 2列目を上にshift
  3. 2行目を左にshift
  4. 1列目を下にshift
  5. 0列目を上にshift

という手順を表す

感想

一つのステージをクリアする度に、 入力を作る作業が一番の手間だった