LoginSignup
1
2
@jajagacchi(jaja gacchi)

Pietインタプリタを自作する

Posted at

Pietとは

多くのプログラミング言語では、ソースコードはテキストファイルの形で与えられる。Pietでは、画像として与えられる。
用いる色は全部で20色と決められており、画像中をあるルールで走査する。その際の色変化に応じてpushやaddなどの命令が割り振られている。
そのルール自体はそれほど難しくないので、インタプリタを自作できそうである。
”Piet入門”などとググれば参考になるサイトがいくつも出てくる。

試しに作ってみることにする。

Pietの大雑把なルール

Pietでは、カラーブロックという同一色の塊からの脱出を繰り返し、その際の色変化で命令を実行する。
どこから脱出するかは、DPというパラメータで決まる。
DPは上下左右のどれかであって、基本的には最もDP方向に遠い画素から脱出する。
候補の画素が複数あることもあるので、その際は、CCというパラメータを参照する。
CCは左か右のどちらかでDP方向を基準に左が右を指す。
候補が複数ある時は最もCC方向に遠い画素を選択する。
脱出の際はDP方向に進む。
画像の端および黒の画素からは脱出できないことになっているので、こういう場合はDPの回転とCCの反転を繰り返して脱出を試みる。
試行の順番はもちろん定義されているがここでは省略。

ここまでで大雑把な挙動については終わり。

例外的なカラーブロックとして白いブロックがある。
白いブロックではひたすらDP方向に直進する。DP方向に遠いとか、CCとかは無関係。
白ブロックから出入りするときは命令は実行されない。
白ブロックから脱出できないときはまたDPとCCをいじって脱出を試みる。
カラーブロックからどうしても出られなければそこで終了。

push命令の際はカラーブロックの面積を参照してpushするようなことが行われるので、インタプリタの実装は若干画像処理的な要素が入ってくる。
ちょっとめんどくさい。

自作インタプリタの実行例

次のようにコマンドラインから実行する。

Piet.exe hi.bmp 16

最後の引数は、コーデルサイズ。Pietでは、コーデルサイズがカラーブロックの大きさの最小単位となるので、これが必要となる。

最後の引数に"-t"をつければ、実行の過程を出力出来る。

Piet.exe hi.bmp 16 -t

出力例は次の通り。

trace: step 0
0,0 -> push(st,9) -> 48,0
trace: stack: 9 

trace: step 1
3,0 -> push(st,8) -> 96,47
trace: stack: 8 9 

trace: step 2
6,2 -> mul(st) -> 112,47
trace: stack: 72 

trace: step 3
7,2 -> duplicate(st) -> 128,47
trace: stack: 72 72 

trace: step 4
8,2 -> Houtc(st) -> 144,47
trace: stack: 72 

trace: step 5
9,2 -> push(st,11) -> 159,96
trace: stack: 11 72 

trace: step 6
9,6 -> push(st,3) -> 159,112
trace: stack: 3 11 72 

trace: step 7
9,7 -> mul(st) -> 159,128
trace: stack: 33 72 

trace: step 8
9,8 -> add(st) -> 159,144
trace: stack: 105 

trace: step 9
9,9 -> ioutc(st) -> 143,144
trace: stack: 

trace: step 10
8,9 -> push(st,10) -> 95,64
trace: stack: 10 

trace: step 11
5,4 -> 
outc(st) -> 79,64
trace: stack: 

trace: step 12
4,4 ->  -> 79,64
trace: stack:

この形式は有名なnpietというインタプリタを参考にしている。

具体的な実装

バグがある可能性も高いし、実効効率が悪いので注意。
npietに比べると圧倒的に遅い。

color.h

#pragma once
#include "CImg.h"
#include <vector>
#include <stack>

using namespace cimg_library;
using Pos = std::pair<int, int>;
const int T_hue = 6;
const int T_brightness = 3;

const unsigned int color24[20] = { 0xffc0c0, 0xff0000, 0xc00000, 0xffffc0, 0xffff00, 0xc0c000, 0xc0ffc0, 0x00ff00, 0x00c000, 0xc0ffff, 0x00ffff, 0x00c0c0, 0xc0c0ff, 0x0000ff, 0x0000c0, 0xffc0ff, 0xff00ff, 0xc000c0, 0x000000, 0xffffff }; // color24[b+T_brightness*h]

class Vec2i // int型を要素とする二次元ベクトルクラス
{
public:
	int i, j;
	Vec2i() {}
	Vec2i(int i, int j) : i{ i }, j{ j }
	{
	}
	int operator()(int en) const // 要素に添字でアクセスする
	{
		return (en == 0 ? i : j);
	}
	bool operator==(const Vec2i& v)
	{
		if (this->i == v.i && this->j == v.j) return true;
		else return false;
	}
	Vec2i rotate(double theta) const // theta > 0 --> clockwise
	{
		Vec2i ret;
		ret.i = std::round(i * cos(theta) - j * sin(theta));
		ret.j = std::round(i * sin(theta) + j * cos(theta));
		return ret;
	}
	void Print(int codel_size = 1)
	{
		std::cout << i / codel_size << "," << j / codel_size;// << std::endl;
	}
};

class CC
{
public:
	CC(int lr) : lr{ lr }
	{
	}
	int lr; // l--> -1, r--> +1
};

class Color
{
public:
	int hue; //  F  
	int brightness;
};

Color get_color(const CImg<unsigned char>& img, const Vec2i& pos)
{
	int i = pos.i, j = pos.j;
	Color ret;
	ret.hue = ret.brightness = -1;
	unsigned char r = img(i, j, 0, 0);
	unsigned char g = img(i, j, 0, 1);
	unsigned char b = img(i, j, 0, 2);

	unsigned int c = (r << 16) | (g << 8) | (b);

	if (0x000000 == c)
	{
		ret.hue = 0;
		ret.brightness = 0;
	}
	else if (0xffffff == c)
	{
		ret.hue = 255;
		ret.brightness = 255;
	}
	else
	{
		for (int h = 0; h < T_hue; h++)
			for (int b = 0; b < T_brightness; b++)
			{
				if (c == color24[b + T_brightness * h])
				{
					ret.hue = h + 1;
					ret.brightness = b + 1;
					return ret;
				}
			}
	}

	return ret;
}

Color d_color(const Color& c0, const Color& c1) // calculate the difference of the color
{
	Color ret;
	int d_hue = c1.hue - c0.hue;
	int d_brightness = c1.brightness - c0.brightness;

	ret.hue = (d_hue >= 0 ? d_hue : d_hue + T_hue);
	ret.brightness = (d_brightness >= 0 ? d_brightness : d_brightness + T_brightness);

	return ret;
}

bool is_island(const CImg<unsigned char>& img, const Vec2i& pos, const Color& color)
{
	Color c = get_color(img, pos);
	if (c.hue == color.hue && c.brightness == color.brightness) return true;
	else return false;
}

std::vector<Vec2i> get_island(const CImg<unsigned char>& img, const Vec2i& pos0) 
{
	Color color = get_color(img, pos0);
	int width = img.width();
	int height = img.height();

	std::stack<Vec2i> spos;
	spos.push(pos0);

	std::vector<Vec2i> island;

	std::vector<Vec2i> done;

	while (!spos.empty())
	{
		Vec2i pos_cur = spos.top(); spos.pop(); // current node
		island.push_back(pos_cur);
		done.push_back(pos_cur);

		// push all of child nodes
		for (int di = -1; di <= 1; di += 2) // search left or right
		{
			Vec2i pos = pos_cur;
			pos.i += di;

			if (pos.i < width && pos.i >= 0 && is_island(img, pos, color))
			{
				if (find(done.begin(), done.end(), pos) == done.end()) spos.push(pos), done.push_back(pos); //  
			}
		}

		for (int dj = -1; dj <= 1; dj += 2) // search up or down
		{
			Vec2i pos = pos_cur;
			pos.j += dj;

			if (pos.j < height && pos.j >= 0 && is_island(img, pos, color))
			{
				if (find(done.begin(), done.end(), pos) == done.end()) spos.push(pos), done.push_back(pos); // 
			}
		}
	}
	return island;
}

operation.h

#pragma once
#include "color.h"
void push(std::stack<int>& st, int S)
{
	st.push(S);
}

bool pop(std::stack<int>& st)
{
	if (st.size() == 0) return false;
	int ret = st.top();
	st.pop();
	return true;
}

bool add(std::stack<int>& st)
{
	if (st.size() < 2) return false;

	int e0 = st.top(); st.pop();
	int e1 = st.top(); st.pop();

	st.push(e0 + e1);
	return true;
}

bool sub(std::stack<int>& st)
{
	if (st.size() < 2) return false;

	int e0 = st.top(); st.pop();
	int e1 = st.top(); st.pop();

	st.push(e1 - e0);
	return true;
}

bool mul(std::stack<int>& st)
{
	if (st.size() < 2) return false;

	int e0 = st.top(); st.pop();
	int e1 = st.top(); st.pop();

	st.push(e1 * e0);
	return true;
}

bool div(std::stack<int>& st)
{
	if (st.size() < 2) return false;

	int e0 = st.top(); st.pop();
	int e1 = st.top(); st.pop();

	if (e0 == 0) return false;

	st.push(e1 / e0);
	return true;
}

bool mod(std::stack<int>& st)
{
	if (st.size() < 2) return false;

	int e0 = st.top(); st.pop();
	int e1 = st.top(); st.pop();

	if (e0 == 0) return false;

	//	st.push(e1%e0);
	int r = e1 - e0 * (int)(e1 / e0);
	st.push(r);
	return true;
}

bool Not(std::stack<int>& st)
{
	if (st.size() == 0) return false;

	int e0 = st.top(); st.pop();

	if (e0 == 0) st.push(1);
	else st.push(0);
	return true;
}

bool greater(std::stack<int>& st)
{
	if (st.size() < 2) return false;

	int e0 = st.top(); st.pop();
	int e1 = st.top(); st.pop();

	if (e1 > e0) st.push(1);
	else st.push(0);
	return true;
}

bool pointer(std::stack<int>& st, Vec2i& dp)
{
	if (st.size() == 0) return false;

	int e0 = st.top(); st.pop();
	dp = dp.rotate(e0 * M_PI / 2.);
	return true;
}

bool Switch(std::stack<int>& st, CC& cc)
{
	if (st.size() == 0) return false;

	int e0 = st.top(); st.pop();
	for (int n = 0; n < std::abs(e0); n++) cc.lr *= -1;
	return true;
}

bool duplicate(std::stack<int>& st)
{
	if (st.size() == 0) return false;

	int e0 = st.top();
	st.push(e0);

	return true;
}

bool roll(std::stack<int>& st) // n==0ｿｿｿｿｿ
{
	if (st.size() < 2) return false;

	int c = st.top(); st.pop();
	int n = st.top(); st.pop();

	if (n < 0 || st.size() < n) return false;

	if (c > 0)
	{
		//		std::cout << "c = " << c << std::endl;
		for (int ci = 0; ci < c; ci++)
		{
			std::stack<int> tst;
			int top = st.top(); st.pop();
			for (int m = 0; m < n - 1; m++)
			{
				tst.push(st.top()); st.pop();
			}
			st.push(top);
			for (int m = 0; m < n - 1; m++)
			{
				st.push(tst.top()); tst.pop();
			}
		}
	}
	else
	{
		for (int ci = 0; ci < -c; ci++)
		{
			std::stack<int> tst;
			for (int m = 0; m < n; m++)
			{
				tst.push(st.top()); st.pop();
			}
			int top = tst.top(); tst.pop();
			for (int m = 0; m < n - 1; m++)
			{
				st.push(tst.top()); tst.pop();
			}
			st.push(top);
		}
	}

	return true;
}

bool outc(std::stack<int>& st)
{
	//	std::cout << "out-->";
	if (st.size() == 0) return false;
	char c = st.top(); st.pop();
	//	std::cout << (int)c << "<--";
	//	std::cout << c;
	printf("%c", c);
	return true;
}

bool outn(std::stack<int>& st)
{
	//	std::cout << "out-->";
	if (st.size() == 0) return false;
	int c = st.top(); st.pop();
	//	std::cout << c << "<--";
	printf("%d", c);
	return true;
}

bool in(std::stack<int>& st)
{
	int i;
	std::cin >> i;
	st.push(i);
	return true;
}

bool inc(std::stack<int>& st)
{
	char c;
	std::cin >> c;
	st.push(c);
	return true;
}

void op(const Color& dc, std::stack<int>& st, Vec2i& dp, CC& cc, int S, bool debug = false)
{
	if (dc.hue == 0 && dc.brightness == 1) push(st, S);
	else if (dc.hue == 0 && dc.brightness == 2) pop(st);
	else if (dc.hue == 1 && dc.brightness == 0) add(st);
	else if (dc.hue == 1 && dc.brightness == 1) sub(st);
	else if (dc.hue == 1 && dc.brightness == 2) mul(st);
	else if (dc.hue == 2 && dc.brightness == 0) div(st);
	else if (dc.hue == 2 && dc.brightness == 1) mod(st);
	else if (dc.hue == 2 && dc.brightness == 2) Not(st);
	else if (dc.hue == 3 && dc.brightness == 0) greater(st);
	else if (dc.hue == 3 && dc.brightness == 1) pointer(st, dp);
	else if (dc.hue == 3 && dc.brightness == 2) Switch(st, cc);
	else if (dc.hue == 4 && dc.brightness == 0) duplicate(st);
	else if (dc.hue == 4 && dc.brightness == 1) roll(st);
	else if (dc.hue == 4 && dc.brightness == 2) in(st);
	else if (dc.hue == 5 && dc.brightness == 0) inc(st);
	else if (dc.hue == 5 && dc.brightness == 1) outn(st);
	else if (dc.hue == 5 && dc.brightness == 2) outc(st);

	if (debug)
	{
		if (dc.hue == 0 && dc.brightness == 1) std::cout << "push(st," << S << ")";
		else if (dc.hue == 0 && dc.brightness == 2) std::cout << "pop(st)";
		else if (dc.hue == 1 && dc.brightness == 0) std::cout << "add(st)";
		else if (dc.hue == 1 && dc.brightness == 1) std::cout << "sub(st)";
		else if (dc.hue == 1 && dc.brightness == 2) std::cout << "mul(st)";
		else if (dc.hue == 2 && dc.brightness == 0) std::cout << "div(st)";
		else if (dc.hue == 2 && dc.brightness == 1) std::cout << "mod(st)";
		else if (dc.hue == 2 && dc.brightness == 2) std::cout << "Not(st)";
		else if (dc.hue == 3 && dc.brightness == 0) std::cout << "greater(st)";
		else if (dc.hue == 3 && dc.brightness == 1) std::cout << "pointer(st, dp)";
		else if (dc.hue == 3 && dc.brightness == 2) std::cout << "Switch(st, cc)";
		else if (dc.hue == 4 && dc.brightness == 0) std::cout << "duplicate(st)";
		else if (dc.hue == 4 && dc.brightness == 1) std::cout << "roll(st)";
		else if (dc.hue == 4 && dc.brightness == 2) std::cout << "in_num(st)";
		else if (dc.hue == 5 && dc.brightness == 0) std::cout << "in_char(st)";
		else if (dc.hue == 5 && dc.brightness == 1) std::cout << "outn(st)";
		else if (dc.hue == 5 && dc.brightness == 2) std::cout << "outc(st)";
	}
}

main.cpp

#define _USE_MATH_DEFINES
#include <stdio.h>
#include <cmath>
#include <iostream>
#include <vector>
#include "operation.h"
#include "color.h"

using Bmp = CImg<unsigned char>;


int sign(int num)
{
	if (num > 0) return 1;
	else if (num < 0) return -1;
	else return 0;
}

std::vector<Vec2i> find_edge(const Bmp& img, const Vec2i& pos0, const Vec2i& dp)
{
	std::vector<Vec2i> ret;
	std::vector<Vec2i> island = get_island(img, pos0);

	int i = (dp.i != 0 ? 0 : 1); // DP方向の添字
	std::sort(island.begin(), island.end(), [&](const Vec2i& p0, const Vec2i& p1)
		{
			return (p0(i) < p1(i)); // 昇順
		});
	int distance_to_edge = island.back()(i) - pos0(i); // +方向に進むときのedgeには必ずisland.back()が含まれる
	if (dp(i) < 0) distance_to_edge = island[0](i) - pos0(i); //  -方向に進むときのedgeには必ずisland[0]が含まれる

	int n0 = (dp(i) < 0 ? 0 : island.size() - 1); // -方向に進むときはisland[0]から順探索, +方向に進むときはisland.back()から逆探索
	int n1 = (dp(i) < 0 ? island.size() - 1 : 0); // 

	for (int n = n0; n * (-sign(dp(i))) <= n1; n -= dp(i))
	{
		int d = island[n](i) - pos0(i);
		if (d == distance_to_edge) ret.push_back(island[n]); // DP方向に最も遠い画素はedgeに含まれる
	}

	return ret;
}

Vec2i cc_direction(const Vec2i& dp, const CC& cc) // edgeから出る方向を決定する
{
	double theta;
	if (cc.lr == -1) theta = -M_PI / 2.;
	else theta = M_PI / 2.;

	return dp.rotate(theta);
}

Vec2i find_end_point(const std::vector<Vec2i>& edge, const Vec2i& dp, const CC& cc) // edgeの中で最もCC方向にあるコーデルがカラーブロック中の終端 (end_point)
{
	std::vector<Vec2i> Edge = edge;
	Vec2i direction = cc_direction(dp, cc);
	int i = (direction.i != 0 ? i = 0 : i = 1); // CC方向の添字
	std::sort(Edge.begin(), Edge.end(), [&](const Vec2i& p0, const Vec2i& p1)
		{
			return (p0(i) < p1(i)); // 昇順
		});
	if (direction(i) < 0) return Edge[0];
	else return Edge.back();
}

bool range_check(const Bmp& img, const Vec2i& pos)
{
	int width = img.width();
	int height = img.height();
	if (pos.i >= 0 && pos.i < width && pos.j >= 0 && pos.j < height) return true;
	else return false;

}

Vec2i find_move_point(const Bmp& img, const Vec2i& pos, Vec2i& dp, CC& cc) // 移動先座標を返す
{
	int width = img.width();
	int height = img.height();

	Vec2i end_point;
	if (get_color(img, pos).hue == 255)
	{
		end_point = pos;
	}
	else
	{
		std::vector<Vec2i> edge = find_edge(img, pos, dp);
		end_point = find_end_point(edge, dp, cc);
	}

	Vec2i ret(end_point.i + dp.i, end_point.j + dp.j);

	if (range_check(img, ret) && get_color(img, ret).hue != 0)
	{
		return ret;
	}
	else // 移動先が黒、または画像外の時は移動できない
	{
		return pos;
	}
}

int main(int argc, char** argv)
{
	bool debug = false;

	CImg<unsigned char> img(argv[1]);
	int width = img.width();
	int height = img.height();
	int codel_size = atoi(argv[2]);
	if (argc==4 && std::string(argv[3]) == "-t") debug = true;

	Vec2i pos(0, 0);
	Vec2i dp(1, 0);
	CC cc(-1);

	int Nrotate = 0;
	Vec2i move_point = pos;

	std::stack<int> st;
	
	int step = 0;
	while (Nrotate < 4)
	{
		int Ntry = 0;
		Nrotate = 0;

		if (debug)
		{
			std::cout << "trace: step " << step++ << std::endl;
			pos.Print(codel_size);
			std::cout << " -> ";
		}

		// 移動先(move_point)を見つけて、演算を実行する
		if (get_color(img, pos).hue != 255)
		{
			Color color0 = get_color(img, pos);
			std::vector<Vec2i> island = get_island(img, pos);
			int S = island.size() / codel_size / codel_size; // コーデルの面積
			while (move_point == pos) 
			{
				switch (Ntry)
				{
					case 0:
						break;
					case 1:
						cc.lr *= -1;
						break;
					case 2:
						dp = dp.rotate(M_PI / 2.);
						Ntry = 0;
						Nrotate++;
						break;
				}
				if (Nrotate == 4) break;
				move_point = find_move_point(img, pos, dp, cc);
				Ntry++;
			}
			Color color1 = get_color(img, move_point);
			Color dc = d_color(color0, color1);
			if (color1.hue != 255) op(dc, st, dp, cc, S, debug);
		}
		else
		{
			while (move_point == pos)
			{
				switch (Ntry)
				{
					case 0:
						break;
					case 1:
						cc.lr *= -1;
						dp = dp.rotate(M_PI / 2.);
						Ntry = 0;
						break;
				}
				move_point = find_move_point(img, pos, dp, cc);
				Ntry++;
				
			}
		}

		pos = move_point;
		std::stack<int> st_tmp = st;
		if (debug)
		{
			std::cout << " -> ";
			pos.Print();
			std::cout << std::endl;
			std::cout << "trace: stack: ";
			for (int s = 0; s < st.size(); s++) { std::cout << st_tmp.top() << " "; st_tmp.pop(); }
			std::cout << std::endl << std::endl;;
		}
	}

	return 0;
}
1
2
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
2