Ruby
Python
C++
どう書く
yhpg

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

More than 1 year has passed since last update.

問題
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