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