LoginSignup
3

More than 5 years have passed since last update.

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

Last updated at Posted at 2015-02-08
問題 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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
3