十字の壁がそそり立つ世界の中を君は螺旋状に歩く (シミュレーション)

問題	http://nabetani.sakura.ne.jp/hena/ord28spirwa/
シミュレーション (Python/Ruby/C++)	http://qiita.com/cielavenir/items/8c77a158136bd668a27b
規則性 (Python/Ruby/C/C#/Java)	http://qiita.com/cielavenir/items/a285b0cea4a26ff886b8
規則性 (D/Go/Swift/PHP/ Vala )	http://qiita.com/cielavenir/items/edb1daff9ea861a418ec
規則性 (VB/F#/Perl)	http://qiita.com/cielavenir/items/0c84af4049ab161f82c1
規則性 (PowerShell)	http://qiita.com/cielavenir/items/d9ef9f12068e99e888f2
規則性 ( AIR-lang )	http://qiita.com/cielavenir/items/d804f61412fb4f07ba06
規則性 (Crystal/Perl6)	http://qiita.com/cielavenir/items/13896a662b05da8b77a2
Rubyの多次元配列で最初の要素を加工して返したい (tap/break等について)	http://qiita.com/cielavenir/items/3f209351b924e2615f5e

入出力について

以下の答案は全て標準入出力を使うので、拙作採点ツールが必要。
https://github.com/cielavenir/procon/blob/498c9856ea73bf871c15575e2d21bae7263d1167/hena/tyama_hena_validator.rb
hena_validator.rb hena28.py 28と実行。

ただし、追加問題については採点ツールを使わずそのまま投げ込んで良い。

右手法 (Python/Ruby/C++)

迷路を解くアルゴリズムに右手法というのがある。
壁が(トポロジー的に)1個しか存在しない場合、右手を離さずに歩けばかならずゴールできるというものである。
これは、進行方向から見てかならず右に曲がろうとすることに相当する。

CheckiOにLantern Festivalという問題がある。
灯篭流しをするときに、今光っているセルの数を答える問題。
これも右手法で解けるので、今回はMazeクラスを流用した。
そのため、今回の主言語はPython。
Ruby版はこれの移植。

C++版は、CodeIQ今週のアルゴリズムの迷路で待ち合わせ？から流用。

hena28.py

# !/usr/bin/env python
# http://qiita.com/Nabetani/items/23ebddb44f0234e7fb15
# http://nabetani.sakura.ne.jp/hena/ord28spirwa/

D=( #Right,Up,Left,Down
	(0,1),
	(-1,0),
	(0,-1),
	(1,0),
)
dir=['E','N','W','S']

class Maze:
	def __init__(self,x,y,d,v):
		self.x=x
		self.y=y
		self.d=d
		self.v=v
		self.v[self.y][self.x]='*'
		self.route=[]
		self.route.append((self.x,self.y))
	def move(self):
		d_orig=(self.d+3)%4
		for i in range(4):
			self.d=(d_orig+i)%4
			if self.v[self.y+D[self.d][0]][self.x+D[self.d][1]]=='.': break
		self.y=self.y+D[self.d][0]
		self.x=self.x+D[self.d][1]
		self.v[self.y][self.x]='*'
		self.route.append((self.x,self.y))

if __name__=='__main__':
	import sys
	if sys.version_info[0]>=3: raw_input=input
	Z=100
	try:
		while True:
			line=raw_input().rstrip().split(':')
			n,e,s,w=[int(e) for e in line[0].split(',')]
			days=int(line[1])
			m=[['.']*(Z*2) for i in range(Z*2)]
			m[Z][Z]='*'
			for i in range(n): m[Z-i-1][Z]='*'
			for i in range(e): m[Z][Z+i+1]='*'
			for i in range(s): m[Z+i+1][Z]='*'
			for i in range(w): m[Z][Z-i-1]='*'
			maze=Maze(Z+1,Z-1,0,m)
			for i in range(days+1):maze.move()
			print(dir[maze.d])
			sys.stdout.flush()
	except EOFError:
		pass

hena28.rb

# !/usr/bin/env ruby
# http://qiita.com/Nabetani/items/23ebddb44f0234e7fb15
# http://nabetani.sakura.ne.jp/hena/ord28spirwa/

D=[ #Right,Up,Left,Down
	[0,1],
	[-1,0],
	[0,-1],
	[1,0],
]
dir=['E','N','W','S']

class Maze
	attr_reader :d
	def initialize(x,y,d,v)
		@x=x
		@y=y
		@d=d
		@v=v
		@v[@y][@x]='*'
		@route=[]
		@route<<[@x,@y]
	end
	def move
		d_orig=(@d+3)%4
		4.times{|i|
			@d=(d_orig+i)%4
			break if @v[@y+D[@d][0]][@x+D[@d][1]]=='.'
		}
		@y=@y+D[@d][0]
		@x=@x+D[@d][1]
		@v[@y][@x]='*'
		@route<<[@x,@y]
	end
end

if __FILE__==$0
	Z=100
	while gets
		line=$_.chomp.split(':')
		n,e,s,w=line[0].split(',').map(&:to_i)
		days=line[1].to_i
		m=(Z*2).times.map{['.']*(Z*2)}
		m[Z][Z]='*'
		n.times{|i|m[Z-i-1][Z]='*'}
		e.times{|i|m[Z][Z+i+1]='*'}
		s.times{|i|m[Z+i+1][Z]='*'}
		w.times{|i|m[Z][Z-i-1]='*'}
		maze=Maze.new(Z+1,Z-1,0,m)
		(days+1).times{maze.move}
		puts dir[maze.d]
		STDOUT.flush
	end
end

hena28.cpp

// http://qiita.com/Nabetani/items/23ebddb44f0234e7fb15
// http://nabetani.sakura.ne.jp/hena/ord28spirwa/

# include <cstdio>
# include <string>
# include <vector>
using namespace std;
const int D[4][2]={ //Right,Up,Left,Down
	{0,1},
	{-1,0},
	{0,-1},
	{1,0},
};

class Maze{
	vector<string> &v;
	int x,y,d;
public:
	Maze(int _x,int _y,int _d,vector<string>&_v)
		: x(_x),y(_y),d(_d),v(_v){
			v[y][x]='*';
	}
	void move(){
		int d_orig=(d+3)%4,i=0;
		for(;i<4;i++){
			d=(d_orig+i)%4;
			if(v[y+D[d][0]][x+D[d][1]]=='.')break;
		}
		y=y+D[d][0];
		x=x+D[d][1];
		v[y][x]='*';
	}
	int dir(){return d;}
};

int main(){
	const string dir="ENWS";
	const int Z=100;
	int n,e,s,w;
	long long days;
	for(;scanf("%d,%d,%d,%d:%lld",&n,&e,&s,&w,&days);){
		vector<string> m(Z*2);
		for(int i=0;i<Z*2;i++)m[i]=string(Z*2,'.');
		m[Z][Z]='*';
		for(int i=0;i<n;i++)m[Z-i-1][Z]='*';
		for(int i=0;i<e;i++)m[Z][Z+i+1]='*';
		for(int i=0;i<s;i++)m[Z+i+1][Z]='*';
		for(int i=0;i<w;i++)m[Z][Z-i-1]='*';
		Maze maze(Z+1,Z-1,0,m);
		for(int i=0;i<=days;i++)maze.move();
		printf("%c\n",dir[maze.dir()]);
		fflush(stdout);
	}
}

シミュレーションの別解 (Ruby)

通常、迷路を解く時は、今向いている方向を覚えておく。
しかし、今回は図形に くぼみが出現しない ので、向いている方向を記録しなくても問題を解くことは可能である。
ビットを立てて壁の方向を保持する戦略。
この「方向」には規則性がある。case-whenを使うとわかりやすい。

hena28_another.rb

# !/usr/bin/env ruby
# http://qiita.com/Nabetani/items/23ebddb44f0234e7fb15
# http://nabetani.sakura.ne.jp/hena/ord28spirwa/

D=[ #Right,Up,Left,Down
	[0,1],
	[-1,0],
	[0,-1],
	[1,0],
]
dir=['E','N','W','S']

class Maze
	def initialize(x,y,v)
		@x=x
		@y=y
		@v=v
		@v[@y][@x]='*'
	end
	def move
		walls=D.each_with_index.map{|e,i|@v[@y+e[0]][@x+e[1]]=='*' ? 1<<i : 0}.reduce(:+)
		d=case walls
			when 8,8+4,8+6
				0
			when 1,1+8,1+12
				1
			when 2,2+1,2+9
				2
			when 4,4+2,4+3
				3
			else
				raise
		end
		@y=@y+D[d][0]
		@x=@x+D[d][1]
		@v[@y][@x]='*'
		d
	end
end

if __FILE__==$0
	Z=100
	while gets
		line=$_.chomp.split(':')
		n,e,s,w=line[0].split(',').map(&:to_i)
		days=line[1].to_i
		m=(Z*2).times.map{['.']*(Z*2)}
		m[Z][Z]='*'
		n.times{|i|m[Z-i-1][Z]='*'}
		e.times{|i|m[Z][Z+i+1]='*'}
		s.times{|i|m[Z+i+1][Z]='*'}
		w.times{|i|m[Z][Z-i-1]='*'}
		maze=Maze.new(Z+1,Z-1,m)
		days.times{maze.move}
		puts dir[maze.move]
		STDOUT.flush
	end
end