[RUBY] Vous marchez en spirale dans un monde où les murs de la croix s'élèvent (simulation)

problème http://nabetani.sakura.ne.jp/hena/ord28spirwa/
simulation(Python/Ruby/C++) http://qiita.com/cielavenir/items/8c77a158136bd668a27b
Régularité(Python/Ruby/C/C#/Java) http://qiita.com/cielavenir/items/a285b0cea4a26ff886b8
Régularité(D/Go/Swift/PHP/ Vala ) http://qiita.com/cielavenir/items/edb1daff9ea861a418ec
Régularité(VB/F#/Perl) http://qiita.com/cielavenir/items/0c84af4049ab161f82c1
Régularité(PowerShell) http://qiita.com/cielavenir/items/d9ef9f12068e99e888f2
Régularité( AIR-lang ) http://qiita.com/cielavenir/items/d804f61412fb4f07ba06
Régularité(Crystal/Perl6) http://qiita.com/cielavenir/items/13896a662b05da8b77a2
Je souhaite traiter le premier élément d'un tableau multidimensionnel Ruby et le renvoyer
(tap/À propos de la pause, etc.)
http://qiita.com/cielavenir/items/3f209351b924e2615f5e

À propos de l'entrée et de la sortie

Toutes les réponses suivantes utilisent des entrées / sorties standard, j'ai donc besoin d'un outil de notation. https://github.com/cielavenir/procon/blob/498c9856ea73bf871c15575e2d21bae7263d1167/hena/tyama_hena_validator.rb Exécutez avec hena_validator.rb hena28.py 28.

Cependant, vous pouvez poser des questions supplémentaires telles quelles sans utiliser l'outil de notation.

Méthode Right (Python / Ruby / C ++)

Il existe une bonne méthode en tant qu'algorithme pour résoudre le labyrinthe. S'il n'y a qu'un seul mur (topologiquement), vous devez marcher sans relâcher votre main droite pour atteindre l'objectif. Cela correspond à toujours essayer de tourner à droite vu du sens de la marche.

CheckiO a un problème avec Festival des lanternes. La question de répondre au nombre de cellules qui brillent actuellement au rinçage de la lanterne Cela peut également être résolu par la bonne méthode, donc cette fois j'ai utilisé la classe Maze. Par conséquent, le langage principal cette fois est Python. La version Ruby en est un portage.

La version C ++ de l'algorithme de CodeIQ de cette semaine 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);
	}
}

Une autre solution pour la simulation (Ruby)

Habituellement, lorsque vous résolvez un labyrinthe, souvenez-vous de la direction à laquelle vous faites face. Cependant, cette fois, il n'y a pas de ** bosses sur la figure **, il est donc possible de résoudre le problème sans enregistrer la direction dans laquelle il fait face. Une stratégie pour se tenir un peu et tenir la direction du mur. Il y a une régularité dans cette «direction». Il est facile de comprendre si vous utilisez le cas-quand.

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

Vous marchez en spirale dans un monde où les murs de la croix s'élèvent (simulation)
Vous marchez en spirale dans un monde où les murs de la croix s'élèvent (régularité, Python / Ruby / C / C # / Java)
Trouvez le rang de la matrice dans le monde XOR (rang de la matrice sur F2)
Si vous voulez un singleton en python, considérez le module comme un singleton
Disposez les nombres en forme de spirale
Vérifiez le nombre de fois où la requête (sql) a été lancée dans django avec un test
Récupérer l'appelant d'une fonction en Python
Copiez la liste en Python
Trouvez le nombre de jours dans un mois
Sortie sous la forme d'un tableau python
Si vous définissez une méthode dans une classe Ruby, puis définissez une méthode dans celle-ci, elle devient une méthode de la classe d'origine.
L'histoire de la création de l'environnement Linux le plus rapide au monde
Un mémorandum sur la mise en œuvre des recommandations en Python
Notez ce que vous voulez faire à l'avenir avec Razpai
Remarque sur le comportement par défaut de collate_fn dans PyTorch
Découvrez la largeur apparente d'une chaîne en python
Présentation de sites où vous pouvez voir les tendances dans le cadre de 2019
Obtenez le nombre d'éléments spécifiques dans la liste python
[Note] Importation de fichiers dans le répertoire parent en Python
Trouver les valeurs propres d'une vraie matrice symétrique en Python