[RUBY] You walk in a spiral in a world where the walls of the cross rise (simulation)

problem http://nabetani.sakura.ne.jp/hena/ord28spirwa/
simulation(Python/Ruby/C++) http://qiita.com/cielavenir/items/8c77a158136bd668a27b
Regularity(Python/Ruby/C/C#/Java) http://qiita.com/cielavenir/items/a285b0cea4a26ff886b8
Regularity(D/Go/Swift/PHP/ Vala ) http://qiita.com/cielavenir/items/edb1daff9ea861a418ec
Regularity(VB/F#/Perl) http://qiita.com/cielavenir/items/0c84af4049ab161f82c1
Regularity(PowerShell) http://qiita.com/cielavenir/items/d9ef9f12068e99e888f2
Regularity( AIR-lang ) http://qiita.com/cielavenir/items/d804f61412fb4f07ba06
Regularity(Crystal/Perl6) http://qiita.com/cielavenir/items/13896a662b05da8b77a2
I want to process the first element in a Ruby multidimensional array and return it
(tap/About break etc.)
http://qiita.com/cielavenir/items/3f209351b924e2615f5e

About input / output

All of the following answers use standard input / output, so I need a scoring tool. https://github.com/cielavenir/procon/blob/498c9856ea73bf871c15575e2d21bae7263d1167/hena/tyama_hena_validator.rb Execute with hena_validator.rb hena28.py 28.

However, you can throw in additional questions as they are without using the scoring tool.

Right method (Python / Ruby / C ++)

There is a right method as an algorithm to solve the maze. If there is only one wall (topologically), you have to walk without releasing your right hand to reach the goal. This corresponds to always trying to turn right when viewed from the direction of travel.

CheckiO has a problem with Lantern Festival. The question of answering the number of cells that are currently shining when lanterning. This can also be solved by the right method, so this time I used the Maze class. Therefore, the main language this time is Python. The Ruby version is a port of this.

The C ++ version of CodeIQ this week's algorithm Meet in the maze? .

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);
	}
}

Another solution for simulation (Ruby)

Usually, when solving a maze, remember the direction you are facing. However, this time, ** no dents appear in the figure **, so it is possible to solve the problem without recording the direction in which it is facing. A strategy to stand a bit and hold the direction of the wall. There is regularity in this "direction". It is easy to understand if you use 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

Recommended Posts

You walk in a spiral in a world where the walls of the cross rise (simulation)
You walk in a spiral in a world of rising cross walls (regularity, Python / Ruby / C / C # / Java)
Find the rank of a matrix in the XOR world (rank of a matrix on F2)
If you want a singleton in python, think of the module as a singleton
When you make a mistake in the directory where you execute `pipenv install`
Arrange the numbers in a spiral shape
Test the number of times you have thrown a query (sql) in django
Get the caller of a function in Python
Make a copy of the list in Python
Find the number of days in a month
Output in the form of a python array
If you define a method in a Ruby class and define a method in it, it becomes a method of the original class.
The story of building the fastest Linux environment in the world
A reminder about the implementation of recommendations in Python
Make a note of what you want to do in the future with Raspberry Pi
A note on the default behavior of collate_fn in PyTorch
Find out the apparent width of a string in python
Introducing sites where you can see trends in the 2019 framework
Get the number of specific elements in a python list
[Note] Import of a file in the parent directory in Python
Find the eigenvalues of a real symmetric matrix in Python
How to get a quadratic array of squares in a spiral!